Let P be a set. If P contains zero as an element, and if "n is an element of P" implies "n+1 is an element of P" for all natural numbers n, then P contains the entire set of natural numbers.A good analogy is dominoes:
Let there be an infinite line of dominoes. If you knock down the first domino, and if each domino knocks down the domino after it, then all dominoes will get knocked over.Each domino in the infinite line of dominoes corresponds to a natural number. The very first domino corresponds to the number zero. The set P is just the set of dominoes which will be knocked over.
I've always wondered why it is we need the axiom of induction. It just seems so obvious and intuitive. Of course you're going to knock down all the dominoes. How could it be any other way? Why do we need to assume, as a fundamental axiom, that the dominoes will all fall over? Is there some system of dominoes which would not all get knocked over?
It turns out that the answer is yes. It's quite simple really. Let's say we have not one, but two infinite rows of dominoes. These dominoes obey all the other Peano Axioms, but they do not obey the axiom of induction. Because if you knock down that first domino, you're only going to get that first row of dominoes, and miss the second row completely.
Supposedly, the axiom of induction is equivalent to the so-called Well Ordering Principle (WOP). The WOP states that given any non-empty set of natural numbers, there is always a least natural number in the set. That is, given any set of dominoes, no matter how many you pick, you will always be able to pick out the single domino which comes first, before all the others.
So, funny story. In my analysis class, we were trying to use the first four Peano Axioms and the Well Ordering Principle to prove the axiom of induction. I pointed out a flaw in the professor's proof. I thought maybe there was some quick fix, some detail we missed. But the next day, the professor came in and explained why I was correct. You cannot prove the axiom of induction from the WOP.
In fact, it is possible to devise a set of numbers which obeys the WOP, but does not obey induction. Let me go back to the domino analogy. Let's say we have two infinite rows of dominoes as shown below.
If you take any set of dominoes, you can always pick out a single domino which occurs first. That is, there will always be one, and only one domino which is to the left of all the others in the set. And yet, if you knock the very first domino in the set, then you will only be able to knock down the first infinite row of dominoes, leaving the second one untouched.The dominoes represent a simple set of numbers, which looks like {0,1/2, 1, 3/2, 2, 5/2, 3, 7/2, ...}. The first row of dominoes represents all the whole numbers {0, 1, 2, 3, ...}. The second row of dominoes represents all the non-whole numbers {1/2, 3/2, 5/2, 7/2, ...}. Induction will only get you all the whole numbers, the first row of dominoes. And yet, this system of numbers obeys all the other Peano axioms and the WOP.
This is really strange, because I've been told many times that the WOP is equivalent to induction. You can use induction to prove the WOP, and you can use the WOP to prove induction. But it's not true! It was all a myth, propagated even by the most authoritative sources. Usually, when they try to prove the axiom of induction from the WOP, they either implicitly or explicitly start with the natural numbers. But you don't have the natural numbers until you first have the axiom of induction! All you really end up showing is that given WOP and induction, you can prove induction.
