Real Numbers are Uncountable/Cantor's Diagonal Argument

From ProofWiki
Jump to navigation Jump to search


Theorem

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


Proof

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


Aiming for a contradiction, suppose that $\hointr 0 1$ is countable.


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

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

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

(By hypothesis, such a mapping can be constructed).

Let $g$ be such a correspondence:

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

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

By Existence of Base-$N$ Representation, any decimal expansion of a real number exists and is unique, or else has exactly two representative strings.

In this case, if there are exactly two representations, one will have an infinite trail of $9$s, and one will terminate.

Restrict $g$ such that there exists no infinite strings of $9$s in the decimal expansions in the question, i.e. to the set:

$S := \left\{ {f: \N \to \set {0, 1, 2, \ldots, 9} }\middle\vert\,{ \forall M \in \N: \exists m \ge M: \map f m \ne 9}\right\}$

of sequences in $\set {0, 1, 2, \ldots, 9}$ not ending in infinitely many $9$s.


Define $g'$ as the restriction of $g$ to $S$:

$g' := g \restriction S$

That is, construct $g'$ such that there exist no infinite strings of $9$s in the decimal expansions in question.

From Injection to Image is Bijection, $g'$ is one-to-one, and consequently is onto.

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

That is, $f: 0 \mapsto 1, 1 \mapsto 2, \dots, 8 \mapsto 9, 9 \mapsto 0$.

Let $y$ be defined by the decimal expansion:

$y = 0.f_1 f_2 f_3 \ldots$


Now:

$y$ differs from $\map {g'} 1$ in the first digit of the decimal expansion
$y$ differs from $\map {g'} 2$ the second digit of the decimal expansion

and generally the $n$th digit of the decimal expansion of $\map {g'} n$ and $y$ is different.

So $y$ can be none of the numbers $\map {g'} n$ for $n \in \N$.

But $g'$ is a surjection.

From this contradiction it is deduced that $\hointr 0 1$ is not countable.

$\blacksquare$


Historical Note

This proof was first demonstrated by Georg Cantor.


Sources