Katzeninduktion

Informationen

Kategorie

Schw.

Tags

Induktion

Aufgabe

Nenne den konkreten Punkt, an dem der folgende Beweis kaputt geht.

Behauptung: Alle Katzen haben die gleiche Augenfarbe. Beweis: Wir beweisen die Behauptung durch vollständige Induktion. Sei $K$ dazu die Menge aller Katzen. Unsere Induktionsaussage soll sein: Für alle natürlichen Zahlen $n$: für alle Teilmengen $T \subset K$ von Katzen mit $|T| = n$ gilt, dass alle Katzen aus $T$ die gleiche Augenfarbe haben.

Für $n=1$ ist die Behauptung offensichtlich. Wir nehmen jetzt an, dass je $n$ Katzen die gleiche Augenfarbe haben und beweisen, dass das auch für je $n+1$ Katzen gilt. Wir nehmen $n+1$ willkürlich ausgewählte Katzen und nummerieren sie. Nach Induktionsvoraussetzung haben die Katzen mit den Nummern $1$ bis $n$ die gleiche Augenfarbe und auch die $n$ Katzen mit den Nummern $2$ bis $n+1$. Zu beiden Mengen gehört zum Beispiel die Katze mit der Nummer $2$, also haben alle $n+1$ Katzen die selbe Augenfarbe.