The Horse paradox refers to the following (invalid) proof of the statement All horses are the same colour.

We use the principle of mathematical induction. As the basis case, we note that in a set containing a single horse, all horses are clearly the same colour. Now assume the truth of the statement for all sets of at most n horses. Let there be n+1 horses in a set. Remove the first horse to get a set of n horses. By the induction assumption, all horses in this set are the same colour. It remains to show that this colour is the same as that of the horse we removed. But this is easy: put back the first horse, take out a different horse and apply the induction principle to this set of n horses. Thus all horses in any set of n+1 horses are the same colour. By the principle of induction, we have established that all horses are the same colour.

The hole in the above "proof" is easy to spot with a little thought: it makes the implicit assumption that the two subsets of horses to which we apply the induction assumption have a common element, but this fails when n=1.

Thus this "paradox" is merely the result of flawed reasoning; it exposes the pitfalls arising from failure to consider special cases for which a general statement may be false.

Another horse paradox

A farmer has 11 horses, and he dies. His will says that his oldest son is to receive 1/2 of the horses in his stable, his middle son is to receive 1/4 of the horses, and the youngest son is to receive 1/6 of the horses. How can the horses be divided?

The lawyer rides to the farm, bringing his own horse. Now there are 12 horses in the stable. The eldest son receives 6 horses, the middle son receives 3 horses, and the youngest son receives 2 horses. The lawyer then takes back his horse.

This paradox works because the farmer, in giving 1/2, 1/4, and 1/6 of his horses, has not given away all of his horses but instead only 11/12 of them. Therefore without the 12th horse, the will gives away 10.083333 horses and leaves 0.916667 horses remaining. Adding the final horse evens out the fractions and allows the 1 remaining horse that the farmer did not give away to return to the lawyer.

A word play

Another "paradox" involving horses is a word-play by Raymond Smullyan, a "proof" that all horses have thirteen legs. First take all your horses and paint them red. Now look at the horses. If all the horses have thirteen legs, then we can stop. But what if one or more of the horses don't have thirteen legs? Well, that would be a horse of a different colour! However, we've painted all of them the same color, so there can't be any such horse: all horses have thirteen legs.

Here Smullyan is making a pun on the phrase "that would be a horse of a different colour", which means roughly "that horse would be different from the rest of the group," apart from the fallacy in assuming that if a horse doesn't have thirteen legs it is different from the rest of the group. Such a statement would be correct only if we were to know that there is a thirteen-legged horse in the group and that there is a horse without thirteen legs.

A related paradox

Also incorrect is the argument that all horses have nine tails: After all, no horse has eight tails, and every horse has one tail more than no horse. Therefore, all horses have nine tails.

This is a word-play that hinges on the use of "no horse" — an empty set in terms of set theory — as something we can assign a number of tails to. But if you say it fast, you might leave the listener scratching their head.