|
#REDIRECT [[Mathematical induction]]
It is possible to prove that [[mathematical induction]] works using a form of [[natural deduction logic]] and using [[proof by contradiction]].
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
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.
| 