Strukturelle Induktion?
Hey
Ist die strukturelle Induktion dasselbe wie die Vollständige? Also beginnen mit Induktionsanfang, -annahme und -schritt?
Und könnte jemanden das hier lösen oder zumindest eine davon, damit ich sehen kann, wie das ist.
1 Antwort
Eine vollständige Induktion ist ein Spezialfall der strukturellen Induktion, welche über der Menge der natürlichen Zahlen aufgebaut wird.
Betrachten wir doch einmal die natürlichen Zahlen. Bei diesen kann ich sagen:
1) 0 ist in den natürlichen Zahlen
2) wenn x in den natürlichen Zahlen ist, ist auch succ(x) in den natürlichen Zahlen.
Damit haben wir diese Menge strukturell aufgebaut. Wir wissen also (wegen 1)), dass 0 drin ist und (wegen 2)) auch succ(0)=1, und dann succ(1)=2, usw.
Eine Induktion funktioniert NUR wegen diesen Regeln darüber. Wenn wir eine Aussage zu zeigen haben, dann zeigen wir sie für die 0 (IA), und dann nehmen wir an, dass ein x gibt, für dass die Aussage gilt (IV) und zeigen, dass es auch für (x+1) gelten muss (IS). Dadurch, dass wir diese IV annehmen, können (und müssen) wir diese auch benutzen im IS.
Das gleiche können wir auch für andere solche strukturell aufgebauten Mengen machen. So zum Beispiel auch in deinem Beispiel, oder generell in verschiedenen Formelsystemen.
Du hast die atomaren Formeln (etwa wie die "0" in N), für die du die Aussage im IS zeigst. Dann hast du verschiedene Regeln, die aus atomaren Formeln weitere Formeln aufbauen. Zum Beispiel "wenn atomare Formeln A und B gegeben sind, so ist auch 'A impliziert B' eine Formel" usw. Du nimmst also in der IV an, dass die Aussage für atomare Formeln (zum Beispiel A und B) gilt, und zeigst dann im IS, dass es auch für "nicht A", "A und B", ... gilt.