Countability

The set of counting numbers, or of positive integers, is the set $\mathbb{Z}^+ = \{1, 2, 3, 4, \ldots\}$.

A set $S$ is called countable or enumerable if there exists a surjection from the counting numbers onto $S$.

Example: The rational numbers

The set of rational numbers, $\mathbb Q$, is the set of integer fractions $\frac{p}{q}$ in reduced form; the greatest common divisor of $p$ and $q$ is one, with $q > 0$.

Theorem The rational numbers are countable.

The proof is, essentially, that $\mathbb Z^+ \times \mathbb Z^+$ is isomorphic to $\mathbb Z$; we count in a roughly spiral pattern centered at zero.

Proof Define the height of $\frac{a}{b}$ to be $|a| + |b|$. We may count the rational numbers in order of height, and ordering by $a$, and then $b$, when the heights are the same. The beginning of this counting is $0 / 1$, $-1 / 1$, $1 / 1$, $-2 / 1$, $-1 / 2$, $1 / 2$, $2 / 1$, $\ldots$ Since there are at most $(2d+1)^2$ rational numbers of height less than or equal to $d$, a rational number with height $d$ is mapped on to by one of the counting numbers up to $(2d+1)^2$; every rational number is mapped onto by this counting. Thus, the rational numbers are countable. $\square$

Note: It is not hard to extend this proof to show that $(\mathbb Z^+)^n$ is countable for any finite $n$.

Theorem If there exists a surjection $f$ from a countable set $A$ to a set $B$, then $B$ is countable. Proof By definition of countable, there exists an enumeration $E$ of $A$. Now, $E\circ f$ is an enumeration of $B$, so $B$ is countable.

Exercises

Show that the set $\Sigma^*$ of [ finite words] of an enumerable [ alphabet] is countable.

%%hidden(Show solution): First, we note that since $\mathbb N^n$ is countable, the set of words of length $n$ for each $n\in \mathbb N$ is countable.

Let $E_n: \mathbb N \to \mathbb N^n$ stand for an enumeration of $\mathbb N ^n$, and $(J_1,J_2)(n)$ for an enumeration of $\mathbb N^2$.

Consider the function $E: \mathbb N \to \Sigma^* , n\hookrightarrow E_{J_1(n)}(J_2(n))$ which maps every number to a word in $\Sigma^*$. Then a little thought shows that $E$ is an enumeration of $\Sigma^*$.

$\square$ %%

Show that the set $P_\omega(A)$ of finite subsets of an enumerable set $A$ is countable.

%%hidden(Show solution): Let $E$ be an enumeration of $A$.

Consider the function $E': \mathbb N^* \to P_\omega(A)$ which relates a word $n_0 n_1 n_2 … n_r$ made from natural numbers to the set $\{a\in A:\exists m\le k E(n_m)=a\}\subseteq A$. Clearly $E'$ is an enumeration of $P_\omega(A)$. %%

Show that the set of [ cofinite subsets] of an enumerable set is countable.

%%hidden(Show solution): Simply consider the function which relates each cofinite set with its complementary. %%