Section 12.6 (Optional) Cantor’s first proof of the uncountability of the reals
For completeness we include Cantor’s first proof that \(|\mathbb{N}| \lt |\mathbb{R}|\text{.}\) This, proved in 1874, is more involved than his very famous diagonal argument which was published in 1891. Despite this it is still accessible to the tools developed in this text.
Like the diagonal argument, this first proof also is a proof by contradiction. We assume the existence of a bijection from
\(\mathbb{N}\) to an interval of the real-line and then show that this leads to a contradiction. However, rather than relying on decimal expansions of real numbers, it instead relies on the supremum — the least upper bound property. The reader should take a moment to examine
Exercise 8.6.15 and
Exercise 8.6.16, and also revise
Section 6.4 before continuing.
Axiom 12.6.1. Least upper bound property of the reals.
Let \(A \subseteq \mathbb{R}\) be bounded above. That is, there is some \(M \in \mathbb{R}\) so that \(a \leq M\) for all \(a \in A\text{.}\) Then the supremum of \(A\) exists and is a real number.
This is the critical difference between the reals and the rationals — the rationals do not satisfy the least upper bound property. For example, one can take the set of truncated decimal expansions of \(\sqrt{2}\text{:}\)
\begin{align*}
\set{1.0, 1.4, 1.41, 1.414, 1.4142, \dots} \amp = \set{\frac{1}{1}, \frac{14}{10}, \frac{141}{100}, \frac{1414}{1000}, \frac{14142}{10000}, \dots}\\
\amp= \set{ \lfloor 10^n \sqrt{n} \rfloor \cdot 10^{-n} \st n \in \mathbb{N}}\\
\amp \subseteq \mathbb{Q}
\end{align*}
We can use the least upper bound property to prove
188 that increasing sequences of real numbers that are bounded above must converge to a real limit.
Lemma 12.6.2.
Let \((a_n)\) be a sequence of real numbers that
is bounded above by some real number \(M\text{,}\) and
satisfies \(a_k \leq a_{k+1}\) for all \(k\text{.}\)
Then the sequence \(a_n\) converges as \(n \to \infty\text{.}\)
Proof.
Now we are ready to get into the proof. Let \([a,b]\) be an interval of the real line with \(a \lt b\text{.}\) Then assume to the contrary, that there is a bijection
\begin{equation*}
g: \mathbb{N} \to [a,b]
\end{equation*}
This bijection defines an infinite sequence via \(x_n = g(n)\) for any \(n \in \mathbb{N}\text{.}\) Notice that all the terms of this sequence must be distinct since \(g\) is injective.
The proof works by finding some \(q \in [a,b]\) so that \(q\) is not part of the sequence. Hence there is no \(n \in
\mathbb{N}\) so that \(g(n)=q\text{,}\) and so \(g\) is not surjective and hence not bijective.
We construct two new sequences \((a_n)\) and \((b_n)\) from the sequence \((x_n)\text{.}\)
Find the first two \(x_n\) lying strictly inside the interval, that is \(a \lt x_n \lt b\text{.}\) These two terms must be distinct and let \(a_1\) be the smaller and \(b_1\) be the larger.
Similarly, find the first two terms of the sequence that lie inside \((a_1,b_1)\) — call the smaller \(a_2\) and the larger \(b_2\text{.}\)
Keep repeating this to define \((a_3,b_3)\text{,}\) \((a_4,b_4)\) and so on.
Notice that
for any \(n\) we must have \(a_n \lt b_n\text{,}\) and
the sequences of \(a\)’s and \(b\)’s satisfy
\begin{equation*}
a \lt a_1 \lt a_2 \lt a_3 \lt \dots \lt b_3 \lt b_2 \lt b_1 \lt b
\end{equation*}
and so the sequence \((a_n)\) is increasing and bounded above by \(b\text{,}\) while the sequence \((b_n)\) is decreasing and bounded below by \(a\text{.}\)
the sequences of \(a\)’s and \(b\)’s may or may not be infinite.
for any \(n\text{,}\) the terms \(x_1,x_2,\dots, x_{2n}\) do not lie inside the interval \((a_n,b_n)\text{.}\)
This last point can be proved quite readily using induction on \(n\text{.}\)
Lemma 12.6.3.
The interval \((a_n,b_n)\) does not contain the sequence terms \(x_1,x_2,\dots,x_{2n}\text{.}\)
Proof.
We prove the result by induction on \(n\text{.}\)
Notice that \(x_1,x_2\) must belong to \(\set{a,b,a_1,b_1}\) (by construction). Thus \(x_1,x_2
\not\in (a_1,b_1)\) since the open interval exludes the endpoints.
Now assume that the result holds for \(n=k\text{,}\) and so \(x_1,x_2,\dots x_{2n}\) are lie outside the interval \((a_n,b_n)\text{.}\) Then either \(x_{2n+1}, x_{2n+2}\) lie outside this interval, or, if they lie inside the interval they are one or both of \(a_{n+1},
b_{n+1}\text{.}\) Consequently they lie outside \((a_{n+1},b_{n+1})\text{.}\)
Hence the result holds for all \(n \in \mathbb{N}\text{.}\)
The sequences \((a_n), (b_n)\) may or may not be infinite. So initially assume that they are finite. That is, the final interval is \((a_N, b_N)\text{.}\) Now notice that there cannot be two or more \(x_n\) inside the interval \((a_N,b_N)\) because otherwise we would use those to define another interval \((a_{N+1},
b_{N+1})\text{.}\) Thus there are either zero or one more term of the sequence \((x_n)\) lying inside \((a_N,b_N)\text{.}\) But this means that any other number inside \((a_N,b_N)\) is not part of the sequence \((x_n)\text{.}\) That is, there is some \(q \in (a_N,b_N)\) so that \(q \neq x_n = g(n)\) for any \(n \in \mathbb{N}\text{.}\)
Now instead, assume that the sequences of
\(a\)’s and
\(b\)’s are infinite. Since the sequence of
\(a\)’s is increasing and bounded above by
\(b\text{,}\) Lemma 12.6.2 implies that it converges to a limit. The same argument (applied to
\(-b_n\)) shows that the sequence of
\(b\)’s also converges to a limit. So define
\begin{equation*}
\lim_{n \to \infty} a_n = \alpha \qquad
\lim_{n \to \infty} b_n = \beta.
\end{equation*}
Notice that we cannot have \(\beta \lt \alpha\) (otherwise we would have \(a_k \gt b_k\) for some \(k\)), and so either \(\alpha \lt \beta\) or \(\alpha = \beta\text{.}\)
If
\(\alpha \lt \beta\text{,}\) then every
\(q \in (\alpha,
\beta)\) is not in the sequence of
\(x\)’s. If
\(q =
x_n\) for some
\(n\text{,}\) then this would contradict
Lemma 12.6.3 above, since it would imply that
\(q =
x_n \in (\alpha,\beta) \subseteq (a_n,b_n)\text{.}\)
On the other hand, if
\(\alpha=\beta\text{,}\) then
\(q =
\alpha\) is not in the sequence of
\(x\)’s. If
\(q=\alpha=x_n\) for some
\(n\text{,}\) then again this would contradict
Lemma 12.6.3 since it would imply that
\(q=x_n =\alpha \in (a_n,b_n)\text{.}\)
Thus even when the sequences of \(a\)’s and \(b\)’s are infinite, there is always some \(q \in [a,b]\) that is not in the sequence of \(x\)’s. Hence the function \(g:\mathbb{N} \to
[a,b]\) is not a surjection, contradicting our initial assumption that it is bijective.
This is a nice and intuitive result; in fact it is such a nice result we set it as an
exercise 8.6.17.
