Strukturelle Induktion

Wer sich mit Informatik oder Mathematik beschäftigt, wird früher oder später einen Beweis führen. Etwa bei der Zugabe zu „Mathematische Folgen“ war das der Fall. Bei endlich vielen Fällen ist das eher überschaubar: Um etwa zu beweisen, dass alle Kinder von Hanspeter größer als 1,40m sind, muss man einfach zu Klaus, Franz und Giesela gehen und nachmessen. Spannend wird es, wenn (wie im genannten Beispiel) über unendlich viele Fälle gesprochen wird.

Im vorliegenden Fall wurde die vollständige Induktion benutzt. Diese bietet sich an, wenn über natürliche Zahlen gesprochen wird, die die Fälle durchnummereien. Zunächst wird eine kleinste natürliche Zahl identifiziert und für den zugehörigen (meist trivialen) Fall ein Beweis geführt. Dies ist der Induktionsanfang. Im Anschluss wird eine Induktionsbehauptung aufgestellt, die besagt, dass es eine Zahl n gibt, bis zu der die zu beweisende Behauptung nachgewiesen ist. Im folgenden Induktionsschritt wird nun gezeigt, dass die Behauptung, so sie denn für n gilt, auch für den Nachfolger gilt. Nun ist die Aussage für jeden beliebige der unendlich vielen Fälle bewiesen, da sich jeder natürliche Zahl (also auch jeder Fall) durch entsprechend häufige Anwendung des Induktionsschrits erreichen lässt.

Induktion ohne natürliche Zahlen

Nun kann es sein, dass unsere Menge von Fällen gar nicht über die natürliche sondern etwa rekursiv definiert ist. Das kann so aussehen:

• Die Menge enthält die Worte „UND“, „NUDELN“ und „POMMES“.
• Für jedes Wort der Menge sind auch die Wörter enthalten, die durch Anhängen von „_UND_NUDELN“ und „_UND_POMMES“ entstehen.
• Die Menge ist genau die von den ersten beiden Punkten beschriebe Menge. (Es sind alle so erzeugbaren Wörter enthalten und sonst nichts)

Wie beweist man nun Behauptungen wie „In jedem Wort kommen ‚NUDELN‘ und ‚POMMES‘ höchstens ein mal öfter als ‚UND’ vor.“? Nun, wir haben zwar keine natürlichen Zahlen zu Verfügung, es lässt sich jedoch ein ähnliches Muster erkennen: Der erste Punkt stellt Anfangselemente dar (entspricht 0 oder 1 bei natürlichen Zahlen), der zweite erläutert, wie die Nachfolger der Elemente rekursiv gebildet werden (entspricht n+1 bei natürlichen Zahlen). Ein Beweis funktioniert dann so:

Beispiel einer strukturellen Induktion

Zu zeigen: anzahl_nudeln(w) ≤ anzahl_und(w) + 1 sowie anzahl_pommes(w) ≤ anzahl_und(w) + 1

Induktionsanfang

Sei w das Wort „UND“, „NUDELN“ oder „POMMES“ aus der Sprache.

• w ≡ „UND“: anzahl_und(w) = 1; anzahl_nudeln(w) = anzahl_pommes(w) = 0. ✓
• w ≡ „NUDELN“: anzahl_und(w) = anzahl_pommes(w) = 0; anzahl_nudeln(w) = 1. ✓
• w ≡ „POMMES“: anzahl_und(w) = anzahl_nudeln(w) = 0; anzahl_pommes(w) = 1. ✓

Induktionsvoraussetzung

Die zu zeigende Behauptung gelte für ein Wort w.

Induktionsschritt

Die Behauptung gilt für das Wort w. Zeige nun, dass sie auch für das Wort w*, das durch Anhängen von „_UND_NUDELN“ oder „_UND_POMMES“ entsteht.

• w* entsteht durch Anhängen von „_UND_NUDELN“. anzahl_und(w*) = anzahl_und(w)+1; anzahl_nudeln(w*) = anzahl_nudeln(w)+1; anzahl_pommes(w*) = anzahl_pommes(w); nach IV: anzahl_pommes(w) ≤ anzahl_und(w) + 1 → anzahl_pommes(w*) ≤ anzahl_und(w) + 1 + 1 → anzahl_pommes(w*) ≤ anzahl_und(w*) + 1; Nach IV: anzahl_nudeln(w) ≤ anzahl_und(w) + 1 → anzahl_nudeln(w) + 1 ≤ anzahl_und(w) + 1 + 1 → anzahl_nudeln(w*) ≤ anzahl_und(w*) + 1 ✓
• w* entsteht durch Anhängen von „_UND_POMMES“: analog.

QED

Nun wurde die Aussage für alle Elemente der unendlichen Menge gezeigt, da die elementaren Wörter der Behauptung genügen und die Bildungsvorschriften die Behauptung erhalten. Gut. Das war quick-and-dirty. Die Wikipedia und das Logikskript (2002, Madlener, S.2) erklären das noch mal richtig. Die verwendete Sprache ist übrigens an ein Beispiel aus „Software-Entwicklung 3“ (Gotzhein) angelehnt.