Are rational numbers countable?

The original article was penned for a the magazine, Teacher, published by the Karnataka chapter of Bharat Gyan Vigyan Samiti. The intended audiences are a combination of high school math teachers and students of the age group 13-15, hence the lack of formal language and rigour. Suggestions and comments are welcome

What is a rational number? A number which can be expressed in the form \frac{p}{q} (p and q being integers) is called a rational number. These numbers follow some interesting properties.

Firstly, between any two rational numbers, there is another rational number.

Try this as an exercise - choose two rational numbers which you feel are close by and try to list a few numbers in between them. You will see that you can grow your list forever. Say you pick \frac{2}{5} and \frac{3}{5} . Lets try to follow a pattern when listing numbers in between them. We know for certain that the average of two numbers in between them. So first, I pick their average \frac{1}{2}. Now I take the average of \frac{2}{5} and \frac{1}{2} - \frac{9}{20}. Now I take the average of \frac{2}{5} and \frac{9}{20} - \frac{13}{20}. And so on. Following this technique, I will be able to keep on listing number, all which are between \frac{2}{5} and \frac{3}{5}. We have just demonstrated that there are infinitely many numbers in between any two rational numbers.

Mathematicians call the set of all rational numbers as a densely ordered set because of this beautiful property.

Now let us introduce real numbers. A set which contains all the rational and all the irrational numbers - all the numbers you can point out on a number line - is called the set of real numbers.

What are irrational numbers? They are those which cannot be represented in the form \frac{p}{q} (p and q being integers). For example, consider

\sqrt{2} = 1.41421356237...
\sqrt{3} = 1.73205080757...
or even
\pi = 3.14159265359...
(note that \frac{22}{7} is just an approximation and is not the exact value of \pi)

All irrational numbers have a non-terminating sequence of digits in their decimal places, because if they were terminating, we could represent them in \frac{p}{q} form (How?).

Real numbers, like rationals, are also densely ordered. That is, between any two real numbers, there exists another real number. Therefore there are infinitely many real numbers between any two real numbers. (Try to follow the same procedure we did for rationals)

Let us now revisit the concept of natural numbers. Natural numbers are those numbers you use to count. Some people argue that 0 is a natural number while some do not agree on it. Let us assume, for the sake of discussion, that 0 is not a natural number for us. You know that there are infinitely many natural numbers (1, 2…). How do we know that? For any number you pick, I can show you another number which is greater than it - just by adding one.
Now let us ask ourselves this question. Is it possible to count rational numbers (using natural numbers)? From what we just learnt, there are infinite rational numbers between any two rational numbers. If you pick the numbers 2 and 3, there are infinite rational numbers in between them. If you pick 4 and 5, we have a completely different infinite set of numbers between them. Now I’m going to claim that rational numbers are countable - that is, you can count every single rational number in the universe, just like you were counting apples or oranges.

This means I shall have counted the all the infinite numbers between 2 and 3, the infinite numbers between 4 and 5 and every other rational number you can think of - all using natural numbers. How is this possible?

Let us see how.

Diagonal argument.svg
Image Credits: Cronholm144/Wikimedia Commons.

We make a large (infinite) table with the rows numbered 1, 2, 3… and the columns also numbered 1, 2, 3.... Now I shall ask you to pick any rational number and I shall show you that it is present in the table. If you pick \frac{1}{3} - I claim that it is present on the 1st row and 3rd column. If you pick \frac{6}{7} - I claim that it is present on the 6th row and 7th column. In general, if you pick \frac{p}{q}, it will be present on the pth row and qth column. Therefore, by construction, we have proved that all the rational numbers you could possibly think of (and not think of) are in this table.

Now, all that remains is to devise a strategy to count them. Look at the figure above and imagine you were walking along the arrows. Whenever you reached a rational number, you increase your count. If you keep counting like this, it is evident that every single rational number in the universe will appear in you walk. This is easy to see because our table covers every rational number and our walk covers every diagonal one by one.

In short, you have counted (or you are forever counting) every rational number using a natural number. Since you can do this, the number of natural numbers is equal to the number of rational numbers! Yes, the profoundness of this statement can only be appreciated once you recall what we proved just now and think about it.

Interestingly, real numbers - which follow the same dense ordering property of rational numbers cannot be counted. Try to devise a method to count the real numbers as an exercise. If you plan to follow the same strategy we followed for rationals, can you point out where non-terminating real numbers come?

Note that not coming up with a method to count the real numbers doesn't mean that there is no method to count them. It just means that you couldn't find one, if it existed. To say for certain that real numbers cannot be counted, you need a proof. There is an interesting proof called Cantor’s Diagonalization Argument which will convince you that the real numbers cannot be counted. We shall see this in the next article.

Published by

Pranav

I'm a student pursuing a masters degree in Theoretical Computer Science. Prior to this, I completed my bachelors in Computer Science and Engineering and worked for an year, until I realized that the slogging off at an office in front of the computer is not the job for me. I am easily fascinated and distracted by everything under the sun, which has kept me busy trying to figure out what I am going to. I love dreaming about making radical life decisions, bringing happiness on faces and about a world full of meadows and fluttery creatures and people who do not judge you for what you love doing.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>