2
$\begingroup$

This is a question regarding cantor normal form, and the steps in putting certain questions into this form, my Prof. gave me one hand out and then a bunch of questions and i cannot figure them out exactly

Prove that $(\omega+1)\omega=\omega^2$

So far I have

$\begin{align*} (\omega+1)\omega &= \mathrm{ord}\Bigl(\mathbb{N} \times(\mathbb{N} \cup \{\infty\})\Bigr)\\ \omega\omega&=\mathrm{ord}(\mathbb{N}\times\mathbb{N})(i,j)\text{ if }i=1,j\neq\infty\\ (i,j) &\longmapsto\left\{\begin{array}{ll} (i+1,1) &\text{if }j=\infty\\ (i,j+1) &\text{if }i\neq 1, j\neq\infty \end{array}\right. \end{align*}$

Is this right? any corrections would be very helpful my stepwise cantor normal form is struggling because of my lack of information on the topic...

two other questions i cannot figure out are

  • write in cantor normal form - $(\omega+1)^2$

  • prove $(\omega+1)^{\omega}=\omega^{\omega}$

any answers for these or help would be appreciated, also any advice on understanding putting these in cantor normal form or the steps involved would help tremendously. Thank you for your time.

  • 0
    the last one i $f$ind mos$t$ difficult whre you have to prove it is equal to w^w2011-05-04

1 Answers 1

14

The Cantor normal form of an ordinal is essentially a finite polynomial in $\omega$ over the ordinals.

But first let us recall the definition of addition, multiplication and exponentiation at limit points,

Suppose $\beta$ is a limit ordinal and $\alpha$ is an ordinal then:

  • $\alpha + \beta = \sup\{\alpha+\gamma\mid \gamma<\beta\}$
  • $\alpha\cdot\beta = \sup\{\alpha\cdot\gamma\mid\gamma<\beta\}$
  • $\alpha^\beta = \sup\{\alpha^\gamma\mid\gamma<\beta\}$.

Note that we can restrict ourselves to any unbounded subset of $\beta$, which allows some degree of freedom when calculating ordinal arithmetic at limit stages.

Now for calculating the Cantor normal form, first we want to calculate the ordinal itself, then we can decompose it to its CNF.

$(\omega+1)\cdot\omega = \sup\{(\omega+1)\cdot n\mid n<\omega\} = \sup\{\omega\cdot n + n\mid n<\omega\}$

We can replace each $\omega\cdot n + n$ by $\omega\cdot n+\omega=\omega\cdot (n+1)$, as it is another sequence of ordinal with the same limit (why?).

Now we have: $(\omega+1)\cdot\omega = \sup\{\omega\cdot (n+1)\mid n<\omega\} = \sup\{\omega\cdot n\mid n<\omega\} = \omega\cdot\omega=\omega^2$.

Now we also note that $\omega^2$ is already in Cantor normal form, and since it is unique we have that this is the CNF of $(\omega+1)\cdot\omega$.

The process for $(\omega+1)^\omega$ is essentially the same, and it yields the result $\omega^\omega$ as needed.

Edit: The $(\omega+1)^\omega$ case goes as follow:

$ \begin{align*} (\omega+1)^\omega &= \sup\{(\omega+1)^n\mid n<\omega\} &\\ &= \sup\{(\omega+\omega)^n\mid n<\omega\} &\\ &= \sup\{(\omega\cdot 2)^n\mid n<\omega\} &\\ &= \sup\{\omega^n\cdot 2^n\mid n<\omega\} &\\ &=\sup\{\omega^n\cdot\omega\mid n<\omega\} &\\ &= \sup\{\omega^{n+1}\mid n<\omega\}\\ &=\omega^\omega \end{align*} $

I am leaving it up to you to justify the transitions between the chosen sequences of ordinals.

Edit II: I'm adding the information from the comment, and a different proof for the above edit, based on that.

By exponentiation and multiplication laws we have $(\omega+1)^2=(\omega+1)\cdot(\omega+1) = (\omega+1)\cdot\omega+\omega+1 = \omega^2 + \omega + 1$, which is in CNF, as needed.

Based on that, we show that $(\omega+1)^\omega = \omega^\omega$:

$(\omega+1)^\omega = (\omega+1)^{2\cdot\omega} = ((\omega+1)^2)^\omega = (\omega^2+\omega+1)^\omega$.

We replace $\omega^2+\omega+1$ by $\omega^3$ which is a bigger ordinal, now we have $(\omega^3)^\omega = \omega^\omega$.

As before, I leave the justification of this replacement to you, essentially showing that $(\omega^2+\omega+1)^n$ has the same limit as $(\omega^3)^\omega$.

A key note: As I said at the beginning, the key issue is that at limit stages we take the supremum of a sequence of ordinals, and we can choose different sequences as we like, and we just need to prove that both the sequences would have the same limit.

Using "sandwich" arguments usually works - in fact by that we have it even simpler, $\omega^\omega \le (\omega+1)^\omega \le (\omega^2)^\omega = \omega^{2\cdot\omega} = \omega^\omega$

  • 0
    @AsafKaragila how does $(\omega +1)\omega=\omega ^2$ settle with the answer to [this question](http://math.stackexchange.com/questions/1340332/bringing-ordinals-to-standard-polynomial-form) where $(\omega +2)\omega=\omega ^2+2$?2015-09-10