Uncountable Sets

We saw that the integers and even the rationals are countable — the same size as \mathbb{N}. It is tempting to conclude that every infinite set is countable, that there is just one infinity. In 1874 Georg Cantor proved otherwise, and the mathematical world has never quite recovered. The real numbers \mathbb{R} — even just the interval [0, 1] — are uncountable: no list, however clever, can contain them all. There are strictly more reals than naturals.

Cantor's diagonal argument

The proof is by contradiction, and it is one of the most elegant arguments in all of mathematics. Suppose [0, 1] were countable, so we could list every real in it 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 brand-new number d by walking down the diagonal and changing every digit: make d's first digit differ from d_{11}, its second from d_{22}, its n-th from d_{nn}. Then d is a perfectly good number in [0, 1] — but it differs from every r_n (at least in the n-th place), so it is not on the list. The list was supposed to contain everything: contradiction. No list can. Watch d get built:

// Pretend this list contains "all" reals in [0,1] (6 shown). We defeat it with the diagonal. const list = [ "0.135724", "0.582917", "0.409156", "0.718293", "0.640831", "0.926450", ]; // Build d by changing the n-th digit of the n-th number (use 5<->6 to stay unambiguous). let d = "0."; for (let n = 0; n < list.length; n++) { const diagDigit = list[n][n + 2]; // +2 skips the "0." d += diagDigit === "5" ? "6" : "5"; // guarantee it DIFFERS from the diagonal digit } console.log("the list claimed to hold every real, e.g.:"); for (const r of list) console.log(" " + r + "..."); console.log("diagonal number d = " + d + "..."); console.log("d differs from row n at digit n, so d is on NO row: the list is incomplete.");

You could add d to the list — but then the same trick builds another missing number, forever. The reals simply cannot be enumerated.

A strictly bigger infinity

This cracks the number line open. Since the algebraic numbers are countable but the reals are not, almost every real number is transcendental — yet transcendental numbers are notoriously hard to exhibit. The size of this bigger infinity, |\mathbb{R}|, is the continuum.

The numbers you can describe — with a formula, an equation, or a finite computer program — form a countable set (there are only countably many finite descriptions). But the reals are uncountable. So the descriptions run out long before the numbers do: almost every real number has no finite description at all. The line you draw on paper is overwhelmingly made of numbers that can never be individually named, computed, or written down. Cantor's diagonal is the proof that this vast, unnameable majority exists.