Real Numbers are Uncountable/Cantor's First Proof

Theorem

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

Cantor's First Proof

We prove the equivalent result that every sequence $(x_k)_{k \in \N}$ omits at least one $x \in \R$.

Given $(x_k)_{k \in \N}$ of distinct real numbers define a sequence on closed real intervals $I_n$ as follows:

Let $a_1 = \min\{x_1,x_2\}$, $b_1 = \max\{x_1,x_2\}$ and $I_1 = [a_1 .. b_1]$.

Since $a_1\neq b_1$ this interval is not a singleton.

Now suppose we are given $I_{n-1} = [a_{n-1} .. b_{n-1}]$.

We may assume that infinitely many of the $x_k$ lie inside $I_{n-1}$ (otherwise we are done).

Let $y$ and $z$ be the first two such numbers, and let

$a_n = \min\{y,z\}$, $b_n = \max\{y,z\}$, $I_n = [a_n .. b_n]$.

Thus we have sequences $(a_k)_{k \in \N}$ and $(b_k)_{k \in \N}$ with

$ a_1 < a_2 < \cdots < b_2 < b_1 $

So $(a_k)_{k \in \N}$ and $(b_k)_{k \in \N}$ are monotone and bounded above and below respectively.

Therefore by the Monotone Convergence Theorem both are convergent. Let

$\displaystyle A = \lim_{k \to \infty} a_k$, $\displaystyle B = \lim_{k \to \infty} b_k$.

Clearly we have $A \leq B$, so $[A,B] \neq \emptyset$.

Let $h \in [A .. B]$. Then $h \neq a_k, b_k$ for all $k$.

We claim that $h \neq x_k$ for all $k$.

Suppose that $h = x_k$ for some $k$.

Then there are only finitely many points in the sequence before $h$ occurs, and therefore only finitely many of the $a_k$ precede $h$.

Let $a_d$ be the last element of the sequence $(a_k)_{k \in \N}$ preceding $h$.

We defined $a_{d+1}$, $b_{d+1}$ to be interior points of $I_d$, and also $h \in I_{d+1}$ by the definition of $h$.

Therefore $a_{d+1}$ must precede $h$ in the sequence, for the sequence is monotone increasing, a contradiction.

$\blacksquare$

Historical Note

This proof was first demonstrated by Georg Cantor.