Kardinalzahlen sind Mengen, die als Repräsentanten von Mengen einer bestimmten Größe dienen. Entsprechend ist eine Ordinalzahl eine Menge, die den Ordnungstyp einer wohlgeordneten Menge repräsentiert.

Eine Menge M heißt Ordinalzahl oder Ordnungszahl genau dann, wenn sie transitiv ist und durch die Elementrelation wohlgeordnet wird, d. h. genau dann, wenn jedes Element von M auch Teilmenge von M ist und jede Teilmenge von M ein e-kleinstes Element hat. Jede Wohlordnung ist dann zu genau einer Ordinalzahl isomorph, und man nennt diese Ordinalzahl den Ordnungstyp der Wohlordnung.

Die Klasse der Ordinalzahlen wird mit ON bezeichnet. ON wird auch Ordinalzahlreihe genannt. ON ist eine echte Klasse. Die Annahme, daß ON eine Menge ist, führt zur Antinomie von BuraliForti (Burali-Forti, Antinomie von). ON ist durch e wohlgeordnet. Hier und im folgenden wird gelegentlich über Eigenschaften echter Klassen gesprochen, und es werden Abbildungen und Relationen auf echten Klassen betrachtet. Zur formalen Interpretation solcher Sachverhalte siehe Axiomatische Mengenlehre.

Wir werden im folgenden bei Vergleichen von Ordinalzahlen auch α< β anstatt α ∈ β schreiben.

Man definiert die Nachfolgeoperation \(\mathbf{N} : \mathbf{ON} \rightarrow \mathbf{ON}, \alpha \mapsto \alpha \cup \{\alpha\}.\) α heißt Nachfolgeordinalzahl genau dann, wenn es eine Ordinalzahl β mit α = N(ß) gibt. Eine Ordinalzahl, die von der leeren Menge verschieden und keine Nachfolgeordinalzahl ist, heißt Limesordinalzahl.

Die leere Menge wird auch als Null bezeichnet: 0 ≔ ø. Mit Hilfe von N lassen sich nun die natürlichen Zahlen definieren: 1 ≔ N(0), 2 ≔ N(l) usw. Die Menge der natürlichen Zahlen ω oder ℕ₀ ist definiert als die kleinste Limesordinalzahl. Das Symbol ℕ bezeichnet die Menge der natürlichen Zahlen ohne die Null: ℕ ≔ ℕ₀ \{0}. Diese Bezeichnungsweise ist jedoch in der Literatur nicht einheitlich.

Ordinalzahlen α mit α< ω heißen endliche oder finite Ordinalzahlen; Ordinalzahlen α mit α ≥ ω heißen unendliche oder transfinite Ordinalzahlen.

Man nennt ℕ₀ nach obiger Definition auch die Menge der natürlichen Zahlen im von Neumannschen Sinn. Im Gegensatz dazu definiert Zermelo 0_Z ≔ oslash;, 1_Z ≔ {0_Z}, 2_Z ≔ {1_Z} usw. Daher nennt man ℕ_0,Z ≔ {0_Z, 1_Z,…} die Menge der natürlichen Zahlen im Zermeloschen Sinn.

Eine konstruktionsunabhängige Charakterisierung der natürlichen Zahlen wird mit Hilfe des Peano-Axiomensystems erreicht. Das Peano-Axiomensystem für eine Menge \({\mathcal{N}}\) und eine Abbildung \({\mathcal{S}}:{\mathcal{N}}\to {\mathcal{N}}\) (man nennt \({\mathcal{S}(n)}\) auch den Nachfolger von n) lautet:

1. \(\emptyset \in {\mathcal{N}}\)
2. \(\emptyset \in {\mathcal{S}}({\mathcal{N}})\) d. h., ø ist nicht Nachfolger einer Zahl aus \({\mathcal{N}}\).
3. \(\mathop{\wedge }\limits_{m,n\in {\mathcal{N}}}m\ne n\Rightarrow \mathcal{S}(m)\ne \mathcal{S}(n)\)d.h., verschie-dene Zahlen haben verschiedene Nachfolger.
4. \(\mathop{\bigwedge }\limits_{N\subseteq {\mathcal{N}}}\left(\emptyset \in N\wedge \mathop{\bigwedge }\limits_{n\in N}\mathcal{S}(n)\in N\right)\Rightarrow N={\mathcal{N}}\) d.h., enthält eine Teilmenge von \({\mathcal{N}}\)die leere Menge und mit jeder Zahl ihren Nachfolger, so handelt es sich bei N bereits um die ganze Menge \({\mathcal{N}}\).

