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.

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\) <div><div>

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

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

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