Editing All horses are the same color

{{Short description|Paradox arising from an incorrect proof}}
{{redirect|Horse paradox|a Chinese white horse paradox|When a white horse is not a horse}}
'''All horses are the same color''' is a [[falsidical paradox]] that arises from a flawed use of [[mathematical induction]] to prove the statement ''All horses are the same color''.<ref>{{cite book|title=Paradoxes|last=Łukowski|first=Piotr|publisher=Springer |year=2011|pages=[https://books.google.com/books?id=p0bpyag497oC&pg=PA15 15]}}</ref> There is no actual contradiction, as these arguments have a crucial flaw that makes them incorrect. This example was originally raised by [[George Pólya]] in a 1954 book in different terms: "Are any {{mvar|n}} numbers equal?" or "Any {{mvar|n}} girls have eyes of the same color", as an exercise in mathematical induction.<ref name=po120>{{cite book|title=Induction and Analogy in Mathematics|last=Pólya|first=George|publisher=Princeton University Press|year=1954|page= 120|author-link=George Pólya}}</ref> It has also been restated as "All cows have the same color".<ref name="TvD">Thomas VanDrunen, ''Discrete Mathematics and Functional Programming'', Franklin, Beedle and Associates, 2012, Section "Induction Gone Awry"</ref>

The "horses" version of the paradox was presented in 1961 in a satirical article by [[Joel E. Cohen]]. It was stated as a [[lemma (mathematics)|lemma]], which in particular allowed the author to "prove" that [[Alexander the Great]] did not exist, and he had an infinite number of limbs.<ref>{{citation|title=On the nature of mathematical proofs|first=Joel E.|last=Cohen|author-link=Joel E. Cohen|year=1961|journal= [[Worm Runner's Digest]]|volume=III|issue=3}}. Reprinted in ''A Random Walk in Science'' (R. L. Weber, ed.), Crane, Russak & Co., 1973, pp. [https://books.google.com/books?id=UGGhM2XKE_0C&pg=PA34 34-36]</ref>

== The argument ==
[[File:Horses induction2.svg|thumb|All horses are the same color paradox, induction step failing for {{math|1=''n'' = 1}}]]
The argument is [[proof by induction]]. First, we establish a base case for one horse (<math>n=1</math>). We then prove that if <math>n</math> horses have the same color, then <math>n+1</math> horses must also have the same color.

===Base case: One horse===
If there is only one horse in the "group", then clearly all horses in that group have the same color; for the colors of the horses in a group to not be homogeneous, there must be at least two horses of different colors, but since there are no two horses in this case’s group in the first place, this requirement is necessarily absent.

===Inductive step===
Assume that <math>n</math> horses always are the same color. Consider a group consisting of <math>n+1</math> horses.

First, exclude one horse and look only at the other <math>n</math> horses; all these are the same color, since <math>n</math> horses always are the same color. Likewise, exclude some other horse (not identical to the one first removed) and look only at the other <math>n</math> horses. By the same reasoning, these, too, must also be of the same color. Therefore, the first horse that was excluded is of the same color as the non-excluded horses, who in turn are of the same color as the other excluded horse. Hence, the first horse excluded, the non-excluded horses, and the last horse excluded are all of the same color, and we have proven that:
*If <math>n</math> horses have the same color, then <math>n+1</math> horses will also have the same color.

We already saw in the base case that the rule ("all horses have the same color") was valid for <math>n=1</math>. The inductive step proved here implies that since the rule is valid for <math>n=1</math>, it must also be valid for <math>n=2</math>, which in turn implies that the rule is valid for <math>n=3</math> and so on.

Thus, in any group of horses, all horses must be the same color.<ref name=po120/><ref>{{cite web|url=https://math.hmc.edu/funfacts/all-horses-are-the-same-color/|title=All Horses are the Same Color|publisher=Harvey Mudd College Department of Mathematics|access-date=10 November 2023|archive-date=12 April 2019|archive-url=https://web.archive.org/web/20190412105542/https://www.math.hmc.edu/funfacts/ffiles/30002.8.shtml|url-status=dead}}</ref>

==Explanation==
The argument above makes the implicit assumption that the set of  <math>n+1</math> horses has the size at least 3,<ref name=TvD/> so that the two proper [[subset]]s of horses to which the induction assumption is applied would necessarily share a common element. This is not true at the first step of induction, i.e., when {{nobr|<math>n+1=2</math>}}.

[[File:Horses in Boone County, Indiana - 2015 - Norm 01.jpg|alt=Two horses standing in a field, one is brown and the other is black.|thumb|Two differently colored horses, providing a [[counterexample]] to the general theorem]]

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 color (only horse B remains). The same is true when horse B is removed. However, the statement "the first horse that was excluded is of the same color as the non-excluded horses, who in turn are of the same color as the other excluded horse" is meaningless, because there are no "non-excluded horses" (common elements (horses) in the two sets, since each horse is excluded once). Therefore, the above proof has a logical link broken. The proof forms a [[falsidical paradox]]; it seems to show by valid reasoning something that is manifestly false, but in fact the reasoning is flawed.

== See also ==
* [[Unexpected hanging paradox]]
* [[List of paradoxes]]
* [[When a white horse is not a horse]]
* [[Principle of explosion]]

==References==
{{reflist}}

[[Category:Inductive fallacies]]
[[Category:Horses in popular culture]]
[[Category:Color]]
[[Category:Mathematical humor]]
[[Category:1961 introductions]]