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.
17 comments:
Hang on a minute. Do your other well-orderings of dominoes obey the other Peano axioms? Certainly if we're just talking about an arbitrary well-ordering of a set, induction does not follow, as your counterexamples demonstrate. But it seems to me that the well-ordering of the natural numbers that is produced by the fifth Peano Axiom is more specific. A proof of induction given the well-ordering of the natural numbers would go as follows:
Assume for contradiction's sake that we have a set P that satisfies the two requirements above (zero is an element, and for every n, if n is in P then n+1 is in P), but that P does not contain all the natural numbers. Then the set P' of all numbers not in P is nonempty, and therefore has a least element k. Since k is nonzero, it is the successor to some number k-1, which must be in P (otherwise k would not be the least element). But if k-1 is in P, then by assumption, k-1+1=k is in P, contradicting that k is in P'! Thus P must contain all natural numbers.
I haven't studied the Peano axioms much, so there may be some hidden assumption that I'm making. But it seems to me that the argument above is sound, and shows that given the specific "well-ordering by succession" of the natural numbers, induction does indeed follow.
[I believe this is one of the Peano Axioms, that every nonzero number is the successor to some number],
The flaw is in this step:
"Since k is nonzero, it is the successor to some number k-1"
This is easy to prove, but you need the axiom of induction to do it. Or you could call it a new axiom #6. Axiom 6 and WOP is equivalent to induction.
Ah, okay, I see now. My vague memory of the Peano axioms led me to believe that "every nonzero number is the successor to another number" was an axiom. Now that I've looked it up I see that's not the case. (And since you can prove it by induction, it doesn't need to be an axiom.) In this case, you're quite right that well-ordering together with the other Peano axioms does not imply induction.
Your discussion of dominoes depends on the existence of rational numbers, which as far as I know (which is admittedly not very far) are often defined by taking the Cartesian product of the natural numbers -- which in turn is defined by taking the power set of the natural numbers, which of course requires a much stronger axiom system. Is there a way to define the rationals with just the peano axioms? And if not, how can you use them as a counterexample in this context?
I'm going to add another thought. Couldn't you, so to speak, add little arms to the left set of dominoes, so that each of them toppled the domino next to them as well as the domino in front of them? The mathematical equivalent would be to define an order relation that worked like this:
(1) 0 -> 1/2 -> 1 -> 3/2 -> 5/2 ...
instead of the order relation
(2) 0 -> 1 -> 2 -> 3... -> 1/2 -> 3/2 -> ...
The difference between these order relations is one of "order type." The order type of (1) is ω, while the order type of (2) is ω + ω. The difference is that in the case of (2), you have to get through all the natural numbers before you get to the rational numbers, which seems to pose a problem for induction. The problem, intuitively, is that you have to count to infinity twice, which seems hard. But with a set with order type ω, you only have to count to infinity once, which seems less hard.
It seems to me, however, that if we interpret the well-ordering principle to mean that the natural numbers can be well-ordered with an order type of ω, then the well-ordering principle must imply induction.
Another, briefer way of saying this might be to say that successor relations and order relations only line up perfectly in ω order types.
There is nothing wrong with assuming the existence of the rational numbers. Yes, we must take several new axioms, but these axioms are only true of the full set of rationals, and not necessarily true of a subset of rationals. So we haven't really taken any new axioms which pertain to the set of dominoes.
Besides, we only need to show the existence of a counterexample number system. As long as the counterexample is consistent, obeys the WOP and the first four Peano axioms, but does not obey induction, then it doesn't matter what other axioms it does or does not obey.
The mathematical equivalent would be to define an order relation that worked like this:
(1) 0 -> 1/2 -> 1 -> 3/2 -> 5/2 ...The order relation is already defined this way. I think you might be confusing the order relation with the successor function. The successor function is not defined as the next greatest number in the set. In this system, the successor function is defined as S(k) = k+1.
However, you could define a new successor function as S(k) = k+1/2. In which case, the axiom of induction would be true! But by doing this, you have constructed an entirely new number system. The new number system does not negate the existence of the previous counterexample.
Yes, we must take several new axioms, but these axioms are only true of the full set of rationals, and not necessarily true of a subset of rationals. So we haven't really taken any new axioms which pertain to the set of dominoes.But if we really haven't taken any new axioms which pertain to the set of dominoes, then why do we have to take new axioms at all? It seems to me that if you can only use peano axioms, your counterexample can't be proven to exist. In other words, I don't think you can prove that 1/2 is a number with only the peano axioms. I don't mean to be pesky, I'm just trying to understand the argument more clearly.
I think you might be confusing the order relation with the successor function. The successor function is not defined as the next greatest number in the set. In this system, the successor function is defined as S(k) = k+1.Well, I wouldn't say that I'm "confusing" them, so much as saying that an order relation yielding a type ω order on our set seems equivalent to a successor function -- S(k) = k + 1/2 in this case. As I see it, that's not creating an entirely new number system -- that's recreating the natural numbers using different symbols!
I'll try to restate my assertion. Say you have (via whatever axioms you like) an infinite countable set. If that set can be well-ordered with order type ω, then you can use the order relation to define a successor relation on that set such that "if k is nonzero, then it is the successor to some number k-1" is true. It would look something like "S(x) = the least element of the set of all y: x < y."
Even more briefly: the "ωOP" = the WOP + axiom 6.
I dunno, what do you think? I feel pretty strongly that this is correct but I'm no expert.
I don't think you can prove that 1/2 is a number with only the peano axioms.No, you can't. You don't have to. You only have to prove that the number 1/2 is consistent with WOP and the first four Peano axioms, not that it is necessary.
The WOP and the first four Peano axioms do not uniquely define a number system. You have to think of it more abstractly. All we need is some set of elements over which the successor function S and the ordering relation "<" are defined. There are many very different sets which obey the first four Peano axioms and the WOP. I just picked out one of those sets, one which can be represented intuitively as a subset of the rationals.
Well, I wouldn't say that I'm "confusing" them, so much as saying that an order relation yielding a type ω order on our set seems equivalent to a successor functionNot quite. And recall that my counterexample already does have a type ω ordering.
The ordering relation ">" and the successor function "S" do not necessarily have any relation to each other. Not unless you take a new axiom saying that they do. The Peano axioms only refer to the successor function. The WOP refers only the the ordering relation. You need an extra axiom if you want to relate the two.
"S(x) = the least element of the set of all y: x < y."We could take this as axiom 7. As far as I know, WOP + axiom 7 are equivalent to induction.
As I see it, that's not creating an entirely new number system -- that's recreating the natural numbers using different symbols!Not really. We can say that two number systems are the same if we can find an isomorphism between the two sets. This isomorphism must preserve the successor function and ordering relations.
Otherwise, it would be possible to prove that the set of rationals and the set of naturals are equivalent number systems, just by redefining the successor function and ordering relation. After all, the two sets are equinumerous.
You have to think of it more abstractly... I just picked out one of those sets, one which can be represented intuitively as a subset of the rationals.Fair enough; I'd rather think about it abstractly. So rather than talking about rational numbers, we focus on the fact that these other numbers in our set, whatever they happen to be, violate axiom 6, insofar as they are nonzero non-successors.
Continuing on, then...
The Peano axioms only refer to the successor function. The WOP refers only the the ordering relation. You need an extra axiom if you want to relate the two.
I suppose this is where we disagree. I think that the order relation of a type ω order is isomorphic with the successor relation in peano arithmatic. They behave in exactly the same way. Thinking abstractly now: take a (countably infinite) set A of elements over which the well-ordering relation "<" is defined. Then the following properties hold:
1) There is a least element l in A
2) For every element a in A, the subset S of elements {b: b > a} has a least element
3) l is not in any subset S as defined in (2)
4) If c is the least element of the subset {x: x > a} and d is the least element of the subset {y: y > b}, then if c = d, then a = b
Each of these properties arises naturally from the definition of a well-ordered set. The first three are fairly obvious; the fourth comes (I'm pretty sure) from the fact that a well-order is also a total order.
Furthermore, if the order relation defines a well-order of type ω then the following holds:
6) If an element a in A is not the least element, then for some element b in A, it is the least element of a subset of elements {x: x > b}
(6) is false for sets of order type ω + 1, ω + ω, etc. -- but it is true for sets of order type ω.
Properties 1-4 and 6 arise from the definition of a well-order of type ω. Don't they rather resemble the peano axioms + 6?
I'm going to reiterate here that I agree that the WOP alone is not equivalent to induction. But the reason I believe this is that ω + 1 (for example) is a well-order, but it doesn't satisfy (6).
Yeah, I agree, though you still need to take axiom 7 (implicitly or explicitly) to define the successor function. It's interesting that only axiom 7 and a type ω ordering are sufficient to generate the entire set of Peano axioms.
Well, I'm glad we mostly agree.
Incidentally -- I really like this blog. I probably should have said that earlier, come to think of it.
Need help for my thesis title, Something related to Peano Axioms and something which is easy to do/understand. :)
If we choose a two-element subset which contains one domino from each row, then this subset doesn't have a smallest element. The elements are not related. So your example doesn't obey WOP.
The ordering I implied is that a is less than b if a is to the left of b. It doesn't need to be directly to the left.
Post a Comment