11.2 Uncountable
Having explored the countable sets, we look at whether there exists sets that are not finite and not countable.
An uncountable set is one where we can not enumerate its elements.
We note that the cardinality of \(\mathbb{Z}_+\) separates finite, countable and uncountable sets. Indeed we leave it as an exercise to show that:
\(X\) is finite if and only if \(|X|<|\mathbb{Z}_+|\);
\(X\) is countable if and only if \(|X|=|\mathbb{Z}_+|\);
\(X\) is uncountable if and only if \(|X|>|\mathbb{Z}_+|\).
We will prove that the set \((0,1)=\{x\in\mathbb{R}:0<x<1\}\) is uncountable. First we need to set up some notation. Let us assume that every real numbers between \(0\) and \(1\) has a decimal expansion of the form \[0.a_1a_2a_3\cdots=\sum_{k\in\mathbb{Z}_+}a_k 10^{-k}\] with \(0\leq a_k \leq 9\) for each \(k\in\mathbb{Z}_+\).
Note however that this representation is not unique. Indeed, we have \(0.99999\dots = 1\), and in general let \(0<\alpha<1\) have decimal expansion \(0.a_1a_2a_3\dots a_N99999\dots\). That is, there exists \(\mathbb{Z}_+\) such that \(a_N\neq 9\) and \(a_n=9\) for all \(n>N\). Then, using the results \[\sum_{k\in\mathbb{Z}_+}10^{-k}=\frac{10^{-1}}{1-10^{-1}}=\frac19.\] We have: \[\begin{align*} 0.a_1a_2a_3\dots a_N999\dots &=\sum_{k\in\mathbb{Z}_+}a_k\cdot 10^{-k}\\ &= \sum_{k=1}^{N}a_k\cdot 10^{-k}+\sum_{k\in\mathbb{Z}_+, k>N}9\cdot 10^{-k}\\ &= \sum_{k=1}^{N}a_k\cdot 10^{-k}+10^{-N}\cdot9\cdot\sum_{k\in\mathbb{Z}_k}10^{-k}\\ &= \sum_{k=1}^{N}a_k\cdot 10^{-k}+10^{-N}\\ &= 0.a_1a_2a_3\dots a_{N-1}b_N, \end{align*}\] where \(b_N=a_N+1\).
Therefore, we will take for granted that every \(\alpha \in \mathbb{R}\) such that \(0<\alpha<1\) can be uniquely expressed as \(0.a_1a_2a_3....\) with \(0\leq a_k \leq 9\) and \(\neg(\exists N\in\mathbb{Z}_+ \text{ so that } \forall n\in\mathbb{Z}_+,\ n>N\implies a_n=9).\) (i.e., \(\forall N \in \mathbb{Z}_+, \exists n\in\mathbb{Z}_+, n>N \text{ so that } a_n\neq 9\)).
The interval \((0,1)=\{x\in\mathbb{R}: 0<x<1 \}\) is uncountable.
We know the interval \((0,1)\) is infinite, since \(f:\mathbb{Z}\to(0,1)\) defined by \(f(k)=10^{-k}\) is easily shown to be injective.
For the sake of contradiction, suppose \((0,1)\) is countable. Thus we can enumerate the elements of \((0,1)\) as \(\alpha_1,\alpha_2,\alpha_3,\ldots\). Write each \(\alpha_k\) as a decimal expansion as described above: \[\alpha_k=0.a_{k1}a_{k2}a_{k3}\cdots\] where \(0\leq a_{ki} \leq 9\) and \(\neg(\exists N\in\mathbb{Z}_+ \text{ so that } \forall n\in\mathbb{Z}_+,\ n>N\implies a_n=9).\) For each \(k\in\mathbb{Z}_+\), set \[b_k=\begin{cases} 1&\text{if $a_{kk}\not=1$,}\\2&\text{if $a_{kk}=1$.}\end{cases}\] Set \(\beta=0.b_1b_2b_3\cdots\). Thus \(\beta\in\mathbb{R}\) with \(0<\beta<1\) and \(\neg(\exists N\in\mathbb{Z}_+ \text{ so that } \forall n\in\mathbb{Z}_+,\ n>N\implies a_n=9).\) Hence by assumption, \(\beta=\alpha_m\) for some \(m\in\mathbb{Z}_+\). But \(b_m\not=a_{mm}\), contradicting the uniqueness of the representation of \(\beta\) as a decimal expansion not ending in an infinite sequence of 9s. Thus the assumption that the interval \((0,1)\) is countable leads to a contradiction, so \((0,1)\) must be uncountable.□
The above theorem is sometimes referred to as Cantor’s diagonalisation argument. While it was not the first proof that Cantor published to show \((0,1)\) is uncountable, it showcases a technique that was used subsequently in many other proofs by other mathematicians.
We have that \(\mathbb{R}\) is uncountable.
Since \((0,1)\subseteq \mathbb{R}\), we have \(|(0,1)|\leq |\mathbb{R}|\). Since \((0,1)\) is uncountable, we have \(|\mathbb{Z}_+|<|(0,1)|\leq |\mathbb{R}|\). Hence \(\mathbb{R}\) is uncountable.
□
While we have shown \(|(0,1)|\leq |\mathbb{R}|\), the following theorem shows that in fact \(|(0,1)|=|\mathbb{R}|\).
There is a bijection between the interval \((0,1)\) and \(\mathbb{R}\).
Exercise.
□
In a way, this highlight another difference between \(\mathbb{R}\), \(\mathbb{Q}\) and \(\mathbb{Z}\). In \(\mathbb{R}\) we can have a bounded subset which is uncountable. However \(\mathbb{Q}\) a bounded subset is either finite or countable, while in \(\mathbb{Z}\) a bounded subset must be finite.
Recall that we have shown that given any \(a,b,c,d\in \mathbb{R}\) such that \(a<b\) and \(c<d\) there exists a bijection \(f:(a,b)\to (c,d)\). In particular if we take \(c=0,d=1\) we have that \(|(0,1)|=|(a,b)|\) for all \(a,b \in \mathbb{R}\) such that \(a<b\). No matter how “small” (length wise) we take \((a,b)\) to be, as a set it is extremely large, i.e. uncountable. If we combine this with the fact that if \(X\) is countable then \(X^n\) is countable for all \(n\in \mathbb{Z}_+\), we have strange results like “for any \(n\in\mathbb{Z}_+\), \(|\mathbb{Q}^n|<\left|\left(0,\frac1n\right)\right|\)”.
Since we have shown \(|\mathbb{Z}|<|\mathbb{R}|\), a natural question is “does there exists a set \(A\) such that \(|\mathbb{Z}|<A<|\mathbb{R}|\)”. This was one of the 23 problems set by Hilbert at the turn of the 20th Century, and is known as the continuum hypothesis. It turns out that this is a subtle question without a yes/no answer: G"odel and Cohen showed that the two statements “the continuum hypothesis is true” and “the continuum hypothesis is false” are both consistent with the standard (ZFC) axioms of mathematics.