## [Wohlbegründete Induktion](/de/node/60958) Definition Das Prinzip, dass, wenn eine Relation R auf einer Menge wohlbegründet ist (es gibt keine unendlichen absteigenden R-Ketten), und jedes Element x die Eigenschaft besitzt, sofern alle R-kleineren Elemente sie besitzen, dann gilt die Eigenschaft für alle Elemente; es verallgemeinert die gewöhnliche Induktion über die natürlichen Zahlen auf beliebige wohlbegründete Ordnungen. ## Prinzip Prinzip Induktion über eine wohlbegründete Relation: Um P(x) für alle x zu beweisen, genügt es zu zeigen, dass für ein beliebiges x aus der Gültigkeit von P(y) für alle y mit y R x (oder y < x) die Gültigkeit von P(x) folgt. Die Wohlbegründetheit verhindert das Paradoxon des minimalen Gegenbeispiels. ## Demonstration Demonstration Um die Terminierung eines Rewriting-Systems zu beweisen, definiert man eine wohlbegründete Maßfunktion, die Ordnungszahlen oder natürliche Zahlen an Terme zuweist, und zeigt, dass jede Reduktion die Maßzahl streng verringert; per wohlbegründeter Induktion auf die Maßfunktion sind unendliche Abstiege unmöglich und alle Reduktionsfolgen terminieren. ## Fehlanwendung Fehlanwendung Wohlbegründete Induktion auf nicht wohlbegründete Relationen anzuwenden (z. B. die ganzen Zahlen mit der üblichen Ordnung) oder anzunehmen, strukturelle Induktion auf Syntax impliziere automatisch wohlbegründete Induktion ohne Prüfung der Wohlbegründetheit der gewählten Relation. ## Konsequenz Konsequenz Bietet ein einheitliches Verfahren zum Beweis von Eigenschaften und Terminierung in unterschiedlichen Bereichen (Ordnungszahlen, Term-Rewriting, Programmterminierung); sie ermöglicht Beweise durch minimales Gegenbeispiel und rechtfertigt rekursive Definitionen, die durch wohlbegründete Maße indiziert sind. ## Umkehrung Umkehrung Ist die Relation nicht wohlbegründet, kann die Induktion fehlschlagen: Es kann Elemente geben, für die kein Argument des minimalen Gegenbeispiels greift, und Eigenschaften, die durch Abstiegsargumente gelten sollten, können aufgrund unendlicher absteigender Ketten falsch sein. ## Abgrenzung Abgrenzung Erfordert, dass die Relation auf der betrachteten Domäne wohlbegründet ist; sie ist nicht anwendbar auf beliebige partielle Ordnungen mit unendlichen Abstiegsfolgen und liefert nicht automatisch einen konstruktiven Zeugen, sofern Relation und Induktionshypothesen nicht effektiv beschrieben sind. ## Semantische Spannung Semantische Spannung Spannung zur strukturellen Induktion und zur gewöhnlichen mathematischen Induktion: Strukturelle Induktion ist ein Spezialfall, wenn die Struktur eine wohlbegründete Relation induziert; wohlbegründete Induktion ist weiter anwendbar, erfordert jedoch möglicherweise nicht-triviale Maße oder Ordinalzeugen. ## Synthese Synthese Wohlbegründete Induktion fasst das Kernprinzip der Induktion zusammen: Durch Ersetzen der Nachfolgerrelation der natürlichen Zahlen durch eine beliebige wohlbegründete Ordnung reduziert sie globale Aussagen auf lokale Abstiegsprüfungen—wenn jedes Element aus allen kleineren Elementen folgt, gilt die Eigenschaft für alle, was Terminierungsbeweise und Reasoning durch minimales Gegenbeispiel ermöglicht.