order of infinite countable ordinal numbers

I'm trying to understand ordinal arithmetic. If one had an ordered list of the some subset of countable ordinal numbers, what order would the following 6 countably infinite ordinals be in? If the following order is not correct, what is correct order and why is that the correct order?

$$\omega\;<\; \omega^2 \;<\; 2^\omega \;<\; \omega^\omega \;<\; {^\omega}2 \;<\;{^\omega} \omega$$

I know $\epsilon_0 = {^\omega} \omega$ is the largest, but is still countable, but I'm not sure where the powers of $2$ fit in versus the powers of $\omega$.

I understand why $\omega^2$ or $\omega^n$ for any finite value of $n$ needs to be countable. But, why does $\omega^\omega$ need to be countable? For cardinal numbers, $2^{\aleph_0}$ is uncountably infinite. Presumably, there would be some contradiction in mathematics if any finite ordinal arithmetic equation involving $\omega$ generated an uncountable infinity.

• What does the notation ${^\omega} 2$ mean? Never saw that (and it's hard to see what to type into Google to find it...) Jul 13, 2015 at 19:12
• Jul 13, 2015 at 19:13
• The defining sequence for $^{\omega} 2$ is $2\;\;2^2\;\;2^{2^2}\;\;2^{2^{2^2}}\;\;2^{2^{2^{2^2}}}....$ Jul 13, 2015 at 19:15
• So then in fact ${^\omega}2=\omega$. Jul 13, 2015 at 19:17
• ok, presumably that is consistent, but it seems a bit odd, that such a fast growing sequence is regarded as smaller than $\omega^2$ Jul 13, 2015 at 19:18

1 Answer

First note that $$^\omega2 := \sup \{ \underbrace{2^{2^{2^\ldots}}}_{n\text{-times}} \mid n < \omega \} = \omega.$$

[..]but it seems a bit odd, that such a fast growing sequence is regarded as smaller than $\omega^2$.

Well, that's the thing when dealing with infinities. Sometimes our intuition fails us. While $(\underbrace{2^{2^{2^\ldots}}}_{n\text{-times}})_{n < \omega}$ could be regarded as "a fast growing sequence", each of its elements is finite and therefore $\omega$ is an upper bound. As $\omega$ certainly is the least upper bound, we get $^\omega2 = \omega$.

By an analogous argument we get that $$2^\omega := \sup \{2^n \mid n < \omega \} = \omega$$

So we are left with ordering $\omega, \omega^2, \omega^\omega$ and $^\omega \omega$.

We have \begin{align}\omega^2 &:= \omega \cdot \omega \\ &= \sup \{ w \cdot n \mid n < \omega\} \\ &\ge \omega \cdot 2 \\ &> \omega \end{align}

and

\begin{align}\omega^\omega &= \sup \{ \omega ^n \mid n < \omega \} \\ &\ge \omega^3 \\ &= \sup \{(\omega^2) \cdot n \mid n < \omega \} \\ &\ge \omega^2 \cdot 2 \\ &> \omega^2. \end{align}

Finally \begin{align}^\omega \omega &:= \sup \{ \underbrace{\omega^{\omega^{\omega^ \ldots}}}_{n\text{-times}} \mid n < \omega \} \\ &\ge \omega^{\omega^\omega} \\ &= \sup\{\left( \omega^\omega \right)^n \mid n < \omega \} \\ &\ge \left(\omega^\omega \right)^2 \\ &= \omega^\omega \cdot \omega^\omega \\ &= \sup \{\omega^\omega \cdot \alpha \mid \alpha < \omega^\omega \} \\ &\ge \omega^\omega \cdot 2 \\ &> \omega^\omega. \end{align}

Combining these calculations we get the desired order: $$\omega = 2^\omega = {^\omega} 2 < \omega^2 < \omega^\omega < ^\omega\omega$$

In general, ordinal and cardinal arithmetic are very different beasts and every ordinal arithmetic expression using only ordinals $\le \omega$ is countable.

proof (sketch)

Take a countable transitive model $M$ of a large enough fracture of $ZFC$. Every ordinal expression using only ordinals $\le \omega$ can be computed correctly inside $M$ (<- this requires some work). As $M$ only contains countable ordinals (as it is transitive), the result follows.

• That is a horrible notation, ${}^\omega2$. Jul 14, 2015 at 6:34
• Thanks for the proof; much to learn. Jul 14, 2015 at 8:39