# Prove principle of complete induction using ordinary induction - Spivak Calculus 2-11

1. Mar 9, 2012

### glb_lub

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.