Vollständige Induktion wo ist der Fehler

Question

Hallo Leute,

diese Aufgabe soll einer traditionelle Aufgabe sein, wenn man gerade das Thema Induktion behandelt. Dennoch schaffe ich es nicht, den Fehler in dieser Aussage zu finden:

Wenn sich unter n Kühen eine lila Kuh befindet, dann sind alle Kühe lila. Dies kann, wie
im Folgenden gezeigt, durch vollständige Induktion bewiesen werden:

Induktionsanfang: Für n = 1 (d.h. eine einzige Kuh in der Menge) ist offensichtlich, dass die Aussage
erfüllt ist. Als Induktionsvoraussetzung können wir somit annehmen, dass die Aussage für eine
Menge von n Kühen wahr ist und folgern nun im Induktionsschluss, dass sie auch für n + 1 gilt.
Angenommen eine Kuh sei lila. Sortieren wir die Kühe derartig um, dass sich die lila Kuh ganz vorne
befindet, bilden die ersten n Kühe eine Menge, für die die Aussage per Induktionsannahme wahr ist.
Die ersten n Kühe sind somit alle lila. Wenden wir die Induktionsvoraussetzung nun auf die letzten n
Kühe an, so ist sicher, dass mindestens eine Kuh in dieser Menge lila ist, was zu dem Ergebnis
führt, dass alle n + 1 Kühe lila sein müssen.

q.e.d.

Ich weiß, dass es falsch ist, aber ich weiß nicht, wo der Fehler ist. Kann mir jemand weiterhelfen.

Comments

Das Beispiel gibts in vielen Varianten und ist tatsächlich ein absoluter Klassiker

Am Induktionsanfang ist nichts auszusetzen.

Wenn du nur eine Kuh hast und diese ist lila, dann hast du nur lila Kühe.

Das Problem muss somit im Induktionsschritt liegen. Bei diesem Beispiel hilft es sich den Induktionsschritt für kleine Werte von n mal explizit anzuschauen.

Von 1 -> 2:

Die Aussage gelte also für n = 1

Wenn du eine Menge mit n=1 Kühen hast, und eine davon ist lila, dann sind alle Kühe dieser Menge lila.

und wir wollen sie nun für n = 2 zeigen.

Du hast jetzt also zwei Kühe. Nennen wir sie mal Anna und Marie. Davon ist eine lila, z.B. die Marie.

Was passiert nun im Induktionschritt: Die Kühe werden in eine Reihe gestellt, die lila Kuh ganz an den Anfang. Machen wir das mal:

Marie, Anna

Anschließend werden die ersten n = 1 Kühe genommen. Wir betrachten jetzt also die Menge {Marie}. Nach Induktionsvoraussetzung sind alle Kühe in dieser Menge lila: Es handelt sich nämlich um eine Menge von n=1 Kühen und eine davon ist lila.

Jetzt betrachten wir die letzten n = 1 Kühe. Ok, da ist jetzt nur noch Anna übrig. Also betrachten wir jetzt die Menge {Anna}

so ist sicher, dass mindestens eine Kuh in dieser Menge lila ist,

Und diese Aussage ist einfach falsch. Es ist überhaupt nicht klar, warum Anna plötzlich lila sein sollte, oder?

Im Schritt 1 -> 2 versagt der Beweis also. Und wenn der erste Dominostein nicht den zweiten umstößt, werden auch alle folgenden nicht mehr fallen.

Answer 1

Wenden wir die Induktionsvoraussetzung nun auf die letzten n Kühe an, so ist sicher, dass mindestens eine Kuh in dieser Menge lila ist

Nein. Wenn n = 1 ist, dann gehört keine der ersten n Kühe zu den letzten n Kühen.