The idea: flip the diagonal
Someone hands you a list and says it holds every infinite sequence of 0s and 1s: row 1, row 2, row 3, and so on forever. Cantor's diagonal argument shows the claim is always false. Read the diagonal: digit 1 of row 1, digit 2 of row 2, digit 3 of row 3, … Flip each one. The flipped digits make a new sequence d, and d is on no row.
Pick a list, then press Next Row to build d one digit at a time, or Flip All for all ten drawn rows. Each diagonal cell turns orange, the flipped digit flies down into d, and the row gets a red ✗: d is not this row.
Why d is on no row
Take any row, say row 7. Digit 7 of d was made from digit 7 of row 7, by flipping it. So d and row 7 differ at digit 7, and two sequences that differ in one digit are different sequences. That works for every n, also for the rows below the ⋮ that the canvas does not draw. So d is not row 1, not row 2, not row n for any n: the list misses d (Demo: 0/1 sequences → d is not on the list).
The argument never looks at the other digits. It does not matter how clever the list is; d is built to disagree with it.
Adding d does not help
The obvious fix is to add d to the list. Add d to List puts it in as the new row 1 and shifts every other row down one. The list is still infinite, nothing is lost. But the new list has a new diagonal, and flipping it gives a new d that is missing again (Demo: add d to the list → a new d escapes). Every list, fixed or not, misses some sequence. Since a list is the same thing as a numbering 1, 2, 3, …, this says the 0/1 sequences cannot be numbered: they are uncountable.
Decimals: the real numbers
The same works for the numbers between 0 and 1, written as decimals 0.d₁d₂d₃… One trap: some numbers have two decimal forms, 0.4999… = 0.5000… A careless d could be one form of a number whose other form is on the list. The fix is a rule that never writes 0 or 9: if digit n of row n is 5, write 4; otherwise write 5. Then d is a decimal of 4s and 5s with one form only, and it differs from every row (Demo: decimals in [0, 1) → the reals are uncountable). The list on the canvas holds π − 3, e − 2, √2 − 1, 1/3 and others, and d = 0.5555555554… is none of them.
| List | Flip rule | d after 10 rows |
|---|---|---|
| 0/1 sequences s1 … s10 | 0 → 1, 1 → 0 | 1101110101… |
| decimals π − 3, e − 2, … | 5 → 4, else → 5 | 0.5555555554… |
| finite sets ∅, {1}, {2}, {1,2}, … | 0 → 1, 1 → 0 | 1111111111… = {1, 2, 3, …} |
| halting table P1 … P10 | H → L, L → H | the program D |
Countable and uncountable
A set is countable if its elements can be put in one list, row 1, row 2, … with every element on some row. Many infinite sets are countable: the integers (0, 1, −1, 2, −2, …) and even the fractions (walk the grid of p/q in a zigzag). The diagonal argument shows the 0/1 sequences and the real numbers are not: there are strictly more of them than there are whole numbers.
Careful with what the argument proves. The finite sets of positive integers can be listed: write n − 1 in binary, smallest digit first, and read digit k = 1 as "k is in the set". Every finite set shows up. Run the diagonal on that list and every row has 0 at its own digit, so d = 111… = {1, 2, 3, …}. d is missing, but d is infinite, so it was never supposed to be there (Demo: every finite set listed → d = {1, 2, 3, …}). The same reading turns 0/1 sequences into all subsets of {1, 2, 3, …}, which proves Cantor's theorem: a set always has more subsets than elements, d = {n : n is not in set n}.
The same trick: the halting problem
Suppose a program could tell, for every program P and input x, whether P halts on x. List all programs P1, P2, P3, … (programs are finite texts, so they can be listed) and fill a table: cell (i, j) is H if Pi halts on input Pj, L if it loops. Now write the program D: on input Pn, look up cell (n, n) and do the opposite, loop if it says H, halt if it says L. D differs from every Pn on input Pn, so D is no row. But D is a program, so it must be some row Pk. Cell (k, k) then asks whether D halts on itself, and D does the opposite of the answer. The table cannot exist, so no halting test exists (Demo: halting table → the program D cannot exist). The programs themselves run on a machine like the one on Turing Machine. Russell's paradox, the set of all sets that are not members of themselves, is the same diagonal once more.
Other proof styles on this site: Proof by Induction walks a row of dominoes, the pigeonhole principle forces a collision, Truth Tables and Sets checks every row, and Proofs Without Words proves by picture.
The Cantor set is a set of length zero that is still uncountable: its points are the infinite strings of base-3 digits 0 and 2.
What the page leaves out
Cantor's first, non-diagonal proof (nested intervals); bijections such as the Cantor pairing function and the Schröder–Bernstein theorem; the continuum hypothesis and the cardinals ℵ₀, ℵ₁, 2^ℵ₀; Gödel's incompleteness theorem, which uses the same diagonal on sentences; and formal versions of the halting proof on a fixed model of computation.