More Than Infinite

Georg Cantor proved in 1874 that the real numbers cannot be listed, and gave the argument everybody now uses in 1891. It takes about a paragraph, and it is one of the few genuinely great proofs that can be explained to somebody who has not studied mathematics.

Suppose somebody hands you a list claiming to contain every number between 0 and 1. It goes on for ever, one number per line, each written as an infinite decimal.

Build a new number as follows. Look at the first decimal place of the first entry: whatever digit is there, choose a different one for your first decimal place. Look at the second decimal place of the second entry: choose a different digit for your second place. Third place of the third entry, and so on, down the diagonal of the list for ever.

The number you have built differs from the first entry in its first decimal place, so it is not the first entry. It differs from the second entry in the second place, so it is not the second. It differs from the millionth entry in the millionth place. For every position on the list, it differs from whatever sits there.

So it is not on the list. And the list was any list at all.

There is no way to repair this. Add your new number to the list and the construction runs again on the new list, producing a different missing number. The argument does not identify a particular gap; it shows that listing is the wrong tool. The reals are uncountable.

The commonest objection is that the new number must be somewhere further down, since the list is infinite. It is worth answering carefully, because the answer is the crux. Take any position you like: the ten billionth. The constructed number differs from the ten-billionth entry in its ten-billionth decimal place, so it is not that entry. The argument never asks anyone to walk the list to its end. It establishes, separately for each finite position, that the number is not there. There is nowhere left.

What follows is a hierarchy. Cantor's theorem generalises the trick: for any set whatever, the collection of all its subsets is strictly larger. So there is no largest infinity, and the sizes continue without end, each generated from the last.

This was not received gracefully. Kronecker, who had been Cantor's teacher, regarded completed infinities as nonsense and worked to block publication. Poincaré called the theory a disease. Cantor spent periods in sanatoria and died in one in 1918. Hilbert's verdict in 1926, no one shall expel us from the paradise Cantor has created, was a defence, which tells you what he was defending against.

Cantor's own reaction to a related result is the most quoted thing he ever wrote. In 1877 he proved that the points of a unit square can be paired one-to-one with the points of a unit interval: a square has no more points than a line. He wrote to Dedekind, in French, 'I see it, but I do not believe it.' The resolution is that the pairing cannot be made continuous (dimension is preserved by continuity, not by cardinality) but proving that took another thirty years and Brouwer.

The argument's afterlife is where it earns its place in a course that is not about set theory.

Turing, in 1936, wanted to know whether a mechanical procedure could decide, for any program and input, whether the program halts. Suppose one exists; call it H. Build a program D which takes a program's description, asks H what that program does when run on itself, and then does the opposite, looping if H says halt, halting if H says loop. Now run D on its own description. If it halts, H said it loops, so it loops. If it loops, H said it halts, so it halts.

Contradiction, so H does not exist. That is the diagonal argument with programs where the decimal expansions were, and the resemblance is not decorative: Turing was consciously adapting Cantor. Gödel's incompleteness proof has the same skeleton. So does Russell's paradox about the set of all sets that do not contain themselves.

One method, three of the twentieth century's central limitative results, and it started with a list of decimals and a walk down the diagonal.