Es ist üblich, das Peano-Axiomensystem in der obigen Form anzugeben, obwohl man eigentlich auf Axiom (2) verzichten könnte, da es aus den Axiomen (3) und (4) folgt.

Das Peano-Axiomensystem charakterisiert die natürlichen Zahlen bis auf Isomorphie. Im Fall \({\mathcal{N}}=\omega \,\text{ist}\,{\mathcal{S}}(n)={\bf N}(n).\)

Das vierte Peano-Axiom bildet die Grundlage für das Beweisprinzip der vollständigen Induktion: Um zu beweisen, daß eine Aussage ϕ(n) für alle natürlichen Zahlen n ∈ ℕ₀ gilt, genügt es zu zeigen, daß ϕ(0), d. h., ϕ(0) gilt (Induktionsanfang oder Induktionsverankerung), und daß aus der Gültigkeit von ϕ(n) (der Induktionsannahme oder Induktionsvoraussetzung) die Gültigkeit von \(\phi ({\mathcal{S}}(n))\) folgt.

Häufig wird das Beweisprinzip der vollständigen Induktion auch in einer äquivalenten Variante benutzt, bei der als Induktionsvoraussetzung die Gültigkeit von ϕ(m) für alle natürlichen Zahlen m ≤ n angenommen wird.

Ähnlich lassen sich auch Abbildungen f mit den natürlichen Zahlen als Definitionsbereich durch

vollständige Induktion definieren, indem f(0) und f (n) ≔ G({(m, f(m)): 0 ≤ m ≤ n}) definiert werden. Dabei ist \({\bf G}:{\bf V}\to {\bf V}\)eine Abbildung auf der Klasse aller Mengen V. Man spricht hierbei auch von einer Definition durch Rekursion.

Ein Beispiel ist die Definition der Fakultätsfunktion f : ℕ₀ → ℕ, f (n) = n! : Zunächst ist die Abbildung \({\bf G}:{\bf V}\to {\bf V},\, M\mapsto {\bf G}(M)\)anzugeben. Handelt es sich bei der Menge M um ein n-Tupel von geordneten Paaren natürlicher Zahlen, d. h., für ein n ∈ ℕ gilt M : n → ℕ₀ × ℕ₀, so sei (a, b) ≔ M(n − 1) und G(M) ≔ (a + 1). b. Für alle anderen Mengen M sei G(M) ≔ 0.

Nun kann man definieren 0! ≔ 1, n! ≔ G({(m, f(m)) : 0 ≤ m ≤ n}) = n. f (n − 1) für n ∈ ℕ. Oftmals schreibt man auch vereinfachend nur 0! ≔ 1, n! ≔ n. (n − 1)! und verzichtet auf die explizite Angabe der Abbildung G.

Das Beweisprinzip der vollständigen Induktion läßt sich auf die gesamte Ordinalzahlklasse verallgemeinern. Man spricht dann vom Beweisprinzip der transfiniten Induktion. Die Grundlage dafür liefert der folgende Satz der transfiniten Induktion:

IstKeine nichtleere Klasse von Ordinalzahlen, d.h. \(\emptyset \ne {\bf K}\subseteq {\bf ON}\),so hatKein kleinstes Element.

Um zu beweisen, daß eine Aussage ϕ (β) für alle Ordinalzahlen β gilt, zeigt man, daß aus der Gültigkeit von ϕ (α) für alle Ordinalzahlen α< β die Gültigkeit von ϕ (β) folgt. Gäbe es dann eine Ordinalzahl γ, für die ϕ (γ) nicht gilt, so gäbe es auch eine kleinste, im Widerspruch zum zuvor Bewiesenen.

Auch die Definition durch Rekursion läßt sich auf ganz ON verallgemeinern. Man verwendet dann synonym die Bezeichnungen Definition durch transfinite Induktion und Definition durch transfinite Rekursion. Man macht sich dabei den folgenden Satz der transfiniten Rekursion zunutze:

