Real Numbers are Uncountable

Theorem

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

Proof

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$

Cantor's Second Proof

By definition, a perfect set is a set $X$ such that every point $x \in X$ is the limit of a sequence of points of $X$ distinct from $x$.

From Real Numbers form a Perfect Set, $\R$ is perfect.

Therefore it is sufficient to show that a perfect subset of $X \subseteq \R^k$ is uncountable.

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

Let $y_1 \in X$, and let $B_1 := \mathcal B_r(y_1)$ be some closed ball centred at $y_1$.

Given $B_{n-1}$ choose a closed ball $B_{n-1} \supseteq B_n := \mathcal B_{\delta(n)}(y_n)$ such that $\delta(n) \leq \delta(n-1)/2$ (note that $\delta(1) = r$), $y_n \in X$ and $x_n \notin B_n$.

We can satisfy the condition $x_n \notin B_n$ because $X$ is perfect, so every ball centred at a point of $X$ contains infinitely many points of $X$.

Since $\displaystyle \delta(n) \leq \frac r{2^{n-1}}$, $y_n$ is Cauchy.

Therefore since a perfect set is necessarily closed we may let $\displaystyle Y = \lim_{n \to \infty} y_n \in X$.

For $n \in \N$ we have $\{ y_m : m > n\} \subseteq B_n$, so $Y \in B_n$.

But by construction for each $n \in \N$ $x_n \notin B_n$.

Therefore $Y \neq x_n$ for all $n \in \N$, and we are done.

$\blacksquare$

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$

Set-Theoretical Approach: Proof 1

By definition a set $A$ is countable iff there is a surjection from $f: \N \to A$.

Suppose there were a surjection $f: \N \to \R$.

Then $\forall x \in \R: \exists n \in \N: f \left({n}\right) = x$ as $f$ is surjective.

Let $d_{n, 0}$ be the integer before the decimal point of $f \left({n}\right)$.

Similarly, for all $m > 0$, let $d_{n, m}$ be the $m$th digit in the decimal expansion of $f \left({n}\right)$.

Let $e_0$ be an integer different from $d_{0, 0}$.

Similarly, for all $m > 0$, let $e_m$ be an integer different from $d_{m, m}$.

Specifically, we can define $e_0$ to be $d_{0, 0} + 1$, and:

$e_m = \begin{cases} 1 & : d_{m, m} \ne 1 \\ 2 & : d_{m, m} = 1 \end{cases}$

Now consider the real number $\displaystyle x = e_0 + \sum_{n=1}^\infty \frac {e_n} {10^n}$.

Its decimal expansion is:

$x = \left[{e_0 . e_1 e_2 e_3 \ldots}\right]_{10}$

Since $e_0 \ne d_{0, 0}$, $x \ne f \left({0}\right)$.

Similarly, for each $n \in \N$ such that $n \ge 1$, we have that $e_n \ne d_{n, n}$ and so $x \ne f \left({n}\right)$.

Thus $x$ is a real number which is not in the set $\left\{{f \left({n}\right): n \in \N}\right\}$.

Hence $f$ can not be surjective.

Set-Theoretical Approach: Proof 2

By Cantor's Theorem there is no surjection $\N \twoheadrightarrow \mathcal P(\N)$.

Additionally, we know that the power set of the natural numbers is not countable.

Therefore, if we can show that $\mathcal P(\N)$ injects into $\R$ then there is no injection $\R \hookrightarrow \N$ and $\R$ is uncountable.

To prove the theorem we construct an injection, say $f$.

For a subset $S \subseteq \N$, let $\chi_S$ be the characteristic function of $S$, and let $d_i = \chi_S(i)$ for all $i \in \N$.

If the sequence $(d_i)_{i \in \N}$ does not terminate in an infinite sequence of $1$'s, then $f$ sends $S \subseteq \N$ to the binary expansion of a number in $[0,1]$:

$ 0.d_1d_2d_3d_4\ldots $

If the sequence $(d_i)_{i \in \N}$ does terminate in an infinite sequence of $1$'s, then $f$ sends $S$ to the binary integer:

$d_1d_2d_3\ldots d_k .000\ldots$

where $d_k$ is the last member of the sequence not equal to $1$.

Injectivity of $f$ follows from the uniqueness statement of Existence of Base-N Representation.

$\blacksquare$

Proof using Ternary Numbers

It is sufficient to show that the real interval $I = \left\{{x \in \R: 0 < x \le 1}\right\}$ is uncountable.

Let $x \in I$.

From Existence of Base-N Representation, $x$ has a unique representation of the form:

$x = \dfrac {\epsilon_1} 3 + \dfrac {\epsilon_2} {3^2} + \dfrac {\epsilon_3} {3^3} + \cdots$

where $\epsilon_k = 0, 1$ or $2$ and an infinite number of $\epsilon_k$ are different from $0$.

Let $S \subseteq I$ be countably infinite.

Let $S = \left\{{x_1, x_2, \ldots}\right\}$.

Let $\epsilon_{k1}, \epsilon_{k2}, \epsilon_{k3}, \ldots$ be the ternary digits of $x_k$.

Let $\epsilon_k = 1 + 2 \epsilon_{kk} - \epsilon_{kk}^2$ so that:

• $\epsilon_k = 1$ if $\epsilon_{kk} = 0$ or $\epsilon_{kk} = 2$
• $\epsilon_k = 2$ if $\epsilon_{kk} = 1$

Then:

$(1): \quad \forall k: \epsilon_k \ne 0$

$(2): \quad \forall k: \epsilon_k \ne \epsilon_{kk}$

We have that $0 < x \le 1$ so $x \in I$.

But the real number $\displaystyle x = \sum \epsilon_k 3^{-k}$ is different from every $x_k \in I$.

Thus we have found an element of $I$ which is not an element of $S$.

Therefore $S$ is a proper subset of $I$.

It follows by definition that $I$ is uncountable.

$\blacksquare$

Notes

This was first demonstrated by Georg Cantor.

Cantor's first and second proofs given above are less well known than the diagonal argument, and were in fact downplayed by Cantor himself: the first proof was given as an aside in his paper proving the countability of the algebraic numbers.

Joseph W. Dauben conjectures that this was because Cantor feared opposition from Leopold Kronecker among other contemporaries who aggressively dismissed Cantor's ideas.

In particular Cantor's first proof is worth reading; several texts reject the first proof as being more complicated and less instructive, but this seems to have arisen because the Diagonal argument has proven to be a more versatile tool and thus the others forgotten and dismissed.

In this instance the first and second proofs of Cantor are of equal merit to the diagonal argument, and the three together present clearly the flavor of the theorem.

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 1.1$: Example $6$