Eine direkte Definition der Exponentiation von Ordinalzahlen

 Die Exponentiation von Ordinalzahlen haben wir durch iterierte Anwendung der Multiplikation definiert. Auch die oben direkt definierten Operationen der Multiplikation und der Addition kann man rekursiv aus jeweils einfacheren Operationen gewinnen.

Übung

Sei α eine Ordinalzahl. Wir definieren α · β durch Rekursion über alle Ordinalzahlen β wie folgt:

α · 0 =  0,
α · (β + 1) =  α · β  +  α für β Ordinalzahl,
α · λ =  sup β < λ α · β für λ Limesordinalzahl.

Zeigen Sie, dass diese Multiplikation mit der alten übereinstimmt.

 Die Addition kann man rekursiv mit Hilfe der Nachfolgeroperation definieren:

α + 0  =  α,

α + (β + 1)  =  (α + β) + 1 für β Ordinalzahl,
α + λ  =  sup β < λ α + β für λ Limesordinalzahl.

 Diese Addition stimmt wie im Falle der Multiplikation mit der alten Addition überein.

 Umgekehrt stellt sich nun die Frage, ob die Exponentiation von Ordinalzahlen direkt, ohne ein rekursives Vorgehen, definiert werden kann. Es ist nicht so ohne weiteres klar, welche Menge als ein natürlicher Träger einer solchen direkten Exponentiation in Frage kommt.

 Die Antwort gibt die folgende Konstruktion.

Definition (die natürliche Exponentiation zweier Wohlordnungen)

Seien 〈 M, < 〉 und 〈 N, < 〉 Wohlordnungen. Dann ist die natürliche Exponentiation 〈 E, <* 〉 von 〈 M, < 〉 und 〈 N, < 〉, in Zeichen

〈 E, <* 〉  =  〈 M, < 〉〈 N, < 〉,

wie folgt definiert. Sei

E  =  { f  ∈  NM | f (x) ≠ 0M für nur endlich viele x  ∈  N } ,

wobei 0M das Anfangselement von M sei. (Also E = ∅, falls M = ∅, N ≠ ∅ und E = { ∅ }, falls N = ∅.) Für f, g  ∈  E mit f ≠ g sei

Δ(f, g)  =  max({ x  ∈  N | f (x) ≠ g(x) }).

Wir setzen dann für f, g  ∈  E:

f <* g  falls  f ≠ g und f (Δ) < g(Δ) für Δ = Δ(f, g).

Die Relation <* heißt die natürliche Ordnung auf E.

Übung

Seien 〈 M, < 〉, 〈 N, < 〉 Wohlordnungen. Dann ist 〈 E, <* 〉 = 〈 M, < 〉〈 N, < 〉 eine Wohlordnung.

 Tatsächlich entspricht nun die natürliche Exponentiation von Wohlordnungen der rekursiv definierten Exponentiation der Ordinalzahlen [Hausdorff 1906b, Hessenberg 1907]:

Satz (Hausdorff-Hessenberg Darstellung von αβ)

Seien 〈 M, < 〉 und 〈 N, < 〉 Wohlordnungen, und sei 〈 E, <* 〉 = 〈 M, < 〉〈 N, < 〉. Sei α = o. t.(〈 M, < 〉), β = o. t.(〈 N, < 〉). Dann gilt

αβ = o. t.(〈 E, <* 〉).

Insbesondere also αβ = o. t.(〈 W(α), < 〉〈 W(β), < 〉).

Beweis

