# 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 $\beta < \gamma \rightarrow \alpha + \beta < \alpha + \gamma$, where $\alpha, \beta, \gamma$ are ordinals .

The way we defined transfinite induction is:

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

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

2. Originally Posted by Yasen
Hi guys,

could you help me with the following?

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

The way we defined transfinite induction is:

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

Then for all ordinals $\alpha$, $\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 $\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 $0+ \beta < 0 + \gamma$, but the definition of addition with 0 is $\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 $\beta$, then sooner or later I would get $\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 $\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 $0+ \beta < 0 + \gamma$, but the definition of addition with 0 is $\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 $\beta$, then sooner or later I would get $\beta > \gamma$, and then what?

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