Mathematical Induction - Proof of Mathematical Induction

Proof of Mathematical Induction

The principle of mathematical induction is usually stated as an axiom of the natural numbers; see Peano axioms. However, it can be proved in some logical systems. For instance, it can be proved if one assumes:

• The set of natural numbers is well-ordered.
• Every natural number is either zero, or n+1 for some natural number n.
• For any natural number n, n+1 is greater than n.

To derive simple induction from these axioms, we must show that if P(n) is some proposition predicated of n, and if:

• P(0) holds and
• whenever P(k) is true then P(k+1) is also true

then P(n) holds for all n.

Proof. Let S be the set of all natural numbers for which P(n) is false. Let us see what happens if we assert that S is nonempty. Well-ordering tells us that S has a least element, say t. Moreover, since P(0) is true, t is not 0. Since every natural number is either zero or some n+1, there is some natural number n such that n+1=t. Now n is less than t, and t is the least element of S. It follows that n is not in S, and so P(n) is true. This means that P(n+1) is true, and so P(t) is true. This is a contradiction, since t was in S. Therefore, S is empty.

It can also be proved that induction, given the other axioms, implies well-ordering.