Lösung für Aufgabe 2.5.7
Wir beweisen:Alle Menschen sind blond.Zwar ist die Anzahl aller Menschen endlich, da wir diese aber nicht genau kennen, führen wir den Beweis mittels vollst"andiger Induktion: F"ur den Induktionsanfang wird es Ihnen nicht schwer fallen, einen blonden Menschen zu benennen. Als Induktionsannahme postulieren wir, wir h"atten bereits f"ur alle Menschenmengen der Größe $k$ gezeigt, dass sie nur blonde Menschen enthalten. F"ur den Induktionsschritt betrachten wir nun eine beliebige Menge von $k+1$ Menschen $\mathcal{M}:=\{M_0,M_1,\dots,M_{k}\}$. Wir bilden nun die Mengen $\mathcal{M}_0:=\{M_0,\dots,M_{k-1}\}$ und $\mathcal{M}_1:=\{M_1,\dots,M_k\}$. Beide dieser Mengen haben $k$ Elemente, und daher sind jeweils alle in ihnen enthaltenen Menschen blond, nach Induktionssannahme. Weil jeder Mensch aus $\mathcal{M}$ in $\mathcal{M}_0$ oder in $\mathcal{M}_1$ enthalten ist, ist jeder Mensch in $\mathcal{M}$ blond. Daher enthalten alle Menschenmengen der Gr"o"se $k+1$ nur blonde Menschen. Aus vollst"andiger Induktion folgt daher, dass alle Menschen blond sind. \medskip Diskutieren Sie den obigen Beweis.
Hinweis: Wenn Sie sich schwer tun, den Fehler im Beweis zu finden, dann konzentrieren sie sich auf den Induktionsanfang.
In der Induktionsannahme teilen wir die Gesamtheit der Menschen in verschiedene Gruppen auf, mit jeweils $k$ Elementen (Menschen), für die gilt, dass alle blond sind. Dann zeigen wir, dass daraus für alle Gruppen der Größe $k+1$ folgt, dass alle Menschen in der Gruppe blond sind. Die Induktion geht also über die Gruppengröße. In jedem Schritt betrachten wir auf einmal alle Gruppen einer bestimmten Größe $k$. Der Fehler liegt darin, dass wir im Induktionsanfang ebenfalls alle Gruppen der Größe $1$ betrachten müssten und nicht wie im vorliegenden Beweis nur eine Gruppe der Größe $1$. Daher ist die Beweisführung falsch.