Durch Induktion nach β bei festem α. Die Details seien dem Leser zur Übung überlassen.

 Ein bemerkenswertes Resultat! Die rekursiv definierte Exponentiation αβ kann durch eine Ordnung dargestellt werden, deren Träger eine kleine Teilmenge von NM ist, wobei o. t.(〈 M, < 〉) = α, o. t.(〈 N, < 〉) = β. Der Träger E besteht aus denjenigen Funktionen von N nach M, die nur an endlich vielen Stellen nichttriviale Werte annehmen. Die Ordnung <* ist über die maximale Stelle Δ(f, g) eines Unterschiedes von zwei Funktionen definiert (eine Definition über die minimale Stelle δ(f, g) eines Unterschiedes ergäbe im Normalfall keine Wohlordnung mehr: betrachte wieder M = { 0, 1 } , N = ℕ). Die Ordnung <* ist also die antilexikographische Ordnung auf der Teilmenge E von NM.

 Wir haben die natürliche Exponentiation hier ad hoc präsentiert. Sie lässt sich analytisch durch eine genaue Betrachtung des Limesschrittes der rekursiv definierten Exponentiation gewinnen. Der Leser ist aufgefordert, dies für den Fall ωω zu tun. Dabei ist die Beobachtung hilfreich, dass die Potenz ωω einer unendlichen Multiplikation nach links entspricht, also ωω = … · ω · … · ω · ω. Dies erklärt auch das Auftreten der maximalen Stellen Δ eines Unterschiedes in obiger Definition.

 Aus der direkten Definition der Ordinalzahlexponentiation erhalten wir einen weiteren Beweis des Multiplikationssatzes. Zunächst folgt aus dem Satz oben, dass die Größe von αβ nur von der Größe der Basis und des Exponenten abhängt:

Korollar

Seien α, β Ordinalzahlen. Dann ist |αβ| = ||α||β|| (mit Ordinalzahlexponentiationen αβ und |α||β|).

Beweis

Seien 〈 E1, <* 〉  =  〈 W(α), < 〉〈 W(β), < 〉,  〈 E2, <* 〉  =  〈 W(|α|), < 〉〈 W(|β|), < 〉.

Dann ist |E1| = |E2| (!). Aber es gilt o. t.(〈 E1, <* 〉) = αβ und o. t.(〈 E2, <* 〉) = |α||β|, sodass

|αβ| = |E1| = |E2| = ||α||β||.

 Zum Vergleich: |α + α| = ||α| + |α|| und |α · α| = ||α| · |α|| sind leicht zu sehen, da Addition und Multiplikation über Vereinigung und Kreuzprodukt direkt definiert sind. Aus der rekursiven Definition für die Exponentiation ist dagegen |2α| = |2|α|| keineswegs klar. Die Aussage lässt sich induktiv beweisen, wenn der Multiplikationssatz benutzt wird, was wir hier gerade vermeiden wollen. Die Hausdorff-Hessenberg-Darstellung von 2α liefert direkt, dass die Größe von 2α nur von der Größe des Exponenten abhängt.

 Zur Vorbereitung des Arguments betrachten wir folgenden Beweis für die Abgeschlossenheit einer unendlichen Kardinalzahl unter Addition.

Satz (2 · κ = κ und additive Abgeschlossenheit unendlicher Kardinalzahlen)

Sei κ eine unendliche Kardinalzahl. Dann gilt 2 · κ = κ. Insbesondere ist α + β < κ für alle α, β < κ.

Beweis

Annahme nicht. Sei dann o. E. κ das kleinste Gegenbeispiel. Wegen κ < 2 · κ = sup { 2 · α | α < κ } existiert dann ein α < κ mit κ ≤ 2 · α. Dann ist |2 · |α|| = |2 · α| ≥ κ > α ≥ |α| und ω ≤ |α| < κ, im Widerspruch zur Minimalität von κ.

Zusatz: Für α ≤ β < κ ist |α + β| ≤ |β + β| = |β · 2| = |2 · β| ≤ 2 · β  < κ, also auch α + β < κ, da κ Kardinalzahl.

 Ein weiteres Argument ist: Es gilt allgemein 2 · λ = λ für alle Limesordinalzahlen λ, wie eine Induktion nach λ zeigt. Jede Kardinalzahl κ ≥ ω ist aber eine Limesordinalzahl.

 Analog folgt nun:

Satz (2κ = κ und multiplikative Abgeschlossenheit unendlicher Kardinalzahlen)

Sei κ eine unendliche Kardinalzahl. Dann ist 2κ = κ (ordinalzahlarithmetisch). Insbesondere ist α · β < κ für alle α, β < κ.

Beweis