Zu jeder Abbildung\({\bf F}:{\bf V}\to {\bf V}\)gibt es genau eine Abbildung\({\bf G}:{\bf ON}\to {\bf V}\)so, daß für jede Ordinalzahl α gilt: \({\bf G}(\alpha )={\bf F}({\bf G}|\alpha ).\)

Zum Verständnis des Satzes beachte man, daß \({\bf G}|\alpha \) als Einschränkung von G auf die Menge α eine Menge ist, nämlich {(β, G(β)) : β ∈ α}. Daher ist der Ausdruck \({\bf F}({\bf G}|\alpha )\)sinnvoll. Man beachte die Analogie zur Definition durch vollständige Induktion: Wieder wird der Wert an der Stelle α in Abhängigkeit der bereits definierten Werte für β< α definiert.

Arithmetik der Ordinalzahlen. Die Addition von Ordinalzahlen läßt sich durch transfinite Rekursion über die Ordinalzahl β definieren: Sei α ∈ ON fixiert. Man definiert α+0 ≔ α, α+N(β) ≔ N(α+β) für Nachfolgeordinalzahlen N(β) und α + β ≔ sup{α + γ : γ< β} für Limesordinalzahlen β.

Es ist üblich, transfinite Rekursionen in dieser Form anzugeben. Am Beispiel der Addition von Ordinalzahlen soll erklärt werden, wie sich eine solche Definition in den formalen Rahmen einbettet. Wieder sei α ∈ ON fixiert. Man definiert zunächst β − 1 ≔ γ, falls β = N (γ ) eine Nachfolgeordinalzahl ist. Um den Satz der transfiniten Induktion anwenden zu können, definiert man \({\bf F}_{\alpha }:{\bf V}\to {\bf V},\, M\mapsto {\bf F}_{\alpha }(M),\), wie folgt: Handelt es sich bei der Menge M : β →ON um eine Abbildung, deren Definitionsbereich aus der Ordinalzahl β besteht, so sei Fa (M) ≔ α für β = 0, F_α (M) ≔ N(M(β − 1)), falls β eine Nachfolgeordinalzahl ist und F_α(M) ≔ ∪_γ<βM(γ), falls ß eine Limesordinalzahl ist. Für alle anderen Mengen M sei F_α (M) := o.

Der Satz der transfiniten Rekursion liefert dann genau eine Abbildung \({\bf G}_{\alpha }:{\bf ON}\to {\bf V}\), so daß für jede Ordinalzahl ß gilt \({\bf G}_{\alpha }(\beta )={\bf F}_{\alpha }({\bf G}_{\alpha }|\beta )\) Schließlich kann man definieren \(\alpha +\beta :={\bf G}_{\alpha }(\beta )\)

Ähnlich lassen sich die Multiplikation von Ordinalzahlen und die Potenzierung von Ordinalzahlen durch transfinite Rekursion über die Ordinalzahl β definieren: Wieder sei α ∈ ON fixiert. Man definiert α · 0 ≔ 0, α · N(β) ≔ a · β + α für Nachfolgeordinalzahlen N(β) und α · β ≔ sup{α · γ : γ< β} für Limesordinalzahlen β sowie Ord(α⁰) ≔1, Ord(α^N(β)) ≔ Ord(α^β) · α für Nachfolgeordinalzahlen N(β) und Ord(α^β) ≔ sup{Ord(α^γ) : γ< β} für Limesordinalzahlen β

