7. Transfinite Induktion und Rekursion
Die transfinite Induktion und Rekursion ermöglicht Beweise und Definitionen entlang der Ordinalzahlen. Wir betrachten zunächst das Schema der vollständigen Induktion für die natürlichen Zahlen, das wir schon an verschiedenen Stellen verwendet haben, etwas genauer. Eine Form dieses Prinzips lautet:
Prinzip der vollständigen Induktion
Sei ℰ(n) eine Aussage. Es gelte:
(1) | ℰ(0) |
(2) | Für alle n ∈ ℕ gilt: ℰ(n) folgt ℰ(n + 1). |
Dann gilt ℰ(n) für alle n ∈ ℕ.
Im Gegensatz zur reinen Zahlentheorie, wo man dieses Prinzip als Axiom annimmt, ist in der Mengenlehre die Induktion ein beweisbarer Satz:
Beweis des Prinzips der vollständigen Induktion
Annahme, es gibt ein n ∈ ℕ mit non ℰ(n). Dann ist
A = { n ∈ ℕ | non ℰ(n) } ≠ ∅.
Da 〈 ℕ, < 〉 wohlgeordnet ist, hat also A ein kleinstes Element n. Nach (1) ist n ≠ 0. Sei also n = m + 1. Nach Definition von A und n gilt ℰ(m). Nach (2) folgt aus ℰ(m) aber ℰ(m + 1), also ℰ(n), Widerspruch!
Entscheidend ist also diese Eigenschaft: Existiert ein Gegenbeispiel zur Behauptung, so existiert ein kleinstes Gegenbeispiel. Dies ist aber gerade die Wohlordnungseigenschaft, und wir können nun mit einem ähnlichen Argument das Prinzip der Induktion auf die transfiniten Zahlen ausdehnen. Wir beweisen die transfinite Induktion in einer starken und kompakten Form, die folgender Version der vollständigen Induktion für die natürlichen Zahlen entspricht:
Prinzip der vollständigen Induktion: starke Form
Sei ℰ(n) eine Aussage.
Für alle n ∈ ℕ gelte:
| (+) | Gilt ℰ(m) für alle m < n, so gilt ℰ(n). |
Dann gilt ℰ(n) für alle n ∈ ℕ.
Der Beweis verläuft wie eben:
Ein kleinstes Gegenbeispiel liefert einen Widerspruch zur Voraussetzung (+). (Aus (+) folgt ℰ(0). Denn für n = 0 ist „für alle m < n gilt ℰ(m)“ sicher richtig. Also gilt ℰ(n) nach (+).)
Die Induktion wird angewendet, um „ℰ(n) gilt für alle n ∈ ℕ“ zu beweisen. Hierzu kann man (1) und (2) zeigen, oder man zeigt (+). Letzteres ist die stärkere Form der Induktion, da man für den Beweis von ℰ(n) die Gültigkeit der Aussage ℰ für alle Vorgänger von n als bereits bewiesen annehmen darf, nicht nur die Gültigkeit für einen unmittelbaren Vorgänger wie in (2).
Im Folgenden bezeichnen wir mit ℰ(α) eine Aussage über Ordinalzahlen, die auch Parameter enthalten darf. Z. B. ist ω ein Parameter in
ℰ(α) = „für alle Ordinalzahlen α ≥ ω gilt |α| = |α + 1|“.
Satz (Beweis durch transfinite Induktion)
Sei ℰ(α) eine Aussage. Für alle Ordinalzahlen α gelte:
(+) Gilt ℰ(β) für alle β < α, so gilt ℰ(α).
Dann gilt ℰ(α) für alle Ordinalzahlen α.
Beweis
Annahme nicht. Dann existiert eine Ordinalzahl γ, für die ℰ(γ) falsch ist. Dann ist also
A = { α ≤ γ | ℰ(α) ist falsch }
eine nichtleere Menge von Oridnalzahlen. Also besitzt A ein kleinstes Element α. Wegen Minimalität von α gilt dann ℰ(β) für alle β < α. Nach (+) gilt also ℰ(α), im Widerspruch zu α ∈ A.
Es genügt also, (+) zu zeigen, um eine Aussage ℰ(α) für alle Ordinalzahlen α nachzuweisen. Hierfür muss man zwar auch noch für ein beliebiges α die Aussage ℰ(α) beweisen, darf dabei aber annehmen, dass ℰ(β) für alle β < α bereits bewiesen ist. Man hat also zur Unterstützung eine − oft stillschweigend gemachte − Induktionsvoraussetzung zur Verfügung.
In der Praxis wird häufig die folgende dreiteilige Version der transfiniten Induktion verwendet, da man zum Nachweis von ℰ(α) nicht immer die Gültigkeit der Aussage für alle Vorgänger von α benötigt:
Ziel: ℰ(α) gilt für alle Ordinalzahlen α.
Zeige dies in drei Teilen:
| (1) | Es gilt ℰ(0). | (Induktionsanfang α = 0) |
| (2) | Aus ℰ(α) folgt ℰ(α + 1) für alle Ordinalzahlen α. | (Nachfolgerschritt von α nach α + 1) |
| (3) | Aus ℰ(α) für alle α < λ folgt ℰ(λ) für alle Limesordinalzahlen λ. | (Limesschritt λ) |
Man sieht sofort, dass die Argumentation über einen „kleinsten Ausreißer“ auch unter diesen Voraussetzungen zu einem Widerspruch führt, falls ℰ(γ) für eine Ordinalzahl γ falsch wäre. Denn ein kleinster Ausreißer ist entweder 0, ein Nachfolger α + 1 oder ein Limes λ. Und aus (1), (2) oder (3) folgt dann im jeweiligen Fall der Widerspruch.
In dieser Form ist die transfinite Induktion soweit als möglich analog zur üblichen „für 0 und von n nach n + 1“-Induktion der natürlichen Zahlen formuliert. Lediglich ein Limesschritt λ kommt hinzu, der zeigt, dass die Richtigkeit der Aussage nicht an einer Limesstufe zum ersten Mal verloren geht.
Ob man (+) wie im Satz oben oder die dreiteilige Form (oder andere Varianten) nachweist, hängt von der Hartnäckigkeit der Aussage ℰ(α) ab. Die Unterscheidung in Nachfolger- und Limesordinalzahlen ist aber den Ordinalzahlen so eigentümlich, dass die dreiteilige Form bei weitem am häufigsten verwendet wird.
Hausdorff (1914):
„Hier muß zunächst auf eine weitgehende Analogie mit der Reihe der endlichen Zahlen … hingewiesen werden, nämlich auf die Anwendbarkeit des sogenannten vollständigen Induktionsschlusses. Der Leser kennt aus zahllosen Beispielen den Schluss von ν auf ν + 1, der besagt: eine Aussage f (ν) bezüglich der endlichen Zahl ν ist für jedes ν richtig, falls f (0) richtig ist und falls aus der Richtigkeit von f (ν) auf die von f(ν + 1) geschlossen werden kann. Im Gebiete der endlichen und unendlichen Ordnungszahlen gilt nun ein ähnliches Schlußverfahren, nämlich:
Eine Aussage f (α) bezüglich der Ordnungszahl α ist für jedes α richtig, sobald f (0) richtig ist und sobald aus der Richtigkeit aller f (ξ) für ξ < α auf die Richtigkeit von f (α) geschlossen werden kann.“
Viele weitere Varianten werden oft ohne Kommentar verwendet, etwa die transfinite Induktion innerhalb eines Intervalls: Sind α0, α1 Ordinalzahlen und ist α0 < α1, so kann man „ℰ(α) gilt für alle α mit α0 ≤ α < α1“ beweisen, indem man zeigt:
| (1) | ℰ(α0), | |
| (2) | ℰ(α) folgt ℰ(α + 1) | für alle α ≥ α0 mit α + 1 < α1 |
| (3) | ℰ(α) für alle α mit α0 ≤ α < λ folgt ℰ(λ) | für alle Limesordinalzahlen λ < α1. |