Countability

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.

LESSWRONG
LW

LESSWRONG
LW

Example: The rational numbers

Exercises