1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove principle of complete induction using ordinary induction - Spivak Calculus 2-11

  1. Mar 9, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove the principle of complete induction from the ordinary principle of induction.
    Hint :- if A contains 1 and A contains n + 1 whenever it contains 1,2,...,n consider the set B of all k such that 1,2,...,k are all in A

    2. Relevant equations

    Principle of mathematical induction.

    3. The attempt at a solution

    It is given that 1 is in A , it follows that 1 is in B. Since for k = 1 , all positive integers ≤ 1 (i.e 1) are in A , k = 1 is in B.

    Let us suppose k is in B. Thus , all positive integers ≤ k are in A. But A contains k+1 whenever it contains all positive integers ≤ k. Thus , A contains all positive integers ≤ k+1.
    Hence k+1 is in B. Thus , whenever k is in B so is k+1. From principle of ordinary induction it follows B contains all the positive integers.

    Let us suppose A doesn't contain all the positive integers. Thus , there is at least one positive integer not in A. Let this be t. Since t is not in A, any integer ≥ t can not be in B. Further the set of positive integers is not bounded above. Thus the set of integers ≥ t is not empty. Thus there are positive integers not in B. But we had proved earlier that B contains all the positive integers giving us a contradiction. Thus our supposition that A doesn't contain all the positive integers is false. Thus , A contains all the positive integers.

    Thus , we find that a set for which the principle of complete induction is true, contains all the positive integers.

    Attempt at solution ends here.

    I would like to know if this proof is complete or if something needs to be done to improve it.
    Have I missed some information in the proof or can it be shortened.I would also like to know if I am making any goof-ups in the 'mathematical grammar' of the proof.

    I am following Apostol's Calculus volume 1 and using Spivak's Calculus as a reference. This was chapter 2 problem 11 in Spivak's Calculus. I am having trouble proving theorems which seem 'self-evident'. The fact that they seem 'self-evident' act as a mental block while attempting a proof. In this problem I am not even sure whether I have actually proved anything.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted