Strukturelle Induktion
aus Wikipedia, der freien Enzyklopädie
Die strukturelle Induktion ist ein Beweisverfahren, das unter anderem in der Logik, der theoretischen Informatik und der Graphentheorie eingesetzt wird. Es handelt sich um eine allgemeinere Form der vollständigen Induktion.
Mit dem Verfahren lassen sich Aussagen über rekursiv definierte Strukturen (zum Beispiel Listen, Formeln, Graphen) beweisen. Zu diesem Zweck wird die Aussage zunächst im Induktionsanfang für alle minimalen Strukturen gezeigt. Im Induktionsschritt wird dann angenommen, die Aussage gelte für Strukturen der n-ten Stufe und gezeigt, dass die Aussage dann auch für Strukturen der n+1-ten Stufe gilt. Damit ist dann gezeigt, dass die Aussage für alle Strukturen gilt.
