A Horse of a Different Color

Using the principle of induction, we will now show that there is no such thing as a "horse of a different color".

A brief review of Proof by Induction

Stated briefly, if something is provably true for sets of 1 member, and if it can be shown that, if it is true for any set of N members, then it is also true for all sets of N+1 members, then it must be true for all sets no matter how large.

For, if that were not the case, we need merely find the smallest set for which it is false. Call it S. Suppose that set S contains M members. Take one away; now we have a set of M-1 members, which we will call T. But since we just said S was the smallest set for which the theorem was false, then it must be true for T, right?  Because, after all, T is smaller than S.  But part of our “proof” consisted of showing that, should the fact be true for a set of size M, then it must also be true of a set of size M+1. So, if it’s true for T, it must be true for S too, since S is just one larger than T.  And that’s how induction works.

Now, let’s get back to the horses.

Definitions

A herd of horses is a bunch of horses.
A monochromatic herd of horses is a herd of horses that are all the same color.

Basis Step

Every herd containing just one (1) horse is (obviously) monochromatic – that is, all the horses in a herd of 1 horse are the same color.

Induction Step

Assume we’ve proved that all herds containing at least N horses are monochromatic.  Now, consider a herd of N+1 horses.

If we take any horse away from the herd of N+1 horses – horse H, for instance – then we’re left with a herd of N horses. That herd must be monochromatic, by assumption.  Now, put horse H back into the herd, and remove a different horse – call it horse K.

Now, the herd again has N horses in it, so, once again, it must be monochromatic. That shows that horse H, which we just put back in, is the same color as all the rest of the horses in the herd (otherwise the herd wouldn’t be monochromatic now that H is back in it).

But the same argument requires that horse K also be the same color as the rest of the horses in the herd – otherwise the herd wouldn’t have been monochromatic when K was in and H was out.

But then if H and K are both the same color as the rest of the horses in the herd, they must be the same color as each other, too.

Therefore, when H and K are both put back into the herd, the herd must necessarily still be monochromatic.

Conclusion

All herds of horses, no matter how many horses they contain, must be monochromatic.
Now, put all the horses in the world into one herd. That herd must be monochromatic, too.

Therefore, all the horses on Earth are the same color.

---

I would like to attribute this rather charming proof but I don't know where it originated.  I ran across it in college, about 30 years ago.  The error in the proof (yes, there is an error in it!) is actually quite a common error in induction proofs, and hence it has some expository value.