Pferde-Paradox

Das Pferde-Paradox (engl. horse paradox) 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

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

Pferde-Paradox, Induktionsschritt funktioniert nur für $n\geq 2$ und nicht für $n=1$

Die zu beweisende Aussage kann wie folgt formuliert werden:

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

Nun führt man eine Induktion über $n$ durch und verankert die Induktion für $n=1$.

Induktionsverankerung

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

Induktionsschritt

Nun setzt man voraus, dass die Aussage bereits für jede Herde mit $n$ Pferden gilt und zeigt, dass sie dann auch für jede Herde mit $n+1$ Pferden gilt. Eine Herde mit $n+1$ Pferden spaltet man in eine Herde von $n$ Pferden und ein einzelnes Pferd auf. In der Herde mit $n$ 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 $n$ gleichfarbigen Pferden, damit hat man nun eine gleichfarbige Herde von $n-1$, 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 $n-1$ Pferden zu einer neuen Herde von $n$ Pferden zusammen. Nach Induktionsvoraussetzung müssen alle Pferde dieser neuen Herde gleichfarbig sein und damit dieselbe Farbe besitzen wie die vorherige Herde von $n-1$ Pferden und das zuvor entfernte gleichfarbige Einzelpferd. Damit hat man insgesamt $n+1$ Pferde gleicher Farbe.

Denkfehler

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 $n$ Pferden und die neue Herde von $n$ 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 $n=2$ anstatt für $n=1$ durchgeführt werden. Dies ist jedoch nicht möglich, da man nicht garantieren kann, dass zwei beliebige Pferde die gleiche Farbe besitzen.

Sonstiges

In der Literatur wird das Pferde-Paradox gelegentlich dem Mathematiker George Pólya (1887–1985) zugeschrieben. 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 $n$ girls have eyes of the same color (dt. „$n$ Mädchen haben immer dieselbe Augenfarbe“) untersucht. 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. 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.

Literatur

• 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

Weblinks

• Alle Dinge sind gleich. Mathematischer Vorkurs, Skript Uni Bielefeld 2010, S. 16
• All Horses are the Same Colour im ProofWiki
• M. Junk, M. Rheinländer: Alle Pferde haben dieselbe Farbe. Analysis I – Ergänzungsblatt, November 2005, Uni Konstanz