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


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.

  • $\begingroup$ Thank you very much for your helpfull answer! $\endgroup$ – topsi Oct 13 '13 at 20:41

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.