Prove that the Well-Ordering Principle implies the Principle of Complete Mathematical Induction.
Thanks in advance!
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.