11.2 Uncountable

Having explored the countable sets, we look at whether there exists sets that are not finite and not countable.

Definition 11.12:
A set X is uncountable if it is infinite but not countable.
Remark:

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).

Theorem 11.13:

The interval (0,1)=\{x\in\mathbb{R}: 0<x<1 \} is uncountable.

Proof.

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.

History:

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.

Corollary 11.14:

We have that \mathbb{R} is uncountable.

Proof.

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}|.

Theorem 11.15:

There is a bijection between the interval (0,1) and \mathbb{R}.

Proof.

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|”.

Interest:

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.