Show that all horses are of the same color.

Im trying to understand the solution about this, and all the other solutions are.. a bit weird for me and dont answer all my questions!

Reference : Questions on "All Horse are the Same Color" Proof by Complete Induction

Im using the answer there as reference, but my understanding is a bit different!

Find the error in the following proof that all horses are the same color. CLAIM: In any set of h horses, all horses are the same color.

PROOF: By induction on h.

Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color. Induction step: For k > I assume that the claim is true for h = k and prove that it is true for h = k + 1. Take any set H of k + 1 horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set H1 with just k horses. By the induction hypothesis, all the horses in H, are the same color. Now replace the removed horse and remove a different one to obtain the set H2 . By the same argument, all the horses in H2 are the same color. Therefore all the horses in H must be the same color, and the proof is complete.

Here's what i have come up with :

Suppose a set of 1 horse. $H_a = { horse_{1} }$

Obviously, all the horses in set $H_a$ are the same, since theres just 1 horse.

So using that as the Basis of the induction we can proceed and try to prove its true for $N$ horses.

-- I dont fully understand the part below

As an example : set $H_0$ :

$H_0 = { horse_{1}, horse_{2}, horse_{3}... horse_{n} }$

In my understanding, its because, I can make a subset formed by 1 horse :

$K_1 = {horse_{1}}$ $K_2 = {horse_{2}}$ ...

I don't get it. I clearly know that this proof is a lie. And for me, its because you cant claim theres a relation on a set with size $>= 2$ , since :

$H_1 = { horse_{1}, horse_{2}}$

Theres nothing that says $horse_{1}$ equals $horse_{2}$. The basis was for one horse. But that alone is not a proof.

So what should I do ?

Solution 1:

The mistake is in the inductive step. The reasoning assumes that there is a $horse_1$ that you can remove, leaving you a set of $k$ horses that, by inductive hypothesis, all have the same color. OK, so far so good. But then it says we can put $horse_1$ back, and remove $horse_2$, and so this new set of $k$ horses have the same color as well. Also good!

OK, but why then doesn't this show that all $k+1$ horses have the same color?! Because if $k =1$, then $horse_1$ and $horse_2$ are the only two horses! And, yes, removing $horse_1$ leaves all remaining horses (which is just $horse_2$) the same color, and the same goes for removing $horse_2$: the only remaining horse is $horse_1$, and all those $k=1$ horses are the same color. But obviously we can not conclude that all $k+1 =2$ horses have the same color!

Of course, the reasoning would go through for $k>1$, for then you would have a $horse_3$ that, when $horse_1$ is removed must have the same color as $horse_2$, and that, when $horse_2$ is removed, must have the same color as $horse_1$, and thus $horse_1$, $horse_2$, $horse_3$, and any other horses would indeed have to have the same color.

But of course: if you assume that any $2$ horses always have the same color, then obviously any sized group of horses will all have the same color.

So, it is really just that 1 case (with 2 horses) that is the crucial case, and neither the base case nor the inductive step cover that case. Or, to be exact: the base doesn't cover it at all, and the reasoning in the inductive step fails for that particular case.