# Thread: Proof of inequality by transfinite induction

1. ## Proof of inequality by transfinite induction

Hi guys,

could you help me with the following?

Prove by transfinite induction that $\displaystyle \beta < \gamma \rightarrow \alpha + \beta < \alpha + \gamma$, where $\displaystyle \alpha, \beta, \gamma$ are ordinals .

The way we defined transfinite induction is:

Suppose that $\displaystyle \phi (x)$ is a statement and
1. $\displaystyle \phi (0)$
2. $\displaystyle \forall \alpha$, $\displaystyle \phi ( \alpha ) \rightarrow \phi ( \alpha + )$
3. If $\displaystyle \lambda$ is a limit and $\displaystyle \forall \alpha < \lambda$, $\displaystyle \phi ( \alpha )$, then $\displaystyle \phi ( \lambda )$

Then for all ordinals $\displaystyle \alpha$, $\displaystyle \phi ( \alpha )$

2. Originally Posted by Yasen
Hi guys,

could you help me with the following?

Prove by transfinite induction that $\displaystyle \beta < \gamma \rightarrow \alpha + \beta < \alpha + \gamma$, where $\displaystyle \alpha, \beta, \gamma$ are ordinals .

The way we defined transfinite induction is:

Suppose that $\displaystyle \phi (x)$ is a statement and
1. $\displaystyle \phi (0)$
2. $\displaystyle \forall \alpha$, $\displaystyle \phi ( \alpha ) \rightarrow \phi ( \alpha + )$
3. If $\displaystyle \lambda$ is a limit and $\displaystyle \forall \alpha < \lambda$, $\displaystyle \phi ( \alpha )$, then $\displaystyle \phi ( \lambda )$

Then for all ordinals $\displaystyle \alpha$, $\displaystyle \phi ( \alpha )$
What have you tried?

3. Originally Posted by Drexel28
What have you tried?
My foremost problem is on which ordinal should I do induction?

If I do induction on $\displaystyle \alpha$, which seems the most natural choice, I face the problem that ordinal addition is defined "on the right", and is moreover not commutative.

(for example, the base case would be that $\displaystyle 0+ \beta < 0 + \gamma$, but the definition of addition with 0 is $\displaystyle \alpha + 0 = \alpha$ . This could be circumvented, but I think it will prove more difficult to do so in the later cases).

On the other hand, if I do induction on $\displaystyle \beta$, then sooner or later I would get $\displaystyle \beta > \gamma$, and then what?

Could you at least give me this hint?

4. Originally Posted by Yasen
My foremost problem is on which ordinal should I do induction?

If I do induction on $\displaystyle \alpha$, which seems the most natural choice, I face the problem that ordinal addition is defined "on the right", and is moreover not commutative.

(for example, the base case would be that $\displaystyle 0+ \beta < 0 + \gamma$, but the definition of addition with 0 is $\displaystyle \alpha + 0 = \alpha$ . This could be circumvented, but I think it will prove more difficult to do so in the later cases).

On the other hand, if I do induction on $\displaystyle \beta$, then sooner or later I would get $\displaystyle \beta > \gamma$, and then what?

Could you at least give me this hint?
I figured out how to do it; by induction on $\displaystyle \gamma$ (which seemed the only alternative from the above argument). And then I fix $\displaystyle \beta$ and have that $\displaystyle \forall \gamma$ s.t. $\displaystyle \gamma \leq \beta$, the statement is vacuously true...