Ein Beweisschema, das eine Eigenschaft für alle natürlichen Zahlen etabliert, indem ein Basisfall (gewöhnlich für 0 oder 1) gezeigt wird und ein Induktionsschritt, der beweist: wenn die Eigenschaft für ein beliebiges n gilt, dann gilt sie für n+1.

Prinzip

Lokal-zu-global-Übertragung auf N: Die ordnende Regel ist, dass die Verifikation einer Basis und die Nachfolgerstabilität ausreichen, um eine Eigenschaft mittels wiederholter Anwendung des Induktionsschritts auf alle natürlichen Zahlen zu übertragen.

Demonstration

Um eine Formel P(n) für alle n∈N zu beweisen, zeigt man P(0) und dass für beliebiges n aus P(n) folgt P(n+1). Beispielsweise beweist man per Induktion, dass die Summe der ersten n natürlichen Zahlen n(n+1)/2 ist, indem man den Basisfall n=0 und den algebraischen Induktionsschritt überprüft.

Fehlanwendung

Ordentliche Induktion anzuwenden, wenn der Induktionsschritt Annahmen über mehrere kleinere Werte erfordert (d. h. nur P(n)⇒P(n+1) zu verwenden, obwohl man Kenntnisse über alle k≤n bräuchte), oder keinen gültigen Basisfall für das beabsichtigte Gebiet zu etablieren.

Konsequenz

Gibt ein kanonisches Verfahren, unendlich viele Aussagen mit endlichem Aufwand zu beweisen; liegt rekursiven Definitionen, Beweisen der Korrektheit von Algorithmen auf den ganzen Zahlen und der Grundlage arithmetischer Eigenschaften zugrunde.

Umkehrung

Die Umkehr besteht darin zu zeigen, dass selbst bei vorhandenem Basisfall und einem behaupteten Induktionsschritt die Eigenschaft fehlschlagen kann, wenn Schritt oder Basis mangelhaft sind; das Weglassen des Basisfalls oder die Verwendung einer nichtstandardmäßigen Nachfolgerregel bricht die Übertragung auf alle natürlichen Zahlen.

Abgrenzung

Gilt für wohlgeordnete, nachfolgerbasierte Bereiche wie N; findet keine direkte Anwendung auf Strukturen ohne klaren Nachfolger oder auf Beweise, die transfinite oder strukturelle Induktion erfordern, ohne entsprechende Anpassung.

Semantische Spannung

Spannung zur starken oder strukturellen Induktion: Die gewöhnliche Induktion setzt eine Ein-Schritt-Nachfolgerimplikation voraus, während starke/strukturierte Varianten Voraussetzungen über alle kleineren Instanzen zulassen oder auf Struktur statt auf numerischen Nachfolger induzieren.

Synthese

Mathematische Induktion ist die endliche, zweistufige Verifikation (Basis und Nachfolgeschritt), die Wahrheit über die natürlichen Zahlen propagiert und als primäres Mittel für arithmetische Identitäten, Korrektheitsbeweise für Ganzzahl-Algorithmen und rekursiv definierte Eigenschaften dient.