Euclidean algorithm for ordinals

Question

I am trying to prove the Euclidean algorithm for ordinals. More specifically: For any ordinals $\alpha, \beta$ where $\beta >0$, there are unique $\gamma, \delta$ such that $\alpha = \beta\gamma+\delta$ and $\delta<\beta$.

For now, I have difficulties. For example, I am not sure what to do when, $\alpha$ is a limit ordinal and $\beta$ is finite (a natural number).. since "diminishing" multiples of $\beta$ from $\alpha$ will not help.. and I don't really have an action of division...

Can anyone help? maybe give me a clue or a direction??

Thanks! Shir

Answer 1

$\beta \omega = \omega$, so you could first "divide" by $\omega$, and then take the result and finish dividing by $\beta$.

Answer 2

Hints: Let $\xi$ be the least ordinal such that $\alpha\le\beta\cdot\xi.$ If $\alpha=\beta\cdot\xi,$ you're done. Suppose that $\alpha<\beta\cdot\xi.$ Show that $\xi$ cannot be a limit ordinal (by our choice), and cannot be $0$, let $\gamma=\sup\xi,$ and proceed to prove existence.

Uniqueness isn't too tricky.