A Horse of a Different Color
Using the principle of induction, we will now show that there is no
as a "horse of a different color".
A brief review of Proof by Induction
something is provably true for sets of 1 member, and
can be shown that, if
it is true for any set of N
it is also true for all sets of N
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
members. Take one away; now we have a set of M
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
one larger than T
. And that’s how induction works.
Now, let’s get back to the horses.
of horses is a bunch of
herd of horses
is a herd of horses that are all the same color.
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.
Assume we’ve proved that all herds
containing at least N
are monochromatic. Now, consider a herd of N
If we take any
horse away from the herd of N
+1 horses – horse H
instance – then we’re left with a herd of N
herd must be monochromatic, by assumption. Now, put
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
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
But then if H
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
put back into the herd, the herd
must necessarily still be monochromatic.
All herds of
horses, no matter how many horses they contain, must be
Now, put all the
horses in the world into one herd. That herd must be monochromatic,
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