Cantor's diagonal argument

Cantor's diagonal argument is a strikingly simple proof that the real numbers cannot be listed, and hence are uncountable. It is a proof by contradiction: suppose you DID have a complete list of all reals in (0, 1), one per row, written as infinite decimals. The argument manufactures a real number that, by construction, differs from every entry on the list — so the list was not complete after all.

The construction is the “diagonal” move. Build a new number d by reading down the diagonal — its n-th decimal digit is chosen to differ from the n-th digit of the n-th number on the list (for instance, change each diagonal digit to 5, or to 6 if it was already 5). Then d cannot equal the first listed number (they differ in position 1), nor the second (they differ in position 2), and so on: d differs from the n-th number in the n-th place. So d is a real in (0, 1) absent from the list, the contradiction sought.

One technical care is required: decimal expansions are not quite unique (0.4999… equals 0.5000…), so one must pick replacement digits avoiding 0 and 9 to dodge this ambiguity. With that fixed, the conclusion stands: no enumeration of the reals exists. The same diagonal idea, applied to characteristic functions, proves Cantor's general theorem that no set surjects onto its power set, and it reappears in logic as the heart of Gödel's incompleteness and the unsolvability of the halting problem.