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 is countable.
Notice that, although it may be surprising in the beginning, that the set 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: , , , , , , , .
Secondly, notice that the set of all finite sequences of zeros and ones: 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 is countable — we can enumerate them taking them in order of maximal element.
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 is onto and is countable, then also is at most countable.
- If is 1-1 and is countable, then also is at most countable.