Results 1 to 5 of 5

Math Help - well-ordering <--> induction principle?

  1. #1
    Junior Member
    Joined
    May 2008
    Posts
    26

    well-ordering <--> induction principle?

    I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by eniuqvw View Post
    I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
    If I understand your question correctly: you want to show (using the principle of mathematical induction) that every non-empty subset A of N has minimal element.
    Suppose that A is a set not having the least element. Denote by B the complement of A.
    Can you show (using induction) that every positive integer is in B? Clearly, B=N implies that A is empty.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by eniuqvw View Post
    I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
    I think I know what you're getting at.

    It appears that your question falls under order theory, and in particular, mathematical induction in its extended form requires a well-founded structure. Well-founded relations are more general than well-ordered ones, i.e., there exist well-founded relations that are not well-ordered.

    Does that answer your question?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by eniuqvw View Post
    I'm aware that well-ordering of all subsets of positive integers is provable from the principle of mathematical induction, but is there a proof of the converse? I'm just curious because I've heard in a past logic course that induction depends on well-ordering.
    You're asking about the derivability relation between the well-ordering principle and the principle of mathematical induction?
    They're interderivable (provably equivalent).

    Proofs in both directions can be found on the Internet.
    I think you'll see that, typically, both derivations are indirect (specifically, by RAA).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,697
    Thanks
    1469
    Kompik gave almost what you want.

    What you need to do is first prove the "strong principal of induction":

    If X is a set of positive integers containing 1 and such that if, for some k, all i\le k are in X, then X is the set of all positive integers. That can be proved from the usual induction principal.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help with well ordering principle
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: May 23rd 2011, 02:40 PM
  2. Replies: 1
    Last Post: November 16th 2010, 01:36 AM
  3. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 08:31 AM
  4. Induction and Well Ordering Principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 8th 2010, 06:09 PM
  5. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2009, 10:59 AM

Search Tags


/mathhelpforum @mathhelpforum