Theorie hinter der vollständigen Induktion (Wohlordnungssatz)?

Question

Können Sie zeigen, dass aus dem Wohlordnungssat die Gültigkeit des Beweisprinzips vollständiger Induktion folgt?

Beweis:
Wir nehmen an, dass \(A(1)\) richtig ist. Weiterhin gilt \(A(n)\implies A(n+1)\). Es gilt zu zeigen, dass zusammen mit Wohlordnungssatz daraus die Richtigkeit von \(A\) für alle natürlichen Zahlen folgt. Angenommen, das trifft nicht zu. Dann gibt es nach dem Wohlordnungsprinzip eine kleinste natürliche Zahl \(n'\), sodass \(A(n')\) falsch ist. Dann ist aber \(A(n'-1)\) richtig und wegen \(A(n)\implies A(n+1)\) auch \(A(n')\), im Widerspruch zur Annahme.

Frage: Ist hier ein Tippfehler unterlaufen? Sollte es nicht \(A(n'+1)\) heißen? Den Rest des Beweises verstehe ich, aber nicht warum hier \(n'-1\) steht, wenn du angemerkt ist, dass \(n'\) die kleinste natürliche Zahl ist.

Quelle: https://link.springer.com/book/10.1007/978-3-8274-2770-0

Comments

A(n'+1) würde auch keinen Sinn machen, denn aus A(n') => A(n'+1) mit A(n'+1) richtig folgt nicht, dass A(n') richtig ist. (Aussagenlogik, Wahrheitstafel von "=>")

Answer 1

Wenn \( n' \) die kleinste Zahl ist, für die \( A(n') \) falsch ist, dann ist \( A(m) \) für alle \(m < n' \) richtig, denn \( n' \) ist ja die kleinste Zahl, für die \( A(n') \) falsch ist. Dann ist aber auch \( A(n'-1) \) richtig, weil \( n'-1 < n \) ist. Dann ist auch \( A(n') \) richtig, im Gegensatz Annahme.

Answer 2

Aloha :)

\(n'\) ist die KLEINSTE natürliche Zahl, für die \(A(n')\) falsch ist. Also muss für alle vorigen \(n\) die Aussage richtig sein, insbesondere muss auch \(A(n'-1)\) richtig sein. Wegen \(A(n)\Rightarrow A(n+1)\) muss aber dann \(A(n')\) richtig sein. Widerspruch.

Da ist kein Tippfehler.