By the end of this post you will understand how to list all (yes, all!) integers and rational numbers and why you can’t list the reals. You will also learn why this weird sequence of numbers is useful:
\(1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 5, \ldots\)
The integers
There’s an easy way to list all the natural numbers without leaving any gaps. Start with 0, then add 1 to the previous number:
\(0, 1, 2, 3, 4, 5, \ldots\)
You will never reach the end, but wherever you stop, you can be confident that you have all the naturals up to that point.
For integers, list the naturals, then for each natural, \(n\), add \(-n\) as follows:
\(0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, \ldots\)
This, by the way, is sequence A001057 in the On-line Encyclopedia of Integer Sequences.
The reals
We can’t list the real numbers, as Cantor showed in 1891.
To see why, let’s explore the reals from 0 to strictly less than 1, or \([0,1)\) for short.
Suppose, for the sake of argument, that we could list them all. This means there will be a first number, a second, a third, and so on. So let’s number them and write some arbitrarily chosen examples to get a sense of how the list might look. I’ve put the ith digit in bold for reasons that will soon be apparent.
| i |
Decimal expansion |
| 1 |
0.00013… |
| 2 |
0.01202… |
| 3 |
0.00310… |
| 4 |
0.12772… |
| … |
|
Here’s Cantor’s trick. Work down the infinite list of numbers to create a new number in the following way.
- From the the 1st number take the 1st digit after the decimal point and subtract it from 9: \(9 – 0 = 9\).
- From the the 2nd number take the 2nd digit after the decimal point and subtract it from 9: \(9 – 1 = 8\).
- From the the 3rd number take the 3rd digit after the decimal point and subtract it from 9: \(9 – 3 = 6\).
- From the the 4th number take the 4th digit after the decimal point and subtract it from 9: \(9 – 7 = 2\).
- More generally, from the ith number take the ith digit after the decimal point and subtract it from 9.
Now use these subtractions to generate a new number. So for the example above, we just subtract 9 from the numbers in bold to make:
0.9862…
Our assumption was that we had listed all the real numbers in \([0,1)\). But here we have created a new number that differs from each one in that list by at least one digit. Our assumption that we could list all the numbers in \([0,1)\) has led to the conclusion that we can’t: a contradiction. If we can’t do it for \([0,1)\) then surely we can’t list all the reals.
Although there are infinitely many integers, we can list them. The number of real numbers is too big an infinity to list!
The rationals: Cantor’s zigzag
We can, however, list the rational numbers in a way that’s guaranteed not to leave any out. Here are two ways to do it. I’ll focus on the non-negative rationals from which it is easy to get the negatives.
The first is due to Cantor, let’s call it the zigzag, and is easiest to show in a picture than to explain. The diagram below puts denominators on the columns and numerators on the rows. Start with \(1/1\) and follow the arrows:
Beautiful, isn’t it? This zigzag solves the problem that if we go down the first column, say,
\(1/1, 1/2, 1/3, 1/4, \ldots\),
we head off to infinity without ever moving to the second column, so, for example, we would miss out \(2/5\) and \(3/4\).
I think about this in terms of compass directions. Begin by adding \(1/1\) to your list of rationals and heading east. Let’s call the numerator \(p\) and denominator \(q\), so we are enumerating \(p/q\). Here’s what happens at each step:
- If we are heading east then set \(p \leftarrow p + 1\) and add \(p/q\) to our list of rationals. Head southwest on the next step.
- If we are heading southwest, then set
\(p \leftarrow p – 1\)
\(q \leftarrow q + 1\)
Add \(p/q\) to our list of rationals.
If \(p = 1\), i.e., we have hit the leftmost column, then head south on the next step.
- If we are heading south then set \(q \leftarrow q + 1\) and add \(p/q\) to our list of rationals. Head northeast on the next step.
- If we are heading northeast, then set
\(p \leftarrow p + 1\)
\(q \leftarrow q – 1\)
Add \(p/q\) to our list of rationals.
If \(q = 1\), i.e., we have hit the top row, then head east on the next step.
All I have done above is spell out the zigzag pattern. You will see that if we are heading east or south, then we just take one step then change direction. Whereas if we are heading southwest or northeast then we keep going until we hit the edge.
The sequences of numerators and denominators are A092543 and A092542, respectively. It’s interesting looking at the numbers and trying to forget that you know how they were generated. Like, what on earth is going on with
\(1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 5, \ldots\)
It makes sense when you look at the numerators in the zigzag diagram. (I bet this sequence is used in an IQ test or job selection exam somewhere, so basically it just asks if you’re aware how to enumerate the rationals.)
The zigzag is great because it’s easy to see that it works. However, it has two problems: (1) we get the same numbers multiple times, e.g., \(1/2\) and \(2/4\) are there and (2) related to this, the fractions aren’t always in their simplest forms, i.e., the numerators and denominators will often have common factors over 1 (again \(2/4\) is an example – top and bottom can be divided by 2).
The rationals: Stern-Brocot’s sandwich
Enter the Stern-Brocot tree. Stern, a mathematician, discovered the approach in 1858 and Brocot, a clockmaker, discovered it independently in 1861 in the process of devising systems of gears. Hayes (2000) delves into the history.
I’m doing to ignore the tree aspect of Stern-Brocot’s approach because I don’t think it helps understand how it works. Instead, let’s consider a multilayer Stern-Brocot sandwich (not on Google when I searched, incidentally) as follows.
Begin with the two fractions \(0/1\) and \(1/0\). The first is zero, the second is weird – we usually aren’t allowed to divide by zero. But you could think of it as an infinitely large number. (Hayes quotes an anonymous source who says that it is “infinity reduced to lowest terms”.)
Now we fill the sandwich by taking the mediant of these two fractions. This is defined:
\(\displaystyle \mathit{mediant}\left( \frac{p_L}{q_L}, \frac{p_R}{q_R} \right) = \frac{p_L + p_R}{q_L + q_R}\).
In other words, simply sum the numerators and sum the denominators of the left and right fractions to get, respectively, the numerator and denominator of the mediant.
Okay, here we go. Start with our sandwich bread(?):
\(\displaystyle \frac{0}{1} \qquad \frac{1}{0}\)
Fill it with the mediant:
\(\displaystyle \frac{0}{1} \qquad \mathbf{\frac{1}{1}} \qquad \frac{1}{0}\)
Now we have created the number 1. Let’s go again, filling the gaps between numbers we have using the mediant:
\(\displaystyle \frac{0}{1} \qquad \mathbf{\frac{1}{2}} \qquad \frac{1}{1} \qquad \mathbf{\frac{2}{1}} \qquad \frac{1}{0}\)
One more go:
\(\displaystyle \frac{0}{1} \mathbf{\quad \frac{1}{3}} \quad \frac{1}{2} \mathbf{\quad \frac{2}{3}} \quad \frac{1}{1} \mathbf{\quad \frac{3}{2}} \quad \frac{2}{1} \mathbf{\quad \frac{3}{1}} \quad \frac{1}{0}\)
Lovely! You get \(2^s + 1\) rationals on each step, \(s\), e.g., the last step above is step three and has \(2^3 + 1 = 9\) numbers. Follow the steps 10 times and you get 1,205 rationals.
It can be proved this works: all non-negative rationals are enumerated in the correct order and in simplest forms. I shall delegate the proofs to a Google search…
By the way, one reason we can list the rationals at all is because there’s the same number of them as natural numbers.
