Set theory ordinal proof practice problem

Question

Prove that for every ordinal $\alpha$ there exists a single $\beta$ and $n$, such that ($\beta$ = $0$ ∨ Lim($\beta$)) $\&$ Nat($n$) $\&$ $\alpha = \beta + n$.

I am sorry for tossing everything to you, but I don't even know where to start. I would be very grateful if someone solves this for me.

Answer 1

Proof by induction on $\alpha$:

It is evidently true for $\alpha=0$ where you can take $\beta=n=0$.

If it is true for $\alpha$ then also it is true for $\alpha+1$. This because $\alpha=\beta+n$ implies that $\alpha+1=\beta+(n+1)$.

If $\alpha$ is a limit then it is true, because we can take $\beta=\alpha$ and $n=0\in\omega$.

Answer 2

Alternative proof:

Proof that every ordinal $\alpha$ is of the form $\omega \cdot \beta + \gamma$ for a unique pair $(\beta, \gamma$) with $\gamma < \omega$.

Uniqueness follows because

• $\alpha \mapsto \omega \alpha$ is strictly increasing,
• $\alpha \mapsto \beta + \alpha$ is strictly increasing for every fixed $\beta$,
• $\omega \cdot \alpha$ is a limit ordinal for all $\alpha > 0$.

Hence is suffices to prove existence:

Let $\beta$ be maximal such that $\omega \cdot \beta \le \alpha$. (Such a $\beta$ exists as $\beta \to \omega \cdot \beta$ is continuous.)

Now let $\gamma$ be unique such that $\omega \cdot \beta + \gamma = \alpha$. We have $\gamma < \omega$ as otherwise $\omega \cdot \beta + \omega = \omega \cdot (\beta + 1) \le \alpha$ -- contradicting the maximality of $\beta$.

I'll leave it to you to fill in the gaps (i.e. prove the facts that I've mentioned).