diagonalargument

Diagonalargument, also known as Cantor’s diagonal argument, is a mathematical technique used to show that certain collections cannot be listed or that one cannot capture all objects of a certain type with a given procedure. The most famous instance demonstrates that the real numbers are uncountable.

In the classic presentation, suppose all real numbers in the interval between 0 and 1 could be listed in a sequence, with each number written in its decimal (or binary) expansion. Construct a new number by altering the nth digit of the nth number in the list: choose a different digit from the nth digit, ensuring the constructed number differs from the nth listed number in that same position. By design, this new number cannot appear anywhere in the list. When decimal representations with trailing nines are avoided (for example, by using binary expansions or restricting representations), the construction is unambiguous. Hence there is no complete listing of all real numbers, showing their uncountability.

The idea generalizes to Cantor’s theorem: for any set A, there is no surjection from A onto its power set P(A). The diagonal argument produces, from any purported listing of the subsets of A, a new subset that differs on the diagonal, guaranteeing a missing element. This yields that the cardinality of P(A) is strictly greater than that of A.

Diagonalization has broad influence in logic and computer science, underpinning proofs of undecidability and various hierarchy results. It appears in proofs of the unsolvability of the Halting Problem and in the establishment of limits on formal systems and computational power.