Results 1 to 4 of 4

Math Help - Induction and Well Ordering Principle

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    Induction and Well Ordering Principle

    Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by meggnog View Post
    Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

    Thanks in advance!

    Suppose P is a proposition appliable to the natural numbers, and suppose that:

    (1) P(n_1) is true for some n_1\in\mathbb{N} ;

    (2) It is true that \forall\,k>n_1\,,\,P(n_1)\wedge P(n_1+2)\wedge\ldots\wedge P(k)\Longrightarrow P(k+1)

    Then we must prove that P(n) is true for all n\in\mathbb{N}-\{1,2,\ldots,n_1-1\}.

    Now, let K:=\{n\in\mathbb{N}\;/\;n>n_1\wedge P(n)\,\, \mbox{isn't true}\} . If K\neq\emptyset then, by the WOP there exists a first (in the natural ordering of the naturals) n_0\in K . Well, now

    look at P(n_1+1),\ldots,P(n_0-1) , apply (2) above and get a contradiction which shows that K cannot be non-empty and we're done.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    769

    Question for Tonio

    Does it work in reverse, namely that Complete Mathematical Induction implies the Well-Ordering Principle?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by wonderboy1953 View Post
    Does it work in reverse, namely that Complete Mathematical Induction implies the Well-Ordering Principle?

    Yes, and it's not hard to prove.Try it, and then you can check here http://www.math.wustl.edu/~chi/310notesIV.pdf

    Tonio
    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. well-ordering <--> induction principle?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 22nd 2010, 04:42 AM
  5. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2009, 10:59 AM

Search Tags


/mathhelpforum @mathhelpforum