Cantor's Diagonal Argument: ℝ is Uncountable

Theorem

The set of real numbers $\mathbb{R}$ is uncountable. There is no surjection from $\mathbb{N}$ to $\mathbb{R}$.

Proof (Cantor’s diagonal argument, 1891)

Suppose for contradiction that we can list all real numbers in $[0, 1)$ as an infinite sequence $r_1, r_2, r_3, \ldots$

Write each $r_i$ in decimal expansion:

$r_i = 0.d_{i1}d_{i2}d_{i3}\ldots$

Construct a new number $x = 0.x_1 x_2 x_3 \ldots$ where each digit $x_i$ differs from $d_{ii}$ (the diagonal digit):

$x_i \neq d_{ii}$

Then $x$ differs from every $r_i$ in at least the $i$-th decimal place. So $x$ is not in our list — contradicting the assumption that we listed all reals. $\blacksquare$

Nikolay Eremeev, Senior Data Infrastructure Engineer. Writes about what he builds in production. CV ·hi@nikolay-eremeev.com