Das Pferde-Paradox (engl. horse paradox[1]) ist ein scheinbares Paradox, das auf einem fehlerhaften Anwenden der Beweismethode der vollständigen Induktion beruht und dadurch vermeintlich einen Beweis für die (unsinnige) Aussage liefert, dass alle Pferde die gleiche Farbe besitzen. Es ist ein Standardbeispiel für den fehlerhaften Umgang mit der vollständigen Induktion und wird in der Literatur gelegentlich dem Mathematiker George Pólya (1887–1985) zugeschrieben.

Scheinparadox

Bearbeiten

Das vermeintliche Paradox besteht darin, dass einerseits die Aussage, dass alle Pferde die gleiche Farbe besitzen, offensichtlich falsch ist beziehungsweise der empirischen Erfahrung widerspricht, man aber andererseits einen mathematischen Beweis für deren Richtigkeit besitzt. Da der Beweis jedoch einen subtilen Denkfehler enthält, ist es natürlich nur ein Scheinparadox. Im Folgenden wird zunächst der fehlerhafte Induktionsbeweis ohne weiteren Kommentar wiedergegeben und der Denkfehler dann anschließend im nächsten Abschnitt erläutert.

Induktionsbeweis

Bearbeiten
 
Pferde-Paradox, Induktionsschritt funktioniert nur für   und nicht für  

Die zu beweisende Aussage kann wie folgt formuliert werden:[2]

In einer Herde mit   Pferden besitzen alle   Pferde die gleiche Farbe.

Nun führt man eine Induktion über   durch und verankert die Induktion für  .

Induktionsverankerung

Bearbeiten

Besteht die Herde nur aus einem Pferd, so besitzen offensichtlich alle Pferde der Herde die gleiche Farbe.[3][2]

Induktionsschritt

Bearbeiten

Nun setzt man voraus, dass die Aussage bereits für jede Herde mit   Pferden gilt und zeigt, dass sie dann auch für jede Herde mit   Pferden gilt. Eine Herde mit   Pferden spaltet man in eine Herde von   Pferden und ein einzelnes Pferd auf. In der Herde mit   Pferden besitzen nun nach Induktionsvoraussetzung alle die gleiche Farbe, allerdings ist noch unklar, ob diese der des einzelnen Pferdes entspricht. Nun entfernt man ein weiteres Pferd aus der Herde mit   gleichfarbigen Pferden, damit hat man nun eine gleichfarbige Herde von  , ein Einzelpferd, das dieselbe Farbe wie die Herde besitzt, und ein Einzelpferd unbekannter Farbe. Nun fasst man das Einzelpferd unbekannter Farbe mit der Herde von   Pferden zu einer neuen Herde von   Pferden zusammen. Nach Induktionsvoraussetzung müssen alle Pferde dieser neuen Herde gleichfarbig sein und damit dieselbe Farbe besitzen wie die vorherige Herde von   Pferden und das zuvor entfernte gleichfarbige Einzelpferd. Damit hat man insgesamt   Pferde gleicher Farbe.[3][2]

Denkfehler

Bearbeiten

Der Induktionsschritt selbst ist korrekt, allerdings benötigt er eine Herde von mindestens zwei Pferden, damit das zusätzliche Einzelpferd unbekannter Farbe die Farbe der bisherigen Herde annimmt. Besteht die Herde nur aus einem Pferd, so erhält man nach dem Entfernen eines Pferdes gleicher Farbe eine leere Herde, in die das Pferd unbekannter Farbe eingefügt wird. Die leere Herde aber hat keine Farbe, die per Induktionsvoraussetzung auf das Pferd unbekannter Farbe übertragen werden könnte. Anders ausgedrückt, die ursprüngliche Herde von   Pferden und die neue Herde von   Pferden, bei der ein Pferd durch das Pferd unbekannter Farbe ausgetauscht wurde, müssen eine nicht leere Schnittmenge besitzen. Für einen korrekten Beweis müsste die Induktionsverankerung daher für   anstatt für   durchgeführt werden. Dies ist jedoch nicht möglich, da man nicht garantieren kann, dass zwei beliebige Pferde die gleiche Farbe besitzen.[3][2]

Sonstiges

Bearbeiten

In der Literatur wird das Pferde-Paradox gelegentlich dem Mathematiker George Pólya (1887–1985) zugeschrieben.[4][5] Dieser beschrieb es unter anderem in seinem 1954 erschienenen Buch Induction and Analogy in Mathematics in einer Übungsaufgabe, dort ist allerdings nicht von Pferden die Rede, stattdessen wird die Aussage Any   girls have eyes of the same color (dt. „  Mädchen haben immer dieselbe Augenfarbe“) untersucht.[6] Generell kann man den fehlerhaften Induktionsbeweis natürlich für beliebige Eigenschaften von Elementen einer Menge durchführen, weshalb sich in der Literatur oft unterschiedliche Einkleidungen des Problems finden. So wird im deutschsprachigen Raum in Anlehnung an die Redensart Nachts sind alle Katzen grau oft bewiesen, dass alle Katzen grau sind.[7] Der Biomathematiker Joel E. Cohen veröffentlichte 1961 den als Satire angelegten Artikel On the nature of mathematical proofs, der eine Darstellung des fehlerhaften Induktionsbeweises anhand von Pferden enthält.[8]

Literatur

Bearbeiten
  • Piotr Łukowski: Paradoxes. Springer, 2011, ISBN 9789400714762, S. 15
  • Anne Rooney: The History of Mathematics. Rosen Publishing Group, 2012, ISBN 9781448873692, S. 198
  • Miklos Bona: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific, 2006, ISBN 9789812568854, S. 23-24
  • Peter van Dongen: Einführungskurs Mathematik und Rechenmethoden: Für Studierende der Physik und weiterer mathematisch-naturwissenschaftlicher Fächer. Springer, 2015, ISBN 9783658075200, S. 41
  • Karsten Wolf: Präzises Denken für Informatiker. Springer, 2017, ISBN 9783662549735, S. 120-121
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Piotr Łukowski: Paradoxes. Springer, 2011, ISBN 9789400714762, S. 15
  2. a b c d Karsten Wolf: Präzises Denken für Informatiker. Springer, 2017, ISBN 9783662549735, S. 120-121
  3. a b c Miklos Bona: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific, 2006, ISBN 9789812568854, S. 23-24
  4. Anne Rooney: The History of Mathematics. Rosen Publishing Group, 2012, ISBN 9781448873692, S. 198
  5. Peter van Dongen: Einführungskurs Mathematik und Rechenmethoden: Für Studierende der Physik und weiterer mathematisch-naturwissenschaftlicher Fächer. Springer, 2015, ISBN 9783658075200, S. 41
  6. George Pólya: Induction and Analogy in Mathematics. Princeton University Press, 1954, S. 120
  7. Siehe zum Beispiel: Nicola Oswald, Jörn Steuding: Elementare Zahlentheorie: Ein sanfter Einstieg in die höhere Mathematik. Springer, 2014, ISBN 9783662442487, S. 39
  8. Joel E. Cohen: On the nature of mathematical proofs, Worm Runner's Digest, III (3), 1961 (gekürzter Nachdruck in Robert L. Weber, E. Mendoza, Eric Mendoza: A Random Walk in Science. CRC Press, 1973, ISBN 9780854980277, S. 34-36)