Cantor Proved Some Infinities Are Bigger Than Others With a Single Diagonal

Georg Cantor was a 28-year-old at Halle when he published, in 1874, the first proof that the real numbers cannot be put into a one-to-one correspondence with the natural numbers. The argument was technical, working through nested intervals. In 1891 he published a much shorter version. It is the one almost everyone learns now, and it is short enough to walk through in a paragraph.

Suppose, for contradiction, that the real numbers between 0 and 1 can be listed: r_1, r_2, r_3, and so on. Each r_i has a decimal expansion 0.d_{i1}d_{i2}d_{i3}.... Now construct a new number, x, whose first digit differs from d_{11}, whose second digit differs from d_{22}, whose third digit differs from d_{33}, and so on down the diagonal of the table. By construction, x cannot equal r_1 — they differ in the first decimal place. It cannot equal r_2 — they differ in the second. It cannot equal any r_i. But x is itself a real number between 0 and 1, so the supposed list omitted at least one real. The list, therefore, cannot exist. The reals are uncountable.

This was the moment set theory acquired a hierarchy. The natural numbers, the rationals, the algebraic numbers — all are 'countably infinite,' the smallest size of infinity, which Cantor labeled aleph-zero. The reals are strictly larger. Cantor's continuum hypothesis asked whether there is anything in between. Kurt Gödel showed in 1940 that the hypothesis cannot be disproved from the standard axioms; Paul Cohen showed in 1963 that it cannot be proved either.

Cantor's contemporaries were not all impressed. Leopold Kronecker, his former teacher, called the work the work of a 'corruptor of youth' and blocked Cantor from senior positions. Cantor spent later years in and out of mental hospitals. He died in 1918. The diagonal survives him.