|
#REDIRECT [[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.
| 