A proof that some infinities are larger than others. It is a few lines long, it requires nothing beyond counting, it was violently rejected when published, and the same technique later established the limits of computation.

Two sets are the same size if their members can be paired off exactly, with nothing left over. This works without counting: a shepherd can verify that every sheep returned by pairing them with pebbles.

Pairing two collections one to one. Two sets are the same size when such a pairing exists, which is a definition that works for infinite sets as well as finite ones.
Pairing two collections one to one. Two sets are the same size when such a pairing exists, which is a definition that works for infinite sets as well as finite ones.Credit: Farkle Griffen (CC0).

Applied to infinite sets, this produces results that look wrong and are not.

The even numbers can be paired with all the whole numbers, by matching each number to its double. Nothing is left over in either direction, so there are exactly as many even numbers as whole numbers, despite the evens being a proper part of the whole.

Galileo noticed this and concluded that size comparisons simply do not apply to infinite collections. Cantor's contribution was to accept the pairing definition and see what followed.

The rational numbers, all the fractions, can also be paired with the whole numbers, by arranging them in a grid and traversing it diagonally. That result is genuinely surprising: the fractions are dense, with infinitely many between any two, and there are no more of them than there are whole numbers.

Sets that can be paired with the whole numbers are called countable.

Georg Cantor published the diagonal argument in 1891, and it shows the real numbers are not countable.

Georg Cantor, who proved in 1891 that no list can contain all the real numbers. The reception was hostile and he spent periods in sanatoria.
Georg Cantor, who proved in 1891 that no list can contain all the real numbers. The reception was hostile and he spent periods in sanatoria.Credit: Unknown authorUnknown author (Public domain).

Suppose someone claims to have a complete list of all the real numbers between zero and one, numbered first, second, third and so on. Each is written as an infinite decimal.

Now build a new number as follows. Its first digit differs from the first digit of the first number on the list. Its second digit differs from the second digit of the second number. Its third differs from the third digit of the third. Continue forever.

The number produced differs from every number on the list, in at least one place: it differs from the nth number at the nth digit.

So the list was not complete. And this holds for any list, since the construction uses only that the list exists. No list can contain all the real numbers.

There are therefore strictly more real numbers than whole numbers, and infinity comes in different sizes.

The argument generalises. Cantor showed that the set of all subsets of any set is strictly larger than the set itself, which means there is no largest infinity: any infinity can be exceeded.

A consequence is worth stating because it is startling. Almost all real numbers are not the solution of any polynomial equation with whole-number coefficients. Those that are, the algebraic numbers, form a countable set, so the rest, the transcendentals, are uncountable and constitute almost everything. Yet proving that any particular number is transcendental is difficult, and it was done for pi only in 1882.

The same is true of computable numbers. The programs that could compute a number are countable, so almost every real number cannot be computed by any algorithm.

Cantor's work was attacked severely. Leopold Kronecker, his former teacher and an influential figure, opposed it as strongly as a mathematician can oppose anything, blocked publication where he could, and reportedly obstructed Cantor's career. He held that mathematics should concern only what can be constructed in finitely many steps, and completed infinities were not that.

Henri Poincare described set theory as a disease from which mathematics would recover.

Cantor suffered from depression and spent extended periods in sanatoria. He died in 1918 in an institution, during the war, in poor conditions.

The work is now foundational. David Hilbert said that no one would expel mathematicians from the paradise Cantor had created, and set theory became the standard foundation of the subject.

The diagonal argument is a method, and its later applications are what secure its importance.

Kurt Godel used it in 1931 to prove the incompleteness theorems. By encoding statements about arithmetic as numbers, he constructed a statement asserting its own unprovability, and diagonalisation is the construction.

Alan Turing used it in 1936 to prove the halting problem undecidable. Suppose a program could determine whether any program halts on any input; diagonalise to construct a program that halts if and only if it does not.

Both results establish limits rather than facts, and both come from the same move: assume a complete enumeration, then build something that must be missing from it. That a proof about the size of the number line turned out to bound what any computer can ever do is among the more remarkable inheritances in mathematics.

Cantor asked whether any infinity lies strictly between the whole numbers and the real numbers. His continuum hypothesis says none does, and he could not prove it.

Godel showed in 1940 that it cannot be disproved from the standard axioms, and Paul Cohen showed in 1963 that it cannot be proved from them either. It is independent: both it and its negation give consistent mathematics.

That is not an unanswered question in the ordinary sense. It is a demonstration that the axioms do not settle it, and whether one of the answers is nonetheless correct is a question about what mathematics is, rather than about sets.