Listing Things

Posted on by Chris Warburton

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 3\sqrt{3}, π\pi and ee. 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 3\sqrt{3}; however, π\pi and ee 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. Here's one specific way we can do this:

For example, if the output begins [0,0,1,1,1,1,0,1,…], we would get a number like …0110.0111…

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 π\pi and ee 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 ;) )