R is uncountable

Statement

Cantor's theorem. The set $\mathbb{R}$ is uncountable.

In other words, there is no bijection from $\mathbb{N}$ onto $\mathbb{R}$: the infinity of the reals is strictly larger than that of the integers. Cantor published this result in 1874, then in 1891 gave the proof that became famous, the diagonal argument.

It is enough to deal with the interval $\left[0, 1\right)$, because if it is uncountable, then $\mathbb{R}$, which contains it, is uncountable as well.

The diagonal argument

Proof by contradiction. Suppose $\left[0, 1\right)$ is countable. Then there is an enumeration $x_0, x_1, x_2, \ldots$ of all its elements. Write the proper decimal expansion of each, denoting by $a_{n,k}$ the $k$-th digit after the decimal point of $x_n$:

Rank	Decimal expansion	Diagonal digit
$0$	$0.\mathbf{1}\,4\,1\,5\ldots$	$a_{0,0} = 1$
$1$	$0.7\,\mathbf{1}\,8\,2\ldots$	$a_{1,1} = 1$
$2$	$0.5\,7\,\mathbf{7}\,2\ldots$	$a_{2,2} = 7$
$3$	$0.3\,0\,1\,\mathbf{0}\ldots$	$a_{3,3} = 0$

Constructing the escaping real. We build a number $y$ in $\left[0, 1\right)$ by requiring its $k$-th decimal digit $b_k$ to be different from $a_{k,k}$:

$$b_k = \begin{cases} 5 & \text{if } a_{k,k} \neq 5 \\ 4 & \text{if } a_{k,k} = 5 \end{cases}$$

In the example, $y = 0.5545\ldots$

Contradiction. The real number $y$ does belong to $\left[0, 1\right)$. Yet, for every $n$, it differs from $x_n$ in the $n$-th decimal place, so $y \neq x_n$. The enumeration, supposed to contain all the elements, misses one: it does not exist. The interval $\left[0, 1\right)$ is uncountable, and so is $\mathbb{R}$.

Why the digits $4$ and $5$

This choice is not cosmetic. The same real number can have two decimal expansions, such as

$$0.4999\ldots = 0.5000\ldots$$

If the digits $0$ and $9$ were allowed in the construction, the number $y$ obtained could coincide with some $x_n$ despite having a different expansion, and the argument would collapse. By using only $4$ and $5$, we avoid any sequence ending in infinitely many $0$s or $9$s: the expansion of $y$ is proper, and the digit-by-digit comparison is legitimate.

The general form: Cantor's theorem

The same argument, applied to indicator functions, gives a much stronger result:

For any set $E$, there is no surjection from $E$ onto the set $\mathcal{P}(E)$ of its subsets.

Proof. Let $f : E \to \mathcal{P}(E)$. Set $D = \left\{\, x \in E \;:\; x \notin f(x) \,\right\}$. If $D$ had a preimage $d$, then $d \in D \iff d \notin f(d) = D$, which is contradictory. The set $D$ therefore has no preimage, and $f$ is not surjective.

Starting from $\mathbb{N}$, we thus obtain a strictly increasing sequence of infinities: there is no largest cardinal.

Classic pitfall

Objecting "just add $y$ to the list." This misreads the reasoning: we are not constructing a number missing from one particular list, we are showing that every enumeration misses one. Adding $y$ produces a new enumeration, to which the same procedure will immediately apply a new escaping number.