Theorem 12.3.1. Cantor 1891.
The open interval \((0,1) = \set{x \in \mathbb{R} \so 0 \lt x \lt 1}\) is uncountable.
Section 12.3 Uncountable sets
We are now ready to move on to one of the nicest results of the course and arguably one of nicest in Mathematics. We will prove that there is no bijection between the natural numbers and the reals and so that the reals are uncountable. It is due to Georg Cantor. He proved the result first in 1873, and again by a simpler method in 1891. We will do the second version here, since it is easier. We give Cantor’s first proof as an optional section 12.6 later in this chapter.
The proof works by a contradiction and also relies on some facts about decimal expansions of real numbers.
- Every rational number has a repeating decimal expansion
- eg 1/3 = 0.333333333…
- eg 2/11 = 0.1818181818181…
- Some rational numbers have two repeating expansions
- eg 1/2 = 0.500000… = 0.499999999…
- eg 1/5 = 0.2… = 0.1999999999…
- One can show that a rational number \(p/q\) (reduced) has two expansions if only if \(q\) is a product of powers of 2 and 5. In this case the expansions terminate either with 9’s or 0’s.
- Every irrational number has a unique (non-repeating) decimal expansion
None of the above is too hard to prove, but we won’t do it here. We want to get on to this very important result.
From this result we could prove that all of \(\mathbb{R}\) is uncountable by constructing a suitable bijection (which we will do so at the end of this section). Alternatively, and perhaps more usefully, we can argue that because \((0,1)\) is a subset of \(\mathbb{R}\text{,}\) then \(\mathbb{R}\) cannot be denumerable. By our previous theorem, if \(\mathbb{R}\) were denumerable, then it could not have an uncountable subset. This observation is a pretty important one, so let us write it down as its own theorem.
Theorem 12.3.2.
Let \(A,B\) be sets with \(A \subseteq B\text{.}\) If \(A\) is uncountable then \(B\) is uncountable.
Proof.
Prove the contrapositive. If \(B\) is countable, then it is either finite or denumerable. If \(B\) is finite, then \(A\) must be finite. On the other hand if \(B\) is denumerable then all its subsets must be denumerable. In either case \(A\) must be countable.
So — how do we prove the uncountability of \((0,1)\text{.}\) This comes down to showing that there cannot be a bijection from \(\mathbb{N}\) to \((0,1) \text{.}\) Showing the non-existence of an object is often most easily done by contradiction and that is the approach we will take (following in Cantor’s footsteps).
So we assume that \((0,1)\) is denumerable meaning there is some bijection \(f: \mathbb{N} \to (0,1)\text{.}\) But this means that we can make a big list of all the numbers in \((0,1)\) (just like we did with the even numbers or the squares or … above). For example, we might have:
\begin{align*}
f(1) &= 0.78304492\dots\\
f(2) &= 0.21892653\dots\\
f(3) &= 0.15206327\dots\\
\vdots &
\end{align*}
As we construct our list, if we come across a number in \((0,1)\) that has two expansions (like \(1/2=0.49999=0.50000\)) then we write down the expansion that ends in all zeros. To complete the proof we need to find a contradiction. We do so by finding a real number in \((0,1)\) that is not on our list. This implies that \(f\) is not a bijection and so — contradiction!
To build the number we use a very slick argument 179 argument. Consider the figure below.
We have listed out the (hypothetical) values of each number in our list in order: \(f(1),f(2),f(3)\dots\text{.}\) For each number we have carefully written out its decimal expansion so that all the digits are arranged neatly in an array. Now ignore the leading “0.” and focus on those numbers down the diagonal.
From those digits down the diagonal, we can construct a new number \(\Delta\text{:}\)
\begin{align*}
\Delta &= 0. d_1 d_2 d_3 \cdots
\end{align*}
so that
- The first digit \(d_1\) is first digit of \(f(1) \text{.}\)
- The second digit \(d_2\) is second digit of \(f(2) \text{.}\)
- The third digit \(d_3\) is third digit of \(f(3) \text{.}\)
- \(\displaystyle \vdots\)
- The \(n^{th}\) digit \(d_n\) is the \(n^{th}\) digit of \(f(n)\text{.}\)
- and so on.
Now because the digits of \(\Delta\) agree with some of the digits of each of the \(f(k)\text{,}\) it is possible that \(\Delta\) appears somewhere on our list — so this doesn’t give us the contradiction. However, Cantor realised that from \(\Delta\text{,}\) one can construct a number, \(z\text{,}\) that is definitely not on the list. In particular, construct \(z\) so that each digit of \(z\) is different from the corresponding digit of \(\Delta\text{.}\)
This means that
- The first digit of \(z\) must be different from the first digit of \(f(1) \) — so \(z \neq f(1)\text{.}\)
- The second digit of \(z\) must be different from the second digit of \(f(2) \) — so \(z \neq f(2)\text{.}\)
- The third digit of \(z\) must be different from the third digit of \(f(3) \) — so \(z \neq f(3)\text{.}\)
- \(\displaystyle \vdots\)
- The \(n^{th}\) digit of \(z\) must be different from the \(n^{th}\) digit of \(f(n)\) — so \(z \neq f(n) \text{.}\)
- and so on.
So if we make the digits of \(z\) in this way, it follows that our number \(z\) cannot be any number of the list since it has a different expansion 180 . Contradiction!
Let us be more precise about this and make a proof.
Proof.
Assume, to the contrary, that \((0,1)\) is countable. Since it is finite, it must be denumerable and so there is a bijection \(f: \mathbb{N} \to (0,1)\text{.}\) Hence we can write \((0,1) = \{x_1,x_2,x_3,\dots\}\) where \(x_i = f(i)\text{.}\) Now each of these \(x\)’s has an infinite decimal expansion, so we can write a big array as follows:
\begin{align*}
x_1 &= 0.a_{11} a_{12} a_{13} \cdots,\\
x_2 &= 0.a_{21} a_{22} a_{23} \cdots,\\
x_3 &= 0.a_{31} a_{32} a_{33} \cdots,\\
\vdots &= \vdots
\end{align*}
where each \(a_{ij} \in \{0,1,\dots,9\}\text{.}\)
Now we construct a number \(z\) that is not on the list. Write \(z = 0.b_1 b_2 b_3
\cdots\text{.}\) And set
\begin{align*}
b_n &= \begin{cases}
1 & \mbox{ if } a_{nn} \neq 1\\
2 & \mbox{ if } a_{nn} = 1
\end{cases}
\end{align*}
\begin{equation*}
\frac{1}{9}=0.111111\dots \lt z \lt 0.222222\dots = \frac{2}{9}
\end{equation*}
and hence \(z \in (0,1)\text{.}\)
Of course, since \(f\) is a bijection, our number \(z\) must appear somewhere on our list. So let us assume that it is the \(k^{th}\) number on the list, namely that \(z = x_k\text{.}\) But, by construction, the \(k^{th}\) digit of \(z\) is not the same as the \(k^{th}\) digit of \(x_k\text{.}\) So \(z \neq x_k\text{.}\) In this way, there is no \(k\) such that \(z = x_k\) and \(z\) is not in the list — a contradiction since \(f\) must be a bijection.
Hence there is no bijection from \(\mathbb{N} \) to the set \((0,1) \text{,}\) and thus \((0,1)\) is uncountable.
So this Theorem proves that there is more than one type of \(\infty\) — something that is really not at all obvious 182 . Let us push through to all reals now.
Corollary 12.3.3.
The set \(\mathbb{R}\) of real numbers is uncountable.
Proof.
If \(\mathbb{R}\) were countable, then all its subsets must be denumerable. Since \((0,1)\) is uncountable, it follows that \(\mathbb{R}\) is uncountable.
Note that the cardinality of the reals is denoted \(c\text{,}\) for continuum. That is \(|\mathbb{R}| = c\text{.}\) Since \(c \neq \aleph_0\) and \(\mathbb{N} \subseteq \mathbb{R}\text{,}\) we must have \(\aleph_0 \lt c\text{.}\) Of course, to give a concrete meaning to the symbol “\(\lt \)” in the context of cardinalities of infinite sets, we have to do some work. That is the subject of our next section.
Cantor was very very clever. This argument is now called “Cantor’s diagonal argument” and it has been used in many places in mathematics. One famous application of the idea is to show that the Halting Problem is not solvable. The interested reader should search-engine their way to more information.
We should be a little careful about 9’s and 0’s when we do this — and we will avoid those two digits when we do this in our proof.
Note that we could have used any two digits except \(9\text{,}\) in order to avoid the problem of representing the same number with two different expansions.
This is a really beautiful result about the nature of the infinite! The author still finds it incredible that one can prove such a deep statement about the universe in a one term course. Remember, we started out with truth tables, and sets and we’ve just demonstrated that there is not just one infinity! Amazing!
