Exercise 1.2

]> Exercise 1.2

Home \| 18.013A \| Chapter 1 \| Section 1.2		Tools Glossary Index Up Previous Next

Exercise 1.2

Is $ℚ$ countable?

Solution:

Each rational number $r$ in $ℚ$ is a numerator in $ℤ$ divided by a denominator in $ℕ$ . It is characterized then by the pair $(a, b)$ such that $r = \frac{a}{b}$ . If we look at all pairs $(a, b)$ for $a$ in $ℤ$ and $b$ in $ℕ$ , we will actually get every $r$ over and over again, as $\frac{a}{b}, \frac{2 a}{2 b}, \frac{3 a}{3 b}, \dots$

Therefore if we can list all the pairs $(a, b)$ for $a$ in $ℤ$ and $b$ in $ℕ$ we can get a list of the elements of $ℚ$ by throwing away duplicates on this list.

Imagine then that we have a vertical column for each $b$ in $ℕ$ and that column consists of a list of the elements of $ℤ$ (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 $ℤ$ and $b$ in $ℕ$ .

You run through the elements of $ℕ$ much faster than you do the elements of $ℚ$ 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

\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots

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 $\frac{a}{b}$ will then appear as the ratio in the position $\frac{(a + b - 1) (a + b - 2)}{2} + a$ on the list.

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