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 die Elemente von rekursiv aufgebauten Mengen (zum Beispiel Mengen von Listen, Formeln, Graphen) beweisen.

Bei der vollständigen Induktion werden Eigenschaften der natürlichen Zahlen bewiesen; bei der strukturellen Induktion werden Eigenschaften für Mengen bewiesen, deren Elemente aus Grundelementen durch eine endliche Anzahl von Konstruktionschritten (unter Verwendung bereits konstruierter Elemente) bzw. mittels eines Erzeugungssystems entstehen. Es gibt also minimale (auch: einfachste oder Grund-)Elemente und rekursiv definierte (oder: rekursiv gebildete) Elemente der Menge. Bei den natürlichen Zahlen ist das Grundelement 0 und der Konstruktionsschritt ist der Übergang von einer Zahl n zur Zahl n + 1.

Um eine Aussage für die Elemente einer Menge zu beweisen, zeigt man im Induktionsanfang die Gültigkeit der Aussage für die einfachsten Elemente und im Induktionsschluss die Gültigkeit der Aussage für die rekursiv gebildeten Elemente unter der Voraussetzung, dass die Aussage für die in der Konstruktion verwendeten Elemente gilt. Ist beides erfüllt, so gilt die Aussage für alle Elemente. Man führt die Induktion also über den strukturellen Aufbau der Elemente.

Strukturelle Induktion ist ein Spezialfall der Induktion für Mengen mit einer wohlfundierten (partiellen) Ordnung.