Results 1 to 4 of 4

Math Help - Proof of inequality by transfinite induction

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    5

    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 )
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Yasen View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    5
    Quote Originally Posted by Drexel28 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2010
    Posts
    5
    Quote Originally Posted by Yasen View Post
    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...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 8th 2011, 10:19 AM
  2. Induction proof concerning a finite sum inequality
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 11th 2011, 08:44 AM
  3. [SOLVED] Transfinite Induction?
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 31st 2011, 09:34 PM
  4. Induction Proof (Inequality) SIMPLE!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 3rd 2010, 02:58 AM
  5. Transfinite Induction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 26th 2008, 08:46 PM

Search Tags


/mathhelpforum @mathhelpforum