Cantor's diagonal argument

Lore & Background

Georg Cantor published this proof in 1891, though it was not his first proof of the uncountability of the real numbers, which appeared in 1874. The argument considers the set T of all infinite sequences of binary digits. Cantor constructs a sequence s whose nth digit differs from the nth digit of the nth sequence in any enumeration, showing that s cannot be in the enumeration. This lemma leads to a proof by contradiction that T is uncountable.

Reader's Guide

The diagonal argument demonstrates a general technique that has since been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the Entscheidungsproblem. Diagonalization arguments are also often the source of contradictions like Russell's paradox and Richard's paradox. The argument also generalizes to Cantor's theorem: for every set S, the power set of S cannot be in bijection with S itself. This establishes a hierarchy of infinite cardinalities, with the cardinality of the continuum denoted c or 2^ℵ₀.

Did You Know?

• Cantor's diagonal argument was published in 1891, but his first proof of the uncountability of the real numbers appeared in 1874.
• The argument constructs a sequence s that differs from every sequence in an enumeration by flipping the nth digit of the nth sequence.
• Diagonalization arguments are used in Gödel's incompleteness theorems and Turing's solution to the Entscheidungsproblem.
• The argument generalizes to Cantor's theorem: the power set of any set S cannot be put into bijection with S.