Conference rusure::math

293.0. "A Horse of a Different Color" by ALIEN::POSTPISCHIL () Tue May 28 1985 15:50

My teacher for Abstract Algebra, Dr. Georgantas of Rochester Institute of
Technology, started the course with this "proof":

Theorem:	All horses are white.

Lemma:		All horses are the same color.

Proof of Lemma:

	This will be a proof by induction.  Let C(n) represent the statement
	"In any set of n horses, each horse is the same color as the rest."

	The Math Induction Theorem says:

		If S is a subset of the positive integers, and
		1 is in S, and
		if k is in S, then k+1 is in S, then
		S is the set of positive integers.

	Let S be the set of all positive integers n for which C(n) is true. 
	Clearly, S is a subset of the positive integers.  Also, C(1) is
	trivially true, so 1 is in S.

	Suppose k is in S.  Then C(k) is true.  To show C(k+1) is true,
	consider an arbitrary set of k+1 horses:

		+---------------------+
		| A   B   C   D . . . |
		+---------------------+

	(The +'s, -'s, and |'s are parts of a corral.  The letters are various
	horses.)  Now consider the set with horse A removed.  There is now
	a set of k horses.  Since C(k), horse B must be the same color as
	horse C.  Now consider the set with A returned and C removed.  This
	is again a set of k horses, so horse A must be the same color as
	horse B.  Since A is the same color as B and B is the same color as
	C, horse A is clearly the same color has every horse in the set of
	horses excluding A.  Thus the entire set of k+1 horses contains
	horses of the same color.  Therefore, C(k+1).

	So k is in S implies k+1 is in S.

	Therefore S is the set of positive integers, so C(n) is true for each
	positive integer n.  So no matter how many horses there are, they all
	must be the same color, since they are in the set of all horses.

Proof of Theorem:

	If you leave Rochester Institute of Technology by traveling west on
	Route 252, you will come to a farmhouse after 16.2 miles.  Tied
	to a post in front of the house is a white horse.  Since this horse
	is white, all horses must be white, by the lemma.
 
 
Are there any dissenting opinions?
 
 
				--edp

Actually, all horses are black.  I saw a black horse today. :-).

The induction proof needs 3 or more horses  (a distinct "A", "B", and "C").
Given c(1), you can't prove c(2).

Perhaps we should take the research approach, as follows:

Theory:  all horses are white.

"all horses are white" is equivalent to "all non-white things are non-horses."

So, I can start my research here by looking at non-white things.  Each one 
that I find that is a non-horse is evidence for "all non-white things are 
non-horses", and its equivalent "all horses are white."

Ok, my desk is non-white and it's not a horse.
    The wall is non-white and it's not a horse.
    The floor is non-white and its not a horse.

Of course, this is only three pieces of evidence.  Give me enough time and I'll
catalog as many pieces of evidence as you might require.

Martin Gardner discussed this proof in an old "Mathematical Games" column.

-Jim.

I also noticed the problem with the way the induction step was done.
However, this is easily corrected, and the proof valid.

The "Mathematical Games" column to which you refer concerns corroborative
evidence -- not proofs.  Certainly, any white horses can be considered
corroborative evidence for the assertion that all horses are white.  But
it's strange that any red pencils or black crows we find are also provide
corroborative evidence of the assertion, via its contrapositive.

re. .2 
all horses *are* black, but the proof is a horse of a different color...