TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 25

Wo steckt der Fehler im "Beweis" der folgenden Behauptung:

Ist in einer Gruppe von Personen eine Person blond, so sind alle blond.

Beweis: a) $n=1$: Hier stimmt die Behauptung trivialerweise.

b) Die Behauptung gelte für Gruppen der Größe $n$.

Nun sei von $n+1$ Personen eine blond. Betrachte man diese Person zusammen mit $n-1$ weiteren.

Dann sind nach der Induktionsannahme diese $n-1$ Personen auch blond. Folglich ist in der Gruppe dieser $n-1$ Personen zusammen mit der noch nicht betrachteten Personen wieder wenigstens eine blond, woraus folgt, dass auch diese letzte Person blond sein muss.

Ist das so simpel? - Die vollständige Induktion heisst ja bekanntlich "Schluss von n auf n + 1" ... da scheint mir die einfache Umkehrung nicht opportun. --20:27, 2. Nov 2005 (CET)

Zusatzhinweis: Die vollständige Induktion beinhaltet den Schluss von n auf n+1 (= Einbahnstrasse). Sie gilt nicht, wenn man von n auf n-1 wie in diesem Beispiel schliessen will. --Mnemetz 22:51, 2. Nov 2005 (CET)

Siehe auch: http://de.wikipedia.org/wiki/Hilberts_Hotel

Es gibt kein Problem mit dem n-1. Die Vereinigung der einen Person (P1) und n-1 weiteren ist eine Menge von n Personen, daher wenn P1 wie angenommen blond ist, tatsächlich müssen auch die restlichen n-1 Personen nach Induktionsannahme blond sein, weil sie ja zusammen eine n-elementige Menge bilden. Der Rest funktioniert genauso, also der Beweis, in dem Sinne, ist vollkommen richtig, das Problem liegt nicht da.

Das Problem ist dass angenommen wird, dass diese n-1 Personen eine nichtleere Menge ist, was für n=2 nicht gilt. Hätten wir manuell gezeigt, dass die Behauptung für n=2 gilt, würde es tatsäclich bedeuten dass sie auch für alle n gilt - das fehlt aber und der Beweis ist ungültig. 193.170.138.233 22:48, 4. Nov. 2009 (CET) (Irfy)

Der Fehler liegt darin, dass von n auf n-1 geschlossen wird, das widerspricht dem 5. Peanoaxiom. Wenn aber die 1. und 2. Person blond sind, sind dann alle blond? Nein, weil laut dem 2. Peanoaxiom jede Natürliche Zahl genau einen Nachfolger hat. Personen einer Gruppe können aber nicht gereiht werden. Kristina 22:13, 20. Mär. 2011 (CET)

Lösung lt. Tutor

"Das Problem ist dass angenommen wird, dass diese n-1 Personen eine nichtleere Menge ist, was für n=2 nicht gilt. Hätten wir manuell gezeigt, dass die Behauptung für n=2 gilt, würde es tatsächlich bedeuten dass sie auch für alle n gilt - das fehlt aber und der Beweis ist ungültig." 193.170.138.233 22:48, 4. Nov. 2009 (CET) (Irfy)