Countable Sets

“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 then 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.

Just because two sets are infinite doesn’t mean they are the same size!
Just because one set “feels” much bigger than another, doesn’t mean it’s bigger!

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 and compare them.

Definition

For sets $S$ and $T$ , we say $|S| \leq |T|$ if there exists an injection (one-to-one function) from $S$ to $T$ .
For sets $S$ and $T$ , we say $|S| = |T|$ if $|S| \leq |T|$ and $|S| \leq |T|$ , i.e., if there are injections going in each direction.

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

$|\,\{p,d,q\}\,| \leq |\,\{a,b,c,d\}\,|$
(Many suitable injections exist, such as $p\mapsto d, \ d\mapsto a, \ q\mapsto c$ .)
$|\,\{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\}$ .)
$|\,\{\}\,| \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

The sets $\mathbb{N}$ (natural numbers), $\mathbb{Z}$ (integers), $\mathbb{Q}$ (rationals), and $\mathbb{R}$ (reals) are all infinite, because the identity function is an injection from $\mathbb{N}$ to each of these sets.
The set $\mathbb{E} := \{\,0,2,4,6,8,\ldots\}$ of even numbers is infinite; if $k$ is any nonzero even number, the function $f:\mathbb{N}\to\mathbb{E}$ defined by $f(x)=kx$ is an injection.

Proving A Set is Countable

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

Set $S$ is countable if $|S| \leq |\mathbb{N}|$ , and uncountable otherwise.
Set $S$ is countably infinite if $|S| = |\mathbb{N}|$ ,
i.e., if $|S| \leq |\mathbb{N}|$ ( $S$ is countable) and $|\mathbb{N}|\leq |S|$ ( $S$ is infinite).

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.

Claim

$\{\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

Claim

$\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.

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

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

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}

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

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

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.

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 \cup S_n).

Example

The set $\mathbb{Z}$ is countable because it is the union of two countable sets: $\{0,1,2,3,\ldots\}$ and $\{0,-1,-2,-3,\ldots\}$ .
The set $\mathbb{N}{\times}\mathbb{N}$ of pairs of natural numbers is countable because it a countable union of countable sets:

\begin{array}{rl} &\{(0,0), (0,1), (0,2), (0,3), \ldots, (0,n)\}\\ {\cup}&\{(1,0), (1,1), (1,2), (1,3), \ldots, (1,n)\}\\ {\cup}&\{(2,0), (2,1), (2,2), (2,3), \ldots, (2,n)\}\\ {\cup}&\cdots\\ \end{array}

The Computer Scientist’s Strategy

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

The infinite set $\mathbb{Q}$ is countable. Given any specific $x\in\mathbb{Q}$ , we can imagine storing $x$ in a computer file.

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) .jpg or .png image.
The set of all WFFs of Predicate Logic is countable. Each such WFF can be written in LaTeX and saved in a .tex file.
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) .zip file 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 .py file.

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