Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 27.11.2000

\underline{(6.2) SATZ:} Beweis durch vollständige Induktion, 1. Version

Es sei A(n) ein Prädikat (n ∈ IN). Kann man dann die beiden folgenden Eigenschaften beweisen:

i) A(1) ist richtig,

ii) Aus der Richtigkeit von A(n) für eine beliebige natürliche Zahl n ∈ IN folgt die Richtigkeit von A(n + 1),

so ist A(n) für alle natürlichen Zahlen n ∈ IN richtig.

Formal läßt sich ii) schreiben als ∀ n ∈ IN : A(n) ⟹ A(n + 1)

Bezeichnungen: Ein Induktionsbeweis besteht immer aus 2 Beweis–Teilen:

1) dem Induktionsanfang (IA)

hier wird bewiesen, daß die Behauptung für n = 1 richtig ist

2) dem Induktionsschluß (IS) oder dem “Schluß von n auf n + 1“:

hier wird unter der Induktionsvoraussetzung (IV), daß die Behauptung für eine beliebige (aber feste) natürliche Zahl n richtig ist, die Induktionsbehauptung (IB) bewiesen, daß dann die Behauptung auch für n + 1 richtig ist.

(6.3) PEANO–Axiome für die natürlichen Zahlen:

P_{1}) 1 ist eine natürliche Zahl

P_{2}) Jede natürliche Zahl n besitzt eine natürliche Zahl n′ als Nachfolger

P_{3}) 1 ist nicht Nachfolger einer natürlichen Zahl

P_{4}) Haben zwei natürliche Zahlen denselben Nachfolger, so sind sie gleich

P_{5}) Induktionsprinzip

Eine Menge T natürlicher Zahlen, die 1 enthält und mit jeder Zahl auch deren Nachfolger, enthält alle natürlichen Zahlen.

Ordnet man jeder natürlichen Zahl ihren Nachfolger zu, so wird dadurch eine Abbildung ν : IN ⟶ IN definiert. Diese Abbildung ν ist injektiv (P_{4}) , aber nicht surjektiv, da 1 ∉ Bild(ν) (P_{3}). Etwas formaler:

P_{1}) 1 ∈ IN
P_{2}) ∀ n ∈ IN ∃ n′ ∈ IN : n′ = n + 1
P_{3}) ∀ n ∈ IN : n′ ≠ 1
P_{4}) ∀ m ∈ IN ∀ n ∈ IN : m′ = n′ ⟹ m = n
P_{5}) Induktionsprinzip

Ist T ⊆ IN mit i) 1 ∈ T und ii) ∀ n ∈ IN : n ∈ T ⟹ n′ ∈ T , so folgt T = IN.

\underline{(6.6) SATZ:} Beweis durch vollständige Induktion, 2. Version

Sei n_{0} ∈ IN eine feste natürliche Zahl und A(n) ein Prädikat (n ∈ IN , n ≥ n_{0}). Kann man dann die beiden folgenden Eigenschaften beweisen:

i) A(n_{0}) ist richtig,

ii) Aus der Richtigkeit von A(n) für eine beliebige natürliche Zahl n ≥ n_{0} folgt die Richtigkeit von A(n + 1),

so ist A(n) für alle natürlichen Zahlen n ≥ n_{0} richtig.

\underline{(6.7) SATZ:} Beweis durch vollständige Induktion, 3. Version

Sei n_{0} ∈ IN eine feste natürliche Zahl und A(n) ein Prädikat (n ∈ IN , n ≥ n_{0}). Kann man dann die beiden folgenden Eigenschaften beweisen:

i) A(n_{0}) ist richtig,
ii) Aus der Richtigkeit von A(n_{0}) , A(n_{0} +1) , A(n_{0} +2) , …, A(n) für eine

beliebige natürliche Zahl n ≥ n_{0} folgt die Richtigkeit von A(n + 1),

so ist A(n) für alle natürlichen Zahlen n ≥ n_{0} richtig.

Auch hier die zweite Bedingung noch einmal etwas formaler:

∀ n ∈ IN, n ≥ n_{0} : (∀ k ∈ IN, n_{0} ≤ k ≤ n : A(k)) ⟹ A(n + 1)