Transfinite Rekursion
Neben dem Beweis durch transfinite Induktion gibt es die Definition durch transfinite Rekursion, die manchmal auch induktive Definition genannt wird. Hierbei wollen wir der Reihe nach für jede Ordinalzahl α ein Objekt 𝒢(α) in einer bestimmten Weise konstruieren, und dabei auf alle bereits konstruierten Objekte 𝒢(β) für β < α zurückgreifen. Die „bestimmte Weise“ ist gegeben durch eine Operation auf dem Universum V aller Objekte:
Definition (Eigenschaften als Operationen)
Eine Eigenschaft ℱ(x, y) heißt eine Operation auf V, falls für jedes Objekt x genau ein Objekt y existiert mit ℱ(x, y). Analog heißt 𝒢(α, y) eine Operation auf den Ordinalzahlen, falls für jede Ordinalzahl α genau ein Objekt y existiert mit 𝒢(α, y). Wir schreiben auch ℱ(x) = y, falls ℱ(x, y) gilt.
Dass wir hier von Eigenschaften reden anstatt einfach von Funktionen hängt damit zusammen, dass die Vielheit V aller Objekte keine Menge ist und also auch eine „Funktion“ ℱ : V → V keine Menge sein kann. Beispiele für Operationen auf V sind:
ℱ(x) = ⋃ x (d. h. ℱ(x, y) gilt genau dann, wenn y = ⋃ x),
ℱ(x) = ℘(x), jeweils mit der Konvention ⋃ x = ℘(x) = x, falls x Grundobjekt,
Hierbei ist x ein beliebiges Objekt des Universums. Im letzten Beispiel ist ℕ ein Parameter der Operation.
Bevor wir den Rekursionssatz formulieren und beweisen, werfen wir wieder einen Blick auf die natürlichen Zahlen. Ein Beispiel für eine rekursive Definition einer Operation 𝒢 auf ℕ − hier einfach eine Funktion auf ℕ − ist die Fakultät:
| (1) | 0! = 1, | (Rekursionsanfang) |
| (2) | (n + 1)! = n! · (n + 1) für n ∈ ℕ. | (Rekursionsschritt von n nach n + 1) |
Für die Fakultät 𝒢 : ℕ → ℕ, 𝒢(n) = n! für n ∈ ℕ, gilt also die Rekursionsgleichung
𝒢(n + 1) = 𝒢(n) · (n + 1) = ℱ(𝒢(n), n),
mit der Operation ℱ(m, n) = m · (n + 1).
Ein rekursiver Funktionswert 𝒢(n) kann aber auch von mehreren Werten 𝒢(m), m < n, abhängen. Ein bekanntes Beispiel hierfür liefern die Fibonacci-Zahlen 1, 1, 2, 3, 5, … Die n-te Fibonacci-Zahl 𝒢(n) ist hierbei rekursiv definiert durch 𝒢(0) = 𝒢(1) = 1, 𝒢(n) = 𝒢(n − 1) + 𝒢(n − 2) für n ≥ 2.
Allgemein ist der Rückgriff auf die ganze Liste der bereits definierten Funktionswerte möglich, und die Rekursionsgleichung lautet dann:
𝒢(n) = ℱ(〈 𝒢(n′) | n′ < n 〉) = ℱ(𝒢|n),
wobei ℱ eine gegebene Operation ist, die die „bestimmte Weise“ beschreibt, wie 𝒢(n) aus 𝒢(0), … , 𝒢(n − 1) hervorgeht. Speziell ist 𝒢(0) = ℱ(∅). (Der häufig zur Definition von 𝒢(n) = ℱ(𝒢|n) benötigte Index n selbst lässt sich aus 𝒢|n zurückgewinnen, denn es ist n = dom(𝒢|n).)
Für Ordinalzahlen lautet nun der allgemeine Rekursionssatz:
Satz (transfiniter Rekursionssatz)
Sei ℱ eine Operation auf V. Dann existiert genau eine Operation 𝒢 auf den Ordinalzahlen, sodass gilt:
(+) Für alle Ordinalzahlen α ist 𝒢(α) = ℱ(𝒢|W(α)),
wobei 𝒢|W(α) die Funktion gα : W(α) → V ist mit
gα(β) = 𝒢(β) für alle β < α.
Die Rekursionsgleichung (+) können wir auch in der Form
𝒢(α) = ℱ(〈 𝒢(β) | β < α 〉)
schreiben. So kommt besonders deutlich zum Ausdruck, dass das im α-ten Schritt mittels ℱ rekursiv definierte Objekt 𝒢(α) von allen in früheren Schritten β < α konstruierten Objekten 𝒢(β) abhängen kann.
Beweis
Wir zeigen zunächst die Existenz von 𝒢. Wir nennen für eine Ordinalzahl α eine Funktion g : W(α) → V eine α-Rekursion gemäß ℱ, falls gilt:
g(β) = ℱ(g|W(β)) für alle β < α.
(Derartige g sind die Anfangsstücke der gesuchten Operation 𝒢.)
Es gilt nun:
(i) | Für alle Ordinalzahlen α gilt: Sind g und h α-Rekursionen gemäß ℱ, so ist g = h. |
(ii) | Für alle Ordinalzahlen α existiert eine α-Rekursion gemäß ℱ. |
Beweis hierzu
zu (i): Sei α eine Ordinalzahl und seien g, h α-Rekursionen gemäß ℱ. Wir zeigen g(β) = h(β) durch Induktion nach β < α.
Induktionsschritt β < α: Es gelte g(β′) = h(β′) für alle β′ < β. Dann ist
g|W(β) = h|W(β), also g(β) = ℱ(g|W(β)) = ℱ(h|W(β)) = h(β).
zu (ii): Beweis durch Induktion nach α.
Induktionsanfang α = 0:
Die leere Menge ist eine 0-Rekursion gemäß ℱ.
Induktionsschritt von α nach α + 1:
Nach Induktionsvoraussetzung existiert eine α-Rekursion g gemäß ℱ. Sei g′ = g ∪ { (α, ℱ(g)) }. Dann ist g′ eine (α + 1)-Rekursion gemäß ℱ.
Limesschritt λ:
Nach Induktionsvoraussetzung und (i) existiert für jedes α < λ eine eindeutige α-Rekursion gα gemäß ℱ. Wir setzen:
g = ⋃α < λ gα.
Dann ist g eine λ-Rekursion gemäß ℱ.
Wir definieren nun eine Operation 𝒢 auf den Ordinalzahlen durch:
𝒢(α) = „das x mit g(α) = x, wobei g die eindeutige (α + 1)-Rekursion gemäß ℱ ist“.
Nach Konstruktion gilt dann 𝒢(α) = ℱ(𝒢|W(α)) für alle Ordinalzahlen α.
Dies zeigt die Existenz.
Zum Beweis der Eindeutigkeit seien nun 𝒢1, 𝒢2 Operationen mit (+) wie im Rekursionssatz. Dann sind 𝒢1|W(α) und 𝒢2|W(α) α-Rekursionen gemäß ℱ für alle Ordinalzahlen α. Also gilt
𝒢1|W(α) = 𝒢2|W(α) für alle α nach (i).
Dann gilt aber 𝒢1(α) = 𝒢2(α) für alle Ordinalzahlen α.
Hausdorff (1914):
„Wir können aber nicht nur induktiv schließen, sondern auch induktiv definieren. Bedeutet f (α) jetzt nicht eine Aussage hinsichtlich α, sondern ein der Zahl α zugeordnetes Ding, eine Funktion von α …, so lautet das induktive Definitionsverfahren:
f (α) ist für jedes α definiert, sobald f (0) definiert ist und sobald vermöge der Definition aller f (ξ) für ξ < α auch f (α) definiert ist.“
Hausdorff hat diese Möglichkeit der rekursiven Definition für so selbstverständlich erachtet, dass er keine weitere Begründung angibt.