Results 1 to 2 of 2

Math Help - use the well-ordering property to prove the Principle of Strong induction

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    124

    Post use the well-ordering property to prove the Principle of Strong induction

    use the well-ordering property to prove the Principle of Strong induction

    I don't know how to start...

    I know the well-ordering property is If S is a nonempy set of N, then there exists an element m ∈ S such that m≤k for all k∈S

    and the Principle of Strong induction is:
    Let P be property of N, assume:
    1) P(1) holds
    2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    the Principle of Strong induction is:
    Let P be property of N, assume:
    1) P(1) holds
    2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)
    This is strong induction on natural numbers with usual ordering. In general, strong induction can be used on any well-ordered set, and its proof is no more difficult.

    Suppose you have a set A well-ordered by <. The strong induction principle is:

    If for all x in A, (for all y < x, P(y)) implies P(x), then for all x in A, P(x).

    You may wonder where the base case is. The set A has the least element, call in x0. Then the premise "for all y < x0, P(y)" is vacuously true: there are no y < x0. Therefore, "(for all y < x0, P(y)) implies P(x0)" is equivalent to P(x0). The idea is that in the induction step, you have to prove P(x) from all P(y) for y < x. Since x0 is the least element, you get no help and you have to prove P(x0) directly.

    The easiest way to prove strong induction is by contradiction. Assume that for all x in A, (for all y < x, P(y)) implies P(x). Also, suppose that P(x) is not universally true. Consider the set {x in A | P(x) is false} and use the well-ordering property on this set.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof using principle of strong induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 20th 2010, 03:16 PM
  2. Induction and Well Ordering Principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 8th 2010, 06:09 PM
  3. well-ordering <--> induction principle?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 22nd 2010, 04:42 AM
  4. Well ordering property and induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 30th 2009, 05:03 AM
  5. strong induction property of sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 12th 2008, 08:18 PM

Search Tags


/mathhelpforum @mathhelpforum