Why induction works

This is a footnote to the above post for the mathematically inclined, or those who've heard it before but don't remember why it works. If you can already give a proof... pat yourself on the back! The proof is by contradiction. Induction says that if the following premises 1) and 2) are true, then the conclusion 3) is true:

1) P(1) is true.
2) If P(n) is true, then P(n+1) is also true.
3) In conclusion, the property P is true for all natural numbers n.

Let's assume the argument is false. Again, that means we grant that 1) and 2) are true, but claim that 3) is false. If 3) is false, that means P is not true for all natural numbers n. Let's call the set of nat. numbers for which P is false, X. The only new idea is the Well Ordering Principle, which says that any non-empty set of the nat. numbers has a least element, i.e. an element which is less than all others. There's nothing fishy here -- you can either assume the WOP by axiom and then prove induction, or assume induction works by axiom and then prove the WOP, however you like. Now, our set X is non-empty if we assume 3) is false, and X is also a subset of the nat. numbers; thus, it has a least element, which we'll call k. It cannot be 1, because that would contradict 1).

Let's look at that nat. number before k, namely k-1. Either P is true or false for k-1. If it's true for k-1, then by 2), P is also true for k-1+1, which is k -- but we chose k so that P(k) was false, a contradiction. What if P is not true for k-1? Then it belongs to the set X. Ah, but we chose k so that it was the least element of X, and surely k-1 is less than k, also a contradiction. No matter what, we get a contradiction, and therefore our assumption that induction doesn't work must be false: it is valid after all.