8
$\begingroup$

The title is one of my homework assigments, (and the above greek letters are ordinal numbers) but this is the first one containing inequalities, and I dont really know how to do it. My guess is induction, and I think this might be a way to do it:

First we prove that $\alpha\leq \beta$ imply that $\alpha+\gamma \leq \beta +\gamma$:

Induction on $\gamma$. If $\gamma=0$ then the statement is trivial. Now assume that the statement holds for all $x<\gamma$. If $\gamma$ is a succesor, then there exists a $y$ such that $Sy=\gamma$, then:$\alpha+\gamma=S(\alpha+y)\leq S(\beta+y)=\beta+\gamma$If $\gamma$ is a limit ordinal, then:$\alpha+\gamma=\mbox{sup}(\alpha+x: x<\gamma)\leq \mbox{sup}(\beta+x: x<\gamma)=\beta+\gamma$and thus we have that $\alpha+\gamma\leq \beta+\gamma$. Then my idea is to prove that if $\gamma\leq \delta$, then we have that $\beta+\gamma\leq \beta+\delta$ and then the statement would follow.

My question: For this last part do we do induction with base case $\delta=\gamma$? and then do the same routine of considering cases when $\delta$ is a limit or a successor. Is there another way to tackle this problem?

Thanks!

1 Answers 1

5

I’m assuming that your definition of ordinal addition is the inductive one according to which $\alpha+0=\alpha$, $\alpha+S(\beta)=S(\alpha+\beta)$, and $\alpha+\lambda=\sup\{\alpha+\beta:\beta<\lambda\}$ if $\lambda$ is a limit ordinal. You’ve already shown that if $\alpha\le\beta$, then $\alpha+\gamma\le\beta+\gamma$ for every $\gamma$, but note how your induction worked: it was induction on the second operand of the sum, because that’s how the definition of addition is set up. Thus, to show that $\beta+\gamma\le\beta+\delta$ whenever $\gamma\le\delta$, you won’t be able to induct on $\beta$: you’ll have to make the induction run on the second operand, exactly as you suggest doing.

In short, yes: start with a base case $\gamma=\delta$, and induct on $\delta$. I don’t see any slicker way to do it using the inductive definition of addition.