9.6: Uncountable sets

The preceding section showed that many sets (including \(\mathbb{N}\), \(\mathbb{Z}\), and \(\mathbb{Q}\)) are countable. We will now see that some sets are not countable.

9.6A. The reals are uncountable.

Here is perhaps the most important example of an uncountable set:

Theorem \(9.6.1\).

The set \(\mathbb{R}\) of real numbers is uncountable.

If \(\mathbb{R}\) were countable, then all of its subsets would be countable. Thus, in order to establish Theorem \(9.6.1\), it suffices to find an uncountable subset of \(\mathbb{R}\). Here are some well-known examples of subsets:

Notation \(9.6.2\).

For \(a, b \in \mathbb{R}\) with \(a < b\):

• open interval: \((a, b)=\{x \in \mathbb{R} \mid a<x<b\}\).
• closed interval: \([a, b]=\{x \in \mathbb{R} \mid a \leq x \leq b\}\).
• half-open interval: \([a, b)=\{x \in \mathbb{R} \mid a \leq x<b\}\) or \((a, b]=\{x \in \mathbb{R} \mid a<x \leq b\}\).

We will see that all of these intervals are uncountable. Here is one example:

Theorem \(9.6.3\).

The interval \([0, 1)\) is uncountable.

Proof

BY CONTRADICTION.

Suppose \([0, 1)\) is countable. (This will lead to a contradiction.) This means there is a list \(x_{1}\), \(x_{2}\), \(x_{3}\), . . . of all the numbers in \([0, 1)\). To obtain a contradiction, we will use a method called the Cantor Diagonalization Argument. It was discovered by the mathematician Georg Cantor in the 19th century.

Each number in \([0, 1)\) can be written as a decimal of the form 0.\(d_{1}d_{2}d_{3}\). . ., where each \(d_{k}\) is a digit (0, 1, 2, 3, 4, 5, 6, 7, 8, or 9). In particular, we can write each \(x_{i}\) in this form: \[x_{i}=0 . x_{i, 1} x_{i, 2} x_{i, 3} x_{i, 4} x_{i, 5} \ldots\]

Then we can make a list of all of these decimals (omitting the leading 0 in each one): \[\begin{aligned}
x_{1}=& . x_{1,1} x_{1,2} x_{1,3} x_{1,4} x_{1,5} \cdots \\
x_{2}=& . x_{2,1} x_{2,2} x_{2,3} x_{2,4} x_{2,5} \cdots \\
x_{3}=& . x_{3,1} x_{3,2} x_{3,3} x_{3,4} x_{3,5} \cdots \\
x_{4}=& . x_{4,1} x_{4,2} x_{4,3} x_{4,4} x_{4,5} \cdots \\
x_{5}=& . x_{5,1} x_{5,2} x_{5,3} x_{5,4} x_{5,5} \cdots \\
\vdots & \vdots
\end{aligned}\]

The right-hand side can be thought of as an array of digits, and we now focus on the diagonal entries \(x_{i,i}\) of this array, which are circled in the following picture:

They form a sequence \(x_{1,1}, x_{2,2}, x_{3,3}, \ldots\).

The key to the proof is to make a new sequence \(d_{1}, d_{2}, d_{3}, \ldots\) of digits, such that \[d_{1} \neq x_{1,1}, \quad d_{2} \neq x_{2,2}, \quad d_{3} \neq x_{3,3}, \text { etc. }\]

This means that every term of the new sequence is different from the corresponding term of the diagonal sequence. (This idea of choosing a sequence that is completely different from the diagonal is called Cantor diagonalization, because it was invented by the mathematician Georg Cantor.) Also, to avoid problems coming from the fact that \(.999 \cdots=1.000 \cdots\), you should not use the digits 0 and 9. The sequence \(\left\{d_{i}\right\}\) can be constructed in many ways: just be sure to choose each \(d_{i}\) to be a digit that is not \(x_{i,i}\) (and is not 0 or 9). For example, we could let \[d_{i}= \begin{cases}1 & \text { if } x_{i, i} \neq 1 \\ 5 & \text { if } x_{i, i}=1\end{cases}\]

Now, let \[d=0 . d_{1} d_{2} d_{3} \ldots \in[0,1).\]

For each \(i\), we made sure that \(d_{i} \neq x_{i, i}\), which means that the \(i\)th digit of d is different from the \(i\)th digit of \(x_{i}\). Therefore, for each \(i\), we have \(d \neq x_{i} \text { * }\). So \(d\) is an element of \([0, 1)\) that is not in the list \(x_{1}, x_{2}, x_{3}, \ldots\). This contradicts the fact that \(x_{1}, x_{2}, x_{3}, \ldots\) is a list of all the numbers in \([0, 1)\).

Exercise \(9.6.4\).

1. Show that the interval \((0, 1)\) is uncountable. [Hint: \([0,1)=(0,1) \cup\{0\}) is uncountable.]
2. Suppose \(a, b \in \mathbb{R}\). Show that if \(a < b\), then the interval \((a, b)\) has the same cardinality as \((0, 1)\). [Hint: Define \(f:(0,1) \rightarrow(a, b)\) by \(f(x)=a+(b-a) x\).]
3. Suppose \(a \in \mathbb{R}\). Show that the interval \((a, \infty)\) has the same cardinality as \((0, 1)\). [Hint: Define \(f:(0,1) \rightarrow(a, \infty)) by \(f(x)=(1 / x)+a-1).]

