Pferde-Paradox

Kernidee

Das Pferde-Paradox ist ein scheinbares Paradox aus der Mathematik. Es behauptet scheinbar, mithilfe der vollständigen Induktion beweisen zu können, dass alle Pferde die gleiche Farbe besitzen. Diese Aussage ist offensichtlich falsch und widerspricht der Erfahrung. Der Widerspruch entsteht nicht, weil die vollständige Induktion unzuverlässig wäre, sondern weil sie in diesem Beispiel falsch angewendet wird.

Vollständige Induktion ist eine Beweismethode für Aussagen über natürliche Zahlen. Man zeigt zuerst einen Anfangsfall, die Induktionsverankerung, und danach einen Induktionsschritt: Wenn die Aussage für eine Zahl n gilt, soll daraus folgen, dass sie auch für n+1 gilt. Beim Pferde-Paradox wirkt dieser Aufbau zunächst korrekt, enthält aber an einer entscheidenden Stelle eine versteckte Voraussetzung, die beim Übergang von n=1 zu n=2 nicht erfüllt ist.

Der scheinbare Beweis

Die zu beweisende Aussage lautet: In einer Herde mit n Pferden besitzen alle n Pferde die gleiche Farbe. Man versucht, diese Aussage durch Induktion über n zu zeigen.

Die Induktionsverankerung wird für n=1 gesetzt. Besteht eine Herde nur aus einem Pferd, dann haben alle Pferde dieser Herde dieselbe Farbe, weil es nur ein einziges Pferd gibt.

Im Induktionsschritt nimmt man an, dass die Aussage für jede Herde mit n Pferden gilt. Dann soll gezeigt werden, dass sie auch für jede Herde mit n+1 Pferden gilt. Eine Herde mit n+1 Pferden wird dazu in eine Herde aus n Pferden und ein einzelnes Pferd aufgeteilt. Nach der Induktionsvoraussetzung haben die n Pferde in der Herde alle dieselbe Farbe. Noch offen ist, ob das einzelne Pferd dieselbe Farbe hat.

Wie der Induktionsschritt wirken soll

Um auch das einzelne Pferd unbekannter Farbe einzubeziehen, entfernt man aus der bereits gleichfarbigen Herde von n Pferden ein weiteres Pferd. Übrig bleibt eine Herde von n-1 Pferden, außerdem gibt es ein einzelnes Pferd, das dieselbe Farbe wie diese Herde besitzt, und ein weiteres einzelnes Pferd mit noch unbekannter Farbe.

Nun fasst man das Pferd unbekannter Farbe mit der Herde von n-1 Pferden zu einer neuen Herde von n Pferden zusammen. Nach der Induktionsvoraussetzung müssten alle Pferde in dieser neuen Herde gleichfarbig sein. Daher hätte das zuvor unbekannte Pferd dieselbe Farbe wie die Herde von n-1 Pferden. Zusammen mit dem zuvor entfernten Pferd ergäben sich dann angeblich n+1 Pferde gleicher Farbe.

Der Denkfehler

Der Fehler liegt im Übergang von n=1 zu n=2. Der beschriebene Induktionsschritt funktioniert nur für n >= 2, nicht aber für n=1. Damit das Pferd unbekannter Farbe die Farbe der bisherigen Herde übernehmen kann, muss es eine gemeinsame, nicht leere Gruppe von Pferden geben, die in beiden betrachteten Herden vorkommt.

Wenn n=1 ist, besteht die ursprüngliche Herde nur aus einem Pferd. Entfernt man dieses Pferd, bleibt eine leere Herde. Eine leere Herde hat keine Farbe, die durch die Induktionsvoraussetzung auf das unbekannte Pferd übertragen werden könnte. Anders gesagt: Die ursprüngliche Herde von n Pferden und die neue Herde von n Pferden, bei der ein Pferd ausgetauscht wurde, müssen eine nicht leere Schnittmenge besitzen. Das ist bei n=1 nicht der Fall.

Für einen korrekten Beweis müsste die Induktionsverankerung deshalb bei n=2 liegen. Das ist aber unmöglich, weil man nicht garantieren kann, dass zwei beliebige Pferde die gleiche Farbe besitzen. Deshalb beweist das Argument die Aussage nicht.

Bedeutung und Varianten

Das Pferde-Paradox dient als Standardbeispiel dafür, wie ein Induktionsbeweis durch einen scheinbar kleinen Fehler ungültig werden kann. Es zeigt besonders deutlich, dass der Induktionsschritt wirklich für den Anschluss an die Induktionsverankerung funktionieren muss.

In der Literatur wird das Paradox gelegentlich dem Mathematiker George Pólya (1887-1985) zugeschrieben. Er behandelte 1954 in seinem Buch Induction and Analogy in Mathematics eine ähnliche Übungsaufgabe, allerdings nicht mit Pferden, sondern mit der Aussage Any n girls have eyes of the same color, also sinngemäß: n Mädchen haben immer dieselbe Augenfarbe.

Der fehlerhafte Beweis lässt sich allgemein auf beliebige Eigenschaften von Elementen einer Menge übertragen. Deshalb gibt es verschiedene Einkleidungen. Im deutschsprachigen Raum findet man etwa Varianten mit Katzen, angelehnt an die Redensart Nachts sind alle Katzen grau. Eine Darstellung mit Pferden erschien 1961 in Joel E. Cohens satirischem Artikel On the nature of mathematical proofs.