7. Countable sets

Countable sets

A set of the same cardinality as the set of natural numbers will be called countable (so a set is countable if its elements can be accommodated in Hilbert’s hotel). You can think about countable sets as of class of the ,,smallest” infinite sets. In particular, every infinite subset of a countable set is countable (it is easy to see that every subset of a set which can be accommodated in Hilbert’s hotel can be accommodated in Hilbert’s hotel).

Therefore we say that a set is at most countable if it is finite or countable.

Examples of countable sets

We have already proved that the set of integer numbers \mathbb{Z} is countable.

Notice that, although it may be surprising in the beginning, that the set \mathbb{N}\times\mathbb{N} of pairs of natural numbers. Indeed, we can enumerate them with natural numbers (or in other words we can accommodate them in Hilbet’s hotel), enumerating the subsequent pairs in order of sum of their elements: \left<0,0\right>, \left<1,0\right>, \left<0,1\right>, \left<2,0\right>, \left<1,1\right>, \left<0,2\right>, \left<3,0\right>, \left<2,1\right>, \ldots.

Secondly, notice that the set of all finite sequences of zeros and ones: \{0,1\}^{*} is also countable. We can enumerate its elements taking them in order of their length.

Similarly the set of all finite subsets of the set of natural numbers \mathcal{P}_{fin}(\mathbb{N}) is countable — we can enumerate them taking them in order of maximal element.

So:

    \[|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{N}\times\mathbb{N}|=|\{0,1\}^{*}|=|\mathcal{P}_{fin}(\mathbb{N})|.\]

Properties of countable sets

From the above you can see that:

  • infinite subset of a countable set is countable
  • product of two countable sets is countable
  • product of finite number of countable sets is countable
  • countable sum of countable sets is countable

We can use the above facts to prove that a given set is countable.

Functions and countability

The following theorems are relatively intuitive:

  • If f\colon A\to B is onto and A is countable, then also B is at most countable.
  • If f\colon A\to B is 1-1 and B is countable, then also A is at most countable.