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....

    Quote:
    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.
    Questions??

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

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

    Then....

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

    so how does b become an element of A??

    Danke....
     
  2. jcsd
  3. Oct 8, 2014 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simple Proof for using Induction
  1. A Proof by induction (Replies: 4)

  2. Induction Proof (Replies: 3)

  3. Proof By Induction (Replies: 0)

Loading...