“Not everything that can be counted counts.” - William Bruce Cameron
It’s clear that a set containing the Seven Dwarfs has the same size as a set containing the Days of the Week, and that both sets are smaller than the set of all college students in the US. But what does size mean when we have infinite sets? How does the infinite set of WFFs of Predicate Logic compare (in size) with the infinite set of all Natural Deduction proofs in Propositional Logic?
Georg Cantor invented a very simple and general criterion to decide whether one set has more elements than another. For familiar finite sets we get exactly the results we would expect. For infinite sets, there are surprises.
Most famously, there are more real numbers than there are natural numbers (not all infinities are the same size), but there as many natural numbers as there are rational numbers (even though there are infinitely many rational numbers in-between each pair of consecutive natural numbers). ## Comparing Sets by Size
Definition
For this section, we will just take the natural numbers \(\mathbb{N}\) to be the familiar set of non-negative integers. > >- \(0\) is the smallest natural number. >- There are infinitely many different natural numbers (7, 87383, 314159265, etc.) but each specific* natural number is finite. \(\infty\) is not a natural number!
It is common to use the notation \(|S|\) to denote the size of set \(S\).
However, that immediately raises the question of what sizes are! For example, the size of a set can’t always be a natural number, because the set of integers \(\mathbb{Z}\) is infinite, and we already said that infinity is not a natural number.
So instead, we will use a clever idea of Cantor to directly define whether one set is no larger than another; it sidesteps the need to calculate sizes in order to compare them.
Definition
Recall that function \(f\) is injective when that \(x\not=y\) implies \(f(x) \not= f(y)\).
Equivalently, when \(f\) is injective we know that \(f(x)=f(y)\) guarantees \(x=y\).
Example
(Many suitable injections exist, such as \(p\mapsto d, \ d\mapsto a, \ q\mapsto c\).) 2. \(|\,\{a,b,c,d\}\,| \not\leq |\,\{p,d,q\}\,|\)
(There is no injection that can map each of \(a\), \(b\), \(c\), and \(d\) to different values from \(\{p,d,q\}\) because there is not a unique element for each to map to.) 3. \(|\,\{\}\,| \leq |\,\{0\}\,| \leq |\,\{0,1\}\,| \leq |\,\{0,1,2\}\,| \leq \cdots \leq |\mathbb{N}| \leq |\mathbb{R}|\)
(We can use the identity function as our injection in each case.)
Definition
Set \(S\) is infinite if \(|\mathbb{N}| \leq |S|\), and finite otherwise.
Example
A set is infinite if there is an injection from \(\mathbb{N}\) to the set, and it’s usually easy to see if a set is infinite. A more interesting question is whether there is an injection from the set to \(\mathbb{N}\), a concept known as countability.
Definition
All finite sets are countable, but deciding whether an infinite set is countable requires a bit more work. There are several approaches we can take. ### Direct Proof
One way to show a set is countable is to find a suitable injective function.
Example
\(\{\pi, e, \sqrt{2}\}\) is countable. > >Proof: It suffices to find a suitable injection, such as >\[ >\pi > \mapsto 0,\ e \mapsto 1, \ \sqrt2 \mapsto 2 >\]
Example
\(\mathbb{E} := \{\,0,2,4,6,8,\ldots\}\) is countably infinite.
Proof:
We’ve already proved that \(\mathbb{E}\) is infinite. It is countable (\(|\mathbb{E}| \leq |\mathbb{N}|\)) because the function \(g: \mathbb{E}\to\mathbb{N}\) defined by \(g(n) = n\) is injective. ### Listing the Elements
Here’s another way to prove an infinite set \(S\) is countably infinite.
Theorem
An infinite set \(S\) is countable if we can create an infinite list containing all the elements of \(S\) (the first element of \(S\), the second element of \(S\), the third element, etc.). > It doesn’t matter what order we put the elements of \(S\) as long as every element of \(S\) must appear at some finite index in the infinite list. (Given any element of \(S,\) with enough time and effort we should be able to figure out its position in the list.) It is even OK if the list contains duplicates, as long as every element of \(S\) appears somewhere. > >Proof: If we can create such a list, then the function that maps each element of \(S\) to its position in the list is an injection from \(S\) to \(\mathbb{N}\), and proves that \(|S|\leq\mathbb{N}\). > (If the list has duplicates, we can get an injection from \(S\) to \(\mathbb{N}\) by mapping each element of \(S\) to the first index where that element occurs in the list.)
Example
The following sets are clearly infinite, but they are also countable. > >1. The set of all primes is countable. > > If we list the primes in increasing order >\[ >[2, 3, 5, 7, 11, 13,\ldots] >\] >then every prime is at some finite index in the list (and hence there is an injection from the set of primes to \(\mathbb{N}\)). > >2. The set of all integers is countable: \(|\mathbb{Z}|\leq|\mathbb{N}|\) > > If we list the integers in order of increasing absolute values > >\[ >[0, 1, -1, 2, -2, 3, -3, 4, -4, \ldots] >\] then every integer occurs at some finite index in the list (and hence there is an injection from the set of integers to \(\mathbb{N}\)). > >3. The set of all pairs of natural numbers is countable: \(|\mathbb{N}{\times}\mathbb{N}|\leq|\mathbb{N}|\). > > If we list all pairs (n,m) in order of their sum \(n{+}m\) (and by increasing \(n\) for pairs of the same sum) then every pair of natural numbers occurs at some finite index in the list: >\[ >\begin{array}{l} > [(0,0),\\ > \phantom{[}(0,1), (1,0),\\ > \phantom{[}(0,2), (1,1), (2,0),\\ > \phantom{[}(0,3), (1,2), (2,1), (3,0),\\ > \phantom{[}\ldots]\\ > \end{array} >\] >4. The set of non-negative rational numbers is countable: \(|\mathbb{Q}^{\geq 0}|\leq|\mathbb{N}|\). We can list all fractions in order of increasing numerator + denominator: > >\[ >\begin{array}{l} > [\frac{0}{1}, \\[5pt] > \phantom{[}\frac{0}{2}, \frac{1}{1}, \\[5pt] > \phantom{[}\frac{0}{3}, \frac{1}{2}, \frac{2}{1}, \\[5pt] > \phantom{[}\frac{0}{4}, \frac{1}{3}, \frac{2}{2}, frac{3}{1}, \\[5pt] > \phantom{[}\phantom{[}\ldots]\\ > \end{array} >\] >(It’s true that rational numbers like 0 show up many times in this list, but as mentioned earlier, duplicates are fine as long as every element in the set eventually appears somewhere.) > >5. The set of finite binary sequences is countable: > \(|\{0,1\}^{*}|\leq|\mathbb{N}|\). > > If we list all sequences by length, and then alphabetically (or equivalently, in numerical order in binary) within sequences of the same length, then every finite sequence will appear at some finite position on this list: >\[ >\begin{array}{l} > [~,\\ > \phantom{[}\mathrm{0}, \mathrm{1},\\ > \phantom{[}\mathrm{00}, \mathrm{01}, \mathrm{10}, \mathrm{11},\\ > \phantom{[}\mathrm{000}, \mathrm{001}, \mathrm{010}, \mathrm{011}, > \mathrm{100}, \mathrm{101}, \mathrm{110}, \mathrm{111},\\ > \phantom{[}\ldots]\\ > \end{array} >\]
Usually, there are many choices for the order of our list. For example, in Part (5), we could have chosen a different order for the strings of each length, and everything would still work.
However, we have to be careful that our list puts every element of the set at some finite index, and it is easy to get that wrong.
Example
Here are some flawed proofs that sets are countable. (These sets are countable; it’s just that these aren’t valid proofs.) > >1. The set of all pairs of natural numbers is countable; just list we can list all pairs \((n,m)\) in order of \(n\) (and by increasing \(m\) for pairs of the same \(n\)): >\[ >\begin{array}{l} > [(0,0), (0,1), (0,2), (0,3), \ldots\\ > \phantom{[}(1,0), (1,1), (1,2), (1,3), \ldots \\ > \phantom{[}(2,0), (2,1), (2,2), (2,3), \ldots \\ > \phantom{[}(3,0), (3,1), (3,2), (3,3), \ldots \\ > \phantom{[}\ldots]\\ > \end{array} >\] >Fatal flaw: There are infinitely many sequences of the form \((0,m)\) before we ever get to \((1,0)\), so the pair \((1,0)\) does not have a finite index in this list. > >2. The set of all finite sequences of \(0\)’s and \(1\)’s is countable; just list all sequences in alphabetical order. > > Fatal flaw: If we list the sequences in pure alphabetical order, the the list starts out >\[ >[~, > \mathrm{0}, \mathrm{00}, \mathrm{000}, \mathrm{0000}, \mathrm > {00000}, \ldots] >\] >and we have to get past infinitely many sequences in this list before we ever get to sequences containing a \(1\). > > Or more simply, since all sequences starting with \(0\) come alphabetically before all the sequences starting with \(1\), there’s no finite index for any of the sequences starting with \(1\). ### Union of Countable Sets
Here is another useful fact:
Theorem
The union of a countable number of countable sets is countable. In particular: > >- If \(S_0, S_1, S_2. \ldots, S_{n-1}\) are countable, then so is \((S_0 \cup S_1 \cup \ldots \cup S_{n-1})\). >- If \(S_0, S_1, S_2, \ldots\) are countable, then so is the infinite union >\[ >(S_0 \cup S_1 \cup S_2 \ldots). >\]
Example
There are many other clever ways to prove a set is countable, but there is one that is particularly useful in Computer Science:
Theorem
If each single element of \(S\) could be represented using a computer file (given a sufficiently large, but finite, disk), then \(S\) is countable. > >Proof: On the disk, a computer file is nothing but a finite sequence of bits, i.e., finite sequences of 0’s and 1’s. If each element of \(S\) can be stored in a computer file, then each element of \(S\) corresponds to a (distinct) sequences of 0’s and 1’s. Since there are only countably many such sequences, there can only be countably many elements of \(S\).
In other words, the number of possible computer files is countable, so if each element of a set can be stored in a computer file, we can instantly conclude there are only countably many elements in that set.
(Note that we are only asking whether any one single element of a set could be stored in a computer file of finite size, not whether all the elements of a set can be stored in a single file at the same time!)
Example
For example, we could put \(x\) into a one-line text file consisting of a sign (
+or-), the numerator in decimal (a finite natural number), a slash, and the denominator (a finite natural number).So there can’t be more rational numbers than computer files; since there are only countably many possible computer files, \(\mathbb{Q}\) is countable.
Any finite set of rational numbers is countable. Given any particular set (with size 3 or 10 or one billion or …), we could list the members of the set in a text file, with one integer per line. Since the set contains finitely many rational numbers, and each rational number has a finite numerator and denominator, each such set corresponds to a text file with finitely many characters.
The infinite set of all finite binary trees labeled by integers is countable. Given any one such tree, we can draw that tree and store it in a (potentially large, but finite)
.jpgor.pngimage.The set of all WFFs of Predicate Logic is countable. Each such WFF can be written in LaTeX and saved in a
.texfile.The set of all possible essays on computer ethics is countable. Given any one such essay, we could store it in a Microsoft Word file.
The set of all possible books on Renaissance Art (with pictures) is countable. Given any book, we could scan it (e.g., to a resolution of 1 million dots per inch) and save the scan as a PDF. Since books only have finitely many pages, each PDF will be finite as well.
The set of all syntactially correct Java 8 programs is countable. Each such program could be packaged into a single (finite)
.zipfile containing all the code.The set of all real numbers that a Python 3.12 program could print is countable. Each Python program that prints digits could be stored as a single
.pyfile.
Of course, if you are talking to a mathematician rather than a computer scientist, instead of talking about computer files you could say something like, “Since every element of this set can be encoded into a distinct finite binary sequence, the set must be countable.”
Previous: 5.1 Hoare Logic
Next: 5.3 Uncountable Sets