Let $\gamma$ be the function which associates to each ordinal $\alpha$ the unique ordinal which is isomorphic to the well ordered set $\left(\alpha\times\alpha,\leq_{\text{c}}\right)$ (I have defined $\leq_{\text{c}}$ here Finding an order isomorphism from $\text{On}\times\text{On}$ to $\text{On}$). I want to show that
$$\gamma(\omega^{\beta}n+\eta)=\gamma(\omega^{\beta})+\omega^{\beta}(\omega^{\beta}(n-1)+\eta).$$
If I express $\omega^{\beta}n+\eta$ in its cantor normal form, then this can be done by using induction and the formula
$$\gamma(\omega^{\zeta_{0}}+\omega^{\zeta_{1}}m)=\gamma(\omega^{\zeta_{0}})+\omega^{\zeta_{0}+\zeta_{1}}m $$
(here $m\in\omega-\left\{ 0\right\}$, $\zeta_{0}\geq1$, and $0<\zeta_{1}\leq\zeta_{0}$)
But I want to prove this without using Cantor Normal Form. It is possible to do this?
Best Answer
$\newcommand{\sup}{\operatorname{sup_{i<\xi}}}$
One can do this using induction and basic ordinal arithmetic only.
First lets observe a few rules:
From 2. it follows by induction that $\gamma(\alpha+ n)=\gamma(\alpha)+\alpha 2n +1$ for infinite $\alpha$ and thus we get
Let $A(\beta,n,\eta)$ denote $$\gamma(\omega^\beta n+\eta)=\gamma(\omega^\beta)+\omega^\beta(\omega^\beta(n-1)+\eta)$$ for $\beta\geq 1, 1\leq n<\omega$ and $\eta<\omega^\beta$ not a successor.
In anything what follows, $\beta$ will always be $\geq 1$ and $n$ will be a positive integer and $\eta$ will be an ordinal which is not a successor.
First we will see
So assume $A(\beta, n, \eta)$ is true and $\eta<\omega^\beta$. We will show $A(\beta, n, \eta+\omega)$.
We have: $$\gamma(\omega^\beta n+\eta+\omega)=\gamma(\omega^\beta n+\eta)+(\omega^\beta n+\eta)\omega=\gamma(\omega^\beta)+\omega^\beta(\omega^\beta(n-1)+\eta)+(\omega^\beta n+\eta)\omega$$ Since $\eta<\omega^\beta$, we can simplify the last term $(\omega^\beta n+\eta)\omega$ to $\omega^\beta\omega$. Finally, $$ \gamma(\omega^\beta)+\omega^\beta(\omega^\beta(n-1)+\eta)+\omega^\beta\omega=\gamma(\omega^\beta)+\omega^\beta(\omega^\beta(n-1)+\eta+\omega)$$
For the limit case, assume $\eta=\sup\eta_i$ for limit ordinals $\eta_i$ so that $A(\beta, n,\eta_i)$ holds for all $i<\xi$. Then by 1.: $$\gamma(\omega^\beta n+ \eta)=\sup\gamma(\omega^\beta n+ \eta_i)=\sup\gamma(\omega^\beta)+\omega^\beta(\omega^\beta (n-1)+\eta_i)=\gamma(\omega^\beta)+\omega^\beta(\omega^\beta (n-1)+\eta)$$ To verify the last equality, note that $\sup\delta(\mu+\eta_i)=\sup\delta\mu+\delta\eta_i=\delta\mu+\delta\eta=\delta(\mu+\eta)$ for any choice of $\delta, \mu$.
Next up:
We already know that $A(\beta, n, \omega^\beta)$ is true. But this implies $$\gamma(\omega^\beta (n+1))=\gamma(\omega^\beta n+\omega^\beta)=\gamma(\omega^\beta)+\omega^\beta(\omega^\beta(n-1)+\omega^\beta)=\gamma(\omega^\beta)+\omega^\beta(\omega^\beta n+ 0)$$ which is what we desire.
Note that proving $A(\beta, 1, 0)$ for any $\beta$ is trivial, as this amounts to $\gamma(\omega^\beta)=\gamma(\omega^\beta)$.
All in all, $A(\beta, n, \eta)$ holds for all appropriate $\beta, n, \eta$.