Main Page | See live article | Alphabetical index The Horse paradox refers to the following (invalid) proof of the statement All horses are the same color. 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 color. 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 color. It remains to show that this color 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 color. By the principle of induction, we have established that all horses are the same color. The hole in the above "proof" is easy to spot with a little thought: it makes the implicit assumption that the two sets 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. Table of contents 1 Another horse paradox 2 A Related Paradox, Concerning Cats 3 Yet another horse paradox Another horse paradox Somewhat related 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 would be a different situation". A Related Paradox, Concerning Cats Also false is the statement that all cats have nine tails. After all, no cat has eight tails, and every cat has one tail more than no cat. Therefore, all cats have nine tails. The paradox hinges on the use of 'no cat' - 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're sure to leave the listener scratching their head. Yet another horse paradox A farmer has 11 horses, and he dies. His will says that his eldest son is to receive 1/2 of the horses, 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 article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.