“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\}\) corresponds 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!
Previous: 5.2 Countability