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.