All horses are the same color (paradox)

The horse paradox is a falsidical paradox that arises from flawed demonstrations, which purport to use mathematical induction, of the statement All horses are the same colour. The paradox does not truly exist, as these arguments have a crucial flaw that makes them incorrect. This example was used by George Pólya as an example of the subtle errors that can occur in attempts to prove statements by induction.

The argument

The flawed argument claims to be based on mathematical induction, and proceeds as follows.

Suppose that we have a set of 5 horses. We wish to prove that they are all the same colour. Suppose that we had a proof that all sets of 4 horses were the same colour. If that were true, we could prove that all five horses are the same colour by dividing the horses into two overlapping groups of four horses each. By our supposed existing proof, since these are groups of 4, all horses in them must be the same colour. For example, the first, second, third and fourth horses constitute a group of four, and thus must all be the same colour; and the second, third, fourth and fifth horses also constitute a group of four and thus must also all be the same colour. For this to occur, all five horses in the group of 5 must be the same colour.

But how are we to get a proof that all sets of 4 horses are the same colour? We apply the same logic again. By the same process, a group of 4 horses could be broken down into groups of 3, and then a group of 3 horses could be broken down into groups of 2, and so on. Eventually we will reach a group size of 1, and it is obvious that all horses in a group of 1 horse must be the same colour.

By the same logic we can also increase the group size. A group of 6 horses can be broken down into groups of 5, and so on upwards, so that all finite sized groups of horses must be the same colour.

Explanation

The argument above makes the implicit assumption that the two subsets of horses to which the induction assumption is applied have a common element. This is not true when n = 1, that is, when the original set only contains 2 horses.

Indeed, let the two horses be horse A and horse B. When horse A is removed, it is true that the remaining horses in the set are the same colour (only horse B remains). If horse B is removed instead, this leaves a different set containing only horse A, which may or may not be the same colour as horse B.

The problem in the argument is the assumption that because each of these two sets contains only one colour of horses, the original set also contained only one colour of horses. Because there are no common elements (horses) in the two sets, it is unknown whether the two horses share the same colour. Thus the horse paradox is not truly a paradox, but merely the result of flawed reasoning. The horse paradox exposes the pitfalls arising from failure to consider special cases for which a general statement may be false.

References

• Enumerative Combinatorics by George E. Martin, ISBN 0-387-95225-X

See also

• Pólya's proof that there is no "horse of a different color"

es:Paradoja del caballo gl:Paradoxo do cabalo he:פרדוקס הסוס lt:Arklių paradoksas hu:Ló-paradoxon pl:Paradoks koni ru:Доказательство одноцветности всех лошадей sv:Alla hästar har samma färg