Cantor's diagonal argument

Summary

Cantor's diagonal argument shows that some infinite sets are uncountable. Given a list $s_0, s_1, s_2, \dots$ of infinite sequences of $0$ and $1$, define a sequence $t$ by $t(n) = 1 - s_n(n)$. Then $t$ differs from each $s_n$ at position $n$, so $t$ is not in the list. So the set of all such sequences is not countable.

Remarks

Georg Cantor published the argument in 1891. His first proof that $\mathbb{R}$ is uncountable, from 1874, used another method. The same idea proves Cantor's theorem for every set. Diagonal arguments also appear in the proofs of the halting problem and of Gödel's incompleteness theorems.

Explanations

L1 human

Write the list of sequences as the rows of a table. Go down the diagonal and change each entry. The new row differs from row $n$ at column $n$, so it cannot be any row of the table.