Equine paradox

The horse Paradox (engl. Horse paradox ) is an apparent paradox that on an incorrect application of the method of proof of the complete induction is based, thus providing evidence for the (nonsensical) statement alleged that all horses must have the same color. It is a standard example of incorrect use of full induction and is occasionally attributed to the mathematician George Pólya (1887–1985) in the literature .

Sham paradox

The supposed paradox is that on the one hand the statement that all horses have the same color is obviously wrong or contradicts empirical experience, but on the other hand one has mathematical proof of its correctness. However, since the evidence contains a subtle mistake in reasoning, it is of course only a sham paradox. In the following, the incorrect induction proof is first reproduced without further comment and the reasoning error is then explained in the next section.

Induction proof

Horse paradox, induction step works only for and not for

{\ displaystyle n \ geq 2}

{\ displaystyle n = 1}

The statement to be proven can be formulated as follows:

In a herd of horses, all horses are the same color ${\ displaystyle n}$ ${\ displaystyle n}$ .

Now one performs an induction over and anchors the induction for . ${\ displaystyle n}$ ${\ displaystyle n = 1}$

Induction anchoring

If the herd consists of only one horse, all horses in the herd are obviously of the same color.

Induction step

Now one assumes that the statement already applies to every herd with horses and shows that it then also applies to every herd with horses. A herd of horses is split into a herd of horses and a single horse. In the herd with horses, according to the induction assumption, they all have the same color, but it is still unclear whether this corresponds to that of the individual horse. Now you remove another horse from the herd with horses of the same color , so you now have a herd of the same color, a single horse that has the same color as the herd, and a single horse of an unknown color. Now you combine the single horse of unknown color with the herd of horses to form a new herd of horses. According to the induction requirement, all horses in this new herd must be of the same color and thus have the same color as the previous herd of horses and the previously removed individual horse of the same color . So you have horses of the same color in total . ${\ displaystyle n}$ ${\ displaystyle n + 1}$ ${\ displaystyle n + 1}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n-1}$ ${\ displaystyle n-1}$ ${\ displaystyle n}$ ${\ displaystyle n-1}$ ${\ displaystyle n + 1}$

Mistake in reasoning

The induction step itself is correct, but it requires a herd of at least two horses so that the additional single horse of unknown color takes on the color of the previous herd. If the herd consists of only one horse, after removing a horse of the same color, an empty herd is added to which the horse of unknown color is inserted. The empty herd, however, has no color that could be transferred to the horse of unknown color by induction. In other words, the original herd of horses and the new herd of horses in which one horse has been replaced by the horse of unknown color need to have a non-empty intersection. For a correct proof, the induction anchoring would therefore have to be performed for instead of for . However, this is not possible as there is no guarantee that any two horses will be the same color. ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n = 2}$ ${\ displaystyle n = 1}$

Others

In the literature, the equine paradox is sometimes attributed to the mathematician George Pólya (1887–1985). He described it, among other things, in his 1954 book Induction and Analogy in Mathematics in an exercise, but there is no mention of horses, instead the statement Any n girls have eyes of the same color (Eng. “N girls always have the same Eye color ") examined. In general, one can, of course, carry out the incorrect induction proof for any properties of elements of a set, which is why the problem is often covered in different ways in the literature. In the German-speaking world, based on the saying , all cats are gray at night, it is often proven that all cats are gray. In 1961, the biomathematist Joel E. Cohen published the satirical article On the nature of mathematical proofs , which contains a presentation of the incorrect induction proof using horses.

literature

Piotr Łukowski: Paradoxes . Springer, 2011, ISBN 9789400714762 , p. 15
Anne Rooney: The History of Mathematics . Rosen Publishing Group, 2012, ISBN 9781448873692 , p. 198
Miklos Bona: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory . World Scientific, 2006, ISBN 9789812568854 , pp. 23-24
Peter van Dongen: Introductory course in mathematics and calculation methods: For students of physics and other mathematical and natural science subjects . Springer, 2015, ISBN 9783658075200 , p. 41
Karsten Wolf: Precise thinking for computer scientists . Springer, 2017, ISBN 9783662549735 , pp. 120-121

Web links

All things are the same . Mathematical preliminary course, script Uni Bielefeld 2010, p. 16
All Horses are the Same Color in the ProofWiki
M. Junk, M. Rheinländer: All horses are the same color . Analysis I - supplement sheet, November 2005, University of Konstanz

Individual evidence

^ Piotr Łukowski: Paradoxes . Springer, 2011, ISBN 9789400714762 , p. 15
↑ ^a ^b ^c ^d Karsten Wolf: Precise thinking for computer scientists . Springer, 2017, ISBN 9783662549735 , pp. 120-121
↑ ^a ^b ^c Miklos Bona: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory . World Scientific, 2006, ISBN 9789812568854 , pp. 23-24
^ Anne Rooney: The History of Mathematics . Rosen Publishing Group, 2012, ISBN 9781448873692 , p. 198
↑ Peter van Dongen: Introductory course in mathematics and calculation methods: For students of physics and other mathematical and natural science subjects . Springer, 2015, ISBN 9783658075200 , p. 41
^ George Pólya : Induction and Analogy in Mathematics . Princeton University Press, 1954, p. 120
↑ See for example: Nicola Oswald, Jörn Steuding: Elementary Number Theory: A gentle introduction to higher mathematics . Springer, 2014, ISBN 9783662442487 , p. 39
↑ Joel E. Cohen: On the nature of mathematical proofs , Worm Runner's Digest, III (3), 1961 (reprinted in Robert L. Weber, E. Mendoza, Eric Mendoza: A Random Walk in Science . CRC Press, 1973, ISBN 9780854980277 , pp. 34-36 )

[Łukowski-1] Piotr Łukowski: Paradoxes . Springer, 2011, ISBN 9789400714762 , p. 15

[Wolf-2] Karsten Wolf: Precise thinking for computer scientists . Springer, 2017, ISBN 9783662549735 , pp. 120-121

[Bona-3] Miklos Bona: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory . World Scientific, 2006, ISBN 9789812568854 , pp. 23-24

[Rooney-4] Anne Rooney: The History of Mathematics . Rosen Publishing Group, 2012, ISBN 9781448873692 , p. 198

[5] Peter van Dongen: Introductory course in mathematics and calculation methods: For students of physics and other mathematical and natural science subjects . Springer, 2015, ISBN 9783658075200 , p. 41

[6] George Pólya : Induction and Analogy in Mathematics . Princeton University Press, 1954, p. 120

[7] See for example: Nicola Oswald, Jörn Steuding: Elementary Number Theory: A gentle introduction to higher mathematics . Springer, 2014, ISBN 9783662442487 , p. 39

[Cohen-8] Joel E. Cohen: On the nature of mathematical proofs , Worm Runner's Digest, III (3), 1961 (reprinted in Robert L. Weber, E. Mendoza, Eric Mendoza: A Random Walk in Science . CRC Press, 1973, ISBN 9780854980277 , pp. 34-36 )