Starke Induktion und Prinzip des kleinsten Elements
Die Ordnung ≤ auf den natürlichen Zahlen erlaubt es uns, ein starkes neues Induktionsprinzip zu formulieren und aus dem alten abzuleiten. Bei diesem Prinzip haben wir die Induktionsvoraussetzung nicht nur für eine Zahl zur Verfügung, sondern für alle „bereits durchlaufenen“ Zahlen. Wir definieren hierzu:
Definition (die Anfangsstücke W(n))
Für alle n ∈ ℕ setzen wir
W(n) = { m ∈ ℕ | m < n } für alle n ∈ ℕ.
und nennen W(n) das durch n gegebene Anfangsstück von ℕ.
Wir zeigen nun:
Satz (starke Induktion)
Sei X ⊆ ℕ und für alle n ∈ ℕ gelte:
(+) W(n) ⊆ X impliziert n ∈ X.
Dann gilt X = ℕ.
Beweis
Wir zeigen durch Induktion nach n, dass W(n) ⊆ X für alle n ∈ ℕ gilt.
Induktionsanfang:
Trivialerweise ist W(0) = ∅ ⊆ X.
Induktionsschritt von n nach S(n):
Nach I. V. gilt W(n) ⊆ X. Nach (+) ist also auch n ∈ X. Folglich ist W(S(n)) = W(n) ∪ { n } ⊆ X.
Damit können wir wie folgt zeigen, dass eine Eigenschaft ℰ(n) für alle n ∈ ℕ gilt: Wir zeigen für ein beliebiges n, dass ℰ(n) gilt, und dürfen dabei annehmen, dass ℰ(m) für alle m < n bereits gezeigt ist.
Analog können wir bei der rekursiven Definition einer Funktion f mit Definitionsbereich ℕ alle Werte f (m), m < n, zur Definition von f (n) verwenden.
Wir folgern aus der starken Induktion noch eine fundamentale Eigenschaft der natürlichen Zahlen.
Korollar (Prinzip des kleinsten Elements)
Sei X ⊆ ℕ nichtleer. Dann besitzt X ein kleinstes Element (bzgl. ≤), d. h. es gibt ein n ∈ X derart, dass n ≤ m für alle m ∈ X gilt.
Beweis
Annahme nicht. Wir zeigen durch starke Induktion, dass n ∉ X für alle n ∈ ℕ gilt, im Widerspruch zu X nichtleer.
Induktionsschritt n:
Nach I. V. gilt m ∉ X für alle m < n, d . h. es gilt W(n) ∩ X = ∅. Dann gilt aber auch n ∉ X, da sonst n das kleinste Element von X wäre.
De facto sind die starke Induktion und das Prinzip des kleinsten Elements rein logisch äquivalent. Wir diskutieren dies in den Übungen.
Allgemein heißt eine lineare Ordnung ≤ auf einer Menge M eine Wohlordnung, falls jedes nichtleere X ⊆ M ein kleinstes Element besitzt. Die Ordnung auf den natürlichen Zahlen ist also eine Wohlordnung.
Das Prinzip des kleinsten Elements wird oft wie folgt angewendet. Wir wollen wieder zeigen, dass X = ℕ für eine Teilmenge X von ℕ gilt. Annahme, dies ist nicht der Fall. Dann ist die Komplementmenge Y = ℕ − X nichtleer und besitzt also ein kleinstes Element n*. (Ist hier X = { n ∈ ℕ | ℰ(n) }, so ist n* also das kleinste „Gegenbeispiel“ für die Eigenschaft ℰ(n).) Wir argumentieren nun solange, bis wir ein n′ < n* gefunden haben, das ebenfalls ein Element von Y ist. Damit ist dann der erwünschte Widerspruch erreicht, denn n′ widerspricht der minimalen Wahl von n*.