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

Simple Proof for using Induction

  1. Oct 8, 2014 #1
    Dear All,
    I am trying to understand this proof for using induction. Please help me!!

    As per the book "Alan F beardon, Abstract algebra and geometry" The following....

    Proof: Let B be the set of positive integers that are not in A. Suppose that
    B = ∅; then, by the Well-Ordering Principle, B has a smallest element, say b.
    As before, b ≥ 2, so that now {1, . . . , b − 1} ⊂ A. With the new hypothesis,
    this implies that b ∈ A which is again a contradiction. Thus (as before) B = ∅,and A = N.

    b is >= 2 because 1 is in A right?

    b - 1 is 1 right?? therefore it should be in A??


    b - 1 is an element of A so b is an element of A + 1??

    so how does b become an element of A??

  2. jcsd
  3. Oct 8, 2014 #2


    User Avatar
    Science Advisor

    It would help if you would include the statement of the theorem.
  4. Oct 9, 2014 #3
    Proof by Induction

    The Principle of Induction II : Suppose that A ⊂ N, 1 ∈ A, and for every m,
    {1, . . . ,m} ⊂ A implies that m + 1 ∈ A. Then A = N.
  5. Oct 9, 2014 #4


    User Avatar
    Science Advisor

    You mean "suppose that B is NOT empty" don't you?

    "As before"?? Was there something you didn't tell us? You hadn't said, before that 1 was in A.
    Because, if n is in A then so is n+1.

    Yes. "Induction" says that "if 1 is in A and, whenever, n is in A so is n+ 1, then A= N".

    Not necessarily! But b- 1 is less than b and b is, by hypothesis, the smallest member of B.

    I don't know what you mean by "A+ 1". A is a set and 1 is a number.

    Because of the "induction hypothesis": "if n is in A then so is n+ 1".

  6. Oct 9, 2014 #5


    User Avatar
    Science Advisor

    Let k be the smallest integer not in A, (k must be >1). (1,. . .,k-1) are in A, therefore k is in A, contradiction.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook