Real Numbers are Uncountable/Cantor's Diagonal Argument

Theorem

The set of real numbers $\R$ is uncountably infinite.

Cantor's Diagonal Argument

We show that the unit interval $[0 . . 1]$ is uncountable, from which uncountability of $\R$ follows immediately.

Suppose that $[0 . . 1]$ is countable.

Clearly $[0 . . 1]$ is not finite because $\displaystyle \frac 1 n$ are distinct for $n \in \N$.

Therefore an injection $[0 . . 1]\hookrightarrow \N$ enumerates $[0 . . 1]$ with a subset of the natural numbers.

By relabeling, we can associate each $x \in [0 . . 1]$ to precisely one natural number to obtain a bijection.

Let $g$ be such a correspondence:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 1\)	\(\leftrightarrow\)	\(\displaystyle 0.d_{11}d_{12}d_{13}\ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 2\)	\(\leftrightarrow\)	\(\displaystyle 0.d_{21}d_{22}d_{23}\ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle n\)	\(\leftrightarrow\)	\(\displaystyle 0.d_{n1}d_{n2}d_{n3}\ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

where juxtaposition of digits descibes the decimal expansion of a number.

Note that the decimal expansion is not directly unique, because of 0.999...=1.

This problem is overcome by disallowing infinite strings of $9$'s in the decimal expansion.

For every $k \in \N$ define $f_k = d_{kk} + 1$ taken modulo $10$.

Let $y$ be defined by the decimal expansion:

$y = 0.f_1 f_2 f_3 \ldots$

Now

• $y$ differs from $g(1)$ in the first digit of the decimal expansion
• $y$ differs from $g(2)$ in the second digit of the decimal expansion

and generally the $n^\text{th}$ digit of the decimal expansion of $g(n)$ and $y$ is different.

By Existence of Base-N Representation, any decimal expansion of a real number is unique (except for the issue from 0.999...=1).

So $y$ can be none of the numbers $g(n)$ for $n \in \N$.

But $g$ is a bijection, a contradiction.

$\blacksquare$

Historical Note

This proof was first demonstrated by Georg Cantor.

Sources

• René L. Schilling: Measures, Integrals and Martingales (2005)... (previous)... (next) $2.8$