Cantor's Diagonal Argument — Watch ℝ Escape Every List

Here is the theorem you are about to watch happen in front of you:

\mathbb{R} \text{ is uncountable} \quad \Longleftrightarrow \quad |\mathbb{R}| > |\mathbb{N}|.

No matter how clever your enumeration scheme, the real numbers between 0 and 1 cannot be arranged into a list r_1, r_2, r_3, \ldots that contains every one of them. This is not a statement about computational difficulty or human ingenuity. It is a logical impossibility: any list you propose comes with a recipe for building a real number that is provably missing. Cantor found that recipe in 1891, and it is so clean you can watch it run on an imaginary enumeration right here.

The setup — assume the list exists

Suppose, for contradiction, that you do have a complete list of every real number in [0, 1]. Write each one out as a decimal expansion:

\begin{aligned} r_1 &= 0.\mathbf{a_{11}}\, a_{12}\, a_{13}\, a_{14}\, a_{15}\, \dots \\ r_2 &= 0.a_{21}\, \mathbf{a_{22}}\, a_{23}\, a_{24}\, a_{25}\, \dots \\ r_3 &= 0.a_{31}\, a_{32}\, \mathbf{a_{33}}\, a_{34}\, a_{35}\, \dots \\ r_4 &= 0.a_{41}\, a_{42}\, a_{43}\, \mathbf{a_{44}}\, a_{45}\, \dots \\ &\vdots \end{aligned}

The bold digits form a diagonal: a_{11}, a_{22}, a_{33}, \ldots — the k-th digit of the k-th number. This diagonal is the weapon. You are going to use it to manufacture a real number x \in [0, 1] that cannot appear anywhere on the list, contradicting the assumption that the list was complete.

Why the diagonal specifically: it is the unique digit position where you have freedom to disagree with row k without worrying about any other row. To guarantee x \ne r_k for every k, you need to disagree with r_k in at least one digit. The k-th digit is the cheapest choice — one disagreement, one row handled, move on.

The diagonal flip

For each row k, take the k-th digit a_{kk} and produce a new digit x_k that is guaranteed different:

x_k \;=\; (a_{kk} + 1) \bmod 10.

So if a_{kk} = 3, set x_k = 4. If a_{kk} = 9, set x_k = 0. Always a change of one digit — never equal to the original. Assemble:

x \;=\; 0.x_1\, x_2\, x_3\, x_4\, x_5\, \ldots

This x is a real number in [0, 1]. And it differs from r_k in the k-th decimal place, for every k. So x cannot equal r_1 (different in position 1), cannot equal r_2 (different in position 2), cannot equal r_3 (different in position 3), \ldots The list was supposed to contain every real in [0, 1], yet here is one it missed. Contradiction. No such list exists. \mathbb{R} is uncountable.

Watch it happen row by row

The widget below is a finite slice of the argument. Each row shows a pretend real number from the assumed list. The diagonal digit is circled in red. The slider advances one row at a time; as it does, the diagonal digit is copied over to the constructed number x at the bottom, with +1 \bmod 10 applied. Press Play to animate the assembly.

row k:

Ten rows of pretend reals $r_1, \ldots, r_{10}$, each shown to ten decimal places. The circled digit in row $k$ is $a_{kk}$. As you advance the slider, the constructed number $x$ fills in its $k$-th digit as $(a_{kk} + 1) \bmod 10$ — guaranteed different from row $k$. After ten rows, $x$ disagrees with every row shown, in at least one place each.

Why the construction is airtight

The slick thing about Cantor's construction is that it uses the list against itself. You did not need to know anything about how the list was generated — alphabetical, by some formula, by Monte Carlo simulation, by an oracle. The only thing the argument uses is that each row has a well-defined k-th digit. That is enough.

Every row r_k gets handled exactly once, in position k:

x_1 \ne a_{11}, so x \ne r_1 (they disagree in position 1).
x_2 \ne a_{22}, so x \ne r_2 (they disagree in position 2).
x_k \ne a_{kk}, so x \ne r_k (they disagree in position k).

For every natural number k, the constructed x is different from the k-th entry. Since the list was assumed to cover every real in [0, 1], and x is missing from it, the assumption fails. No list of all reals exists.

Why shifting by +1 \bmod 10 and not by +5 or -1: any flip that always produces a different digit works. The +1 \bmod 10 rule is just the cleanest choice — it is defined for all ten possible digits without special cases. An alternative Cantor sometimes used was "x_k = 5 if a_{kk} \ne 5, else x_k = 6" — equivalently simple.

A subtle technicality: 0.4999\ldots = 0.5000\ldots

A careful reader might worry: what if the flipped x happens to equal some r_k under a different decimal representation? For example, 0.4999\ldots and 0.5000\ldots name the same real. Could the diagonal produce 0.4999\ldots while one of the rows holds 0.5000\ldots?

The fix is to forbid the digits 0 and 9 in the construction. Replace the rule with

x_k = \begin{cases} 3 & \text{if } a_{kk} \ne 3 \\ 4 & \text{if } a_{kk} = 3 \end{cases}

Now x_k \in \{3, 4\} always. A decimal made only of 3s and 4s has exactly one representation — there is no ambiguous trailing-9s business. The construction still disagrees with every row in at least one position, and the ambiguity-loophole is closed. Cantor's original paper handled this cleanly; the widget above uses +1 \bmod 10 for visual simplicity, and in the rare edge case you can always fall back to the \{3, 4\} variant.

The same proof works in binary

The argument does not care that we used base ten. Write every real in [0, 1] in binary: r_k = 0.b_{k1} b_{k2} b_{k3} \ldots where each b_{kj} \in \{0, 1\}. Flip the diagonal: set x_k = 1 - b_{kk}. The resulting x disagrees with every row in at least one position, and binary has the same 0.1111\ldots = 1.0000\ldots kind of edge case, handled the same way by restricting to non-terminating representations. The uncountability of \mathbb{R} is a base-independent fact.

More generally, the same argument shows that the power set of any set S has strictly larger cardinality than S itself — Cantor's theorem. The diagonal is just one application of a technique called diagonalisation that reappears throughout logic, computability theory (Turing's halting-problem proof), and Gödel's incompleteness theorems.

Linking back to "countable rationals, uncountable reals"

You already saw in Rationals Are Countable, Reals Are Not that the rationals can be listed by Cantor's grid walk, giving a one-to-one correspondence with \mathbb{N}. The diagonal argument above is the companion result: no such correspondence can work for \mathbb{R}.

Put them together and you get the first clear sign that infinity is stratified. The countable infinity of \mathbb{N}, \mathbb{Z}, \mathbb{Q}, and even the algebraic numbers is one size — \aleph_0. The uncountable infinity of \mathbb{R} is a strictly larger size — 2^{\aleph_0}, often called the continuum. And since \mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q}) with \mathbb{Q} countable, it follows that the irrationals themselves must be uncountable: they carry all the "excess" cardinality.

That is why you cannot list the reals row by row, no matter how clever you get. The diagonal is watching, ready to flip whatever you write down.