533:
81:
540:
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
295:
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
541:
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
526:
489:
452:
426:
400:
374:
344:
230:
168:
122:
318:
293:
273:
253:
204:
142:
495:
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
178:
The case with just one horse is trivial. If there is only one horse in the "group", then clearly all horses in that group have the same color.
45:. There is no actual contradiction, as these arguments have a crucial flaw that makes them incorrect. This example was originally raised by
57:
girls have eyes of the same color", as an exercise in mathematical induction. It has also been restated as "All cows have the same color".
275:
horses always are the same color. Likewise, exclude some other horse (not identical to the one first removed) and look only at the other
672:
714:
564:
20:
709:
545:; it seems to show by valid reasoning something that is manifestly false, but in fact the reasoning is flawed.
704:
724:
554:
532:
645:
676:
350:
We already saw in the base case that the rule ("all horses have the same color") was valid for
34:
660:
589:
499:
8:
468:
431:
405:
379:
353:
323:
209:
147:
101:
69:
65:
542:
303:
278:
258:
238:
189:
127:
95:
30:
559:
60:
The "horses" version of the paradox was presented in 1961 in a satirical article by
536:
Two differently colored horses, providing a counterexample to the general theorem.
606:
46:
719:
698:
640:
61:
376:. The inductive step proved here implies that since the rule is valid for
296:
last horse excluded are all of the same color, and we have proven that:
19:"Horse paradox" redirects here. For a Chinese white horse paradox, see
630:, Franklin, Beedle and Associates, 2012, Section "Induction Gone Awry"
80:
465:
The argument above makes the implicit assumption that the set of
84:
All horses are the same color paradox, induction step failing for
457:
Thus, in any group of horses, all horses must be the same color.
206:
horses always are the same color. Consider a group consisting of
675:. Harvey Mudd College Department of Mathematics. Archived from
492:
40:
68:, which in particular allowed the author to "prove" that
659:(R. L. Weber, ed.), Crane, Russak & Co., 1973, pp.
491:
horses has the size at least 3, so that the two proper
72:
did not exist, and he had an infinite number of limbs.
502:
471:
434:
408:
382:
356:
326:
306:
281:
261:
241:
212:
192:
150:
130:
104:
235:
First, exclude one horse and look only at the other
428:, which in turn implies that the rule is valid for
520:
483:
446:
420:
394:
368:
338:
312:
287:
267:
247:
224:
198:
162:
136:
116:
98:. First, we establish a base case for one horse (
696:
643:(1961), "On the nature of mathematical proofs",
628:Discrete Mathematics and Functional Programming
255:horses; all these are the same color, since
49:in a 1954 book in different terms: "Are any
613:. Princeton University Press. p. 120.
583:
531:
79:
601:
599:
173:
16:Paradox arising from an incorrect proof
697:
170:horses must also have the same color.
639:
622:
620:
605:
346:horses will also have the same color.
611:Induction and Analogy in Mathematics
596:
13:
617:
14:
736:
565:When a white horse is not a horse
320:horses have the same color, then
181:
144:horses have the same color, then
33:that arises from a flawed use of
21:When a white horse is not a horse
673:"All Horses are the Same Color"
75:
665:
633:
577:
460:
1:
570:
27:All horses are the same color
402:, it must also be valid for
7:
548:
10:
741:
555:Unexpected hanging paradox
18:
715:Horses in popular culture
124:). We then prove that if
657:A Random Walk in Science
584:Łukowski, Piotr (2011).
53:numbers equal?" or "Any
37:to prove the statement
710:Mathematical paradoxes
537:
522:
485:
448:
422:
396:
370:
340:
314:
289:
269:
249:
226:
200:
164:
138:
118:
91:
35:mathematical induction
588:. Springer. pp.
535:
523:
521:{\displaystyle n+1=2}
486:
449:
423:
397:
371:
341:
315:
290:
270:
250:
227:
201:
165:
139:
119:
83:
64:. It was stated as a
646:Worm Runner's Digest
500:
469:
432:
406:
380:
354:
324:
304:
279:
259:
239:
210:
190:
174:Base case: One horse
148:
128:
102:
705:Inductive fallacies
484:{\displaystyle n+1}
447:{\displaystyle n=3}
421:{\displaystyle n=2}
395:{\displaystyle n=1}
369:{\displaystyle n=1}
339:{\displaystyle n+1}
225:{\displaystyle n+1}
163:{\displaystyle n+1}
117:{\displaystyle n=1}
70:Alexander the Great
725:Mathematical humor
626:Thomas VanDrunen,
543:falsidical paradox
538:
518:
481:
444:
418:
392:
366:
336:
310:
285:
265:
245:
222:
196:
160:
134:
114:
96:proof by induction
92:
43:are the same color
31:falsidical paradox
560:List of paradoxes
313:{\displaystyle n}
288:{\displaystyle n}
268:{\displaystyle n}
248:{\displaystyle n}
199:{\displaystyle n}
137:{\displaystyle n}
732:
689:
688:
686:
684:
679:on 12 April 2019
669:
663:
654:
637:
631:
624:
615:
614:
603:
594:
593:
581:
528:
527:
525:
524:
519:
490:
488:
487:
482:
453:
451:
450:
445:
427:
425:
424:
419:
401:
399:
398:
393:
375:
373:
372:
367:
345:
343:
342:
337:
319:
317:
316:
311:
294:
292:
291:
286:
274:
272:
271:
266:
254:
252:
251:
246:
231:
229:
228:
223:
205:
203:
202:
197:
169:
167:
166:
161:
143:
141:
140:
135:
123:
121:
120:
115:
94:The argument is
90:
56:
52:
740:
739:
735:
734:
733:
731:
730:
729:
695:
694:
693:
692:
682:
680:
671:
670:
666:
655:. Reprinted in
638:
634:
625:
618:
604:
597:
582:
578:
573:
551:
501:
498:
497:
496:
470:
467:
466:
463:
433:
430:
429:
407:
404:
403:
381:
378:
377:
355:
352:
351:
325:
322:
321:
305:
302:
301:
280:
277:
276:
260:
257:
256:
240:
237:
236:
211:
208:
207:
191:
188:
187:
184:
176:
149:
146:
145:
129:
126:
125:
103:
100:
99:
85:
78:
54:
50:
24:
17:
12:
11:
5:
738:
728:
727:
722:
717:
712:
707:
691:
690:
664:
641:Cohen, Joel E.
632:
616:
595:
575:
574:
572:
569:
568:
567:
562:
557:
550:
547:
517:
514:
511:
508:
505:
480:
477:
474:
462:
459:
443:
440:
437:
417:
414:
411:
391:
388:
385:
365:
362:
359:
348:
347:
335:
332:
329:
309:
284:
264:
244:
221:
218:
215:
195:
183:
182:Inductive step
180:
175:
172:
159:
156:
153:
133:
113:
110:
107:
77:
74:
15:
9:
6:
4:
3:
2:
737:
726:
723:
721:
718:
716:
713:
711:
708:
706:
703:
702:
700:
678:
674:
668:
662:
658:
652:
648:
647:
642:
636:
629:
623:
621:
612:
608:
607:Pólya, George
602:
600:
591:
587:
580:
576:
566:
563:
561:
558:
556:
553:
552:
546:
544:
534:
530:
515:
512:
509:
506:
503:
494:
478:
475:
472:
458:
455:
441:
438:
435:
415:
412:
409:
389:
386:
383:
363:
360:
357:
333:
330:
327:
307:
299:
298:
297:
282:
262:
242:
233:
219:
216:
213:
193:
179:
171:
157:
154:
151:
131:
111:
108:
105:
97:
88:
82:
73:
71:
67:
63:
62:Joel E. Cohen
58:
48:
44:
42:
36:
32:
28:
22:
681:. Retrieved
677:the original
667:
656:
650:
644:
635:
627:
610:
585:
579:
539:
464:
456:
349:
234:
186:Assume that
185:
177:
93:
86:
76:The argument
59:
47:George Pólya
38:
26:
25:
683:10 November
461:Explanation
454:and so on.
699:Categories
571:References
586:Paradoxes
609:(1954).
549:See also
232:horses.
493:subsets
41:horses
720:Color
661:34-36
66:lemma
29:is a
685:2023
39:All
653:(3)
651:III
300:If
89:= 1
701::
649:,
619:^
598:^
590:15
529:.
687:.
592:.
516:2
513:=
510:1
507:+
504:n
479:1
476:+
473:n
442:3
439:=
436:n
416:2
413:=
410:n
390:1
387:=
384:n
364:1
361:=
358:n
334:1
331:+
328:n
308:n
283:n
263:n
243:n
220:1
217:+
214:n
194:n
158:1
155:+
152:n
132:n
112:1
109:=
106:n
87:n
55:n
51:n
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.