What ordinal is bigger ?
$\omega^{\omega+1}, (\omega+1)^{\omega}$
I think $\omega^{\omega+1}>(\omega+1)^{\omega}$
$\omega^{\omega+1}=\bigcup_{\alpha <\omega+1} \omega^\alpha >\bigcup_{\alpha <\omega} \omega^\alpha = \omega^{\omega}$
$(\omega+1)^{\omega}=\bigcup_{\alpha <\omega} (\omega+1)^\alpha$
Is it correct $(\omega)^{\omega}=(\omega+1)^{\omega}$?
I have no idea how to prove this problem.
I'd be grateful for your help!
Best Answer
Note that for all ordinals $\alpha$, we have $\alpha^\omega = \sup\limits_{n < \omega} \alpha^n$.
We wish to prove that for all $n \in \mathbb{N}$, $(\omega + 1)^n < \omega^n \cdot 2$.
Let us prove this by induction. The base case is immediate.
We now proceed with the inductive step. Suppose $(\omega + 1)^j < \omega^j \cdot 2$. Then
$\begin{equation} \begin{split} (\omega + 1)^{j + 1} &= (\omega + 1)^j \cdot (\omega + 1) \\ &\leq (\omega^j \cdot 2) \cdot (\omega + 1) \\ &= (\omega^j \cdot 2) \cdot \omega + (\omega^j \cdot 2) \cdot 1 \\ &= \omega^j \cdot (2 \cdot \omega) + \omega^j \cdot 2 \\ &= \omega^j \cdot \omega + \omega^j \cdot 2 \\ &= \omega^{j + 1} + \omega^j \cdot 2 \\ &< \omega^{j + 1} + \omega^j \cdot 2 + \omega^j \cdot \omega \\ &= \omega^{j + 1} + \omega^j \cdot (2 + \omega) \\ &= \omega^{j + 1} + \omega^j \cdot \omega \\ &= \omega^{j + 1} \cdot 2 \end{split} \end{equation}$
Therefore, we see that for all $n \in \mathbb{N}$, we have $\omega^n \leq (\omega + 1)^n < \omega^n \cdot 2 < \omega^n \cdot \omega = \omega^{n + 1}$.
From here, it follows that $(\omega + 1)^\omega = \omega^\omega$.
Now the question is how to compare $\omega^\omega$ with $\omega^{\omega + 1} = \omega^\omega \cdot \omega$. This is quite easy using the distributive property, since we see that $\omega^\omega \cdot \omega = \omega^\omega \cdot (1 + \omega) = \omega^\omega + \omega^\omega \cdot \omega$. Therefore, we see that $\omega^\omega < \omega^{\omega + 1}$.
Thus, we see that the larger of the two ordinals is in fact $\omega^{\omega + 1}$.