Mathematics

Cantor's Diagonal Argument: Why Some Infinities Are Bigger

We present Cantor's diagonal argument proving that the real numbers are uncountable, explore its consequences for set theory, and examine how it forever changed our understanding of infinity.

Set Theory Foundations

The Theorem

Theorem (Cantor, 1891)

The set $\mathbb{R}$ of real numbers is uncountable. That is, there is no surjection from $\mathbb{N}$ onto $\mathbb{R}$ .

In modern language: $|\mathbb{N}| < |\mathbb{R}|$ , or equivalently $\aleph_0 < |\mathbb{R}| = 2^{\aleph_0}$ .

Countable vs. Uncountable

A set $S$ is countable if there exists a bijection $f: \mathbb{N} \to S$ (or $S$ is finite). Equivalently, the elements of $S$ can be listed as a sequence $s_1, s_2, s_3, \ldots$ that exhausts the entire set.

Countable Sets

$\mathbb{N}, \; \mathbb{Z}, \; \mathbb{Q}$

All can be listed in a sequence

Uncountable Sets

$\mathbb{R}, \; [0,1], \; \mathcal{P}(\mathbb{N})$

Cannot be listed in any sequence

The fact that $\mathbb{Q}$ is countable (proved by Cantor's earlier zig-zag argument) makes the uncountability of $\mathbb{R}$ all the more surprising. Between any two rationals lies another rational, and between any two reals lies a rational — yet somehow the reals are "far more numerous."

The Diagonal Argument

We prove that even the interval $[0,1]$ is uncountable.

Proof (by contradiction)

Step 1 — Assume a listing exists.

Suppose $[0,1]$ is countable. Then we can list all its elements:

$r_1, \; r_2, \; r_3, \; r_4, \; \ldots$

Write each in its decimal expansion (choosing the non-terminating form when there is ambiguity):

$r_1 = 0.\mathbf{d_{11}} d_{12} d_{13} d_{14} \cdots$ $r_2 = 0.d_{21} \mathbf{d_{22}} d_{23} d_{24} \cdots$ $r_3 = 0.d_{31} d_{32} \mathbf{d_{33}} d_{34} \cdots$ $r_4 = 0.d_{41} d_{42} d_{43} \mathbf{d_{44}} \cdots$ $\vdots$

where each $d_{ij} \in \{0, 1, 2, \ldots, 9\}$ .

Step 2 — Construct a number not in the list.

Define a new real number $x = 0.c_1 c_2 c_3 c_4 \cdots$ by setting:

$c_n = \begin{cases} 3 & \text{if } d_{nn} \neq 3 \\ 7 & \text{if } d_{nn} = 3 \end{cases}$

(The choice of $3$ and $7$ avoids complications with $0.999\ldots = 1.000\ldots$ .)

Step 3 — Reach a contradiction.

The number $x$ differs from $r_n$ in the $n$ -th decimal place for every $n \in \mathbb{N}$ . Therefore $x \neq r_n$ for all $n$ , so $x \notin \{r_1, r_2, r_3, \ldots\}$ .

But $x \in [0,1]$ , contradicting the assumption that the list was exhaustive. $\square$

Why the Argument Works

The core logic is a self-referential diagonalization: we use the $n$ -th digit of the $n$ -th number to construct something that escapes the entire list. The "diagonal" comes from reading the entries $d_{11}, d_{22}, d_{33}, \ldots$ — the main diagonal of the infinite matrix $(d_{ij})$ .

The diagonal method is a universal technique: wherever you have a complete enumeration of objects, the diagonal constructs something that cannot be in the enumeration. It appears in the proofs of the halting problem, Gödel's incompleteness theorems, and Russell's paradox.

Cantor's Theorem (General Version)

The diagonal argument generalizes far beyond the reals.

Cantor's Theorem

For every set $A$ , there is no surjection $f: A \to \mathcal{P}(A)$ . In particular, $|A| < |\mathcal{P}(A)|$ .

Proof. Suppose $f: A \to \mathcal{P}(A)$ is a surjection. Define the diagonal set:

$D = \{a \in A : a \notin f(a)\}$

Since $f$ is surjective, there exists $d \in A$ with $f(d) = D$ . Now:

If $d \in D$ , then by definition of $D$ , $d \notin f(d) = D$ . Contradiction.
If $d \notin D$ , then $d \notin f(d)$ , so $d \in D$ by definition. Contradiction.

Either way we reach a contradiction, so no surjection exists. $\square$

An Infinite Hierarchy of Infinities

Applying Cantor's theorem repeatedly:

$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$

In terms of cardinal numbers:

$\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$

There is no "largest infinity" — the tower of power sets grows without bound.

The Continuum Hypothesis

Since $|\mathbb{R}| = 2^{\aleph_0} > \aleph_0$ , a natural question arises:

The Continuum Hypothesis (CH). There is no set $S$ with $\aleph_0 < |S| < 2^{\aleph_0}$ . Equivalently, $2^{\aleph_0} = \aleph_1$ .

Cantor believed this was true but could not prove it. Hilbert listed it as the first of his famous 23 problems in 1900. The resolution came in two stages:

Gödel (1940) showed that CH is consistent with ZFC (cannot be disproved).
Cohen (1963) showed that CH is independent of ZFC (cannot be proved either).

The continuum hypothesis is therefore undecidable within standard set theory — a stunning consequence of the diagonal method's legacy.

The Reals and the Power Set

Why does $|\mathbb{R}| = 2^{\aleph_0} = |\mathcal{P}(\mathbb{N})|$ ? The key bijection is:

$\mathcal{P}(\mathbb{N}) \longleftrightarrow \{0,1\}^{\mathbb{N}} \longleftrightarrow [0,1]$

where a subset $S \subseteq \mathbb{N}$ maps to its characteristic function $\chi_S$ , and a binary sequence $b_1 b_2 b_3 \cdots$ maps to the real number $\sum_{n=1}^{\infty} b_n / 2^n$ . (This is a bijection up to a countable set of dyadic rationals, which does not affect cardinality.)

Applications of Diagonalization

Non-Computable Functions Exist

The set of all Turing machines is countable (each is described by a finite string). The set of all functions $f: \mathbb{N} \to \{0,1\}$ has cardinality $2^{\aleph_0}$ , which is uncountable. Therefore most functions are not computable.

The Halting Problem

Turing's proof that no algorithm can decide whether an arbitrary program halts uses the same diagonal trick: assume a decider exists, and construct a program that contradicts the decider on its own input.

Gödel's Incompleteness

Gödel assigned numbers to formulas (Gödel numbering) and used a diagonal construction to build a sentence that says "I am not provable," leading to the First Incompleteness Theorem.

Historical Context

Georg Cantor published his first uncountability proof in 1874, using a different method (nested intervals). The elegant diagonal argument appeared in an 1891 paper, "Über eine elementare Frage der Mannigfaltigkeitslehre."

Cantor's work was revolutionary but fiercely opposed. Leopold Kronecker called him a "scientific charlatan," and Henri Poincaré described set theory as a "disease." Despite this, David Hilbert declared: "No one shall expel us from the paradise that Cantor has created."

Today, Cantor's ideas form the foundation of modern set theory, topology, measure theory, and mathematical logic.

Common Misconceptions

"The diagonal argument only works for decimal expansions." No — it works for any representation. The general Cantor theorem (for power sets) needs no decimals at all.

"You can defeat the argument by using a different listing." The argument works for any proposed listing. There is no clever enumeration that escapes the diagonal.

"Countable and uncountable are just different ways of being infinite." They reflect a genuine structural difference: you cannot pair up $\mathbb{N}$ and $\mathbb{R}$ one-to-one, no matter how hard you try.

Summary

\begin{aligned} &\textbf{Assume } [0,1] = \{r_1, r_2, r_3, \ldots\} \\[6pt] &\Downarrow \\[6pt] &\textbf{Form diagonal: } d_{11}, d_{22}, d_{33}, \ldots \\[6pt] &\Downarrow \\[6pt] &\textbf{Flip each digit: } c_n \neq d_{nn} \\[6pt] &\Downarrow \\[6pt] &x = 0.c_1c_2c_3\cdots \text{ differs from every } r_n \\[6pt] &\Downarrow \\[6pt] &x \notin \{r_1, r_2, \ldots\} \quad \textbf{Contradiction!} \quad \square \end{aligned}

References

Cantor, G., "Über eine elementare Frage der Mannigfaltigkeitslehre," Jahresbericht der DMV, 1891.
Halmos, P., Naive Set Theory, Springer, 1974.
Enderton, H., Elements of Set Theory, Academic Press, 1977.
Wikipedia — Cantor's diagonal argument
Wikipedia — Cantor's theorem
3Blue1Brown — How many real numbers are there?

Back to all posts