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

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.

• $\omega_1$ is the supremum of all countable ordinals. Have you read the Wikipedia article about this?
– MJD
Sep 17, 2012 at 4:06
• @MJD I changed the question a bit. Would you answer this question also? thanks. Sep 17, 2012 at 4:12
• Now it's an interesting question!
– MJD
Sep 17, 2012 at 4:20
• See also this question: Do $\omega^\omega=2^{\aleph_0}=\aleph_1$? Sep 17, 2012 at 4:51
• And also How is $\epsilon_0$ countable? Nov 6, 2012 at 12:18

$\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 \omega^{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.

• Importantly, there is an explicit sequence of countings of $\:\left\langle \omega^0,\omega^1,\omega^2,\omega^3,...\right\rangle\:$. $\hspace{1.5 in}$ (This allows the proof to go through in ZF.) $\;\;$
– user57159
Sep 17, 2012 at 4:43
• Did I miss something? I would have said this is exactly what I am saying in the paragraph that points out that the product of countable sets is countable.
– MJD
Sep 17, 2012 at 4:47
• I would think you should say that "an explicit counting of $\omega^i$ yields an explicit counting of $\omega^{i+1}$".
– user57159
Sep 17, 2012 at 5:11
• If one is lazy, one can avoid worrying about verifying that there are explicit countings of these ordinals, by noting that their definitions are absolute, and they are countable in $L$. Nov 5, 2012 at 23:31

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 might not be countable.