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:
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)
“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)
“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)
“They relieve and recommend each other, and the sanity of society is a balance of a thousand insanities. She punishes abstractionists, and will only forgive an induction which is rare and casual.”
—Ralph Waldo Emerson (1803–1882)