Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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