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.


2 Answers 2


$\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.

  • 2
    $\begingroup$ 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.) $\;\;$ $\endgroup$
    – user57159
    Sep 17, 2012 at 4:43
  • $\begingroup$ 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. $\endgroup$
    – MJD
    Sep 17, 2012 at 4:47
  • $\begingroup$ I would think you should say that "an explicit counting of $\omega^i$ yields an explicit counting of $\omega^{i+1}$". $\endgroup$
    – user57159
    Sep 17, 2012 at 5:11
  • $\begingroup$ 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$. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.