# Proof of mathematical induction

The principle of

mathematical induction can be proved if the following

axiom is assumed:

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

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. The key technique is natural deduction logic and

proof by contradiction.

Suppose

P(0) [1]

and

For all n >=0, P(n) => P(n+1) [2]

Consider also the statement

For all m >=0, P(m) [3]

- in other words P is

**true** for all integer values of m.

Assume this is **false**, which is equivalent to

There exists an m such that not P(m) [4]

The proof hinges on showing that if [1] and [2] hold, then [4] is false, hence [3].

Assume [1], [2] and [4].

Using [4],
let m' be the **smallest** such value such that **not** P(m), hence **not** P(m')

Clearly m' cannot be 0, since this leads to an immediate contradiction [ P(0) & **not** P(0] with P(0) - rule [1]

Suppose m'>0.

From the definition of m', P(m'-1), hence by [2] P(m'). This also gives a contradiction [P(m') & **not** P(m')] since we are assuming **not** P(m').

It thus follows that [1] and [2] together imply **not** [4], which we have already established is just [3].

Hence if

P(0) [1]

and

P(n) => P (n+1) [2]

it follows that

*(with a trivial change of variable)*

for all n >=0, P(n) [3],

which is the principle of mathematical induction.

## Converse

Conversely, the axiom can be proved by the principle of mathematical induction. Indeed, the two are equivalent.

Let *S* be a set of natural numbers. We want to prove that either *S* has a smallest element or else that *S* is empty. Let *P*(*n*) be the statement that no element of *S* is smaller than *n*. *P*(0) is certainly true, since there is no natural number smaller than 0. Suppose that *P*(*n*) is true for some *n*. If *P*(*n*+1) were false, then *S* would have an element smaller than *n*+1, but it could not be smaller than *n*, because *P*(*n*) was true, and so *S* would have a minimal element, namely *n*, and we would be done. So *P*(*n*) implies *P*(*n*+1) for all *n*, or else *S* has a minimal element. But if *P*(*n*) implies *P*(*n*+1) for all *n*, then by induction we know that *P*(*n*) is true for all *n*, and therefore for all *n*, no element of *S* is smaller than *n*. But this can only be vacuously true, if *S* has no elements at all, since every natural number is smaller than some other natural number. Thus we are done.