Hallo,zuerst einmal hier geht es nicht um eine Hausaufgabenhilfe.
Bin 50 Jahre alt und habe leider nie eine Uni von innen gesehen.
Heute kam mein Sohn aus seiner ersten technischen Informatik Vorlesung.
Neugierig wollte ich wissen was sie gemacht haben.
Er zeigte mir eine Aufgabe die er lösen soll und das lässt mich nicht
mehr los.
Die Aufgabe lautet:
Induktionsaussage: Wenn sich unter n Kühen eine lila Kuh befindet,dann
sind alle Kühe lila.
Induktionsanfang: Wenn n = 1, dann ist es logisch, dass alle Kühe lila
sind, da nur eine existiert.
Induktionsvoraussetzung: Dies gilt auch dann für n+1 Kühe.
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.
Sind Sie nun überzeugt? Falls nicht, worin besteht hier der Fehler?
Ich habe mir das jetzt mind. 20 mal durchgelesen und verstehe den Sinn
dahinter nicht. Könnte mir jemand das mal verständlich rüberbringen.
Sohn kann ich nicht fragen, der ist selber am verzweifeln.
Vielen Dank im Voraus,
Andy
Hallo, vielen Dank für die Antwort.Ich verstehe ehrlich gesagt gar nicht
den
Sinn der ganzen Sache und das wurmt mich.Könnte mir jemand vielleicht
anhand eines Beispiels die Sache mit den Kühen erklären oder hat jemand
einen Link wo das auch für einen Nichtstudierten verständlich erklärt
wird.
Vielen Dank
Andy
Dass Kühe lila sind, braucht nicht mehr bewiesen werden. Das lernen die
Kinder als Selbverständlichkeit aus dem Werbefernsehen. Beweis durch
vollständige Indoktrination.
Kann man sich doch heute alles auf Youtube ansehen :)
Vollständige Induktion: Beispiel mit einer Gleichung Teil 1
https://youtu.be/zM997Tpr59k
Vollständige Induktion: Beispiel mit einer Gleichung Teil 2
https://youtu.be/cIhXNVnkPc0
Sam F. schrieb:> Ich habe mir das jetzt mind. 20 mal durchgelesen und verstehe den Sinn> dahinter nicht. Könnte mir jemand das mal verständlich rüberbringen.
Der Sinn dahinter ist, dass nicht alles, was auf den ersten Blick wie
eine vollständige Induktion aussieht, auch eine ist. Manchmal ist es
einfach nur vollständiger Unsinn.
Sam F. schrieb:> Hallo, vielen Dank für die Antwort.Ich verstehe ehrlich gesagt gar> nicht den Sinn der ganzen Sache und das wurmt mich.
Der Aufgabensteller geht davon aus, dass bekannt ist, was Vollständige
Induktion ist und die man damit Beweise führen kann — war meinerzeit
Schulstoff der 9. oder 10. Klasse.
Die Aufgabe besteht in einer offensichtlich falschen Behauptung nebst
fehlerhafter Beweis, und es soll der Fehler im "Beweis" gefunden werden.
Vielen Dank für all die Posts.
Habe viel gelernt, jedoch nicht so recht wie man den Bezug zu den Kühen
aufbauen soll.
Mein Sohn meinte, dass der Induktionsanfang korrekt ist ( was logisch
ist), jedoch von n=1 auf n= 2 ein Fehler vorliegt ( wie bereits hier
erwähnt).
"Nimmt man von den 2 Kühen erst eine heraus und dann die andere, so kann
man nicht schließen, dass die beiden die gleiche Farbe haben, da eine
dritte Vergleichskuh fehlen würde."
Gruß Andy
Da braucht man auch nicht den Bezug zum Rindvieh zu suchen.
Die Beweisführung durch Induktion setzt voraus, daß die Gesetze der
mathematischen Logik eingehalten werden.
Wenn eines der Viecher lila ist, gilt eben "alle Kühe sind lila" nur
wenn Du genau eine hast.
Damit ist aber die genannte Induktionsvoraussetzung hinfällig, da
offensichtlich nicht nur unlogisch sondern auch unsinnig.
Sam F. schrieb:> "Nimmt man von den 2 Kühen erst eine heraus und dann die andere, so kann> man nicht schließen, dass die beiden die gleiche Farbe haben, da eine> dritte Vergleichskuh fehlen würde."
Farbenblindheit wird hier nicht erwähnt.
Auf eine einzelne Kuh reduziert besagt die Induktionsaussage, dass diese
Kuh blau ist, wenn sie blau ist. Nicht aber dass sie blau ist.
Der Schritt von n auf n+1 funktioniert nur, wenn die Induktionsaussage
auf die übrige Kuh zutrifft. Also die Kuh blau ist wenn sie blau ist.
Somit ist nur bewiesen, dass eine Herde von Kühen durchweg blau ist,
wenn man mit der ersten Kuh anfangend stets nur blaue Kühe hinzufügt.
Der Beweis würde nur dann gelingen, wenn man von der Farbe einer Kuh auf
die Farbe der nächsten Kuh schließen könnte.
Du müsstest also beweisen, dass wenn du 2 Kühe hast, und die erste lila
ist, dass dann die 2. auch lila ist.
Genau dies kann aber nicht bewiesen werden. Es fehlt also der
"Induktionsschritt".
Doch nur in diesem Fall könnte man das unendlich fortsetzen.
Denn wenn die 2. Kuh lila ist, weil die 1 Kuh lila ist,
dann ist auch die 3. Kuh lila, weil die 2. Kuh lila ist,
usw...
Ich glaube, was Dir noch niemand gesagt hat, ist was hinter der
sagenumwobenenen "vollständigen Induktion" eigentlich steckt.
Das ist nämlich die Definition der natürlichen Zahlen nach den
Peano-Axiomen, hier zweckgerichtet zur Anschaulichkeit zusammengestutzt:
a) 0 ist die erste natürliche Zahl. [™]
b) jede natürliche Zahl hat genau einen Nachfolger.
Damit ist im Prinzip egal, ob man die Zahlen 0, 1, 2, 3, 4 oder 0, Kuh,
Resi, Franzi, Muhtschi, ... nennt: Wenn man die gleiche Struktur
wiederfindet.
Vollständige Induktion ist, wenn man "alle" (Zahlen, Kühe,
Nitrohydranten, whatever) dadurch prüft, daß man zwei Dinge feststellt:
a) Beim ersten (mit der Nummer 0) stimmts
b) Wir vergewissern uns, daß wenn es beim "n" stimmt, dann auch beim
Nachfolger von "n" (vulgo "n+1").
Dann haben wir definitionsgemäß alle durchgecheckt.
Bei den Kühen würde mich zum Beispiel überzeugen:
a) Die erste Kuh (die heißt dummerweise "0" weil ihr Pappa ein
versoffener Mathemathik-Studienabbrecher-Stier war) in der Reihe ist
Lila.
b) Ein Schokoladenhersteller garantiert uns gegen hohe Pönalestrafe und
bringt auch eine entsprechende Bankgarantie mit, daß immer dann wenn wir
bei einer Kuh festgestelt haben, daß sie lila ist, auch die nachfolgende
Kuh lila sein wird.
Dann sind alle Kühe lila.
Die Angabe würde ich dann so ins Falsiversum argumentieren:
Die herumwandernden Kühe ("wir sortieren sie um") verletzten
a) weil nicht die 0-Kuh gecheckt, sondern eine lila Kuh vernullt wurde
und
b) weil "genau ein Nachfolger" nicht eingehalten wird.
---
[*] Hier stecken in Wahrheit zwei Regeln drin: "a) 0 ist eine natürliche
Zahl" und "c) 0 ist kein Nachfolger" was logischerweise erst nach b)
ausgesagt werden kann, da es bei a) noch kein Nachfolgerkonzept gibt.
Die volle Wahrheit hat wie üblich Wikipedia und die einschlägig
amtsbekannte Fachliteratur.
Hallo Sam,
erst mal ein Link mit einer guten Beschreibung der vollständigen
Induktion: www.math.uni-
magdeburg.de/lehrver/analysis/vollstaendige_induktion.pdf
Sei A(i) eine Behauptung für alle i aus den natürlichen Zahlen.
In Deinem Fall z.B. ist A(i) die Behauptung:
"Wenn unter i Kühen mindestens eine Kuh lila ist, dann sind alle i Kühe
lila"
Mit vollständiger Induktion soll nun bewiesen werden, dass diese Aussage
für alle natürlichen Zahlen gilt
Dazu muss man zwei Schritte zeigen:
Schritt 1 (Induktionsanfang):
A(1) gilt.
Bei Dir ist das also:
"Wenn unter 1er Kuh mindestens eine Kuh lila ist, dann sind alle 1 Kühe
lila"
Soweit ist das auch richtig.
Im Schritt zwei, dem Induktionsschluß muss man nun zeigen
Wenn A(n) richtig ist, dann ist auch A(n+1) richtig
A(n) heist Induktionsannahme oder Induktionsvoraussetzung
In Deinem Fall bedeutet daß aus der Gültigkeit von
"Wenn unter n Kühen mindestens eine Kuh lila ist, dann sind alle n
Kühe lila"
geschlossen werden muss, dass auch
"Wenn unter n+1 Kühen mindestens eine Kuh lila ist, dann sind alle
n+1 Kühe lila" gültig ist.
Das sollte mit (Zitat aus Deinem Text)
"
Angenommen eine Kuh (aus n+1) 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
"
gemacht werden.
Nun ist aber dummerweise dies Argumentation für n = 1 falsch.
Wenn wir 2 Kühe haben wobei mindestens eine lila ist, können wir diese
lila Kuh schon vorn einsortieren. Aber von den letzten n Kühen (hier
ist n ja 1) also von der letzten Kuh können wir nicht mehr behaupten
dass mindestens eine Kuh davon lila ist. Damit hilft uns die
Induktionsvoraussetzung A(1) nichts, weil ihre Voraussetzung nicht
notwendigerweise erfüllt sein muss.
In dem zitierten Argument wird das aber falsch benutzt.
Und damit stürzt der Induktionsbeweis wie ein Kartenhaus ein.
Schade eigentlich :(
MfG
egonotto
