Die Cantorsche Normalform
Die Ordinalzahlpotenzen ωα haben eine Reihe interessanter Eigenschaften, die wir im Folgenden näher untersuchen wollen.
Definition (Hauptzahlen)
Eine Ordinalzahl β heißt eine (additive) Hauptzahl, falls es eine Ordinalzahl α gibt mit β = ωα.
Zunächst betrachten wir für eine Ordinalzahl γ ≥ 1 die Stelle α etwas genauer, für die der Schritt von ωα zu ωα + 1 die Zahl γ erfasst:
Definition (ωα-Ausschöpfung)
Sei γ ≥ 1 eine Ordinalzahl. Wir setzen:
| E(γ) | = „die größte Ordinalzahl α mit ωα ≤ γ“, |
| N(γ) | = „das größte n ∈ ℕ mit ωE(γ) · n ≤ γ“, |
| R(γ) | = „die eindeutige Ordinalzahl ρ mit ωE(γ) · N(γ) + ρ = γ“. |
Dies ist wohldefiniert, und es gilt
0 ≤ R(γ) < ωE(γ) ≤ γ.
Große natürliche Zahlen kann man z. B. in Dezimalschreibweise „exponentiell verkürzt“ angeben. So ist etwa
1304 = 103 · 1 + 102 · 3 + 100 · 4.
Die Cantorsche Normalform ist nun ein Analogon für Ordinalzahlen, wobei ω statt 10 (oder allgemeiner statt einem n ∈ ℕ, n ≥ 2) als Basis gewählt wird.
Satz (Cantorsche Normalform zur Basis ω)
Jede Ordinalzahl γ lässt sich in eindeutiger Weise schreiben als
γ = ωα1 · n1 + … + ωαk · nk,
wobei k ∈ ℕ, 1 ≤ ni < ω für 1 ≤ i ≤ k, α1 > α2 > ... > αk ≥ 0. (Der Fall k = 0 entspricht γ = 0.)
Beweis
Wir zeigen die Existenz und Eindeutigkeit der Normalform durch Induktion über alle Ordinalzahlen γ. Für γ = 0 ist nichts zu zeigen. Sei also γ > 0. Wir setzen α1 = E(γ), n1 = N(γ). Wegen R(γ) < γ existiert nach Induktionsvoraussetzung eine Normalform von R(γ), die wir in der Form
R(γ) = ωα2 · n2 + ... + ωαk · nk
notieren können. Aber es gilt γ = ωα1 · n1 + R(γ), und damit ist wegen
ωα2 ≤ R(γ) < ωα1
offenbar eine Normalform von γ gefunden.
Zum Beweis der Eindeutigkeit sei
γ = ωα1 · n1 + ... + ωαk · nk
eine beliebige Normaldarstellung von γ. Dann ist
ωα2 · n2 + ... + ωαk · nk ≤ ωα2 · (n2 + ... + nk) < ωα2 · ω ≤ ωα1 .
Hieraus folgt, dass α1 = E(γ) und n1 = N(γ) gelten muss. Nach Induktionsvoraussetzung ist die Normaldarstellung von R(γ) eindeutig, und damit ist auch die von γ selbst eindeutig.
Cantor hat die Normaldarstellung in [Cantor 1897, § 19] nur für abzählbare Ordinalzahlen aufgestellt. Der Beweis von Cantor bleibt aber für alle Ordinalzahlen α richtig.
Es gibt auch eine Normalform zur Basis 2. Sie lautet:
Übung
Jede Ordinalzahl γ lässt sich in eindeutiger Weise schreiben als
γ = 2α1 + ... + 2αk, wobei k ∈ ℕ, α1 > α2 > ... > αk ≥ 0.
Allgemeiner existiert eine eindeutige Normalform zu jeder Basis β ≥ 2. Die Terme der Summe sind dann von der Form βα · δ, mit 1 ≤ δ < β. Zwei Zahlen γ1 und γ2 in Normalform zur Basis β können der Größe nach dann leicht verglichen werden, indem von „links nach rechts“ Exponenten und Koeffizienten auf einen Unterschied untersucht werden (völlig anlog zu 99 < 100 und 1046 < 1052).
Die Hauptzahlen lassen sich nun leicht charakterisieren:
Übung
Sei γ eine unendliche Ordinalzahl. Dann sind äquivalent:
(i) | γ ist eine Hauptzahl. |
(ii) | γ ist abgeschlossen unter Addition, d. h. δ1 + δ2 < γ für alle δ1, δ2 < γ. |
(iii) | Es gilt β + γ = γ für alle β < γ. |
Es gibt eine analoge Charakterisierung für die Ordinalzahlmultiplikation, und hierbei spielt zudem die Paarungsoperation Γ eine Rolle:
Übung
Sei γ eine unendliche Ordinalzahl. Dann sind äquivalent:
(i) | γ ist eine multiplikative Hauptzahl, d. h. es gibt eine Ordinalzahl α mit γ = ωωα. |
(ii) | γ ist abgeschlossen unter Multiplikation, d. h. es gilt δ1 · δ2 < γ für alle δ1, δ2 < γ. |
(iii) | Es gilt β · γ = γ für alle 1 ≤ β < γ. |
(iv) | Es gilt γ = Γ(0, γ) für die kanonische Paarungsfunktion Γ. |
Für alle multiplikativen Hauptzahlen γ ist also die Paarungsfunktion Γ eine einfach definierte Bijektion von W(γ)2 nach W(γ).
Eine wichtige Anwendung der Normalform ist eine auf den ersten Blick etwas kauzige Variante der Ordinalzahladdition.
Definition (Hessenbergsumme und Paarungssumme)
Seien γ, δ Ordinalzahlen, und sei
γ = ωα1 · n1 + ... + ωαk · nk,
δ = ωα1 · m1 + ... + ωαk · mk
die gemeinsame Normaldarstellung von γ und δ, d. h. wir lassen ni = 0 oder mi = 0 zu, um eine identische absteigende Folge von Exponenten zu erhalten; jedoch soll gelten ni ≠ 0 oder mi ≠ 0.
Dann ist die Hessenbergsumme von γ und δ, in Zeichen γ # δ, und die Paarungssumme von γ und δ, in Zeichen γ & δ, definiert durch:
| γ # δ | = ωα1 · (n1 + m1) + ... + ωαk · (nk + mk), |
| γ & δ | = ωα1 · π(n1, m1) + ... + ωαk · π(nk, mk), |
wobei π : W(ω) × W(ω) → W(ω) die Cantorsche Paarungsfunktion ist.
Satz
Sei α eine Hauptzahl. Dann ist & : W(α) × W(α) → W(α) bijektiv.
Beweis
Wir haben γ & δ < α für alle γ, δ < α, denn α ist als Hauptzahl abgeschlossen unter Addition, und damit auch unter Paarungssummen. Bijektivität folgt aus der Bijektivität der Cantorschen Paarungsfunktion π und der Eindeutigkeit der Normalform (und aus π(0, 0) = 0).
Korollar (Multiplikationssatz)
Sei M eine unendliche Menge. Dann gilt |M × M| = |M|.
Beweis
Sei α = |M|. Dann ist α eine unendliche Kardinalzahl und damit abgeschlossen unter Addition und somit eine Hauptzahl.
Dann aber |M| = |W(α)| = |W(α) × W(α)| = |M × M|.
In dieser Weise hat Hessenberg 1906 den Multiplikationssatz bewiesen. Er verwendet allerdings die Funktion # statt &, und braucht dann ein zusätzliches Argument, da die Hessenbergsumme nicht injektiv ist. Sie ist aber fast injektiv: Für jedes α existieren nur endlich viele Paare (γ, δ) mit γ # δ = α (!). Dies genügt Hessenberg für einen Beweis. Die naheliegende Bemühung der Cantorfunktion macht diesen Beweis des Multiplikationssatzes, der fast nur aus Definitionen besteht, aber noch etwas transparenter.
Die Hessenbergsumme # ist darüber hinaus in der Beweistheorie von Interesse. In der Mengenlehre haben wir die folgende kombinatorische Eigenschaft:
Übung
Seien α1, …, αn Ordinalzahlen. Dann gilt:
| α1 # … # αn = | sup { o.t.(⋃1 ≤ i ≤ n Ai) | Ai ist eine Menge von Ordinalzahlen mit o.t.(Ai) = αi für 1 ≤ i ≤ n }. |