# Real Numbers are Uncountable/Cantor's First Proof

## Theorem

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

## Proof

We prove the equivalent result that every sequence $\left\langle{x_k}\right\rangle_{k \in \N}$ omits at least one $x \in \R$.

Let $\left\langle{x_k}\right\rangle_{k \in \N}$ be a sequence of distinct real numbers.

Let a sequence of closed real intervals $\left\langle{I_n}\right\rangle$ be defined as follows:

Let:

- $a_k = \min \left\{ {x_k, x_{k+1} }\right\}$
- $b_k = \max \left\{ {x_k, x_{k+1} }\right\}$

and:

- $I_k = \left[{a_k \,.\,.\, b_k}\right]$

Since the terms of $\left\langle{x_k}\right\rangle_{k \in \N}$ are distinct, $a_k \ne b_k$.

Thus $I_k$ is not a singleton.

Let:

- $I_{n-1} = [a_{n-1} \,.\,.\, b_{n-1}]$

It can be assumed that infinitely many of the $x_k$ lie inside $I_{n-1}$.

Otherwise the proof is complete.

Let $y$ and $z$ be the first two such terms of $\left\langle{x_k}\right\rangle_{k \in \N}$.

Let:

- $a_n = \min \left\{ {y, z}\right\}$
- $b_n = \min \left\{ {y, z}\right\}$
- $I_n = \left[{a_n \,.\,.\, b_n}\right]$

Thus we have sequences:

- $\left\langle{a_k}\right\rangle_{k \in \N}$
- $\left\langle{b_k}\right\rangle_{k \in \N}$

with:

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

So $\left\langle{a_k}\right\rangle_{k \in \N}$ and $\left\langle{b_k}\right\rangle_{k \in \N}$ are monotone, and bounded above and bounded below respectively.

Therefore by the Monotone Convergence Theorem (Real Analysis) both are convergent.

Let:

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

Clearly we have $A \le B$.

So:

- $\left[{A \,.\,.\, B}\right] \ne \varnothing$

Let $h \in [A \,.\,.\, B]$.

Then:

- $h \ne a_k, b_k$ for all $k$.

We claim that $h \ne 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.

Therefore only finitely many of the $a_k$ precede $h$.

Let $a_d$ be the last element of the sequence $\left\langle{a_k}\right\rangle_{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.

This is a contradiction.

$\blacksquare$

## Historical Note

This proof was first demonstrated by Georg Cantor.