WOP vs Induction [optional]

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: So we come to the part that a lot of students have been asking about, but which in fact is entirely optional. So that if you care to skip this little piece of video, you're welcome to. It's not going to appear on any exam or anything.

But people have consistently asked how they choose which method of proof to use among ordinary induction or strong induction or well-ordering. And the answer is that it's hard to tell them apart, because in an easy technical sense, they're really all equivalent. So let's look at them one by one.

First of all, it's clear that ordinary induction is a special case of strong induction. In the ordinary induction, you're allowed to assume only p of n. In strong, you can assign everything from p of 0 up to p of n to prove p of n plus 1. But you don't have to use all the extra assumptions. You could just use p of n so that any ordinary induction can be seen as just a special case of a strong induction. It would be a little misleading to call it strong induction, but it is strong induction.

So why bother with it? Well, the answers, basically, it's an expository difference. It helps your reader to know that the proof for n plus 1 is only going to depend on n not on the k's that are less than n as they would typically in a genuine strong induction proof.

Second, is some argument that an ordinary induction going from n to n plus 1 is more intuitive than strong induction that goes from anywhere less than or equal to n up to n plus 1. I'm not sure that I subscribe to that, but I've heard people make that claim.

All right. There's another perspective, which is interesting and maybe surprising, which is, why not always use ordinary induction? Oh, wait a minute. How do you replace strong induction with ordinary induction? Well it's easy. Suppose that you've proved for all m P of m using strong induction with induction hypothesis P of m, what have you done?

Well, it's the same base case whether you're using ordinary or strong. But in strong, you would do an inductive step where you actually assumed not just p of n, but P of for all k less than or equal to n. And then using all those hypotheses about P of k, you prove P of n plus 1 in the strong induction.

Well, how do you turn it into an ordinary induction? Just let Q of n be that assumption, that for all k less than or equal to n P of k. And if you think about it for a moment, just revising the induction hypothesis to include that universal quantifier, for all k less than or equal to n, means that the strong induction on P of k becomes an ordinary induction on Q of n. And we have a trivial change decorating a bunch of occurrences of formulas with for all we have converted and strong induction into an ordinary induction.

So we see that strong induction and no power above and beyond ordinary induction. It just lets you omit a bunch of universal quantifiers that would otherwise have to be made explicit if you were going to do it by ordinary induction. Then why use strong? Just precisely, because it's cleaner. You don't have to write those for all k less than or equal to ends all over.

And now we come to the final question about, what's the relation between the well-ordering principle in induction? Well, it's basically the same deal. You can easily rephrase an induction proof. An induction proof, just transform it's template to fit the template of a well-ordering proof and vice versa. We're not going into the details of exactly how, because it's not important, but it is routine.

It follows that well-ordering principle is not adding any new power or even new perspective on the mathematics of any given proof. It's just a different way to organize and tell the same story. And it also means conceptually, which is nice that these apparently different inference rules, strong induction, ordinary induction, well-ordering principle, there's really only one. And the others can be justified in terms of it and explained as variations of it.

So that's intellectually economical to not have a proliferation of different reasoning principles, which brings us to the question of which one to use. And all I can say is that it's a matter of taste. The truth is that when I'm writing up proofs, I will often try different versions. I'll try it by ordinary induction. And I'll try it by well-ordering. And I'll read the two and decide which one seems to come out the more cleanly. And I'll go with that one.

So there isn't any simple rule about which to choose. But in a certain sense, it really doesn't matter. Just pick one. The only exceptions to that, of course, is when on an exam or similar setting, you're told to use one of these particular methods as a way to demonstrate that you understand it, then, of course, you can't pick and choose.

So finally, we come to a pedagogical question about, why is it that in 6042 we taught well-ordering and principal first, in fact, the second lecture, and are only now at the end of third week getting to the induction principle, which is much more familiar, and people argue they like it better, at least most of them. Well, the answer is it's a pedagogical strategy. And it's one, in fact, which the authors disagree with, not united on.

My view is that we're better off doing well-ordering principles first. And the reason is that our impression from conversations with students, and surveys, and from exam performance shows that only about 20% of the students get induction no matter how hard we try to explain and teach it. They report worrying about things about that assuming P of n to prove p of n plus 1 is somehow circular. And it's certainly measurable that 20% or so of the class just can't reliably do proofs by induction.

Now this baffles the 80% to whom it's obvious and who know how to do it easily. And it baffles us instructors. We can't figure out what the problem is that those 20% have. And we've been trying to teach induction lots of different ways.

On the other hand, nobody has trouble believing the well-ordering principle and working with it. And they certainly don't have any harder time using it then they do using ordinary induction or strong induction. And this conceptual problem about is it safe and do I really believe in it just doesn't come up with a well-ordering principle. Everybody agrees that it's obvious that a non-negative set of a non-empty set of non-negative integers is going to have at least one.

And so we chose to do well-ordering right away, because there's no overhead in explaining it. And it lets us get going on interesting proofs from the get go as opposed to waiting a while or spending a couple of lectures working through induction and get leaving that with the main if only method that people have for proving things about non-negative integers.

Free Downloads

Video


Caption

  • English-US (SRT)