Results 1 to 4 of 4

Math Help - well ordering principle

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    well ordering principle

    This is what I read somewhere

    "well-ordering principle for natural numbers is equivalent to the principle of mathematical induction"

    Now using well-ordering principle (that every non empty subset of natural numbers has a minimum) I could prove mathematical induction (if P(1) is true and P(n) => P(n+1) then P(i) is true for all i in N)

    This is rather trivial.


    But using mathematical induction I could not derive well-ordering principle. So is 'well-ordering principle' more powerful assertion than induction? Or, there is a nice way to prove it.

    Any help plz?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    Take a subset X of \mathbb{N}. We want to show that if it does not have a minimum, then it is empty.

    If 1 belongs to X, it has a minimum.

    If 1 does not belong to X, 1 satisfies the property P(n)\ :\ " \forall x\in X(n<x)". And...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by clic-clac View Post
    Hi

    Take a subset X of \mathbb{N}. We want to show that if it does not have a minimum, then it is empty.

    If 1 belongs to X, it has a minimum.

    If 1 does not belong to X, 1 satisfies the property P(n)\ :\ " \forall x\in X(n<x)". And...
    Thanks. Too stupid of me, this was actually not tough.


    So let X be subset that has no minimum. i.e. for every n in X there exists m, where m < n and m i also in X

    We need to prove X is empty

    Let P(k) be true if for all i <= k; i doesn't belong to X

    P(1) is obviously true

    Assume P(n) is true
    Then P(n+1) will be true as other wise this will imply that (n+1) is in X and by the way we define X it means there exists some i<(n+1) which is in X thus voilating assumption about P(n)

    Hence P(n+1) is true

    Thus by principle of induction P(n) is true for all n thus X is empty
    Hence well ordering principle is proved.

    I hope this proof is pretty rigorous. If you think there is any flaw please do high-light

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    769

    History repeats itself

    On Meggnog's posting of 6/8/2010 (Induction and Well Ordering Principle), we discussed this very question (with an answer) which you should check out further.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 08:31 AM
  2. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 18th 2009, 02:18 PM
  3. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2009, 10:59 AM
  4. well-ordering principle
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 10th 2007, 08:09 PM
  5. Well ordering principle
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 14th 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum