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.

Thank you for your help!


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.

  • $\begingroup$ 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"? $\endgroup$ – anonra Oct 7 '16 at 12:05
  • $\begingroup$ 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. $\endgroup$ – Daniel Robert-Nicoud Oct 7 '16 at 12:20
  • $\begingroup$ Oh my, you're absolutely right. This is exactly what I needed. Thanks a lot, kind stranger. $\endgroup$ – anonra Oct 7 '16 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.