Proof of mathematical induction

Encyclopedia : P : PR : PRO : Proof of mathematical induction

The principle of mathematical induction can be proved if the following axioms are assumed:

(A1) The set of all natural numbers is well-ordered (that is, every non-empty set of natural numbers has a least element).

(A2) if m > 0, then there exists n such that m = n + 1

A simplified version is given here. This proof does not use the standard mathematical symbols for there exists and for all to make it more accessible to less mathematically motivated readers.

Suppose

(1) P(0)

and

(2) For all n ≥ 0, P(n) ⇒ P(n + 1)

We wish to prove:

(3) P is true for all integer values of m.

Let S be the set of numbers for which P is false.

Using (1), we see that 0 is not an element of S and is therefore not the minimal element of S.

Using (A2), if m > 0, then m = n + 1. Now if n is in S, then m being bigger cannot be the minimal element of S. But if n is not in S, P(n) and using (2) P(n + 1) and so m is not in S and cannot be the minimal element of S.

Thus, S has no minimal element, and by (A1) must be empty. Thus, P is true for all integer values of m

Converse

Conversely, the axiom (A1) can be proved by the principle of mathematical induction. Indeed, given (A2), the two are equivalent.

Let S be a set of natural numbers. We want to prove that if S has no smallest element then S is empty.

Consider a set S with no smallest element and let P(n) be the statement that n is NOT an element of S.

(1) Since S has no smallest element, 0 cannot belong to S and so P(0) is true.

(2) Suppose that P(n) is true for some n. That is, n does not belong to S. Since S has no smallest element, n + 1 cannot belong to S either and so we have P(n+1)

Then by induction, we know that P(n) is true for all n, and therefore S is empty. Thus, we are done.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.