Tag Archives: induction

robert Pet Peeves and Inductive Horses by

Put your math pants on ladies and gentleman, this one’s gonna be a vomitbuster.

This post will be about mathematical induction (if you aren’t familiar with induction, it’s a simple and powerful proof technique that is ubiquitous in mathematics. For the intuitive picture, go here). Well, it will sort of be about mathematical induction. This post will use mathematical induction to help express my hatred for incomplete explanations. We will prove the following theorem (anybody who has seen induction will have seen this theorem and the proof before.)

Theorem All horses are the same colour.

Proof. We will proceed by induction on the size of the set of horses. Suppose that we have a single horse. Then, clearly all (one) of our horses have the same colour. Assume inductively that for every collection of n horses, all the horses in A have the same colour. We will show that in every collection of n+1 horses, all the horses have the same colour.

Let H = {h(1), h(2), …, h(n+1)} be a collection of n+1 horses. Then we can choose two sub-collections of H: A = {h(1), h(2), …, h(n)} and B = {h(2), h(3), …, h(n+1)}. By our inductive assumption, all the horses in A and B have the same colour. It follows that the colour of h(1) is the same as the colour of h(2) which is the same as the colour of h(n+1), and so all the horses in H must have the same colour. Q.E.D.

Now, clearly all horses are not the same colour.

And so pretty!

Not the same colour.

Let’s name those two horses Flowerpot and Daffodil. Most explanations of why the above theorem is wrong go like this:

Teacher: Clearly, the set of horses P = {Flowerpot, Daffodil} is a contradiction to our theorem. So, class, what have we learned? When you’re doing induction, always check your base cases!

Right, but quite an unsatisfying explanation. This explains why the theorem is wrong. But why is the proof wrong? That’s actually a bit of a head scratcher.

Mmmmmm. Yellow.

Go on. Do it. Scratch that head. Get them lices out.

I mean, we followed all the steps of mathematical induction — we chose a base case, we proved that theorem was correct. We made an inductive assumption for some n, and using the assumption we proved the theorem holds for n+1. Where’s the problem?

Well, lets look at our proof. We have a set H of size n+1, which clearly can be done. We chose two subsets of H, A and B, both of size n. Also can be done. Next, we apply the inductive hypothesis to A and B, and so all the horses in A and B are the same colour. Now, since A and B have a non-empty intersection… Ahah. There’s the problem. What if n = 1? Then H = {h(1), h(2)}, and A = {h(1)}, B = {h(2)}. But then A and B have an empty intersection. If A is the set containing Flowerpot and B is the set containing Daffodil, then we cannot say that Flowerpot is the same colour as Daffodil. Okay! Great!

I think that this is fundamentally different from the broad sweep of “You didn’t check all your base cases”. This is really saying your logic used in the inductive step does not apply to all of the base cases. It’s subtle, but a very important difference. The pedagogical conclusion: teachers, think hard about what you’re presenting. When you think you understand something, it turns out that you usually don’t.

One more thing. In a way, the problem really comes from how I wrote H in the first place! Remember I wrote H = {h(1), h(2), …, h(n+1)}. When performing the partitioning of H into A = {h(1), h(2), …, h(n)} and B = {h(2), h(3), …, h(n+1)}, this suggests that the intersection of A and B is non-empty. This is an interesting instance of the form of our text affecting the content of our text (at least to us). This is an idea I will hopefully return to in later posts.

Finally, a moment of silence. Searching for an image of a head scratcher led me deep into a rabbit hole from which I may never return.

And you can barely even see it!

A nose straightener.