# 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.

Parents:

- Mathematics
Mathematics is the study of numbers and other ideal objects that can be described by axioms.