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:
“In the reproof of chance
Lies the true proof of men.”
—William Shakespeare (1564–1616)
“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)
“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)