0 Daumen
734 Aufrufe
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

Avatar von 28 k

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 "=>")

2 Antworten

+1 Daumen
 
Beste Antwort

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.

Avatar von 39 k
+1 Daumen

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.

Avatar von 148 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community