# Countability

The set of count­ing num­bers, or of pos­i­tive in­te­gers, is the set $$\mathbb{Z}^+ = \{1, 2, 3, 4, \ldots\}$$.

A set $$S$$ is called countable or enu­mer­able if there ex­ists a sur­jec­tion from the count­ing num­bers onto $$S$$.

### Ex­am­ple: The ra­tio­nal numbers

The set of ra­tio­nal num­bers, $$\mathbb Q$$, is the set of in­te­ger frac­tions $$\frac{p}{q}$$ in re­duced form; the great­est com­mon di­vi­sor of $$p$$ and $$q$$ is one, with $$q > 0$$.

The­o­rem The ra­tio­nal num­bers are countable.

The proof is, es­sen­tially, that $$\mathbb Z^+ \times \mathbb Z^+$$ is iso­mor­phic to $$\mathbb Z$$; we count in a roughly spiral pat­tern cen­tered at zero.

Proof Define the height of $$\frac{a}{b}$$ to be $$|a| + |b|$$. We may count the ra­tio­nal num­bers in or­der of height, and or­der­ing by $$a$$, and then $$b$$, when the heights are the same. The be­gin­ning of this count­ing is $$0 / 1$$, $$-1 / 1$$, $$1 / 1$$, $$-2 / 1$$, $$-1 / 2$$, $$1 / 2$$, $$2 / 1$$, $$\ldots$$ Since there are at most $$(2d+1)^2$$ ra­tio­nal num­bers of height less than or equal to $$d$$, a ra­tio­nal num­ber with height $$d$$ is mapped on to by one of the count­ing num­bers up to $$(2d+1)^2$$; ev­ery ra­tio­nal num­ber is mapped onto by this count­ing. Thus, the ra­tio­nal num­bers are countable. $$\square$$

Note: It is not hard to ex­tend this proof to show that $$(\mathbb Z^+)^n$$ is countable for any finite $$n$$.

The­o­rem If there ex­ists a sur­jec­tion $$f$$ from a countable set $$A$$ to a set $$B$$, then $$B$$ is countable. Proof By defi­ni­tion of countable, there ex­ists an enu­mer­a­tion $$E$$ of $$A$$. Now, $$E\circ f$$ is an enu­mer­a­tion of $$B$$, so $$B$$ is countable.

## Exercises

Show that the set $$\Sigma^*$$ of finite words of an enu­mer­able alpha­bet 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 enu­mer­a­tion of $$\mathbb N ^n$$, and $$(J_1,J_2)(n)$$ for an enu­mer­a­tion of $$\mathbb N^2$$.

Con­sider the func­tion $$E: \mathbb N \to \Sigma^* , n\hookrightarrow E_{J_1(n)}(J_2(n))$$ which maps ev­ery num­ber to a word in $$\Sigma^*$$. Then a lit­tle thought shows that $$E$$ is an enu­mer­a­tion of $$\Sigma^*$$.

$$\square$$ <div><div>

Show that the set $$P_\omega(A)$$ of finite sub­sets of an enu­mer­able set $$A$$ is countable.

Let $$E$$ be an enu­mer­a­tion of $$A$$.

Con­sider the func­tion $$E': \mathbb N^* \to P_\omega(A)$$ which re­lates a word $$n_0 n_1 n_2 ... n_r$$ made from nat­u­ral num­bers to the set $$\{a\in A:\exists m\le k E(n_m)=a\}\subseteq A$$. Clearly $$E'$$ is an enu­mer­a­tion of $$P_\omega(A)$$. <div><div>

Show that the set of cofinite sub­sets of an enu­mer­able set is countable.

Sim­ply con­sider the func­tion which re­lates each cofinite set with its com­ple­men­tary.

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.