Die vollständige Induktion ist das wichtigste Beweisprinzip für Eigenschaften von natürlichen Zahlen.

Die natürlichen Zahlen lassen sich im Rahmen der Mengenlehre wie folgt repräsentieren: 0 ≔ Ø (leere Menge), 1 ≔ {0} (die Menge, die nur 0 als einziges Element enthält), 2 ≔ {0, 1} (die Menge, die aus den beiden Elementen 0, 1 besteht), 3 ≔ {0, 1, 2}, usw. Ist auf diese Weise eine natürliche Zahl n ≔ {0, 1,..., n − 1} gegeben, dann ist der unmittelbare Nachfolger n′ oder n + 1 von n als n′ ≔ n ∪ {n} definiert (die Menge n vereinigt mit der Einermenge {n}); dies ergibt die Menge

\begin{eqnarray}{n}^{\prime}=n+1=\{0,1,\ldots, n-1,n\}.\end{eqnarray}

Die natürliche Zahl n ist also eine Menge, die (im anschaulichen Sinne) aus n Elementen besteht. Faßt man genau die Elemente zusammen, die – mit der leeren Menge beginnend – aus Ø durch Nachfolgerbildung erzeugt werden können, so erhält man eine neue Menge, die Menge ℕ der natürlichen Zahlen (die Existenz dieser Mengen wird durch mengentheoretische Axiome gesichert).

Häufig wird die Arithmetik ohne Rückgang auf die Mengenlehre eingeführt. In diesem Falle legt man das Peanosche Axiomensystem zugrunde (Arithmetik Erster Ordnung, Peano-Axiome) und leitet alle betrachteten Eigenschaften für natürliche Zahlen aus diesen Axiomen her. Im Rahmen der Mengenlehre sind die Peano-Axiome beweisbare Sätze.

Das Induktionsprinzip beruht insbesondere auf der Gültigkeit des Induktionsaxioms (auch fünftes Peanosches Axiom):

Die Menge der natürlichen Zahlen ist die kleinste Menge, die die Null enthält, und die mit jeder natürlichen Zahl auch deren unmittelbaren Nachfolger enthält.

Der folgende grundlegende Satz über die vollständige Induktion legt eine Strategie fest, wie Induktionsbeweise zu führen sind.

Trifft eine Eigenschaft E auf die natürliche Zahl 0 zu, und folgt für jede natürliche Zahl n aus der Gültigkeit von E(n) auch die Gültigkeit von E(n + 1), dann besitzen alle natürlichen Zahlen die Eigenschaft E.

In übersichtlicher (formalisierter) Form lautet der Satz dann:

\begin{eqnarray}E(0)\wedge \forall n(E(n)\to E(n+1))\to \forall mE(m),\end{eqnarray}

wobei m, n Variablen für natürliche Zahlen sind, und E eine beliebige Eigenschaft für solche Zahlen darstellt. Um also ∀mE(m) zu beweisen, genügt es, die folgenden Beweisschritte zu überprüfen:

1. E(0), (d. h., die Eigenschaft E trifft auf die Null zu; dieser Beweisschritt heißt auch Induktionsanfang).
2. ∀n(E(n) → E(n + 1)) (Induktionsschritt).

Eine All-Aussage

\begin{eqnarray}{\forall}_{n}(E(n)\to E(n+1))\end{eqnarray}

ist genau dann gültig, wenn

\begin{eqnarray}E(m)\to {\rm{\hspace{0.17em}}}E(m+1)\end{eqnarray}

für jede konkrete natürliche Zahl m gilt. Daher setzt man beim Induktionsschritt (2.) voraus, daß m eine beliebige, aber dann fixierte natürliche Zahl ist. Für dieses konkrete m ist die ImplikationE(m) → E(m + 1) zu beweisen, hierbei heißt E(m) Induktionsvoraussetzung und E(m + 1) Induktionsbehauptung.

Eine Implikation ist schon immer dann wahr, wenn die Prämisse falsch ist. Wenn also E auf m nicht zutrifft, dann ist die Implikation trivialerweise richtig, und man hat nichts zu beweisen. Dieser triviale Fall wird in der Regel bei Induktionsbeweisen übergangen. Es bleibt nur der Fall zu betrachten, daß E(m) gilt. Unter dieser Voraussetzung ist E(m + 1) nachzuweisen. Wegen der Richtigkeit des Induktionsaxioms in der Form

\begin{eqnarray}E(0)\wedge {\rm{\hspace{0.17em}}}{\forall}_{n}(E(n)\to E(n+1))\to {\forall}_{m}E(m)\end{eqnarray}

ist somit ∀mE(m) gezeigt, da die Prämisse des Axioms als richtig nachgewiesen wurde.

Achtung! Häufig benutzte falsche Formulierung für die Induktionsvoraussetzung: „Für eine beliebige natürliche Zahl n gelteschon E(n)”. Wer dies so formuliert, hat die Behauptung bereits vorausgesetzt.

Die folgenden Modifikationen des Induktionsaxioms lassen entsprechend modifizierte Induktionsbeweise zu:

Seien m, k natürliche Zahlen, dann gilt:

• \(E(k)\wedge \forall n(k\le n\wedge E(n)\to E(n+1))\to \forall n(k\le n\to E(n))\)
• \(E(k)\wedge \forall n(k\le n\lt m\wedge E(n)\to E(n+1))\to \forall n(k\le n\le m\to E(n))\)

wline>Im ersten Fall wird die Eigenschaft E für alle natürlichen Zahlen nachgewiesen, welche größer oder gleich k sind, im zweiten Fall sind es alle n mit k ≤ n ≤ m.

Induktive Beweise lassen sich nicht nur für natürliche Zahlen, sondern auch für beliebige Mengen von Elementen führen, denen zuvor natürliche Zahlen zugeordnet worden sind, so, daß die Elemente der Menge dadurch eine gewisse Stufung erfahren haben. Dabei können auch mehrere Elemente die gleiche Stufe erhalten.

Betrachtet man z. B. die Menge M aller Ausdrücke des Aussagenkalküls, wobei p₁, p₂, p₃, … als Aussagenvariablen, \(\neg, \wedge, \vee, \to, \leftrightarrow \) als Konnektoren, und (,) als technische Zeichen auftreten, dann sind die Aussagenvariablen atomare Ausdrücke oder Ausdrücke der Stufe 0.

Sind φ, ψ Ausdrücke mit einer Stufe kleiner oder gleich n, dann sind

\begin{eqnarray}(\neg \varphi),(\varphi \wedge \psi),(\varphi \vee \psi),(\varphi \to \psi),(\varphi \leftrightarrow \psi)\end{eqnarray}

Ausdrücke mit der Stufe n + 1. Durch die Stufung der Ausdrücke kann ein Induktionsbeweis für die Menge aller Ausdrücke vorgenommen werden.

Literatur

[1] Ebbinghaus, H.-D.: Einführung in die Mengenlehre. B.I.-Wissenschaftsverlag Mannheim, 1994.

[2] Tuschik, H.-P.; Wolter, H.: Mathematische Logik – kurzgefaßt. B.I.-Wissenschaftsverlag Mannheim, 1994.