1
$\begingroup$

I need to prove this using transfinite induction

Let $\alpha, \beta , \gamma $ ordinals

If $\beta <\gamma$ then $\alpha + \beta < \alpha + \gamma$

I am trying to prove the statement by transfinite induction on $\gamma$

for base case $\gamma =0$, I assume that $\beta <0$, but as there is no $\beta<0$ then $\alpha +\beta < \alpha +0$ holds for all $\beta$ ? is that correct ?

Thanks in advance

$\endgroup$
3
  • $\begingroup$ Yes, the base case is correct. $\endgroup$
    – Git Gud
    Mar 21, 2015 at 1:43
  • $\begingroup$ but what if I try to prove that $\alpha + \beta > \alpha + \gamma $ (something that is false), would no be the same argument correct for the base case $\gamma =0$? $\endgroup$ Mar 21, 2015 at 1:47
  • 1
    $\begingroup$ I don't understand what you're saying,but here are some possibly relevant observations. It obviously is false that $\forall \alpha, \beta,\gamma(\alpha+\gamma<\alpha+\beta)$. It is also false that $\forall \alpha,\beta(\alpha+0<\alpha+\beta)$. But it is not false that $\forall \alpha,\beta(\beta <0\to \alpha+0<\alpha+\beta)$. $\endgroup$
    – Git Gud
    Mar 21, 2015 at 1:52

1 Answer 1

1
$\begingroup$

If you take the base case to be $\gamma=0$ (instead of the more common $\beta=0$), you basically shift the problem to the induction step.

To see this, suppose you have shown the inequality for $\gamma_0$, and you want to show it for $\gamma_0+1$. Now $\beta<\gamma_0+1$. You want to use the induction hypothesis, but now we only know $\beta\le\gamma_0$, which means either $\beta<\gamma_0$ or $\beta=\gamma_0$. The first case is handled by the induciton hypothesis, but the second is not, and you have to check it manually. Now $\gamma=\gamma_0+1$, so the inequality you want to check is $\alpha+\beta<\alpha+\gamma_0+1$. This is true because $\beta=\gamma_0$. However, if you reverse the inequality to be shown, then it is false in this special case that is not reduced to the induction hypothesis.

P.S. If you're not entirely comfortable with ordinals (as I am), just substitute natural numbers for them. They are surprisingly similar (to some extent).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .