order of infinite countable ordinal numbers

Question

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.

Answer 1

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.