vollständige und strukturelle Induktion

Question

Aufgabe:

Vergleichen Sie der vollständige Induktion mit dem strukturellen Induktion.

Inwiefern geht es bei der vollständigen Induktion um das Prinzip der strukturellen Induktion?

Problem/Ansatz:

Hallo zusammen, könnte mir jemand bitte erklären was der Unterschied dazwischen ist?

Danke im Voraus!

Answer 1

Die Idee der strukturellen Induktion ist es, eine Aussage über Elemente zu beweisen, die sich aus einander (rekursiv) konstruieren lassen.

Die vollständige Induktion ist ein konkreter Anwendungsfall der strukturellen Induktion, bei der eine Aussage über alle natürlichen Zahlen getroffen wird.

Die natürlichen Zahlen lassen sich aber nach den Peano-Axiomen leicht aus einander konstruieren:

- das "Basiselement", die kleinste natürliche Zahl, ist die 0

- jeder Nachfolger $succ(n)=n+1$ einer natürlichen Zahl $n$ ist erneut eine natürliche Zahl, so also $1=succ(n)$, $2=succ(1)$ usw.

Möchtest du eine Aussage über alle natürlichen Zahlen beweisen, so zeigst du, dass sie für das Basiselement 0 erfüllt ist (Induktionsanfang), sowie für alle aus der Anwendung von $succ$ entstandenen Zahlen (Induktionsschritte).

Da sich jede natürliche Zahl aus der $0$ durch Anwendung endlich vieler $succ$-Operationen erzeugen lässt, hast du damit die Aussage für alle natürlichen Zahlen gezeigt.

Ein anderer Anwendungsfall der strukturellen Induktion könnte z.B. ein Beweis über alle (endlichen) Listen von natürlichen Zahlen sein.

Sei $L$ die Menge aller endlichen Listen über natürliche Zahlen mit $L=\{[x_1,...,x_n]| \ x_1,...,x_n\in \mathbb{N}\}$.

Sei $[]$ bezeichnet als die leere Liste, sowie $insert(x,[x_1,...,x_n])=[x_1,...,x_n,x]$ für $x_1,...,x_n,x\in \mathbb{N}$.

Dann können wir jedes Element aus $L$ über endlich viele Anwendungen von $insert$ aus der leeren Liste konstruieren, da alle $[x_1,...,x_n]\in L$ durch $insert$ von $x_1,...,x_n$ in $[]$ entstehen.

Im Induktionsanfang würdest du die Aussage für die leere Liste beweisen, in den Induktionsschritten für die Listen, die durch $insert$ entstehen.

Noch ein anderer Anwendungsfall wäre z.B. der Beweis über alle ganzen Zahlen.

Diese kann man z.B. in ihrere Struktur definieren wie folgt:

- 0 ist eine ganze Zahl

- jede Zahl $pred(n)=n-1$ für eine ganze Zahl $n$ ist erneut eine ganze Zahl

- jede Zahl $succ(n)=n+1$ für eine ganze Zahl $n$ ist erneut eine ganze Zahl

Im Induktionsanfang würdest du die Aussage für die $0$ beweisen, in den Induktionsschritten sowohl für $pred$, als auch für $succ$.

Noch ein weiterer Anwendungsfall könnte Induktion über alle booleschen Ausdrücke (bzw. aussagenlogischen Formeln) sein, bei welcher die Konstruktion durch Operatoren $\neg$ (Negation), $\land$ (Und), $\vee$ (Oder), $\rightarrow$ (Implikation), $\leftrightarrow$ (Äquivalenz) erfolgt, wobei $\rightarrow$ und $\leftrightarrow$ eigentlich auch wieder nur aus $\neg$, $\land$ und $\vee$ konstruiert werden.

Dazu findest du einen kleinen Absatz unten auf https://de.wikipedia.org/wiki/Strukturelle_Induktion .

Noch ein weiterer Anwendungsfall könnten Graphen sein, die du durch Hinzufügen von Knoten und Kanten aus einander konstruieren kannst...

Ich denke aus den Anwendungsfällen wird klar, dass der Begriff (strukturelle) Induktion weit umfassender ist als die reine vollständige Induktion über natürliche Zahlen.