
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
M1
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.