next up previous contents
Nächste Seite: Fakultät, Binomialkoeffizient Aufwärts: Vollständige Induktion Vorherige Seite: Induktionsprinzip   Inhalt

Varianten des Induktionsprinzips

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

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ß:

$\displaystyle 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:

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

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ß:

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

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:

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

Anmerkung. Manchmal schreibt man auch suggestiver

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

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]).


next up previous contents
Nächste Seite: Fakultät, Binomialkoeffizient Aufwärts: Vollständige Induktion Vorherige Seite: Induktionsprinzip   Inhalt
Analysis1-A.Lambert 2001-02-09