Exercise 1.2

Is Q countable?

Solution:

Each rational number r in Q is a numerator in Z divided by a denominator in N. It is characterized then by the pair (a, b) such that r = a / b. If we look at all pairs (a, b) for a in Z and b in N, we will actually get every r over and over again, as a / b, (2a) / (2b), (3a) / (3b),...

Therefore if we can list all the pairs (a, b) for a in Z and b in N we can get a list of the elements of Q by throwing away duplicates on this list.

Imagine then that we have a vertical column for each b in N and that column consists of a list of the elements of Z (as in Exercise 1.1). We can list the resulting pairs by going up every diagonal as in the illustration below. This will give a list of every pair (a, b) for a in Z and b in N.

You run through the elements of N much faster than you do the elements of Q but again nobody cares about this fact.

To be explicit, we order the elements n of our array in increasing order of a+b and for fixed a+b in increasing order of i.

Thus the first few ratios in this order are

1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, ...

The first of these has a + b = 2 then there are two with a + b = 3, three with a + b = 4, and so on.

The ratio will then appear as the ratio in the position on the list.

You can enter any ratio below and see where it occurs on the list and vice versa.