Definition
Diagonalization is a proof technique in which a new mathematical object is constructed by systematically disagreeing with every element of an assumed complete enumeration — differing from the first element in the first position, the second element in the second position, and so on, tracing the diagonal of the list. The constructed object then cannot appear anywhere in the list, contradicting the assumption that the list was complete.
The technique was introduced by Georg Cantor in 1891 to prove that the set of real numbers is strictly larger than the set of natural numbers — that not all infinities are equal. Even though the natural numbers are infinite, they can be listed in a sequence; the real numbers cannot. No matter how you try to list them, the diagonal construction produces a real number that differs from every entry on your list.
Diagonalization reappears across mathematics, logic, and computer science wherever a system attempts to reason about its own completeness. Its recurring lesson is the same: any attempt to enumerate all objects of a certain kind from within a system will miss something — the diagonal object lies outside whatever the system can see.
Why it matters
How it works
Cantor's original argument
Suppose someone claims to have listed every real number between 0 and 1 as an infinite decimal: the first entry is some number r₁, the second is r₂, and so on. Construct a new number d by looking at the nth decimal digit of rₙ and choosing a different digit for the nth position of d — for instance, always writing 5 unless the nth digit is 5, in which case writing 6. The resulting number d differs from r₁ in the first decimal place, differs from r₂ in the second, and differs from every rₙ in the nth place. Therefore d is not anywhere in the list, which contradicts the claim that the list was complete.
The argument holds regardless of the specific list chosen, which means no list can be complete. The real numbers are uncountably infinite, while the natural numbers are only countably infinite.
Diagonalization and limits of formal systems
Alan Turing's proof that the halting problem is undecidable follows the same blueprint. Suppose a program H exists that decides for any program P and input x whether P halts on x. Construct a new program D that uses H on itself and then does the opposite of what H predicts — halting if H says it loops, looping if H says it halts. When D is run on itself, H's prediction is refuted either way. The contradiction shows that H cannot exist.
Kurt Gödel adapted the same diagonal structure to produce a sentence in arithmetic that effectively says "this statement is not provable in this system." If the system is consistent, that sentence is true but unprovable — a mathematical truth that escapes the system's reach. Both results are applications of the same underlying move: self-reference plus diagonal deviation.