Proving that $\gamma(ω^{β}n+η)=\gamma(ω^{β})+\omega^{β}(ω^{β}(n-1)+η)$, where $n∈ℕ$ , $η0$.

alternative-proofordinalsset-theory

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:

  1. $\gamma$ is continuous, that is whenever $\alpha$ is the limit of a sequence $(\alpha_i)_{i<\delta}$ then $\gamma(\alpha)=\operatorname{sup}_{i<\delta}\gamma(\alpha_i)$
  2. $\gamma(\alpha+1)=\gamma(\alpha)+\alpha 2+1$

From 2. it follows by induction that $\gamma(\alpha+ n)=\gamma(\alpha)+\alpha 2n +1$ for infinite $\alpha$ and thus we get

  1. $\gamma(\alpha+\omega)=\gamma(\alpha)+\alpha\omega$

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

If $A(\beta,n, 0)$ holds, then $A(\beta, n, \eta)$ holds for all non-successor $\eta\leq \omega^\beta$.

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:

If $A(\beta, n, 0)$ holds then $A(\beta, n+1, 0)$ does, too.

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

Related Question