Infinity and Cantor's diagonal

Infinity is not one single thing. There is more than one size of it, and some are genuinely bigger than others.

Start with counting numbers: 1, 2, 3, and on forever. Now think of the even numbers: 2, 4, 6, and on forever. It feels like there should be half as many evens, but there are not. You can pair them up perfectly. Match 1 with 2, 2 with 4, 3 with 6, and keep going. Nobody is left over on either side. When you can pair two collections off one for one like that, they are the same size, even when both go on for ever. The fractions work the same way. There look like far more of them, but you can still line them all up in one long list and count through them.

So the surprise is that some things cannot be listed at all. Take every number between 0 and 1, written as an endless string of digits after the dot. Imagine someone hands you a list that they swear contains every one of them. Here is the trick that always beats them. Walk down the diagonal: take the first digit of the first number, the second digit of the second, the third of the third. Now build a brand new number by changing every one of those digits. Change the first digit, so your number is different from the first one on the list. Change the second, so it differs from the second. Do this all the way down.

The number you end up with cannot be anywhere on the list, because it disagrees with every single entry in at least one spot. However clever the list was, it missed one. So no list can hold them all. That infinity is bigger.

The right way to compare infinite sets is to stop counting and start pairing. Two sets have the same size, the same cardinality, when there is a bijection between them: a rule that matches every element of one to exactly one element of the other, with nothing missed and nothing doubled up. For finite sets this just recovers ordinary counting. For infinite sets it gives some strange results.

A set is called countable when you can list it as a first element, a second, a third, and so on, which is the same as pairing it with the natural numbers \(\mathbb{N} = \{1, 2, 3, \dots\}\). The even numbers are countable: the map \(n \mapsto 2n\) pairs each natural with an even, so \(|\mathbb{N}|\) equals the size of the evens even though one sits inside the other. The integers are countable (list them \(0, 1, -1, 2, -2, \dots\)). Even the rationals are countable, which is the real surprise: arrange every fraction in a grid by numerator and denominator, then sweep along the diagonals, skipping any you have already seen, and you get one endless list that reaches every fraction. This shared smallest infinity has a name, \(\aleph_0\) (aleph-null).

The real numbers are different. Cantor's diagonal argument shows the reals between 0 and 1 cannot be listed at all. Suppose, for contradiction, that they could. Then we can write them in a numbered list, each as an infinite decimal:

\[ \begin{aligned} r_1 &= 0.\,\mathbf{d_{11}}\,d_{12}\,d_{13}\,\dots \\ r_2 &= 0.\,d_{21}\,\mathbf{d_{22}}\,d_{23}\,\dots \\ r_3 &= 0.\,d_{31}\,d_{32}\,\mathbf{d_{33}}\,\dots \end{aligned} \]

Now build a new number \(x = 0.\,x_1 x_2 x_3 \dots\) by looking only at the bold diagonal digits and changing each one: set \(x_n\) to something different from \(d_{nn}\) (say, flip between a 4 and a 5 so you never trip over the \(0.4999\ldots = 0.5000\ldots\) ambiguity). By construction \(x\) differs from \(r_1\) in its first digit, from \(r_2\) in its second, from \(r_n\) in its \(n\)th. So \(x\) is a real number between 0 and 1 that appears nowhere on the list. The list was supposed to be complete, so this is a contradiction. No such list exists.

That makes the reals uncountable: a strictly larger infinity than \(\aleph_0\). Its size is called the cardinality of the continuum, written \(c\) or \(2^{\aleph_0}\). The endless decimals we write every day are a bigger endlessness than all the counting numbers put together. The widget above runs exactly this construction: it lists rows, lights the diagonal, and assembles the number that escapes.

Cardinals and the general theorem. Cardinality is defined by bijection: \(|A| = |B|\) iff a bijection \(A \to B\) exists, \(|A| \le |B|\) iff an injection \(A \to B\) exists. The Cantor–Schröder–Bernstein theorem makes this a genuine order (injections both ways give a bijection). The diagonal argument is one instance of something far more general, Cantor's theorem: for every set \(S\), there is no surjection from \(S\) onto its power set \(\mathcal{P}(S)\), so \(|S| < |\mathcal{P}(S)|\) always. The proof is the diagonal in pure form. Given any \(f : S \to \mathcal{P}(S)\), form the set \(D = \{\, s \in S : s \notin f(s)\,\}\). If \(D = f(t)\) for some \(t\), then \(t \in D \iff t \notin f(t) = D\), a contradiction. So \(D\) is in \(\mathcal{P}(S)\) but not in the image of \(f\). There is no largest cardinal: the hierarchy \(|S| < |\mathcal{P}(S)| < |\mathcal{P}(\mathcal{P}(S))| < \cdots\) climbs without end. The reals are one rung up from the naturals, since \(|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}\).

The continuum hypothesis. The naturals sit at \(\aleph_0\); the next cardinal is \(\aleph_1\); the reals sit at \(2^{\aleph_0}\). Is there any set strictly between them, larger than \(\mathbb{N}\) but smaller than \(\mathbb{R}\)? The continuum hypothesis (CH) says no: \(2^{\aleph_0} = \aleph_1\). Cantor believed it and could not prove it, and it headed Hilbert's 1900 list of problems. The resolution is that it cannot be settled from the usual axioms. Gödel showed in 1940 that CH is consistent with ZFC (it cannot be disproved), and Cohen showed in 1963, inventing forcing to do it, that its negation is also consistent (it cannot be proved). CH is independent of ZFC. The size of the continuum is not pinned down by the axioms we build mathematics on.

The diagonal as a machine. The same move recurs wherever a system tries to enumerate objects that can talk about that enumeration. Turing diagonalised over machines to prove the halting problem undecidable: assume a decider, feed it a program built to do the opposite of what the decider predicts about itself, contradiction. Gödel diagonalised over provable statements to build a sentence asserting its own unprovability, which is the heart of the incompleteness theorems. Russell's paradox is the set-theoretic version, Cantor's \(D\) with \(f\) the identity. All three are one argument: line up the objects, read down the diagonal, flip it, and produce something the line-up left out. Cantor found it first, and it never stops being useful.