Vollständige Induktion


Die vollständige Induktion beruht auf der Axiomatisierung der natürlichen Zahlen nach Peano. Insbesondere durch eine Verallgemeinerung seines fünften Axioms lässt sich die vollständige Induktion herleiten. Deshalb wird dieses fünfte und letzte Axiom auch Induktionsaxiom genannt. Verallgemeinert besagt es:
Enthält die Menge X die Zahl n0 und mit jeder natürlichen Zahl n auch deren Nachfolger n', so bilden die natürlichen Zahlen eine Teilmenge von X.

Seit dem deutschen Mathematiker Richard Dedekind, ist die vollständige Induktion folgendermaßen definiert:
Um zu beweisen, dass ein Satz für alle natürlichen Zahlen nm gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl nm stets seine Gültigkeit auch für die folgende Zahl n+1 folgt.

Damit ergibt sich für die volständige Induktion immer die selber Herangehensweise:
  1. Induktionsanfang: Für den gewählten Startwert n0 wir die Behauptung A(n0) bewiesen
  2. Induktionsvorraussetzung: Für einen beliebigen aber festen Wert n mit n ≥ n0 wird die Aussage A(n) als wahr angenommen
  3. Induktionsschritt: Unter der Induktionsvorraussetzung wir der Beweis geführt, dass die Aussage A(n+1) ebenfalls wahr ist.

Diese drei Schritte, also Induktionsanfang, Induktionsvorraussetzung und Induktionsschritt, stellen sicher, dass die Aussage auch für alle n Gültigkeit besitzt.

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972