Beweis der vollständigen Induktion?
Hallo,
Ich verstehe das Verfahren und wie man es anwendet. Aber mir erschließt sich nicht, wie die Grundlegende Argumentation der vollständigen Induktion funktioniert.
Man möchte beweisen dann A(n) gilt und so beweist man, dass A(n+1) gilt. Aber während ich A(n+1) beweise, setzte ich doch voraus, dass A(n) gilt. Im Induktionsanfang prüfe ich das kleinste n und prüfe dann A(n+1) aber doch unter Prämisse, dass A(n) = True ist - ist das nicht rekursive?
4 Antworten
Natürlich ist das rekursiv. Ein Induktionsbeweis ist ein umgekehrt aufgebauter Rekursionsbeweis.
Allerdings braucht jede Rekursion ein Rekursionsende (welches verwirrenderweise oft "Rekursionsanfang" genannt wird), sonst hätten wir eine "infinite Rekursion", die keine Beweiskraft hat.
Dafür hat ja jeder Induktionsbeweis einen "Induktionsanfang" - A(0) oder A(1).
Das wäre der umgekehrte Weg. Erfordert normalerweise ein etwas anderes Beweisverfahren (wenn es überhaupt möglich ist). Braucht man aber nicht.
Warum wäre das der umgekehrte Weg? Man folgert doch aus A(n) => A(n+1) und beweist dann A(n+1)
aus A(n+1) [...] auf A(n) = True schließen
ist der umgekehrte Weg als von A(n) auf A(n+1) zu schließen. Beim Induktionsbeweis schließt man von A(n) auf A(n+1). (Beim Rekursionsbeweis von A(n-1) auf A(n))
Ich verstehe diese Frage irgendwie nicht. Du schließt ja nicht von A(n+1) = True auf A(n) = True, sondern umgekehrt. Du beweist, daß A(0) = True (wenn 0 Dein kleinstes Element ist). Das ist der Induktionsanfang. Dann nimmst Du für ein *beliebiges* n hypothetisch an, daß A(n)= True. Das ist die Induktionshypothese. Dann beweist Du, daß unter dieser Annahme A(n+1) = True. Das ist der Induktionsschritt. Nun hast Du bewiesen, daß für *alle* n gilt: *Wenn* A(n) = True, dann A(n+1) = True. Und außerdem hast Du bewiesen, daß für das erste n gilt: A(n) = True. Damit hast Du bewiesen, daß für alle n: A(n) = True. Das erste Element besitzt die Eigenschaft, und jedes Element, das die Eigenschaft besitzt, vererbt sie an seinen unmittelbaren Nachfolger weiter, somit besitzen alle Elemente die Eigenschaft.
Stell Dir vor, alle Menschen stammen von Adam ab (nur hypothetisch :-)). Wenn Du dann nachweisen kannst, daß erstens Adam an einer bestimmten Erbkrankheit litt und zweitens jeder Mensch, der an dieser Krankheit leidet, sie zwingend und ohne Ausnahme an alle seine Kinder vererbt, dann hast Du gezeigt, daß alle Menschen an dieser Krankheit leiden.
Ja das kann am Anfang etwas verwirrend sein. Du solltest es so betrachten:
Da du anfängst, die Aussage für das kleinste n = n0 zu beweisen, weißt du, dass die Aussage auf jeden Fall für dieses n0 stimmt.
Würdest du jetzt beweisen, dass es für den nächsten Schritt auch stimmt (also für n0+1), dann wird das (wenn die Aussage natürlich stimmt) auch richtig sein. Jetzt kannst du das immer wieder tun (für n0+2, n0+3, ...) und wirst vielleicht immer richtige Aussagen bekommen, aber daraus kannst du nicht schließen, dass es immer für alle n0+k gelten wird, wobei k bis ins Unendliche gehen kann.
Wie immer in der Mathematik: Wenn man etwas allgemein zeigen möchte, dann lasse auch alle Abhängigkeiten allgemein. Also: Wenn du zeigen kannst, dass A(n+1) richtig ist, unter der Annahme, dass A(n) richtig ist (unabhängig von allem andere), dann folgt ja automatisch, dass A(n0+1) richtig ist, weil du weißt, dass A(n0) garantiert richtig ist. Daraus folgt dann auch A(n0+2) usw.
Du nutzt also einfach die Allgemeinheit aus, damit du nicht mühsam alle unendlichen Aussagen einzeln iterativ beweisen musst.
Wenn ich gezeigt habe, dass A(n=1) wahr ist und gezeigt habe dass, wenn beliebiges A(n) = wahr ist, dann A(n+1) = wahr folgt, dann gilt: Aus A(1) = wahr folgt A(2) = wahr; aus A(2) = wahr folgt A(3) = wahr usw und damit folgt A(n) = wahr für beliebiges n.
siehe Induktionsaxiom von Peano !
Ein Beispiel als Ergänzung
Behauptung: Wurzel(n) < (n+1)/2 für n aus |N.
Wie man leicht sieht ist diese Aussage falsch.
Aus der Annahme Wurzel(N) < (N+1)/2.
kann dennoch die Aussage Wurzel(N+1) < (N+1+1)/2 gefolgert werden.
Laut Aussagenlogik kann doch aber aus einer Falschen Aussage eine Wahre folgen. Wie kann ich dann aus A(n+1) (was ja aus A(n) folgt) = True auf A(n) = True schließen?
Aus einer wahren Aussage kann aber keine falsche Aussage folgen.
Aus A(1) = wahr und aus { [ A(n) = wahr ] => [ A(n+1) = wahr ] } folgt alle Aussagen A(n) = wahr. Ohne den Induktionsanfang hättest du recht.
Du sollst ja von A(n) = True auf A(n+1) = True schließen und nicht umgekehrt.
Zum besseren Verständis wäre es vielleicht sinnvoll den Buchstaben n im ersten Teil durch den Buchstaben N zu ersetzen. In der Schule habe ich es tatsächlich so gemacht. Nur hier bei gutefrage war ich etwas sorgloser. Mir ist es etwas zu spät wieder eingefallen und konnte es nicht mehr ändern.
Du zeigst: für ein bestimmtes A(n) gilt der Zusammenhang. (Induktionsanfang)
Dann zeigst du: WENN der Zusammenhang für A(n) gilt, DANN gilt er auch für A(n+1).
Damit hast du gezeigt, dass es für alle A(x) an deinem Induktionsanfang gilt.
WENN der Zusammenhang für A(n) gilt, DANN gilt er auch für A(n+1).
Das ist eben mein Problem, laut Aussagenlogik muss A(n) nicht wahr sein, damit A(n+1) wahr ist.
Laut Aussagenlogik kann doch aber aus einer Falschen Aussage eine Wahre folgen. Wie kann ich dann aus A(n+1) (was ja aus A(n) folgt) = True auf A(n) = True schließen?