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