Proof of Mathematical Induction
The principle of mathematical induction is usually stated as an axiom of the natural numbers; see Peano axioms. However, it can be proved in some logical systems. For instance, it can be proved if one assumes:
- The set of natural numbers is well-ordered.
- Every natural number is either zero, or n+1 for some natural number n.
- For any natural number n, n+1 is greater than n.
To derive simple induction from these axioms, we must show that if P(n) is some proposition predicated of n, and if:
- P(0) holds and
- whenever P(k) is true then P(k+1) is also true
then P(n) holds for all n.
Proof. Let S be the set of all natural numbers for which P(n) is false. Let us see what happens if we assert that S is nonempty. Well-ordering tells us that S has a least element, say t. Moreover, since P(0) is true, t is not 0. Since every natural number is either zero or some n+1, there is some natural number n such that n+1=t. Now n is less than t, and t is the least element of S. It follows that n is not in S, and so P(n) is true. This means that P(n+1) is true, and so P(t) is true. This is a contradiction, since t was in S. Therefore, S is empty.
It can also be proved that induction, given the other axioms, implies well-ordering.
Read more about this topic: Mathematical Induction
Famous quotes containing the words proof of, proof, mathematical and/or induction:
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
—François, Duc De La Rochefoucauld (1613–1680)
“An accurate charting of the American woman’s progress through history might look more like a corkscrew tilted slightly to one side, its loops inching closer to the line of freedom with the passage of time—but like a mathematical curve approaching infinity, never touching its goal. . . . Each time, the spiral turns her back just short of the finish line.”
—Susan Faludi (20th century)
“One might get the impression that I recommend a new methodology which replaces induction by counterinduction and uses a multiplicity of theories, metaphysical views, fairy tales, instead of the customary pair theory/observation. This impression would certainly be mistaken. My intention is not to replace one set of general rules by another such set: my intention is rather to convince the reader that all methodologies, even the most obvious ones, have their limits.”
—Paul Feyerabend (1924–1994)