This article may have been previously nominated for deletion: Wikipedia:Articles for deletion/Proof of mathematical induction exists. It is proposed that this article be deleted because of the following concern:
If you can address this concern by improving, copyediting, sourcing, renaming, or merging the page, please edit this page and do so. You may remove this message if you improve the article or otherwise object to deletion for any reason. Although not required, you are encouraged to explain why you object to the deletion, either in your edit summary or on the talk page. If this template is removed, do not replace it. This message has remained in place for seven days, so the article may be deleted without further notice. Find sources: "Proof of mathematical induction" – news · newspapers · books · scholar · JSTOR Nominator: Please consider notifying the author/project: {{subst:proposed deletion notify|Proof of mathematical induction|concern=nonstandard presentation of trivial material}} ~~~~Timestamp: 20060723203646 20:36, 23 July 2006 (UTC) Administrators: delete |
The principle of mathematical induction can be proved if the following axioms are assumed:
- (A1) The set of all natural numbers is well-ordered (that is, every non-empty set of natural numbers has a least element).
- (A2) if m > 0, then there exists n such that m = n + 1
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
- (1) P(0)
and
- (2) For all n ≥ 0, P(n) ⇒ P(n + 1)
We wish to prove:
- (3) P is true for all integer values of m.
Let S be the set of numbers for which P is false.
Using (1), we see that 0 is not an element of S and is therefore not the minimal element of S.
Using (A2), if m > 0, then m = n + 1. Now if n is in S, then m being bigger cannot be the minimal element of S. But if n is not in S, P(n) and using (2) P(n + 1) and so m is not in S and cannot be the minimal element of S.
Thus, S has no minimal element, and by (A1) must be empty. Thus, P is true for all integer values of m
Converse
Conversely, the axiom (A1) can be proved by the principle of mathematical induction. Indeed, given (A2), the two are equivalent.
Let S be a set of natural numbers. We want to prove that if S has no smallest element then S is empty.
Consider a set S with no smallest element and let P(n) be the statement that n is NOT an element of S.
- (1) Since S has no smallest element, 0 cannot belong to S and so P(0) is true.
- (2) Suppose that P(n) is true for some n. That is, n does not belong to S. Since S has no smallest element, n + 1 cannot belong to S either and so we have P(n+1)
Then by induction, we know that P(n) is true for all n, and therefore S is empty. Thus, we are done.