# All horses are the same color variation

I'm having trouble understanding a variation of the famous "all horses are the same color" problem, and would like some help. While I am familiar with the original problem, and know what's wrong with it, this one is formulated a bit differently, and I'm a bit confused about how to approach it.

Hyp: When one horse in a group is red, so are all the others.

The proof that I'm supposed to debunk, then goes as follows:

For N = 1, the claim is true.

We assume that the claim goes for groups of the size N.

Now, let one in a group of N+1 horses be red. We consider this horse together with the N-1 others. We can conculde that these are also red, because of the assumption. Because of that, there is at least one red horse in the group of these N-1 horses, together with the one that we haven't considered, which means that the last horse is also red.

Can I apply the same principle where N=2 and the two subsets have no common elements? Because the way I look at it, when I try to do that and have $H_0$ and $H_1$, and argue that I'm saying that if I consider $H_0$ and all the other horses except $H_1$, if one is red, so are the others, and I have my red horse. Then I take all those nonexistent red horses together with $H_1$, the assumption tells us that $H_1$ is red too, which is wrong, since I can't compare a horse to nonexistent horses.

Now, I could just turn that in and be done with it, but I'd really like to understand what's going on? Namely, why can't someone argue that they can simply look at $H_0$ and $H_1$ together, and if $H_0$ is red, then the assumption tells us that $H_1$ too must be red. I feel like I'm close to understanding this, but still have a tiny bit missing.

Abstract this to the following: consider a property $P$ that elements of a subset of a finite set $X$ can have. The (false, of course) claim is:
Let $U\subseteq X$. If for one element $u_0\in U$ we have $P(u_0)$, then $\forall u\in U:P(u)$.
In your case, $X$ is the set of all horses on Earth, and $P(x)$ means "the horse $x$ is red."
The wrong proof is always the same (the one you wrote down), and the problem with it is always the $|U|=2$ case.
• Hm, I see. And regarding the argument in the last part of my question, could I propose a counter argument that looking at $H_0$ and $H_1$ together and using the assumption would effectively be the same as me just assuming P(n+1) is true? In other words, by doing that, I haven't proven that P(n) implies P(n+1), but just laid another assumption on top of another and called it a "proof"? – anonra Oct 7 '16 at 12:05
• When looking at a set with $n+1$ elements, you are allowed to assume that the statement is true for all sets with at most $n$ elements (by induction hypothesis). So when you are looking at the set with $2$ elements, you can safely assume that the statement is true for sets with $1$ element, i.e. if in a set with $1$ element, at least one is red, then all are. But you cannot use the argument on the set with $2$ elements. – Daniel Robert-Nicoud Oct 7 '16 at 12:20