Hauptmenü öffnen

TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 23

< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19

Wo steckt der Fehler im Induktions-”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. Man betrachte diese Person zusammenmit n-1 weiteren. Dann sind nach 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, daß auch diese letzte Person blond sein muss.

Inhaltsverzeichnis

HilfreichesBearbeiten

Das Beispiel ist eine Variante des "All horses are the same color"-Paradoxon. Sehr anschaulich hier erklärt: [1]

Vollständige Induktion[Bearbeiten, WP]
  1. Induktionsanfang (IA)
  2. Induktionsschritt (IS): Induktionsvoraussetzung (IV)   Induktionsbehauptung (IB)

Lösungsvorschlag von samuelpBearbeiten

Zuerst muss klargestellt werden wie der Beweis genau funktioniert.

Induktionsanfang  Bearbeiten

Der Beweis meint, dass die Behauptung trivialerweise stimmt. Für   bedeutet die Aussage, dass wenn eine Person bei einer Gruppe mit einer Person blond ist, dann alle blond sind. Das ist richtig, weil eben nur die eine Person in der Gruppe ist.

Induktionsschritt  Bearbeiten

Induktionshypothese: Falls eine Person in einer Gruppe von   blond ist, dann sind alle blond

Induktionsbehauptung: Falls eine Person in einer Gruppe von   blond ist, dann sind alle blond

Wir geben jeder der   eine Nummer. Wir dürfen voraussetzen, dass eine Person blond ist. Diese bekommt die Nummer 1.

Die Induktionshypothese können wir auf jede Gruppe der Größe   anwenden in der mindestens eine blonde Person ist.

Der Beweis geht in zwei Schritten vor.

1) Wir betrachten Personen mit Nummer 1 bis  . Auf diese Gruppe ist Induktionshypothese anwendbar. Diese besagt, dass alle Personen blond sind.

2) aus dem vorigen Schritt wissen wir das Person   blond sein muss. Wir betrachten die Gruppe von Personen mit den Nummern 2 bis  . Da Person   in dieser Gruppe ist und blond ist, kann die Induktionshypothese auf auf diese Gruppe angewendet werden.

Problem in diesem BeweisBearbeiten

Intuitiv schlägt der Beweis für   (bzw.  ) fehl.

Das einzige Problem mit dem Beweis oben ist die Aussage, dass Person mit der Nummer   in der Gruppe der Personen 2 bis   ist. Diese Gruppe enthält nur Person   ( ) und Person   ( ) eben nicht. Daher kann in dem Fall   die Induktionshypothese im Schritt 2 nicht verwendet werden und es ist nicht möglich zu schießen, dass Person auch 2 blond sein muss.