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

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$$ <div><div>

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

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

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

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

Parents:

• Mathematics

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