Proving Principle of Complete Induction from Ordinary Induction

[glb_lub]

Homework Statement

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

Homework Equations

Principle of mathematical induction.

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.

 

[mighty2000]

I am still at the beginning of Apostol's book.





Thank you for your post. Your proof is correct and complete. You have clearly stated the given information, used the hint provided, and followed the logical reasoning to reach a conclusion. Your mathematical grammar is also correct, and your proof is well-structured and easy to follow.

As for improving your proof, one suggestion would be to provide a brief explanation or justification for each step, especially when using mathematical language or symbols. This will make your proof more clear and understandable to others who may not be familiar with the topic.

Regarding your difficulty with proving "self-evident" theorems, this is a common challenge for many mathematicians. It often helps to break down the problem into smaller steps and to think about why each step is necessary or true. Also, practice makes perfect - the more you work on proofs, the more comfortable you will become with them.

Best of luck in your studies!