In 1891, Georg Cantor published a two-page proof that shattered the naïve idea of infinity as a single, uniform thing. He showed that there are strictly more real numbers than natural numbers — that some infinities are larger than others. The weapon he used was breathtakingly simple: a diagonal.

Two Kinds of Infinite

A set $S$ is countably infinite if there exists a bijection $f: \mathbb{N} \to S$. Otherwise, if $S$ is infinite but not countable, it is uncountably infinite.

The integers $\mathbb{Z}$ and rationals $\mathbb{Q}$ are both countable — you can list them all in a sequence (with some cleverness). The question Cantor asked: what about $\mathbb{R}$?

The Theorem

The set of real numbers in the interval $(0, 1)$ is uncountable. In particular, $|\mathbb{R}| > |\mathbb{N}|$.

Suppose, for contradiction, that $(0,1)$ is countable. Then there exists a surjection $f: \mathbb{N} \to (0,1)$, which we can list as:

$$\begin{array}{c|cccccc} n & d_1 & d_2 & d_3 & d_4 & \cdots \\ \hline f(1) = & \mathbf{a_{11}} & a_{12} & a_{13} & a_{14} & \cdots \\ f(2) = & a_{21} & \mathbf{a_{22}} & a_{23} & a_{24} & \cdots \\ f(3) = & a_{31} & a_{32} & \mathbf{a_{33}} & a_{34} & \cdots \\ f(4) = & a_{41} & a_{42} & a_{43} & \mathbf{a_{44}} & \cdots \\ \vdots & & & & & \ddots \end{array}$$

where $a_{ij}$ is the $j$-th decimal digit of $f(i)$. Now construct a new number $x = 0.b_1 b_2 b_3 \cdots$ where:

$$b_i = \begin{cases} 2 & \text{if } a_{ii} \neq 2 \\ 3 & \text{if } a_{ii} = 2 \end{cases}$$

Then $x \in (0,1)$, but $x \neq f(n)$ for any $n \in \mathbb{N}$: $x$ differs from $f(n)$ in the $n$-th decimal place by construction. This contradicts the assumption that $f$ is surjective.

Therefore no such surjection exists, and $(0,1)$ is uncountable. $\square$

What the Diagonal Actually Does

The argument is not about finding one number that's missing — it's about showing that any proposed list must be incomplete. Whatever enumeration you provide, the diagonal construction hands you a number guaranteed to not be on it.

This is why the argument is so powerful: it doesn't attack a specific list. It attacks the very concept of a complete list of reals.

Cantor's Hierarchy

Define the cardinality of a set $S$ as $|S|$. Cantor proved:

$$|\mathbb{N}| = \aleph_0 < |\mathbb{R}| = 2^{\aleph_0} = \mathfrak{c}$$

And more generally, for any set $S$, the power set $\mathcal{P}(S)$ satisfies $|\mathcal{P}(S)| > |S|$. This generates an infinite tower of infinities:

$$\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$$
"The essence of mathematics lies in its freedom." — Georg Cantor

Cantor faced fierce opposition from contemporaries including Kronecker, who called his work "a corruption of youth." Today, the diagonal argument is considered one of the most elegant proofs in all of mathematics — a model of how a single idea can permanently restructure our understanding of the infinite.