Bogus Induction

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: Understanding proofs includes the ability to spot mistakes in them. And as a test of that skill and also your understanding of induction, let me see if I can put one over on you. I'm going to show you a bogus proof by induction. And I'm going to prove something that's patently absurd. Namely, that all horses have the same color. Say they're all black. So, there's a bunch of black horses with maybe some highlighted brown manes.

I'm going to prove this by induction. And for a start, there's no n mentioned in the theorem, so that's common for various kinds of things that you need to prove by induction. So I have to rephrase it in terms of n. It's going to be by induction on n. The induction hypothesis is going to be that any set consisting of exactly n horses will all have the same color.

Let's proceed to prove this. Now, I'm going to use the base case n equals 1, just because I don't want to distract you with suspicions that the base case n equals 0, that is no horses, is cheating somehow. It would be, in fact, be perfectly legitimate to start with n equals 0 and argue that all the horses in the empty set have the same color, because there's nothing in the empty set. However, let's not get into that.

We'll start with n equals one. And indeed, if you look at any set of one horse, it is the same color of it as itself. And in fact, I've proved the base case n equals 1. Let's keep going.

Now, in the inductive step, I'm allowed to assume that n horses have the same color, where n is any number greater than or equal to 0. Now right here, students complain that that's not fair, because you're already assuming something false and that's absurd. Well, yeah, it is absurd. But that can't be the problem. I'm just allowed to assume an induction hypothesis. All I have to do is prove that n implies n plus 1. Since it's absurd, there ought to be some problem with the proof. Well, let's watch and see if there's a problem with the proof.

So again, I can assume that any set of n horses have the same color. I have to prove that any set of n plus 1 horses have the same color. How will I do that? Well, there's a set of n plus 1 horses, and let's consider the first n of those horses. Now by induction hypothesis, the first n of them have the same color. Black, maybe.

Also by induction hypothesis, the second set of n horses-- that is, all but the first horse-- have the same color. And what that tells me is that the first and the last horse have the same color as all of the horses in the middle. And therefore, in fact, they all have the same color. End of proof, QED.

So, there had better be something wrong. And what's wrong? Well, what's wrong is that the proof that P of n implies P of n plus 1 is wrong. It looked good, but the proof that P of n implies P of n plus 1 has to work for all n greater than or equal to the base case. And if you look at this proof, it doesn't work in the base case. When n is 1 and you're trying to go from the base case to two and so on by implication, the proof breaks down.

Because what happens with our argument in the case that we're trying to prove that P of n implies P of n plus 1 in the case that n equals 1, well in that case, there aren't any middle horses. N plus 1 is 2, so there's a first horse. And that's the first n horses. And then the second half of set of n horses is the other horse, and there are no middle horses that they both have a color in common with. So, the proof just broke there.

But, you might not have noticed because that was the only place it was broken. This is a case where we were misled by ellipsis, by the way. Where because I was drawing n plus 1 horses with-- showing a lot of horses with dots in the middle, it looked like there were some. But they weren't. And again, as I said, the point though is that the only fallacy in this proof was that it didn't work when n was one. But it certainly worked for implying that if all sets of two horses are the same, that does imply that all sets of three horses are the same color.

And again, it's a false, we'll imply anything, kind of example. But even here, the proof was logically OK. But if it breaks in one place, if there's one domino that's missing from the line when the one before it falls, the rest of them stop falling and the proof breaks down.

Free Downloads

Video


Caption

  • English-US (SRT)