Countability

Countability is a key notion in set theory and apeirology. A set is called countable if it is possible to arrange its elements in a way so that they can be counted off one-by-one. In other words, it has the same size as the set of the natural numbers. The way this is formally defined is that there is a map \( f: x \to \mathbb{N} \), where \( x \) is the set in question, so that different elements of \( x \) are sent to different natural numbers, and every natural number has some element of \( x \) sent to it. In other words, there is a bijection from \( x \) to the natural numbers. However, this may not imply they have the same order-type, if the set is well-ordered.

Georg Cantor, the founder of set theory, proved that the set of integers and the set of rational numbers are both countable, by constructing such maps. More famously, Cantor proved that the real numbers and that the powerset of the natural numbers are both uncountable, by assuming there was a map \( f \) and deriving a contradiction.

In terms of ordinals, it is clear that \( \omega \) is countable. You can also see that \( \omega + 1 \) is countable, by pairing \( \omega \) with zero and \( n \) with \( n + 1 \); that \( \omega 2 \) is countable, by pairing \( n \) with \( 2n \) and pairing \( \omega + n \) with \( 2n + 1 \), and so on. Larger countable ordinals such as \( \omega_1^{\mathrm{CK}} \) also are countable but, due to their size, such a map \( f \) is not \( \Delta_1 \)-definable in their rank of the constructible hierarchy. Furthermore, a gap ordinal may have a map to \( \mathbb{N} \) but this map can not be defined at all using first-order set theory. The least uncountable infinite ordinal is denoted \( \omega_1 \) or \( \Omega \), and it is larger than anything that can be reached from \( \omega \) using successors and countable unions. In particular, it is an epsilon number, and much more. This is why it is useful as a "diagonalizer" in the construction of ordinal collapsing functions, although \( \omega_1^{\mathrm{CK}} \) is sometimes used instead.

Since \( \omega_1 \) and \( \mathbb{R} \) are both uncountable, it is natural to ask whether they have the same size. The affirmative of this question is known as the continuum hypothesis. Cantor failed to prove or disprove it, and Gödel and Cohen later proved that, if the \( \mathrm{ZFC} \) axioms are consistent, then the continuum hypothesis can neither be proven nor disproven.