The set of counting numbers, or of positive integers, is the set .

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, $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 $Z^{+} \times Z^{+}$ is isomorphic to $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$ , $\dots$ Since there are at most $(2 d + 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 $(2 d + 1)^{2}$ ; every rational number is mapped onto by this counting. Thus, the rational numbers are countable. $□$

Note: It is not hard to extend this proof to show that $(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 $Σ^{*}$ of finite words of an enumerable alphabet is countable.

Show solution

First, we note that since $N^{n}$ is countable, the set of words of length $n$ for each $n \in N$ is countable.

Let $E_{n} : N \to N^{n}$ stand for an enumeration of $N^{n}$ , and $(J_{1}, J_{2}) (n)$ for an enumeration of $N^{2}$ .

Consider the function $E : N \to Σ^{*}, n ↪ E_{J_{1} (n)} (J_{2} (n))$ which maps every number to a word in $Σ^{*}$ . Then a little thought shows that $E$ is an enumeration of $Σ^{*}$ .

$□$

Show that the set $P_{ω} (A)$ of finite subsets of an enumerable set $A$ is countable.

Show solution

Let $E$ be an enumeration of $A$ .

Consider the function $E^{'} : N^{*} \to P_{ω} (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 \leq k E (n_{m}) = a} \subseteq A$ . Clearly $E^{'}$ is an enumeration of $P_{ω} (A)$ .

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

Show solution

Simply consider the function which relates each cofinite set with its complementary.