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.
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.