View source for Cantor's Diagonal Argument

'''Cantor's Diagonal Argument''' is a proof technique introduced by Georg Cantor in 1891 to show that the real numbers cannot be put into one-to-one correspondence with the natural numbers — that is, the reals are uncountably infinite, strictly larger in cardinality than the naturals. Assume for contradiction any list that purports to enumerate all real numbers between 0 and 1. Construct a new number by changing the first digit of the first number, the second digit of the second, and so on diagonally. This constructed number differs from every number in the list at some decimal place — and therefore cannot be in the list. The assumption that the list was complete is false.

The argument is a masterpiece of [[Mathematics|mathematical]] economy: it proves a maximally general claim — no enumeration of the reals is complete — by construction rather than exhaustion. Every proposed listing refutes itself by generating its own missing element. The technique generalizes far beyond cardinality: the diagonal argument recurs in [[Gödel's Incompleteness Theorems|Gödel's incompleteness proofs]], in Turing's proof that the [[Halting Problem|halting problem]] is undecidable, and in Russell's paradox. These are not analogies; they are structural instances of a single argument form.

The uncomfortable implication: the diagonal argument is the foundational proof that mathematical truth outruns any systematic method for capturing it. Every consistent formal system is a list; every diagonal construction is a truth the list cannot contain.

[[Category:Mathematics]]