How do we prove Cantor's normal form can produce all ordinal numbers?
Also, it's a bit difficult to picture $\omega_1$ as a format in Cantor's normal form. Can anyone show how to do this?
How do we prove Cantor's normal form can produce all ordinal numbers?
Also, it's a bit difficult to picture $\omega_1$ as a format in Cantor's normal form. Can anyone show how to do this?
To prove the Cantor Normal Form Theorem you unsurprisingly use (transfinite) induction.
Suppose that $\alpha > 0$ is an ordinal ($0$ clearly has a Cantor Normal Form), and a Cantor Normal Form exists for all ordinals $\gamma < \alpha$. Note that there is a greatest ordinal $\delta$ such that $\omega^\delta \leq \alpha$ (since the least ordinal $\zeta$ such that $\omega^\zeta > \alpha$ must be a successor ordinal). Now there are unique ordinals $\beta , \gamma$ such that $\alpha = \omega^\delta \cdot \beta + \gamma$ and $\gamma < \omega^\delta$. Based on our choice of $\delta$ it must be that $\beta < \omega$, and we can use our inductive assumption that $\gamma$ has a Cantor Normal Form.
As mentioned by Zhen Lin in the comments, the Cantor Normal Form for $\omega_1$ is simply $\omega^{\omega_1}$. This can be seen by the definition of cardinal exponentiation: $\omega^{\omega_1} = \sup_{\alpha < \omega_1} \omega^\alpha$ since $\omega_1$ is a limit ordinal. It is easy to show that $\alpha \leq \omega^\alpha$ for all $\alpha$, and in particular $\omega_1 \leq \omega^{\omega_1}$. On the other hand, if $\alpha$ is countable, then so is $\omega^\alpha$, which then implies $\omega^{\omega_1} \leq \omega_1$.