Ein grundlegendes Beweisprinzip, das besagt, dass eine Eigenschaft P(n) für alle n∈ℕ gilt, wenn (i) P(0) zutrifft (Basisfall) und (ii) für jedes k gilt: P(k)⇒P(k+1) (Nachfolgerabschluss). In diesem Nachschlagewerk wird es als Schema dargestellt, das lokales Nachfolger-Reasoning in eine universelle Aussage über die natürlichen Zahlen überführt.

Prinzip

Ist S⊆ℕ eine Menge mit 0∈S und abgeschlossen unter dem Nachfolger (k∈S⇒k+1∈S), dann gilt S=ℕ; äquivalent bedeutet: Basis und Induktionsschritt ergeben einen Beweis für alle natürlichen Zahlen.

Demonstration

Um zu zeigen, dass für alle n die Gleichung n+0=n gilt, beweist man den Basisfall n=0: 0+0=0, nimmt an, dass n+k=k+n für beliebiges n gilt, und zeigt dann für k+1 mit Hilfe der Nachfolgerdefinition, dass die Gleichung weiterhin gilt; Basis und Schritt ergeben somit die Aussage für alle n via Induktion.

Fehlanwendung

Das Schema ohne gültigen Basisfall anwenden, eine unzulässige Induktionsannahme verwenden (z. B. Annahme von P(m) für m>k beim Beweis von P(k+1)), oder gewöhnliche Induktion auf nicht wohlgegründete Bereiche übertragen, führt zu fehlerhaften Folgerungen.

Konsequenz

Korrekt angewandt verwandelt Induktion eine endliche Überprüfung (Basis und Schritt) in eine unendliche Menge von Theoremen über alle natürlichen Zahlen; sie ist Grundlage für viele Konstruktionen in Arithmetik, Kombinatorik und Informatik und erzeugt Varianten wie starke oder strukturelle Induktion.

Umkehrung

Das Umgekehrte ist das Prinzip des Gegenbeispiels: ein einzelnes n mit ¬P(n) widerlegt die Allgemeinaussage; konzeptionell steht die Negation der Induktion für eine endliche Widerlegung statt eines universellen Beweises. Ein weiterer Kontrast ist die unendliche Abstiegsargumentation, die Unmöglichkeit durch Erzeugung immer kleinerer Gegenbeispiele zeigt.

Abgrenzung

Gilt für Eigenschaften über ℕ (oder beliebige Peano-ähnliche induktive Strukturen) mit definiertem Null- und Nachfolgeroperator; ohne wohlgegründete Struktur oder in anderen geordneten Mengen, z. B. den reellen Zahlen, ist eine geeignete wohlbegründete/strukturelle Induktion erforderlich.

Semantische Spannung

Spannung besteht zwischen einfacher Induktion, starker Induktion und struktureller/well-founded Induktion: auf ℕ sind sie oft äquivalent, doch unterscheiden sie sich in Formulierung und Beweistechnik, was zu Missverständnissen über die implizierte Form führen kann.

Synthese

Das Prinzip der Mathematischen Induktion verbindet lokale Prüfungen (Basis und Nachfolgeschritt) zu einer globalen Wahrheit über ℕ: durch Nachweis von Basis und Nachfolgerabschluss wird schrittweises Argumentieren zu einer Aussage, die für alle natürlichen Zahlen gilt, mit wohldefinierten Variationen für andere Strukturen.