Uncountable Sets

“Not everything that counts can be counted”
—William Bruce Cameron

We have seen that the infinite sets $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ , $\mathbb{N}{\times}\mathbb{N}$ are all countably infinite (and hence have the “same size” as $\mathbb{N}$ ). We might ask, then, whether all infinite sets are countable. The answer is no; there are lots of sets which are strictly bigger than $\mathbb{N}$ ; in this section we will look at a few examples.

Infinite Sequences are Uncountable

Earlier we saw that the set of all finite binary sequences is countable, because we can enumerate all the elements of this set in order. In contrast, the set of all infinite binary sequences is not countable; this set is strictly larger than the infinite set of natural numbers.

Theorem

The set of infinite binary sequences is not countable

Proof: Suppose, by way of contradiction, that the set were countable, so that we can create a complete list $s_0, s_1, s_2, \ldots$ of all possible infinite binary sequences. Let $s_i[j]$ be the $j^\mathrm{th}$ digit in the $i^\mathrm{th}$ sequence. Then, we can define a new sequence $s$ as follows:

s[j] = 1 - s_j[j].

That is, the $j^\mathrm{th}$ digit in $s$ is the opposite of the $j^\mathrm{th}$ digit in $s_j$ . Note that $s\not=s_0$ because $s$ and $s_0$ differ in the first digit. Similarly $s\not=s_1$ because $s$ and $s_1$ differ in the second digit, and in general $s\not=s_k$ because $s$ and $s_k$ differ in the $k^\mathrm{th}$ digit.

Thus $s$ is an infinite binary sequence that doesn’t appear at any finite index in the list $s_0, s_1, s_2, \ldots$ ; this contradicts our assumption that the list contains all infinite binary sequences, so the set of such sequences is not countable.

Arbitrary Sets of Natural Numbers are Uncountable

Earlier we saw that the collection of all finite sets of natural numbers is countable, because any such set could be stored in a finite computer file. In contrast, the set of all sets of natural numbers is not countable.

Theorem

The set ${\cal P}(\mathbb{N})$ of all sets of natural numbers is infinite but not countable:

|\mathbb{N}| < |{\cal P}(\mathbb{N})|.

Proof:
There is a one-to-one correspondence between sets of natural numbers and infinite binary sequences. Specifically, the set $S$ corresponds to a sequence whose $k^\mathrm{th}$ digit is 1 if $k$ is an element of $S$ and 0 otherwise.

For example, the set of all even numbers contains 0, 2, 4, etc., and hence coresponds to the infinite sequence

101010101010\cdots

while the set $\{0, 1, 2, 5\}$ coresponds to the infinite sequence

11100100000000\cdots.

Since the infinite binary sequences cannot be enumerated, neither can ${\cal P}(\mathbb{N})$ .

This argument can be generalized (“Cantor’s Theorem”) to show that $|S| < |{\cal P}(S)|$ for every set $S$ ! This immediately gives us an infinite sequence of larger and larger infinite sets:

|\mathbb{N}| < |{\cal P}(\mathbb{N})| < |{\cal P}({\cal P}(\mathbb{N}))| < |{\cal P}({\cal P}({\cal P}(\mathbb{N})))| < \cdots.

The Real Numbers are Uncountable

Finally, while the set of real numbers than can be printed by a Python program is countable, the set of all real numbers is not countable.

Theorem

$\mathbb{R}$ is not countable.

Proof:
We can argue that the real numbers between 0 and 1 are uncountable because any such number can be represented as an infinite decimal expansion (e.g., 0.14159265…). There are even more of these than infinite binary expansions, so the real numbers between 0 and 1 are uncountable. And there are even more real numbers than there are real numbers between 0 and 1, so $\mathbb{R}$ is uncountable.

Of course, the number of possible math papers and textbooks is infinite but countable. It follows that most real numbers cannot be directly mentioned or described because the number of real numbers is a much larger infinite set than the number of possible descriptions!