Listing Things
In From Euclid to Cantor, Colin Beveridge summarises and compares two well-known proofs: Euclid’s proof of the infinitude of primes, and Cantor’s proof that the cardinality of the reals is larger than that of the naturals. He notes how they both rely on attempting to construct an exhaustive list of some type of object (prime numbers and real numbers, respectively), then using that list to construct a new object which doesn’t appear in the list, hence proving that it cannot be exhaustive.
Since I’m of the opinion that the reals get far more attention than they deserve, I spotted that Colin jumps straight from the rationals to the reals, pointing out that the latter includes irrational numbers like $\sqrt{3}$, π and e. This seems to be a common habit among mathematicians, so I thought I’d take a look at a set of numbers “in between” (in a sub/superset sense) the rationals and the reals.
One candidate we might look at is the algebraic numbers, since they include roots of polynomials like $\sqrt{3}$; however, π and e are not algebraic (non-algebraic numbers are called transcendental).
Instead we’ll look at the set of computable numbers, which I think are underrated. All of these examples, along with (most) ‘interesting’ numbers, are computable.
It turns out we can list computable numbers very easily, by reading the output of every computer program. There are many equivalent ways we can do this, here’s a simple one.
- Choose some universal Turing machine. To make things easy we’ll pick one without a halt state, and we’ll make it monotone: this means we give it an extra tape, which only moves in one direction. This will be our “output”.
- For the nth number in the list (starting from the 0th), write n on to the machine’s work tape. Use the number of symbols as the base, e.g. if the machine uses binary, write the number in binary. Start with the least-significant digit and end with the most-significant (what would happen if we wrote it with the most-significant digit first?)
- Run the machine; it will keep going forever, since there’s no “halt” state.
- Read the contents of the output tape as a number. One simple way is to read two sequences of digits: the first comes from every other cell on the tape (1st, 3rd, 5th, etc.); the second come from the cells in between (2nd, 4th, 6th, etc.). We turn these into a number by writing a radix point and having the first sequence go off to the left, and the second go off to the right.
For example, if the output begins [0,1,2,3,4,5,6,7,…], we would get a number like …6420.1357…
Some programs will never output any bits; some will output a finite number of bits then switch to not outputting anything; others will keep outputting bits forever. Since there are algorithms which spit out the bits/digits of numbers like π and e forever, we will eventually run a program implementing such an algorithm, and hence those numbers will appear in our list, despite having a never-ending decimal.
Since we can list all computable numbers, they have the same cardinality as the natural numbers. This shows that almost all real numbers are uncomputable, and since the universe is computable, almost all real numbers aren’t actually “real” (and hence my opinions of them ;) )