WikiDer > Strukturelle Induktion

Strukturelle Induktion oder Strukturinduktion ist eine Beweismethode, mit der man beweisen kann, dass eine bestimmte Eigenschaft für alle Elemente einer induktiv definierten Menge gilt. Es ist eine Form von mathematische Induktion. Eine induktiv (oder rekursiv) definierte Menge besteht aus mehreren Basisobjekten und ist dann gesperrt unter mehreren Operationen. Beispiele für induktiv definierte Mengen sind logische Formeln, mathematische Begriffe und viele Strukturen aus der theoretischen Informatik, wie z Bäume.

Die Idee hinter der Strukturinduktion ist, dass wenn

1. alle möglichen Basisobjekte haben eine bestimmte Eigenschaft ${Anzeigestil P}$ haben; und
2. alle Möglichkeiten, ein neues Objekt aus alten Objekten zu erstellen, für die diese Eigenschaft ${Anzeigestil P}$ gilt, ergibt wieder ein Objekt, für das ${Anzeigestil P}$ gilt

die Eigenschaft gilt dann für alle Objekte in der Auflistung.

Induktion im Allgemeinen ist eine Beweismethode, die für wohlbegründete Mengen (Mengen mit wohlbegründeter Ordnung) verwendet werden kann. Die strukturelle Induktion unterscheidet sich von der Induktion über die natürlichen Zahlen (volle Einweisung) weil die verwendete Anordnung nicht gesamt ist. Außerdem ist die Reihenfolge in der induktiven Definition meist implizit definiert. Die kleinsten Objekte sind die Grundobjekte und beim Zusammenfügen von Objekten entsteht ein größeres Objekt. Strukturinduktion erfolgt oft innerhalb der Binnen Algebra, Logik, Theoretische Informatik und andere Bereiche, die Formeln, Begriffe, Listen, Programme und andere induktiv definierte Mengen beinhalten.

In den Grundlagen der Mathematik werden die natürlichen Zahlen manchmal induktiv wie folgt definiert:

• ${Anzeigestil 0}$ (Null) ist eine natürliche Zahl.
• wenn ${Anzeigestil x}$ eine natürliche Zahl ist, dann auch ${Anzeigestil S(x)}$ (lies: Nachfolger von ${Anzeigestil x}$, oder ${Anzeigestil x 1}$) ist eine natürliche Zahl.
• Nichts anderes ist eine natürliche Zahl.

Definieren wir die natürlichen Zahlen so, so ist die vollständige Induktion über natürliche Zahlen ein Spezialfall der Strukturinduktion; das heißt, die Strukturinduktion ist a Verallgemeinerung ist von vollständiger Induktion.

Beispiel

Definition. Die Menge der positiven propositional Formeln ist die kleinste Menge, so dass:

• ein atomarer Satz ${displaystyle p_{i}}$ (vor dem ${displaystyle iin mathbb {N} }$) ist eine positive Formel;
• wenn ${Anzeigestil Varphi }$ und ${Anzeigestil psi }$ sind positive Formeln, dann ${Anzeigestil Varphi Wedge psi }$, ${Displaystyle Varphi Rinder psi }$ und ${Anzeigestil Varphi oder Psi}$;

Gestell. Eine positive Formel ${Anzeigestil Varphi }$ ist erfüllbar. Stärker: ${Anzeigestil Varphi }$ ist erfüllt durch die Bewertung aller in enthaltenen atomaren Aussagen ${Anzeigestil Varphi }$ den Wahrheitswert verhindern wahr Zuschüsse.

Beweise.

Grundlegender Schritt. Eine atomare Formel ${displaystyle p_{i}}$ wird durch die Bewertung von erfüllt ${displaystyle p_{i}}$ der Wahrheitswert wahr Zuschüsse.

Induktionsschritt.

Annehmen ${Anzeigestil Varphi }$ des Formulars ${Displaystil-Varphi _{1}Keil-Varphi _{2}}$ ist. Nach der Induktionshypothese können wir annehmen, das ${displaystyle varphi_{1}}$ und ${displaystyle varphi_{2}}$ werden durch die Bewertungen aller atomaren Aussagen in erfüllt ${displaystyle varphi_{1}}$ bzw. ${displaystyle varphi_{2}}$wahr gewähren. Das bedeutet nach der Semantik von ${Anzeigestil-Keil}$ Welche ${Displaystil-Varphi _{1}Keil-Varphi _{2}}$ wird durch die Bewertung aller atomaren Aussagen erfüllt wahr Zuschüsse.

Annehmen ${Anzeigestil Varphi }$ des Formulars ${displaystyle varphi _{1}Rinder varphi _{2}}$ ist. Nach der Induktionshypothese können wir annehmen, das ${displaystyle varphi_{1}}$ und ${displaystyle varphi_{2}}$ sind erfüllt durch die Bewertungen aller atomaren Aussagen in ${displaystyle varphi_{1}}$ bzw. ${displaystyle varphi_{2}}$wahr gewähren. Das bedeutet nach der Semantik von ${displaystyle rinder }$ Welche ${displaystyle varphi _{1}Rinder varphi _{2}}$ wird durch die Bewertung aller atomaren Aussagen erfüllt wahr Zuschüsse.

Annehmen ${Anzeigestil Varphi }$ des Formulars ${displaystyle varphi _{1} oder varphi _{2}}$ ist. Nach der Induktionshypothese können wir annehmen, das ${displaystyle varphi_{1}}$ und ${displaystyle varphi_{2}}$ werden durch die Bewertungen aller atomaren Aussagen in erfüllt ${displaystyle varphi_{1}}$ bzw. ${displaystyle varphi_{2}}$wahr gewähren. Das bedeutet nach der Semantik von ${Anzeigestil o}$ Welche ${displaystyle varphi _{1} oder varphi _{2}}$ wird durch die Bewertung aller atomaren Aussagen erfüllt wahr Zuschüsse.

Dies beweist die Aussage.