How many infinities?

Two sets have the same size — the same cardinality — when their elements can be paired off one-to-one, by a bijection. For finite sets this is just counting. For infinite sets it gives surprises: the even numbers $0, 2, 4, \dots$ can be paired with all counting numbers $0, 1, 2, \dots$ by $n \mapsto 2n$, so there are "as many" even numbers as counting numbers. A set that can be listed as $s_1, s_2, s_3, \dots$ is called countable.

Are all infinite sets countable? In 1891 Georg Cantor gave a famous argument that the answer is no.

Suppose someone hands us a list $s_1, s_2, s_3, \dots$ of infinite 0–1 sequences. Build a new sequence $d$ by flipping the diagonal: let the $n$-th digit of $d$ be the opposite of the $n$-th digit of $s_n$. Then $d$ differs from $s_1$ in position $1$, from $s_2$ in position $2$, and in general from $s_n$ in position $n$. So $d$ is not anywhere on the list.

Since every list misses some sequence, the set of all infinite 0–1 sequences is uncountable: it is a strictly bigger infinity than the counting numbers.

The same diagonal idea reappears across mathematics and computer science: in showing that the real numbers are uncountable, in Gödel's incompleteness theorems, and in Turing's proof that no program can decide whether every program halts.