Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Cantor normal form isn't all that useful. The normal form of $\omega_1$, for example, is just $\omega^{\omega_1}$. –  Zhen Lin Sep 17 '12 at 4:45
    
To elaborate on Zhen's comment, there is a proper class of ordinals $\alpha$ for which $\omega^\alpha=\alpha$--such $\alpha$ are called "epsilon numbers." Every uncountable aleph (from $\omega_1$ on up) is an epsilon number, but there are many others before that--in fact, if we enumerate them by $\varepsilon_\alpha$, then $\varepsilon_\alpha$ is countable precisely when $\alpha$ is, so $\varepsilon_{\omega_1}=\omega_1$, meaning there are actually $\aleph_1$ many epsilon numbers before we even reach uncountable ordinals! –  Cameron Buie Sep 17 '12 at 14:30

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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