I'm just learning transfinite induction over the ordinals, and I'm finding it a bit difficult to organize proofs. There seems to be several ways to organize almost any proof, but only one of which leads some place. Is the following proof right? Can it be proved "better"?

Proposition. Let $\alpha, \beta, \gamma$ be ordinals with $\beta < \gamma$. Then $\alpha + \beta < \alpha + \gamma$.

Proof I. By induction over $\gamma$.

  • Assume $\beta < \delta \Rightarrow \alpha + \beta < \alpha + \delta$ for $\delta < \gamma$.

  • Show $\beta < \gamma \Rightarrow \alpha + \beta < \alpha + \gamma$

In this post I will only deal with the case where $\gamma$ is a successor ordinal, $\gamma = \delta + 1$. Assume $\beta < \delta < \delta + 1 =\gamma$. Then $\beta < \delta < \gamma$ implies $\alpha + \beta < \alpha + \delta < \alpha + \delta + 1$, or $\alpha + \beta < \alpha + \gamma$.

Proof II. Induction over $\alpha$.

  • Assume $\beta < \gamma$
  • Assume $\delta + \beta < \delta + \gamma$ for $\delta < \alpha$.

  • Show $\alpha + \beta < \alpha + \gamma$.

Now I let $\alpha = \delta + 1$ (again, I'll only dealing with successor ordinals), and I need to show $(\delta + 1) + \beta < (\delta + 1) + \gamma$. This is where I get stuck using this organization.

Is there a "best" or more elegant way to prove this simple proposition on ordinal addition?


I don't think we can get to general principles, but I'll comment on this problem at least.

Bear in mind that ordinal addition isn't commutative, so you can't learn much about $\delta+1+\beta$ from knowing $\delta+\beta$. That alone suggests you should focus on proof I, not II.

One also really needs to consider the limit-ordinal case to decide whether a proof is viable, so let's do that for proof I. The case $\gamma=0$ is trivial, so write a limit ordinal $\gamma\ne$ as $\beta+\eta$ with $0<\eta$. Since $+$ associates (which has a surprisingly long proof), $\alpha+\beta<\alpha+\beta+\eta=\alpha+\gamma$. But having written that, we realise there was never a need to induct over $\gamma$ anyway, or even to separately consider limit and successor $\gamma$.

What you might want to do is prove, by induction on $\alpha_2$, that $\alpha_1<\alpha_1+\alpha_2$ for ordinals $\alpha_1,\,\alpha_2$ with the latter $\ne 0$. After all, this theorem is crucial in the argument above.


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.