Varianten des Induktionsprinzips

Anmerkung. Aus den Peano-Axiomen folgen alle weiteren Eigenschaften der natürlichen Zahlen; insbesondere:

• Die natürlichen Zahlen haben eine Anordnung (totale Ordnung).
• Die Addition und Multiplikation natürlicher Zahlen ergibt wieder natürliche Zahlen.

Die Herleitung dieser Aussagen erfolgt in einer langen Kette an sich einfacher Induktionsbeweise, die man aber in der richtigen Reihenfolge durchführen muß (siehe [LANDAU] ).

Wir verwenden diese Regeln im folgenden kommentarlos.

Anmerkung. Darüber hinaus kann man zeigen:

Jeder geordnete Körper, insbesondere $\mathbb{R}$, enthält die natürlichen Zahlen.

Letzteres kann man auch zur Definition der natürlichen Zahlen erheben.

In einem strengen axiomatischen Aufbau führe man zunächst die reellen Zahlen mit den folgenden Axiomen ein:

Körperaxiome (K1)-(K11), Ordnung (O1)-(O3) und die Supremumseigenschaft (S)

Anschließend kann man die natürlichen Zahlen als Teilmenge von $\mathbb{R}$ definieren und das Induktionsprinzip beweisen:

$\mathbb{N}$ ist der Durchschnitt aller Teilmengen $M \subset \mathbb{R}$, die die folgenden beiden Eigenschaften haben:
         $1\in M$.
         Aus $n\in M$ folgt $n+1 \in M$.
Es gibt solche Mengen $M$, z. B. $\mathbb{R}$ selber. Also ist $\mathbb{N}$ wohldefiniert und erfüllt das Induktionsprinzip.

Manchmal ist es praktischer, eine Aussage nicht für die natürlichen Zahlen, sondern für alle ganzen Zahlen ab einem $n_0\in\mathbb{Z}$ zu formulieren:

Feststellung 1.2.9 (Vollständige Induktion ab $n_0$)  

Es sei $n_0\in\mathbb{Z}$. Für $n\in \mathbb{Z}$ mit $n\geq n_0$ sei eine Aussage $A(n)$ gegeben. Es gelte:

Induktionsanfang:

$A(n_0)$ ist richtig .

Induktionsschritt:

Für alle $n\in \mathbb{Z}$, $n\geq n_0$ gilt der Schluß:

$$A(n) \quad\Rightarrow\quad A(n+1).$$

Dann ist $A(n)$ für alle $n\in \mathbb{Z}$ mit $n\geq n_0$ richtig.

Manchmal ist es hilfreich, statt der Aussage $A(n)$ die folgende Aussage zu beweisen:

$$B(n) \quad:\Leftrightarrow\quad A(1)$$ und $$\dots$$    und $$A(n)$$.$$$$

Beim Induktionschluß $B(n) \Rightarrow B(n+1)$ hat man stärkere Vorraussetzungen, muß aber nur $A(n+1)$ zeigen:

Feststellung 1.2.10 (Schluß $1,\dots,n \Rightarrow n+1$)  

Für alle $n\in \mathbb{N}$ sei eine Aussage $A(n)$ gegeben. Es gelte:

Induktionsanfang:

$A(1)$ ist richtig .

Induktionsschritt:

Für alle $n\in \mathbb{N}$ gilt der Schluß:

$$A(1)$$ und $$\dots$$    und $$A(n) \quad\Rightarrow A(n+1)$$.$$$$

Dann ist $A(n)$ für alle $n\in \mathbb{N}$ richtig.

Bezeichnung ( $\{1,\dots,n\}$)

Es sei $n\in \mathbb{N}$. Wir schreiben zur Abkürzung:

$$\{ 1,\dots,n \} :=\{ k \mid k\in\mathbb{N}$$, $$k\leqslant n \}$$.$$$$

Anmerkung. Manchmal schreibt man auch suggestiver

$$\{1,2,\dots,n\} :=\{1,\dots,n\}$$   .$$$$

Man beachte aber, daß im Falle $n=1$ dann $2\not\in \{ 1,2,\dots,n \}$ ist!.

Eine äquivalente Formulierung des Induktionsprinzip ist:

Feststellung 1.2.11 ( $\{1,\dots,n\}\subset M \Rightarrow n+1\in M$)  

Es sei $M\subseteq \mathbb{N}$ ein Menge mit den Eigenschaften

Induktionsanfang:

$1\in M$

Induktionsschritt:

$\{1,\cdots n\}\subseteq M \quad \Rightarrow \quad n+1 \in M$

Dann folgt $M=\mathbb{N}$.

Man benutzt das Induktionsprinzip bei der rekursiven Definition einer Funktion $f$, die für alle natürlichen Zahlen erklärt werden soll:

Feststellung 1.2.12 (rekursive Definition)  

Anfangswert:

Man gebe den Wert $f(1)$ an.

Rekursion:

Man gebe eine Vorschrift an, wie aus den Werten $f(1), \dots, f(n)$ der Wert $f(n+1)$ zu bilden ist.

Dann ist $f$ auf ganz $\mathbb{N}$ erklärt.

Bemerkung. 1. Manchmal beginnt die rekursive Definition auch mit einem Anfangswert $f(n_0)$ für ein $n_0\in\mathbb{Z}$.

2. Die Herleitung des Rekursionsprinzips aus dem Induktionsprinzip ist nicht so einfach (vgl. [VAN DER WAERDEN]).