How to define countability of $\omega^{\omega}$ and $\omega_1$? in set theory?

Question

How is the ordinal $\omega_1$ defined? I know that it is a supremum of all smaller ordinals, but then $\omega^\omega$ is also a supremum of all smaller ordinals. How can we distinguish these two numbers? Edit: changing the question into how $\omega^{\omega}$ can be shown countable, and how other countable ordinals can be shown to be countable.

Answer 1

$\omega^\omega$ is countable because it is a union of a countable collection of sets, each of which is itself countable: $$\omega^\omega = \bigcup_{i<\omega} \omega^i$$

So it suffices to show that:

1. A union of a countable collection of countable sets is countable.
2. $\omega^i$ is countable whenever $i$ is finite.

(1) should be familiar to you; it is the usual Cantor argument for showing that the rationals are countable. If the countable sets are $S_0, S_1\ldots$ with elements $S_i = \{s_{i0}, s_{i1}, \ldots\}$, then we can enumerate the union of the $S_i$ as $s_{00}; s_{10}, s_{01}; s_{20}, s_{11}, s_{02}; s_{30}, \ldots$.

(2) is not hard either; you can prove the the product of two countable sets is countable (essentially as in the previous paragraph) and then show that since $\omega^{i+1} = \omega\times\omega^i $, countability of $\omega^{i+1}$ follows from that of $\omega^i$, which is enough to establish the result.

(You may want to look up the notion of cofinality. An ordinal $X$ has countable cofinality if it is a countable union of smaller ordinals. If those smaller ordinals are themselves countable, then $X$ is countable. So to show that $\omega^\omega$ is countable, it is enough to show that it has countable cofinality, which we can do by observing that it is the union of the countable ordinals $\omega^i$ for finite $i$.)

Then similarly if $C$ is some countable ordinal, $\omega^C$ is countable. For we can write some countable sequence $c_0, c_1,\ldots$ whose limit is $C$, and then $\omega^C = \bigcup c_i$ expresses $\omega^C$ as a countable union of countable sets. So not only are $\omega$ and $\omega^\omega$ countable, so are $\omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$. And then we can take the union of countable the sequence of countable sets $\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$ and conclude that this union, usually written $\epsilon_0$, is countable as well.

$\epsilon_0$ has the property that it is the smallest ordinal $x$ for which $x=\omega^x$. There is an infinite sequence of countable ordinals with this property, and their union is still countable.

There are quite a few countable ordinals, and some of them are very strange monsters. See for example Church–Kleene ordinal and the Feferman–Schütte ordinal.

Answer 2

Generally speaking, the best course of action when trying to show that $\alpha$ is a countable ordinal, is to show that:

1. $\alpha = \delta+n$ where $\delta$ is a limit ordinal (if $n=0$ then $\alpha=\delta$);
2. $\delta$ is the limit of $\{f(\beta)\mid \beta<\gamma\}$ for some countable $\gamma$; and
3. $f(\beta)$ is countable is countable whenever $\beta$ is countable.

For example, $\epsilon_0$ is the limit of $\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}},\ldots$. We can show that this is the limit of the recursive function $f(n+1)=\omega^{f(n)}$ and $f(0)=\omega$. We can further show that if $\beta$ is countable then $\omega^\beta$ is also countable (note that this is ordinal exponentiation) and therefore $\epsilon_0$ is the countable limit of countable ordinals and thus countable.

The same method can be applied to general ordinals, although obtaining such $f$ is often harder than it is in the case of $\epsilon_0$.

One caveat is that this is true in ZFC but not necessarily in ZF, where a countable union of countable ordinals may be countable.