Cantor's Diagonal Argument

No list of infinite binary sequences can contain them all: change the nth digit of the nth row and the result is missing.

Specifications & Metrics

proved

Georg Cantor, 1891

Core Principles & Analysis

• It shows the real numbers are uncountable — strictly more numerous than the naturals.
• The same move proves the halting problem undecidable in Turing's hands.
• Cantor called the transfinite hierarchy steps toward the absolute infinite, which cannot be a set.