Why Mathematical Induction is valid
The validity of mathematical induction follows from the Well-Ordering Property (WOP),
which is a fundamental axiom of number theory. WOP states that
Every nonempty subset of the set of positive integers has a least element.
Now we use WOP to prove that P(n) is true for all positive integers:
- Assume that there is at least one positive integer for which P(n) is false.
As a result, the set S of positive integers for which P(n) is false is nonempty.
- Thus, by WOP, S has a least element, which will be denoted by m.
Correspondingly, P(m) is false.
- We know that m cannot be 1, because P(1) is true.
- Because m is positive and greater than 1, m-1 is a positive integer.
- Since m-1 is less than m, it is no in S. Therefore P(m-1) must be true.
- Because the conditional statement P(m-1) -> P(m) is true, it must be the case
that P(m) is true.
- This is a contradiction. Hence, P(n) must be true for every positive integers n.