CONCEPT
Cantor's Diagonal Argument
Georg Cantor's 1891 proof that no list can contain all real numbers—a method so general that it became the master technique behind Gödel's incompleteness theorems, Turing's undecidability proof, and the permanent limits of all computation: the shape of the move is always the same, and it defeats every claim that some system can enumerate everything.
The diagonal argument fits on a postcard, and from it descend the deepest negative results in the history of mathematics and computer science.
Georg Cantor published it in 1891 to show that the real numbers cannot be listed. Suppose you could: arrange them as a first, second, third. Build a new number by taking the first decimal digit of the first listed number and changing it, the second digit of the second and changing it, and so on down the diagonal. The constructed number differs from the nth listed number in the nth place—it differs from every number on the list in at least one digit. Yet it is a perfectly good real number between zero and one. The list was incomplete. Since the list was arbitrary, no list can be complete. The reals are uncountable. The proof is a