We deduced the Principle of Mathematical Induction from the Well Ordering Princi

Question

We deduced the Principle of Mathematical Induction from the Well Ordering Principle. The reverse also holds. To show this, assume that the Principle of Mathematical Induction holds but not the Well ordering Principle. Thus, there is a nonempty set S of positive integers with no least number. Let P(subscript)n be the following statement: none of the numbers {1,2,...,n} is in S. Now 1 is not in S, for then 1 would be the least number in S because it is the smallest positive integer. Hence P(subscript)1 is true. Now finish the proof by assuming that P(subscript)k is true and showing P(subscript)(k+1) is true. How do we get a contradiction at the end?

Thanks in advance.

Explanation / Answer

The second statement is that P(k+1) is true for P(k) is true

Since 1 is not in S , our proof is half done

for P(k) to be true, P(k+1) is also true

assume k = n where n is the highest possible integer not in S

then P(n+1) is also true which would mean n+1 is also not in S

But this is a contradiction as we just established n to be the highest possible number not in S. Hence the statement is not valid

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.