Cantor diagonalization

Diagonalization is a clever trick for building something guaranteed to be missing from any list — by deliberately disagreeing with every entry on the list at a different spot. Imagine someone hands you an infinite catalogue claiming to list every infinite sequence of yes/no answers. You build a new sequence by looking down the diagonal: take the opposite of the first item's first answer, the opposite of the second item's second answer, and so on. Your new sequence differs from item k at position k, so it cannot equal any item on the list. The list was incomplete after all.

Georg Cantor used exactly this to prove that some infinities are bigger than others. Suppose you could list all infinite binary sequences as row 1, row 2, row 3, and so on. Form a new sequence whose k-th bit is the flip of the k-th bit of row k. This new sequence disagrees with row 1 in position 1, row 2 in position 2, and generally row k in position k — so it matches no row anywhere. Yet it is a perfectly valid infinite binary sequence. The assumed complete list cannot exist; the set of such sequences is uncountable. The same machinery shows the power set of any set is strictly larger than the set itself.

This is the structural skeleton behind the deepest results in computability. The very same diagonal move, applied to a hypothetical list of all programs paired with their behaviour, constructs a behaviour no program on the list can have — which is how one proves the halting problem is undecidable and that unrecognizable languages exist. Important honesty: this entry covers the diagonal technique itself; the specific undecidability proofs that deploy it (the halting problem, self-reference arguments) live in the undecidability material. The trick here is the engine; those are the vehicles it drives.