Annahme nicht. Sei dann o. E. κ das kleinste Gegenbeispiel. Wegen

κ  <  2κ  =  sup { 2α | α < κ }

existiert ein α < κ mit 2α ≥ κ. Dann ist aber |2|α|| = |2α| ≥ κ > |α| ≥ ω, im Widerspruch zur Minimalität von κ.

Zusatz: Sind α ≤ β < κ, so ist β + β < κ und damit:

α · β  ≤  β · β  ≤  2β · 2β  =  2β + β  <  2κ  =  κ.

Korollar (Multiplikationssatz)

Sei M eine unendliche Menge. Dann ist |M × M| = |M|.

Beweis

Sei κ = |M|. Dann ist |M × M| = |κ · κ| < κ+ wegen κ · κ  < κ+. Hieraus folgt |M × M| = κ.

 Dieser Beweis des Multiplikationssatzes folgt [Hessenberg 1907]. Das Argument ist eine hübsche Anwendung der direkten Definition der Exponentiation.

 Schließlich halten wir fest:

Korollar (Exponentiationssatz)

(i)

Seien α, β Ordinalzahlen mit αβ ≥ ω. Dann gilt |αβ| = max(|α|, |β|).

(ii)

Seien 〈 M, < 〉, 〈 N, < 〉 Wohlordnungen, und sei 〈 E, <* 〉  =  〈 M, < 〉〈 N, < 〉.

Ist E unendlich, so gilt |E| = max(|M|, |N|).

Beweis

zu (i):  Sei κ = max(|α|, |β|). Dann ist κ ≥ ω. Offenbar κ ≤ αβ, also auch κ ≤ |αβ| wegen κ Kardinalzahl. Es gilt αβ ≤ (2α)β = 2α · β. Also

|αβ|  ≤  |2|α · β||  =  |2κ|  =  κ.

zu (ii):  Sei α = o. t.(〈 M, < 〉), β = o. t.(〈 N, < 〉). Dann gilt |E| = |αβ|, und die Behauptung folgt also aus (i).

 Die systematische Untersuchung linearer Ordnungen war einer der Schwerpunkte der mengentheoretischen Forschung von Felix Hausdorff. Ziel war ein systematischer Aufbau aller Typen von linearen Ordnungen durch arithmetische Operationen. Hausdorffs Vision einer „Beherrschung der Typenwelt“ erfüllte sich nur zum Teil. Die Wege von einfachen zu komplizierteren linearen Ordnungen erwiesen sich als zu verzweigt, um durch eine Strukturtheorie vollständig vermessen und kartographiert werden zu können. Man wird also mit Teilresultaten zufrieden sein müssen, zumal die Theorie der Wohlordnungen schon komplex genug ist. Eine Methode, die Hausdorff in der Verhaltensforschung linearer Ordnungen einsetzte, werden wir im nächsten Kapitel noch kennenlernen.

Aus der Einleitung von Felix Hausdorffs „Grundzüge einer Theorie der geordneten Mengen“

 „Im Folgenden wird zum ersten Male eine systematische und möglichst allgemein gehaltene Einführung in das von Herrn G. Cantor erschlossene, aber noch so gut wie unbekannte Gebiet der einfach [linear] geordneten Mengen versucht, von denen bisher eigentlich nur die wohlgeordneten Mengen und die Mengen reeller Zahlen eine eingehende Betrachtung erfahren haben. Auch meine eignen Vorarbeiten, von denen hier übrigens nichts vorausgesetzt wird, verfolgen im ganzen eine speziellere Richtung … In der vorliegenden Abhandlung, sollte sie nicht zum Buche anschwellen, mussten diese spezielleren [Ordnungs-] Typen durchaus in die Rolle gelegentlicher Illustrationsbeispiele zurücktreten und die allgemeinen Methoden den Vordergrund einnehmen. Das vorschwebende Ideal war etwa eine Beherrschung der Typenwelt in dem Sinne, dass die komplexen Gebilde durch erzeugende Operationen aus elementaren aufgebaut erscheinen sollten … “

(Felix Hausdorff 1908)