Hacker News Reader

Comment by georgeoliver | Hacker News Reader

Wow, I guess I should have studied logic!

Can someone explain in English how the author goes from "[now] suppose for all sets of n horses, every horse in the set has the same color" to 'proving' anything?

View on HN

Though incorrect, this is meant to be an example of proof by induction. Proof by induction is (to simplify a little) where you prove that any number N+1 will have a given property as long as N has that property. You can use this same rule twice to prove that N+2 has this property, and so on.

Finally, you prove that any arbitrary number (say, 1) has the property in another way, and you've proven that property for all N greater than or equal to 1.

The error in the proof is explained in the linked page, but basically the problem is that the proof that N implies N+1 doesn't actually work for all N, and particularly it doesn't let us go from 1 to 2.

This is standard induction: let P(n) be some statement about the number n. If you can establish that P(n) implies P(n+1) for all n >= 1, and that P(1) is true, then P must be true for every positive integer. You can find many examples by googling for “induction proof”.

The problem in the proof is that the inductive step P(n) implies P(n+1) only holds for n >= 3, and so the fact that P(1) is true does not imply anything for the larger integers.

Okay, but my issue and I think the one of the OP is that even for n >= 3 how did they prove that all horses are the same color for n >= 3?

Yeah this is why I'm confused as well. I don't follow how if we assume n are the same color, that it implies anything about n+1. It sounds like the article is saying that the N+1 logic makes sense for n > 2, but I don't see how it does.

Assume (accept without questioning) that it’s a property of the universe that any group of 2 horses are the same color.

Now, say you have a group of 3 horses, A, B, and C. You can use your knowledge about groups of 2 horses here: A and B must be the same color because they are a group of 2 horses. B and C must be the same color for the same reason. So all the horses are the same color.

You can now use the proof for groups of 3 horses to prove the same fact about groups of 4 horses, and so on.

The flawed inductive proof tries to generalize this argument to all groups of n and n+1 horses. That is, assume the property is true for groups of n horses, and show that it logically follows that it’s true for groups of n+1 horses. The structure of the argument is the same as my 2/3 horses example. However, you can’t use an argument like that for any value of n, as it isn’t true for n=1. That is, it’s not true that if every group of 1 horses is the same color (a true fact in nature) then it follows that every pair of horses is the same color.

It’s more like “in a world where every group of n horses are the same colour”, no matter of whether that world is the real world or not, “prove that any group of n+1 horses are the same colour”. This inductive step proves nothing about the real world, it needs a base case to kick things off. If you can prove it true for n=5 say, then the inductive step gives you every higher number.

The idea is that if it holds for n = 3 then it holds for n > 3. The way to show that it holds for n = 3 is to show that it holds for n = 2, which it doesn't.

It's not proven in a vacuum: it's proven under the assumption that it's true for N-1. E.g. if we assume that all groups of 2 horses are the same color, we can prove that all groups of 3 horses are by labelling them A, B, C. A and B are the same color because they are a group of 2; B and C are the same color because they are also a group of 2; A and C are the same color transitively (or because they are also a group of 2). Therefore A, B, and C are the same color. This step is logically sound, and you can do this for any N greater than three.

The problem is that this fails when tried for N=2, because then each sub-group can have only one horse in it. We already know that each horse is the same color as itself, so we don't actually reveal any new information by doing this. Since it doesn't work for N=2, the base assumption used for the N=3 case is incorrect.

This is quite tricky to do, because it’s almost a sleight of hand and expressing it in English is like watching the trick from behind the magician - you can obviously see the wrongness.

But: if you skip a pair of horses (which is how the trick is done/the error introduced) it might be:

Assume any group of 3 horses are the same colour. Can we show that adding another horse will result in a group of horses that are all the same colour?

Well yes: take your new group of 4 horses, and extract 1. (h1). Three horses remain and they must by definition be the same colour. Put h1 back and extract a different horse (h2). Now three remain and must by definition be the same colour as each other.

But when h2 was out, h1 was part of a group that was all the same colour. And when h1 was out, h2 was part of a group that was all the same colour. Therefore they must all be the same colour. It doesn’t matter how many different horses you find and bring to your initial group of 3, the rules will mean the resulting group of 4 is always the same colour. And so it is true for a group of 4 horses.

By the same reasoning, it must then be true for a group of 5, and so on up to all horses.

So all horses are the same colour, so long as the first assumption (that any group of 3 horses must be the same colour) holds.

The trick/error is jumping from “a group of 1 horses must all be the same colour” to “a group of 3 horses must be the same colour” which is an easy jump to miss if you go from “1” to “n”, instead of “1” to “3”.

(The logic doesn’t work for a pair of horses, because once h1 is taken out there are no other horses left that h2 must be the same colour as.)

This is called proof by induction. There is an intuitive path to understand it: Consider the set of the natural numbers; it contains 0 (zero) and for any K which belongs to this set, its successor (K + 1) also does. It is clear that if a property if valid for 0 and, in the case it is valid for a K which is not 0 implies it is also valid for K + 1, then such property is valid for all natural numbers.

He does't. Read the last paragraph:

This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not n=1, but rather n=2. Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.

Reply on news.ycombinator.com