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:
“To cease to admire is a proof of deterioration.”
—Charles Horton Cooley (1864–1929)
“The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
—Raymond Chandler (1888–1959)
“It is by a mathematical point only that we are wise, as the sailor or the fugitive slave keeps the polestar in his eye; but that is sufficient guidance for all our life. We may not arrive at our port within a calculable period, but we would preserve the true course.”
—Henry David Thoreau (1817–1862)
“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)