Corollary \(9.6.5\).

If \(a, b \in \mathbb{R}\) and \(a < b\), then the intervals \((a, b)\), \([a, b]\), \([a, b)\), and \((a, b]\) are uncountable.

Exercise \(9.6.6\).

Decide which of the following sets are countable, and which are uncountable. (You do not need to justify your answers.)

1. The closed interval \([3,3.1]\)
2. \(\{1,2,3, \ldots, 1000\}\)
3. \(\mathbb{Z} \times \mathbb{Z}\)
4. \(\mathbb{Z} \times \mathbb{Q}\)
5. \(\mathbb{R} \times \mathbb{N}\)
6. \(\mathbb{R} \backslash \mathbb{Q}\)
7. \(\mathbb{Q} \backslash \mathbb{R}\)
8. \((\mathbb{R} \backslash \mathbb{Q}) \cap(\mathbb{Q} \backslash \mathbb{R})\)
9. \((\mathbb{R} \backslash \mathbb{Q}) \cup(\mathbb{Q} \backslash \mathbb{R})\)
10. \((\mathbb{R} \backslash \mathbb{Q}) \times(\mathbb{Q} \backslash \mathbb{R})\)
11. \(\{x \in \mathbb{R} \mid 2<x<3\}\)
12. \(\left\{x \in \mathbb{R} \mid x^{2}=3\right\}\)
13. \(\left\{x \in \mathbb{R} \mid x^{2}+12<3\right\}\)
14. \(\left\{x \in \mathbb{R} \mid x^{2}+3<12\right\}\)
15. \(\left\{x \in \mathbb{Q} \mid x^{2}+3<12\right\})
16. \(\{(x, y) \in \mathbb{R} \times \mathbb{R} \mid x-y=1\})
17. \(\{(x, y) \in \mathbb{R} \times \mathbb{R} \mid x-y \in \mathbb{Z}\}\)
18. \(\{(x, y) \in \mathbb{Z} \times \mathbb{R} \mid x-y \in \mathbb{Q}\}\)
19. \(\left\{(x, y) \in \mathbb{R}^{2} \mid x^{2}+y^{2}=1\right\})
20. \(\left\{(x, y) \in \mathbb{R}^{2} \mid x^{2}+y^{2}=-1\right\})

9.6B. The cardinality of power sets.

If \(A\) is a finite set, then the set \(\mathcal{P}(A)\) of all subsets of \(A\) is also finite. (Indeed, \(\# \mathcal{P}(A)=2^{\# A}\).) However, this assertion does not remain true when the word “finite” is replaced with “countable”:

Exercise \(9.6.7\).

Show that \(\mathcal{P}\left(\mathbb{N}^{+}\right)\) is uncountable. [Hint: For any \(f: \mathbb{N}^{+} \rightarrow \mathcal{P}\left(\mathbb{N}^{+}\right)\), the set \(\left\{i \in \mathbb{N}^{+} \mid i \notin f(i)\right\}\) is not in the image of \(f\).]

For every set \(A\), not just the countable ones, the same argument shows that the cardinality of \(\mathcal{P}(A)\) is greater than the cardinality of \(A\). Thus, there is no “largest” infinite set. For every set, there is always some set that has much larger cardinality.

Exercise \(9.6.8\).

For every set \(A\), show there does not exist an onto function \(f: A \rightarrow \mathcal{P}(A)\). [Hint: The set \(\{a \in A \mid a \notin f(a)\}\) is not in the image of \(f\).]

The preceding exercises are very closely related to a classical paradox:

Example \(9.6.9\) ("Barber Paradox").

Suppose there is a town with only one barber, and that barber is a man. Furthermore, assume the barber shaves precisely those men in the town who do not shave themselves. More precisely, if \(B\) is the Barber, and \(M\) is any man in the town, then \[B \text { shaves } M \quad \text { iff } \quad M \text { does not shave } M\]

Now, we ask: \[\text { Does the barber shave himself? }\]

Solution

This question is a paradox:

• If the answer is yes, then the barber shaves himself. But the barber does not shave men who shave themselves, so this means that the barber does not shave himself. But we already said that the barber does shave himself, so this is nonsense.
• If the answer is no, then the barber does not shave himself. But the barber does shave any man who does not shave himself, so this means that the barber does shave himself. But we already said that the barber does not shave himself, so this is nonsense.

The upshot of this discussion is that the hypothesized situation leads to a contradiction, so it is impossible.

The same reasoning shows there is no set that contains precisely the sets that do not contain themselves. (Otherwise, the question “Does the set contain itself?” would be a paradox. Do you see why?) The solutions of Exercises \(9.6.7\) and \(9.6.8\) are based on the same idea.

_________________
\(\text { * }\)The digits of \(d\) are only 1’s and 5’s, so it is not a problem that numbers ending 000 . . . can also be expressed as a different decimal that ends 999 . . ..