Rechenregeln für Ordinalzahlen: Für α, β, γ ∈ ON gilt: \begin{eqnarray}\begin{array}{rcl}\alpha +(\beta +\gamma & = &(\alpha +\beta )+\gamma, \\ \alpha +0 & = &\alpha, \\ \alpha +1 & = &{\bf N}(\alpha ),\\ \alpha +{\bf N}(\beta ) & = &{\bf N}(\alpha \beta ),\\ \alpha \cdot (\beta \cdot \gamma ) & = &(\alpha \cdot \beta )\cdot \gamma, \\ \alpha \cdot 0 & = &0,\\ \alpha \cdot 1 & = &\alpha, \\ \alpha \cdot {\bf N}(\beta ) & = &\alpha \cdot \beta +\alpha, \\ \alpha \cdot (\beta +\gamma ) & = &\alpha \cdot \beta +\alpha \cdot \gamma, \\ Ord({\alpha }^{0} & = &1,\\ Ord({\alpha }^{\beta +1}) & = &Ord({\alpha }^{\beta })\cdot \alpha \end{array}\end{eqnarray}Weder die Addition noch die Multiplikation von Ordinalzahlen ist kommutativ, z. B. hat man 1 + ω = ω ≠ ω + 1 sowie 2 · ω = ω ≠ ω + ω = ω · 2. Im Gegensatz zum linksseitigen Distributivgesetz gilt das rechtsseitige Distributivgesetz nicht, z. B. ist (1 + 1) · ω = ω ≠ 1 · ω + 1 · ω.

Die Größe von Mengen vergleicht man mit Hilfe injektiver Abbildungen. Sind zwei Mengen A, B gegeben, so schreibt man \(A\precsim B\) genau dann, wenn es eine injektive Abbildung i : A → B gibt, und A ≈ B genau dann, wenn die Abbildung i sogar bijektiv ist. Gilt A ≈ B, so sagt man, die Mengen A und B sind gleichmächtig.

Die Relation „\(\precsim \)“ist transitiv; bei„ ≈ “ handelt es sich um eine Äquivalenzrelation. Es gilt der Satz von Schröder-Bernstein: Aus \(A\precsim B\)und \(B\precsim A\)folgtA ≈ B.

Läßt sich die Menge A wohlordnen, so definiert man ihre Kardinalität oder Mächtigkeit als die kleinste Ordinalzahl α mit α ≈ A. Die Kardinalität von A wird mit #A oder \(|A|\)bezeichnet.

Im allgemeinen benötigt man das Auswahlaxiom, um eine Menge wohlzuordnen, und damit auch, um ihre Kardinalität zu definieren. Setzt man das Auswahlaxiom voraus, so wird mit Hilfe der Kardinalität jeder Äquivalenzklasse von „ ≈ “ genau ein Repräsentant zugeordnet.

Für Ordinalzahlen ist die Kardinalität auch ohne Voraussetzung des Auswahlaxioms immer definiert. Eine Ordinalzahl α heißt Kardinalzahl genau dann, wenn sie mit ihrer Kardinalität übereinstimmt: α = #α. Die (echte) Klasse der Kardinalzahlen wird mit \({\bf CARD}\) bezeichnet.

Während sich beliebige Mengen ohne das Auswahlaxiom nicht bezüglich ihrer Größe vergleichen lassen, ist die Vergleichbarkeit von Kardinalzahlen immer gegeben, da \({\bf CARD}\) als Teilklasse von ON sogar wohlgeordnet ist.

Für jede Kardinalzahl κ nennt man die Menge \({\aleph }_{\alpha }\)anstatt \({\omega }_{\alpha }\) geschrieben. Daher spricht man bei der Zuordnung \(\alpha \mapsto {\omega }_{\alpha }={\aleph }_{\alpha }\)auch von der Aleph-Funktion. Man beachte, daß es sich hierbei formal um eine echte Klasse handelt.

Jede endliche Ordinalzahl n ∈ ω ist eine Kardinalzahl; man spicht von endlichen, finiten oder natürlichen Kardinalzahlen. Kardinalzahlen, die nicht endlich sind, heißen unendliche oder transfinite Kardinalzahlen.

Auch bei der Menge ω handelt es sich um eine Kardinalzahl. Eine Menge A heißt endlich genau dann, wenn ihre Kardinalität endlich ist, und andernfalls unendlich. Im Fall #A ≤ ω heißt A abzählbar und andernfalls überabzählbar.

Ist κ eine Kardinalzahl, so bezeichnet man mit κ⁺die kleinste Kardinalzahl, die größer als κ ist. Eine Kardinalzahl λ heißt Nachfolgekardinalzahl genau dann, wenn es eine Kardinalzahl κ mit λ = κ⁺ gibt, andernfalls heißt λ Limeskardinalzahl.

Arithmetik der Kardinalzahlen. Durch transfinite Rekursion bezüglich der Ordinalzahl α definiert man die Kardinalzahlen Ω_α:

1. ω₀ ≔ ω.
2. ω_α+1≔ (ω_α)⁺.
3. ω_α ≔ sup{ω_γ : γ< α} für Limesordinalzahlen α

Besonders in der älteren Literatur wird auch \(\aleph_{\alpha}\)anstatt \(\omega_{\alpha}\) geschrieben. Daher spricht man bei der Zuordnung \(\alpha \mapsto \omega_{\alpha} = \aleph_{\alpha}\)auch von der Aleph- Funktion. Man beachte, daß es sich hierbei formal um eine echte Klasse handelt.

Bei allen ω_α handelt es sich um Kardinalzahlen, und umgekehrt ist jede unendliche Kardinalzahl mit einem geeigneten ω_α identisch. Die Aleph-Funktion ist streng isoton, d.h., α< β impliziert ω_α< ω_β · ω_α ist genau dann eine Limeskardinalzahl, wenn α eine Limesordinalzahl ist, und ω_α ist genau dann eine Nachfolgekardinalzahl, wenn α eine Nachfolgeordinalzahl ist. Jede unendliche Kardinalzahl ist eine Limesordinalzahl.

Addition, Multiplikation und Potenzierung von Kardinalzahlen: Für Kardinalzahlen κ, λ definiert man \(\kappa \oplus \lambda :=\# (\kappa \times \{0\}\mathop{\mathop{\cup }\limits^{.}}\limits^{}\times 1),\kappa \otimes \lambda :=\# (\kappa \times \lambda ),{\kappa }_{\lambda }:= {\mathcal F} (\lambda,\kappa ),\) d.h., κ^λ ist die Kardinalität der Menge der Abbildungen von λ nach κ.

Wie schon durch die unterschiedliche Symbolik angedeutet, sind die Addition, Multiplikation und Potenzierung von Kardinalzahlen von den entsprechenden Verknüpfungen der Ordinalzahlen sauber zu unterscheiden. Beispielsweise sind die Addition und Multiplikation von Kardinalzahlen im Gegensatz zur Addition und Multiplikation von Ordinalzahlen kommutativ.

Rechenregeln für Kardinalzahlen: Für m, n ∈ ω gilt:

m ⊕ n = m + n< ω, m⊗n = m · n< ω.

Für unendliche Kardinalzahlen κ, λ gilt:

κ ⊕ λ = κ ⊗ λ = max{κ, λ}.

Ist κ eine unendliche Kardinalzahl, so ist die Kardinalität einer Vereinigung von höchstens κ vielen Mengen, die alle höchstens die Kardinalität κ haben, höchstens κ. Zum Beweis dieser Aussage benötigt man das Auswahlaxiom. Es läßt sich z. B. zeigen, daß es mit ZF konsistent ist, daß ω₁ und auch \({\mathcal{P}}(\omega )\) abzählbare Vereinigungen abzählbarer Mengen sind.

Der Satz von Cantor besagt, daß jede Menge kleiner ist als ihre Potenzmenge: Es gibt keine surjektive Abbildung von einer Menge M auf ihre Potenzmenge \({\mathcal{P}}(M)\).

Bei Verwendung des Auswahlaxioms folgt aus dem Satz von Cantor, daß für jede Menge M gilt \(\# M\text,\lt\,\# {\mathcal{P}}(M)\) und insbesondere κ< 2^κ für jede Kardinalzahl κ.

Die bekannten Potenzgesetze für natürliche Zahlen gelten für beliebige Kardinalzahlen κ, λ, σ: \begin{eqnarray}{\kappa }^{\lambda \oplus \sigma }={\kappa }^{\lambda }\otimes {\kappa }^{\sigma },{({\kappa }^{\lambda })}^{\sigma }={\kappa }^{\lambda \otimes \sigma }.\end{eqnarray} Sind κ und λ Kardinalzahlen, ist λ unendlich und 2 ≤ κ ≤ λ, so gilt κ^λ = 2^λ.

Die der Aleph-Funktion verwandte Beth-Funktion wird durch transfinite Rekursion bezüglich der Ordinalzahl α definiert durch

1. \((1){\beth }_{0}:=\omega,\)
2. \((2){\beth }_{\alpha +1}:={2}^{{\beth }_{\alpha }},\)
3. \((3){\beth }_{\alpha }:=\sup \{{\beth }_{\gamma }:\gamma \lt \alpha \}\) für Limesordinalzahlen α.

Die Rankfunktion ist durch transfinite Rekursion bezüglich der Ordinalzahl α definiert durch

1. R(0) := 0,
2. \(R(\alpha +1):={\mathcal{P}}(R(\alpha )),\)
3. \(R(\alpha ):=\displaystyle {\cup }_{\gamma \lt \alpha }R(\gamma )\,\) für Limesordinalzahlen α.

Eine Abbildung zwischen zwei Ordinalzahlen f : α → β heißt kofinal genau dann, wenn es zu jedem b ∈ β ein a ∈ α mit b ≤ f(a) gibt. Die Kofinalität einer Ordinalzahl β ist die kleinste Ordinalzahl α, so daß es eine kofinale Abbildung f : α → β gibt. Man bezeichnet α dann mit cf (β).

Es gelten folgende Regeln für Kofinalitäten von Ordinalzahlen α: cf (α) ≤ α, cf (α) = 1, falls α eine Nachfolgeordinalzahl ist, cf (cf(α)) = cf (α), cf(ω_α) = cf (α), falls α eine Limesordinalzahl ist.

Es gilt der Satz von König:

Sind κ, λ Kardinalzahlen, ist κ unendlich und cf (κ) ≤ λ, so gilt κ^λ >κ.

Als Folgerung hat man cf (2^κ) >κ für unendliche Kardinalzahlen κ.

Sind κ, λ ≥ 2 Kardinalzahlen, ist mindestens eine von beiden unendlich, und setzt man die verallgemeinerte Kontinuumshypothese voraus, so gelten \begin{eqnarray}\begin{array}{ccccc}\kappa \le \lambda & \Rightarrow & {\kappa }^{\lambda } & = & {\lambda }^{+},\\ \kappa \gt \lambda \ge \text{cf(}\kappa \text{)} & \Rightarrow & {\kappa }^{\lambda } & = & {\kappa }^{+},\\ \lambda \lt \text{cf(}\kappa \text{)} & \Rightarrow & {\kappa }^{\lambda } & = & \kappa.\end{array}\end{eqnarray}Eine Ordinalzahl α wird regulär genannt, wenn sie eine Limesordinalzahl ist und cf(α) = α erfüllt. Ansonsten heißt sie singulär. Eine Kardinalzahl heißt regulär, wenn sie eine reguläre Ordinalzahl ist, und sonst singulär.

Es zeigt sich, daß ω und alle unendlichen Nachfolgekardinalzahlen regulär sind. Eine reguläre Limeskardinalzahl heißt schwach unerreichbar. Gilt für eine Kardinalzahl λ, daß für jede kleinere Kardinalzahl κ< λ auch 2^κ< λ gilt, so wird λ eine starke Limeskardinalzahl genannt. Ist eine starke Limeskardinalzahl zusätzlich regulär, so heißt sie stark unerreichbar. Stark unerreichbare Kardinalzahlen sind damit auch schwach unerreichbar, und unter GCH sind die Begriffe identisch.

Nach dieser Definition ist ω stark unerreichbar. Manchmal wird in der Literatur bei der Definition von schwach und stark unerreichbar auch explizit verlangt, daß die Zahlen von ω verschieden sein müssen.

Es ist mit ZFC konsistent, daß ω die einzige schwach unerreichbare Kardinalzahl ist. Ist ZFC konsistent, so läßt sich die Konsistenz von ZFC mit der Existenz von ω verschiedener, schwach unerreichbarer Kardinalzahlen in ZFC nicht beweisen. Man kann jedoch zeigen, daß jedes der folgenden Axiomensysteme (i)-(iv) genau dann konsistent ist, wenn die anderen drei konsistent sind.

Bezeichnet man mit M_I bzw. M₂ die kleinste ω₁-I-meßbare bzw. ω₁-2-meßbare Kardinalzahl, so sind M_I, M₂ >ω, M_I ist schwach unerreichbar, und M₂ ist stark unerreichbar. Es gilt entweder M_I ≤ 2^ω oder M₂ = M_I. Ist eine Kardinalzahl λλ-I-meßbar, so ist sie schwach unerreichbar, ist sie sogar λ-2-meßbar, so ist sie stark unerreichbar.

Man nennt eine Kardinalzahl λ meßbar genau dann, wenn sie λ-2-meßbar ist.