Die vollständige Induktion

Ein grundlegender Satz über die natürlichen Zahlen ist:

Satz (Prinzip der vollständigen Induktion)

Gilt eine Eigenschaft natürlicher Zahlen für die Null und vererbt sie sich von jeder natürlichen Zahl auf ihren Nachfolger, so gilt sie für jede natürliche Zahl.

Genauer formuliert:

Satz (Prinzip der vollständigen Induktion, formale Version)

Sei ℰ(n) eine Eigenschaft natürlicher Zahlen. Dann gilt:

(+) ℰ(0) ∧ ∀n (ℰ(n) → ℰ(n + 1)) → ∀n ℰ(n)

Wer lieber mit Mengen als mit Eigenschaften argumentiert, wird folgende Version bevorzugen:

Satz (Prinzip der vollständigen Induktion, Version für Mengen)

Sei A ⊆ ℕ. Dann gilt:

(++) 0  ∈  A ∧ ∀n (n  ∈  A → n + 1  ∈  A) → A = ℕ

Die Mengen-Induktion für A ergibt sich durch Eigenschafts-Induktion mit der Eigenschaft

ℰ(n) = „n  ∈  A“.

Umgekehrt ergibt sich die Eigenschafts-Induktion für ℰ(n) durch Mengen-Induktion mit der Menge

A = { n  ∈  ℕ | ℰ(n) }.

Bemerkung zur logischen Stellung der Induktion

Wir haben die Induktion als Satz formuliert. In der Tat sind obige Sätze genauso beweisbar wie alle anderen Sätze der Mathematik, wenn wir eine mengentheoretische Axiomatik zugrunde legen, in der die Struktur der natürlichen Zahlen definiert wird. Wir betrachten die Prinzipien hier als gegeben, da wir eine mengentheoretische Konstruktion und Untersuchung der natürlichen Zahlen nicht durchführen wollen, sondern ℕ wie die anderen Zahlbereiche als gegeben betrachten. Dies entspricht dem Vorgehen der reinen Zahlentheorie, die − ohne mengentheoretischen Hintergrund − die Induktion in der Form (+) mit Eigenschaften als Axiom oder genauer als Axiomschema ansieht (ein Axiom pro Eigenschaft).

Die Induktion ist als Satz bzw. Axiom kein rein logisches Beweisprinzip wie etwa der indirekte Beweis oder der Widerspruchsbeweis. Aufgrund ihres schematischen Charakters wird sie aber als solches erlebt:

Verlauf eines Beweises durch vollständige Induktion

Um zu zeigen, dass jede natürliche Zahl n die Eigenschaft ℰ besitzt, können wir so vorgehen:

Induktionsanfang n = 0:

Wir zeigen ℰ(0).

Induktionsschritt von n nach n + 1:

Wir zeigen ℰ(n + 1) mit Hilfe der Induktionsvoraussetzung ℰ(n). Hierbei ist n eine beliebige natürliche Zahl.

Üblich sind in diesem Schema die folgenden Abkürzungen: I. A. für Induktionsanfang, I. S. für Induktionsschritt und I. V. für Induktionsvoraussetzung.

Im Induktionsschritt ist die schlichte Formulierung „Es gelte ℰ(n).“ als Induktionsvoraussetzung korrekter als „Sei ℰ(n) bereits bewiesen.“ Letzteres suggeriert einen unendlich langen Beweis. Der Induktionsschritt ist einfach ein Beweis einer für alle natürlichen Zahlen gültigen Implikation. Dies wird in der formalen Version besonders deutlich: Wir zeigen

∀n (ℰ(n) → ℰ(n + 1)).

Dies geschieht wie üblich:

„Sei n beliebig. Es gelte ℰ(n) (I. V.). Wir zeigen, dass ℰ(n + 1) (Beweisziel).“

Der Induktionsanfang und der Induktionsschritt zusammengenommen beweisen die durch ∧ verbundene Aussage auf der linken Seite des Implikationspfeils in (+):

ℰ(0) ∧ ∀n (ℰ(n) → ℰ(n + 1)).

Der Satz über Induktion liefert nun

∀n ℰ(n).

Varianten

(1)	Ist n₀ eine natürliche Zahl und wollen wir zeigen, dass jede natürliche Zahl n ≥ n₀ die Eigenschaft ℰ(n) besitzt, so zeigen wir ℰ(n₀) (Induktionsanfang n = n₀). Der Induktionsschritt von n nach n + 1 bleibt gleich, wobei nun n eine beliebige natürliche Zahl größergleich n₀ ist.

(2)	Den Induktionsschritt können wir auch von n − 1 nach n durchführen: Wir zeigen ℰ(n) mit Hilfe der Induktionsvoraussetzung ℰ(n − 1). Hier ist n eine beliebige Zahl größergleich 1.

(3)	Um zu zeigen, dass alle geraden Zahlen die Eigenschaft ℰ(n) besitzen, zeigen wir ℰ(0) und führen den Induktionsschritt von n nach n + 2 für gerade n durch. Wir zeigen im Induktionsschritt also ℰ(n + 2) unter der I. V. ℰ(n). Hierbei ist n eine beliebige gerade natürliche Zahl.

(4)	Viele weitere Varianten sind möglich.