Proof of mathematical inductionThe 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).
For all n >=0, P(n) => P(n+1) Consider also the statement
For all m >=0, P(m) - 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) The proof hinges on showing that if  and  hold, then  is false, hence .
Assume ,  and .
Using , 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 
From the definition of m', P(m'-1), hence by  P(m'). This also gives a contradiction [P(m') & not P(m')] since we are assuming not P(m').
It thus follows that  and  together imply not , which we have already established is just .
P(n) => P (n+1) it follows that (with a trivial change of variable)
for all n >=0, P(n) ,which is the principle of mathematical induction.
ConverseConversely, 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.