## [Prinzip der Mathematischen Induktion](/de/node/60960) Definition 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 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 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 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 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 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 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 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 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.