0
$\begingroup$

Let $\alpha,\beta,\gamma,\tau$ be ordinals. Then

  1. $\tau<\alpha\cdot\beta\iff \tau=\alpha\cdot\eta+\zeta$ for a unique $\eta<\beta,\zeta<\alpha$

  2. $\tau<\alpha^\beta\alpha^\gamma\implies \tau=\alpha^\beta\cdot\eta+\zeta$ for some $\eta,\zeta\le\alpha^\delta$ and $\delta<\gamma$


My attempt:

1a. $\tau<\alpha\cdot\beta\implies \tau=\alpha\cdot\eta+\zeta$ for a unique $\eta<\beta,\zeta<\alpha$

Uniqueness

Assume that $\alpha\cdot\eta+\zeta=\alpha\cdot\eta'+\zeta'$.

Assume $\eta\neq\eta'$. WLOG, we assume $\eta<\eta'$ and thus $\eta+1\le\eta'$. It follows that $\alpha\cdot(\eta+1)\le\alpha\cdot\eta'$ and thus $\alpha\cdot\eta+\alpha\le\alpha\cdot\eta'$. Then $(\alpha\cdot\eta+\alpha)+\zeta'\le\alpha\cdot\eta'+\zeta'$ and thus $\alpha\cdot\eta+(\alpha+\zeta')\le\alpha\cdot\eta'+\zeta'$. Moreover, $\zeta<\alpha$, then $\zeta<\alpha+\zeta'$. Hence $\alpha\cdot\eta+\zeta<\alpha\cdot\eta+(\alpha+\zeta')\le\alpha\cdot\eta'+\zeta'$ and thus $\alpha\cdot\eta+\zeta<\alpha\cdot\eta'+\zeta'$. This is a contradiction and thus $\eta=\eta'$.

It follows that $\zeta=\zeta'$ and thus $(\eta,\zeta)=(\eta',\zeta')$.

Existence

We prove by induction on $\tau$.

  • If $\tau=0$ then $\tau=\alpha\cdot 0+0$.

  • If $\tau=\tau'+1$, then by IH $\tau'=\alpha\cdot\eta'+\zeta'$ and thus $\tau'+1=(\alpha\cdot\eta'+\zeta')+1=$ $\alpha\cdot\eta'+(\zeta'+1)$.

  • If $\tau$ is a limit ordinal, then by IH $\forall \tau'<\tau:\tau'=\alpha\cdot\eta'+\zeta'$

I'm stuck at showing $\tau=\alpha\cdot\eta+\zeta$

1b. $\tau<\alpha\cdot\beta\Longleftarrow \tau=\alpha\cdot\eta+\zeta$ for a unique $\eta<\beta,\zeta<\alpha$

$\eta<\beta\implies\eta+1\le\beta\implies\alpha\cdot(\eta+1)\le\alpha\cdot\beta\implies\alpha\cdot\eta+\alpha\le\alpha\cdot\beta$. Moreover, $\zeta<\alpha\implies\alpha\cdot\eta+\zeta<\alpha\cdot\eta+\alpha$. Thus $\alpha\cdot\eta+\zeta=\tau<\alpha\cdot\beta$.


Pleas help me prove $\tau=\alpha\cdot\eta+\zeta$. Thank you so much!

$\endgroup$

1 Answer 1

0
$\begingroup$

I have figured out the proof and posted here.


1a. $\tau<\alpha\cdot\beta\implies \tau=\alpha\cdot\eta+\zeta$ for a unique $\eta<\beta,\zeta<\alpha$

Uniqueness

Assume that $\alpha\cdot\eta+\zeta=\alpha\cdot\eta'+\zeta'$.

Assume $\eta\neq\eta'$. WLOG, we assume $\eta<\eta'$ and thus $\eta+1\le\eta'$. It follows that $\alpha\cdot(\eta+1)\le\alpha\cdot\eta'$ and thus $\alpha\cdot\eta+\alpha\le\alpha\cdot\eta'$. Then $(\alpha\cdot\eta+\alpha)+\zeta'\le\alpha\cdot\eta'+\zeta'$ and thus $\alpha\cdot\eta+(\alpha+\zeta')\le$ $\alpha\cdot\eta'+\zeta'$. Moreover, $\zeta<\alpha$, then $\zeta<\alpha+\zeta'$. Hence $\alpha\cdot\eta+\zeta<\alpha\cdot\eta+(\alpha+\zeta')\le$ $\alpha\cdot\eta'+\zeta'$ and thus $\alpha\cdot\eta+\zeta<\alpha\cdot\eta'+\zeta'$. This is a contradiction and thus $\eta=\eta'$.

It follows that $\zeta=\zeta'$ and thus $(\eta,\zeta)=(\eta',\zeta')$.

Existence

For $\tau<\alpha\cdot\beta$, let $X=\{\gamma\mid\alpha\cdot\gamma\le\tau\}$ and $\eta=\sup X$. Since $\tau<\alpha\cdot\beta$, $\forall\gamma\in X:\gamma<\beta$ and thus $\eta\le\beta$.

First, we prove that $\eta<\beta$.

  • If $\beta=\beta'+1$, then $\forall\gamma\in X:\gamma\le\beta'$ and thus $\eta=\sup X\le\beta'<\beta$.

  • If $\beta$ is a limit ordinal, we assume the contrary that $\eta=\beta$. Then $\gamma<\beta\implies\gamma<\eta=\sup X$ $\implies\gamma<\gamma'$ for some $\gamma'\in X$ $\implies\alpha\cdot\gamma<\alpha\cdot\gamma'\le\tau$ for some $\gamma'\in X$. Thus $\gamma<\beta\implies$ $\alpha\cdot\gamma<\tau$. We have $\alpha\cdot\beta=\sup\{\alpha\cdot\gamma\mid\gamma<\beta\}\le\sup\{\tau\mid\gamma<\beta\}=\tau$, which is a contradiction. It follows that $\eta\neq\beta$ and thus $\eta<\beta$.

Second, we prove $\alpha\cdot\eta\le\tau$.

  • If $\eta\in X$, then $\eta=\gamma$ for some $\gamma\in X$. It follows that $\alpha\cdot\eta=\alpha\cdot\gamma\le\tau$.

  • If $\eta\notin X$, then $\eta$ is clearly a limit ordinal. We have $\gamma<\eta\implies\gamma<\sup X\implies\gamma<\gamma'$ for some $\gamma'\in X$ $\implies\alpha\cdot\gamma<\alpha\cdot\gamma'\le\tau$ for some $\gamma'\in X$. It follows that $\gamma<\eta\implies\alpha\cdot\gamma<\tau$. Then $\alpha\cdot\eta=\sup\{\alpha\cdot\gamma\mid\gamma<\eta\}\le\sup\{\tau\mid\gamma<\eta\}=\tau$. Thus $\alpha\cdot\eta\le\tau$ and hence $\eta\in X$, which contradicts to our very first assumption that $\eta\notin X$. As a result, this case does not exist.

As a result, there is a unique $\zeta$ such that $\tau=\alpha\cdot\eta+\zeta$.

Finally, we prove $\zeta<\alpha$. Assume the contrary that $\alpha\le\zeta$, then $\alpha+\delta=\zeta$ for some $\delta$. Then $\tau=\alpha\cdot\eta+\zeta=\alpha\cdot\eta+(\alpha+\delta)=(\alpha\cdot\eta+\alpha)+\delta=\alpha\cdot(\eta+1)+\delta$. This contradicts the fact that $\eta=\sup X$.

1b. $\tau<\alpha\cdot\beta\Longleftarrow \tau=\alpha\cdot\eta+\zeta$ for a unique $\eta<\beta,\zeta<\alpha$

$\eta<\beta\implies\eta+1\le\beta\implies\alpha\cdot(\eta+1)\le\alpha\cdot\beta\implies\alpha\cdot\eta+\alpha\le\alpha\cdot\beta$. Moreover, $\zeta<\alpha\implies\alpha\cdot\eta+\zeta<\alpha\cdot\eta+\alpha$. Thus $\alpha\cdot\eta+\zeta=\tau<\alpha\cdot\beta$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .