Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

Thanks in advance!

Printable View

- Jun 8th 2010, 04:09 PMmeggnogInduction and Well Ordering Principle
Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.

Thanks in advance! - Jun 8th 2010, 05:02 PMtonio

Suppose is a proposition appliable to the natural numbers, and suppose that:

(1) is true for some ;

(2) It is true that

Then we must prove that is true for all .

Now, let . If then, by the WOP there exists a first (in the natural ordering of the naturals) . Well, now

look at , apply (2) above and get a contradiction which shows that cannot be non-empty and we're done.

Tonio - Jun 8th 2010, 05:32 PMwonderboy1953Question for Tonio
Does it work in reverse, namely that Complete Mathematical Induction implies the Well-Ordering Principle?

- Jun 8th 2010, 07:09 PMtonio

Yes, and it's not hard to prove.Try it, and then you can check here http://www.math.wustl.edu/~chi/310notesIV.pdf

Tonio