Countable sets

From the two previous examples, we have seen that many sets have the same cardinality as ${\mathbb N}$. We call those sets countable sets (they are infinite, but it's possible to count them ☺️).

Definition 2

A set $X$ is countable if it is finite or there is a bijection between $X$ and ${\mathbb N}$.

In fact, when $X$ is infinite, we don't really need a bijection here. It suffices to show the onto mapping.

Exercise 80

A set $X$ is countable if and only if there is an onto mapping from ${\mathbb N}$ to $X$.

One can say that this is the reason why such a set is called countable: We can actually list the elements of $X$ one-by-one based on the onto function $f: {\mathbb N} \rightarrow X$ by just $f(1), f(2),\ldots$. The onto property guarantees that we will eventually list all the elements in $X$ (some elements might be listed more than once, but that's OK).

Theorem 31

The set ${\mathbb Q}$ of rational numbers is countable.

Proof:

For simplicity, we will only deal with positive rational numbers (dealing with negative numbers only requires a small modification). We define an onto mapping $f: {\mathbb N} \rightarrow {\mathbb Q}^+$ as follows. When we write a positive rational number as $p/q$ (for positive integers $p,q$) we can imagine dividing ${\mathbb Q}^+$, into (overlapping) groups based on the value of $p+q$. That is,

${\mathbb Q}^+ = \mathcal{S}_2 \cup \mathcal{S}_3 \cdots$

where $\mathcal{S}_k = \{p/q: p,q \ge 1, p+q = k\}$. Notice that $|\mathcal{S}_k| \leq k^2$, so each such set is finite. Intuitively, the function $f$ first lists the elements in $\mathcal{S}_1$, then the ones in $\mathcal{S}_2$, and so on.

Often, one would encounter an incorrect proof (from students) of the following form. List all rational numbers of the form $1/q$ (for all $q \in {\mathbb N}$), then the ones of the form $2/q$, and so on. Let us call this mapping $g$. At some point we would end up listing all of them. Do you know what goes wrong with such an argument? The problem with the above listing is that we cannot formally pinpoint when a given number would be listed, e.g., what is the value of $x$ for which $g(x) = 2/101$? This problem occurs because listing numbers of the form $1/q$ alone is an infinite process.

In comparison, the proof of Theorem 31 makes it cleat that every number would be listed at some point. For instance, what is the value of $x$ for which $f(x)= 2/101$. Well, $2/101 \in \mathcal{S}_{103}$, so we know that it would be listed when all $\mathcal{S}_1,\ldots, \mathcal{S}_{102}$ are finished. Although giving the exact position in the listing is technical, we know that $x \leq 1^2 + 2^2 + \ldots + 103^2$.