Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complete Induction

  1. Jun 18, 2010 #1


    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Prove the principle of complete induction using either the well-ordering principle or ordinary mathematical induction.

    2. Relevant equations


    3. The attempt at a solution

    Suppose that [itex]A[/itex] is a collection of natural numbers such that [itex]1 \in A[/itex] and [itex]n+1 \in A[/itex] whenever [itex]1, \dots, n \in A[/itex]. Now suppose that [itex]B[/itex] is the collection of those natural numbers not in [itex]A[/itex]. If [itex]B \neq \emptyset[/itex], then by the well-ordering principle, [itex]B[/itex] must have some least element. Clearly, this least element cannot be 1 so suppose instead that [itex]k+1[/itex] is the least element in [itex]B[/itex], in which case [itex]1, \dots, k[/itex] are all in [itex]A[/itex]; however, this implies that [itex]k+1 \in A[/itex] which is a contradiction. Thus our assumption that [itex]B[/itex] was non-empty must have been incorrect and [itex]A = \mathbb{N}[/itex].

    Is this correct?
  2. jcsd
  3. Jun 19, 2010 #2


    User Avatar
    Gold Member

    Since it's been roughly a day, does anyone have feedback?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook