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.
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.