2
$\begingroup$

I know from a Discrete Mathematics class in the spring that Mathematical Induction depends on the well-ordering principle for natural numbers. The explanation in my textbook (Rosen) did not give me the level of understanding I was hoping for.

Could someone explain the equivalence of the well-ordering principle and the principle of mathematical induction?

I am aware there are resources for proofs of this, but I am looking for a more "intuitive" explanation than a proof- proofs I can read on my own.

$\endgroup$
3
$\begingroup$

The principle of mathematical induction and the well ordering principle for the natural numbers are equivalent. The intuitive idea, for me, is the following:

  • Induction works from zero "upwards", showing that every natural number satisfies some property. You first show that zero has the property (the base case), and then that if a number $n$ has the property than so does $n+1$ (the successor step).

  • The well ordering principle works "downwards", but to prove the equivalence with induction you look at the least number that does not satisfy the property. If you look at the least number that does not satisfy the property, then either that number is zero (which is ruled out by the base case of the induction proof) or that number is of the form $n+1$ (which is ruled out by the successor step of the induction proof).

So induction and the well ordering principle only differ in the "direction" that they look at things.

In the end, it does not matter which one you take as an axiom. In certain constructions of the natural numbers, the well ordering principle is established first, and in that sense only the principle of induction depends on the well ordering principle. But other systems take induction as a basic axiom, and then derive the well ordering principle from it.

$\endgroup$
  • $\begingroup$ And this ties in with Infinite Descent, because infinite descent relies on the fact that there is a least number with a given property, correct? $\endgroup$ – Antonios-Alexandros Robotis Nov 17 '15 at 2:45
  • 1
    $\begingroup$ Infinite descent is simply another way of working with the well-ordering principle. At the time the Fermat began using infinite descent, the general idea of a well ordering had not been explored, so the phrase "the natural numbers are well ordered" would not have had any meaning to Fermat. $\endgroup$ – Carl Mummert Nov 17 '15 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.