Und wieder mal die vollständige induktion...

[Pippen]

In der vI beweist man eine Aussage A(n) durch:

1. A(1)
2. indem man A(n) (als wahr) annimmt und zeigt, dass A(n+1) gilt.

Wenn man diese zwei Schritte beweist, dann soll A(n) für alle nat. Zahlen bewiesen sein. Aber: Man hat ja genaugenommen A(n) nie bewiesen, sondern nur A(n+1), d.h. A(n) könnte falsch sein und A(n+1) wahr. Die Implikation, der 2. zugrundeliegt, nämlich A(n) -> A(n+1), wäre dann trotzdem wahr. Ist damit der Beweis nicht unvollständig bzw. woraus ergibt sich, dass A(n) nicht falsch sein kann?

[tomS]

Man benötigt einen Induktionsanfang A(1) sowie einen Induktionsschritt von A(n) auf A(n+1), wobei hier A(n+1) unter der Annahme von A(n) bewiesen wird. Insofern hängt der Induktionsschritt in der Luft, weil A(n) zunächst nicht bewiesen ist. Allerdings ist n ja beliebig, und es kann daher insbs. auch n=1 sein. D.h. A(n=1) wird direkt bewiesen, A(n=2) folgt mittels Induktion aus A(1), A(3) folgt dann aus A(2) usf.

[Pippen]

Man benötigt einen Induktionsanfang A(1) sowie einen Induktionsschritt von A(n) auf A(n+1), wobei hier A(n+1) unter der Annahme von A(n) bewiesen wird. Insofern hängt der Induktionsschritt in der Luft, weil A(n) zunächst nicht bewiesen ist. Allerdings ist n ja beliebig, und es kann daher insbs. auch n=1 sein. D.h. A(n=1) wird direkt bewiesen, A(n=2) folgt mittels Induktion aus A(1), A(3) folgt dann aus A(2) usf.

Um es mal bildlich an der Dominosteinkette klarzumachen: Durch das Beweisverfahren der sog. vollständigen Induktion wüßten wir, dass der erste Stein fällt und das wenn der Vorgänger fällt, dann auch sein Nachfolger. Dann sagt uns das Induktionsaxiom: In diesem Fall darfst du davon ausgehen, dass alle Steine fallen. Warum? Nehmen wir an, irgendein Stein x würde nicht umfallen. Da wir wissen, dass wenn der Vorgänger fällt, dann auch der Nachfolger, dürfte auch x-1 nicht umfallen und das gleiche gilt für dessen Vorgänger usw. bis hin zum ersten Stein, der nicht umfallen dürfte, von dem wir aber wissen, dass er umfällt, also Widerspruch, so dass die Annahme falsch sein muss.

Es ist interessant, wie wenig man beweisen muss (fettmarkiert), um sicherzustellen, dass der Antezedens des Induktionsaxioms vorliegt: (X € 0 & alle n € IN: n € X => n+1 € X) => X Teilmenge von IN. Die fettmarkierten Terme garantieren, dass auch "n € X" wahr sein muss. (Mein Fehler war wohl, dass ich die Pfeile als Implikation und nicht als Folgerungspfeile interpretiert habe. Interpretiert man sie als Folgerungspfeile, dann gilt: Wenn n € X falsch wäre, dann würde nicht n+1 € X folgen (und das würde auf einen Widerspruch hinauslaufen, weil X € 0 bereits feststünde).

[tomS]

Deine Schlussfolgerung ist mir zu kompliziert (obwohl du natürlich zum korrekten Ergebnis gelangst).

Führen wir doch einfach einen Widerspruchsbeweis durch:

Wir nehmen an, dass das Prinzip der vollständigen Induktion gilt, dass ein A(1) gilt, dass jedoch für ein nicht näher bestimmtest n die Aussage A(n) nicht gilt, d.h. dass ~A(n) gilt.
Gemäß dem Induktionsschritt von n auf n+1 folgt aus ~A(n) zwingend ~A(n-1); durch wiederholte Anwendung also ~A(1) im Widerspruch zur Annahme.

q.e.d.