Beweisarchiv: Mengenlehre: Ordinalzahlen: Definitionen

Beweisarchiv: Mengenlehre

Charakteristikum unendlicher Mengen

Injektivität Surjektivität Bijektivität: Faktoren · Komposition · Linksinverse · Linkskürzbarkeit · Rechtsinverse · Rechtskürzbarkeit

Verkettungen: Assoziativgesetz der Hintereinanderausführung

Mächtigkeiten (Kardinalzahlen): lineare Ordnung · Kardinalität und Bijektionen · Potenzmenge

Deskriptive Mengenlehre: Satz von Young

Rechenregeln für Mengenoperationen: Assoziativgesetze · Distributivgesetze · Differenzgesetze · Grundeigenschaften der Inklusion · De Morgansche Regeln für Mengen · Bild und Urbild

Ordinalzahlen: Ordinalzahlen enthalten sich nicht selbst als Element · Elemente von Ordinalzahlen sind Ordinalzahlen · Durchschnitte von Ordinalzahlen sind Ordinalzahlen · Wohlordnung der Klasse aller Ordinalzahlen · Ordinalzahlen bilden eine echte Klasse · Der Nachfolger einer Ordinalzahl ist Ordinalzahl · Vereinigungen von Ordinalzahlen sind Ordinalzahlen · Limes- und Nachfolgerzahlen · Äquivalenz verschiedener Definitionen

Sätze die in ZF Äquivalent zum Auswahlaxiom sind: Alternative Darstellung des Auswahlaxioms · Wohlordnungssatz · Lemma von Zorn

Historisch gibt es zahlreiche verschiedene, jedoch auf der Basis des Axiomensystems von Zermelo-Fraenkel ohne Fundierungsaxiom (und ohne Unendlichkeitsaxiom) äquivalente Definitionen des Begriffs der Ordinalzahl. Die Äquivalenz der verschiedenen Definitionen mit der hier verwendeten (siehe Ordinalzahlen) ist jeweils ein Satz, der nachfolgend bewiesen wird. Verwendet werden hierbei jeweils in verschiedenem Umfang die in den vorhergehenden Abschnitten bewiesenen Aussagen über Ordinalzahlen, also

(1) Ordinalzahlen enthalten sich nicht selbst als Element

(2) Elemente von Ordinalzahlen sind Ordinalzahlen

(3) Durchschnitte von Ordinalzahlen sind Ordinalzahlen

(4) Wohlordnung der Klasse aller Ordinalzahlen

(5) Ordinalzahlen bilden eine echte Klasse

(6) Der Nachfolger einer Ordinalzahl ist Ordinalzahl

(7) Vereinigungen von Ordinalzahlen sind Ordinalzahlen

Bei den nachfolgenden Sätzen beziehen sich die Definitionsnummerierungen in Klammern auf die Nummerierung im Wikipedia-Artikel Ordinalzahl. Die hier im Archiv verwendete Definition ist in diesem Sinne die Definition VII.

Zermelo, 1915/1941 (Definition II)

Satz

Die Menge $X$ ist genau dann Ordinalzahl, wenn für jedes $y\in X$ die Menge $y\cup \{y\}$ [entweder] ein Element von $X$ oder identisch mit $X$ ist und für jede Teilmenge $Y$ von $X$ die Vereinigung der Elemente von $Y$ [entweder] ein Element von $X$ oder identisch mit $X$ ist.

Bemerkung: Im vorstehenden Satz wurde das Wort „entweder“ jeweils in Klammern gesetzt. Zermelo formulierte ursprünglich ohne „entweder“ (also mit inklusivem Oder), während einige spätere Autoren zum exklusiven Oder übergingen. Der nachfolgende Beweis zeigt genau gelesen, dass jede Ordinalzahl die Zermelo-Definition mit sogar exklusivem Oder erfüllt und dass jede die Zermelo-Definition mit lediglich inklusivem Oder erfüllende Menge eine Ordinalzahl ist. Mithin ist es gleichgültig, ob man in dieser Definition inklusives oder exklusives Oder verwendet.

Beweis

Sei zunächst $X$ Ordinalzahl. Dann ist für jedes $y\in X$ gemäß (2) und (6) $y\cup \{y\}$ eine Ordinalzahl und für jede Teilmenge $Y\subseteq X$ ist gemäß (2) und (7) die Vereinigung $\bigcup Y$ eine Ordinalzahl. Da diese Ordinalzahlen gemäß (4) mit $X$ vergleichbar sind, sind sie jeweils entweder Element von $X$ oder identisch mit $X$ oder enthalten $X$ als Element. Es genügt also, die Annahme, dass eine dieser Mengen $X$ als Element enthält, auf einen Widerspruch zu führen. Aus $y\in X$ und $X\in y\cup \{y\}$ ergäbe sich $X=y\in X$ oder $X\in y\in X$ und wiederum $X\in X$, auf jeden Fall ein Widerspruch zu (1). Aus $Y\subseteq X$ und $X\in \bigcup Y$ folgte $X\in Z$ für ein $Z\in Y$ also $X\in Z\in X$, wiederum im Widerspruch zu (1).

Umgekehrt erfülle jetzt $X$ die Zermelo-Definition. Sei $Y=\{x\in X\mid x\in \mathrm {On} \}$. Dann ist $u:=\bigcup Y$ gemäß (7) eine Ordinalzahl und nach Voraussetzung $u=X$ oder $u\in X$. Im ersten Fall sind wir fertig. Im zweiten Fall setze $s:=u\cup \{u\}$. Gemäß (6) ist auch $s$ Ordinalzahl und nach Voraussetzung $s=X$ oder $s\in X$. Im ersten Fall sind wir wieder fertig. Der zweite Fall führt dagegen wegen $u\in s\in Y$ über $u\in s\subseteq u$ auf $u\in u$ im Widerspruch zu (1).

Von Neumann, 1923 (Definition III)

Satz

Eine Menge $X$ ist genau dann Ordinalzahl, wenn es eine Wohlordnung < auf $X$ gibt mit $\forall y\in X\colon y=\{z\in X\mid z<y\}$.

Beweis

Sei zunächst $X$ Ordinalzahl. Nach Voraussetzung ist $<\;:=\;\in$ Wohlordnung auf $X$. Sei $y\in X$. Dann ist $y':=\{z\in X\mid z<y\}=X\cap y$ und mit (3) folgt $y'=\min\{X,y\}=y$.

Sei nun umgekehrt $X$ eine Von-Neumann-Ordinalzahl und < die zugehörige Wohlordnung. Wegen $y=\{z\in X\mid \ldots \}$ ist jedes Element $y$ von $X$ auch Teilmenge, also ist $X$ transitiv. Für $z,y\in X$ gilt $z\in y\iff z<y$, d. h. die Relationen $\in$ und < stimmen überein, so dass auch $\in$ eine Wohlordnung auf $X$ ist.

Gödel, 1937 (Definition IV)

Satz

Eine Menge $X$ ist genau dann Ordinalzahl, wenn sie transitiv ist, jedes Element transitiv ist und jede nichtleere Teilmenge fundiert ist.

Beweis

Ist $X$ Ordinalzahl, so ist laut (2) auch jedes Element Ordinalzahl und folglich transitiv. Ist $A\subseteq X$ eine nichtleere Teilmenge, setze man $y=\min A$. Dann gilt $y\cap A=\emptyset$, denn für $z\in y\cap A$ würde $z\in A$ und $z\in y$ folgen im Widerspruch zur Minimalität von $y$.

Sei nun umgekehrt $X$ Gödel-Ordinalzahl. Sei

$A=\{x\in X\mid x\notin \mathrm {On} \}$.

Angenommen $A$ ist nicht leer. Dann ist $A$ fundiert, d. h. es gibt ein $a\in A$ mit $a\cap A=\emptyset$. Für jedes $t\in a$ gilt $t\notin A$ und wegen der Transitivität von $X$ auch $t\in X$, d. h. jedes Element von $a$ ist Ordinalzahl. Daher ist $a$ durch $\in$ wohlgeordnet und nach Voraussetzung als Element von $X$ transitiv, also selbst eine Ordinalzahl im Widerspruch zu $a\in A$. Folglich ist $A$ leer und $X$ selbst eine transitive Menge von Ordinalzahlen, mithin wie eben selbst Ordinalzahl.

Robinson, 1937 (Definition V)

Satz

Eine Menge $X$ ist genau dann Ordinalzahl, wenn sie transitiv ist, jede nicht-leere Teilmenge fundiert ist und für jede zwei verschiedene Elemente $y$ und $z$ von $X$ entweder $y\in z$ oder $z\in y$ gilt.

Beweis

Ist $X$ Ordinalzahl, so ist $X$ transitiv und jede nicht-leere Teilmenge ist fundiert (durch ihr Minimum, vgl. Beweis zu Gödel). Da $X$ durch $\in$ (wohl-)geordnet ist, folgt auch die letzte Eigenschaft.

Sei nun umgekehrt $X$ eine Robinson-Ordinalzahl. Zu zeigen ist, dass $X$ durch $\in$ wohlgeordnet ist. Für $y\in X$ ist $y\in y$ ausgeschlossen, da $\{y\}$ fundiert ist. Somit gilt für $y,z\in X$ genau eine der Beziehungen $y\in z$, $y=z$ oder $z\in y$. Für $y,z,w\in X$ mit $y\in z$ und $z\in w$ folgt so zunächst $y\neq w$. Ferner muss die Menge $A:=\{y,z,w\}\subseteq X$ fundiert sein. Wegen $z\in w\cap A$ und $y\in z\cap A$ bleibt nur die Möglichkeit $y\cap A=\emptyset$, was $w\notin y$, also $y\in w$ bedeutet. Somit ist $\in$ eine Totalordnung auf $X$. Falls $A\subseteq X$ nicht leer ist, gibt es ein $a\in A$ mit $a\cap A=\emptyset$. Da für $y\in A$ dann stets $y\notin a$ folgt, ist $a$ minimales Element von $A$, d. h. $X$ ist wohlgeordnet.

Bernays, 1941 (Definition VI)

Satz

Eine Menge $X$ ist genau dann Ordinalzahl, wenn sie transitiv ist und jede transitive echte Teilmenge von $X$ Element von $X$ ist.

Beweis

Ist $X$ Ordinalzahl, so ist $X$ transitiv. Jede transitive echte Teilmenge $A$ von $X$ ist laut (2) eine Menge von Ordinalzahlen, also gemäß (4) wohlgeordnet, d. h. eine Ordinalzahl. Da $X\in A\subset X$ laut (1) und $X=A$ laut Voraussetzung ausgeschlossen sind, folgt mit (4), dass $A\in X$ gilt, und mithin ist $X$ auch eine Bernays-Ordinalzahl.

Sei nun umgekehrt $X$ eine Bernays-Ordinalzahl. Da Die Ordinalzahlen gemäß (5) eine echte Klasse bilden, gibt es Ordinalzahlen, die nicht in $X$ enthalten sind. Sei $Y$ die gemäß (4) existente kleinste solche Ordinalzahl. Dann ist $Y$ nach Voraussetzung keine transitive echte Teilmenge von $X$. Da $Y$ als Ordinalzahl auf jeden Fall transitiv ist, ist $Y$ also keine echte Teilmenge von $X$. Andererseits gilt aufgrund der Minimalität von $Y$ gewiss $z\in X$ für jedes $z\in Y$, denn solche $y$ sind laut (2) Ordinalzahlen. Also gilt $Y\subseteq X$. Zusammen bedeutet dies $Y=X$, also ist $X$ Ordinalzahl.

Moderne Variante (Definition VIII)

Satz

Ordinalzahlen sind genau die Bilder der Funktionen $E(a)=\{E(x)\mid x<a;x\in A\}$ für wohlgeordnete Mengen $A$.

Beweis

Sie zunächst $A$ Ordinalzahl, also durch $\in$ wohlgeordnet. Dann ist das wie im Satz definierte $E$ die Identität: Ansonsten sei $a\in A$ minimal mit $E(a)\neq a$. Dann folgt $E(a)=\{E(x)\mid x\in a;x\in A\}=\{x\mid x\in a;x\in A\}=a$, also ein Widerspruch. Somit ist $A$ das Bild dieser Abbildung $E$.

Sei umgekehrt $A$ eine beliebige wohlgeordnete Menge und $E$ wie im Satz. Zu zeigen ist, dass $X:=\{E(a)\mid a\in A\}$ eine Ordinalzahl ist. Ist $z\in y\in X$, so $y=E(a)$ für ein $a\in A$, also $z=E(x)$ für ein $x\in A$ mit $x<a$, folglich $z\in X$. Somit ist $X$ transitiv. Wegen $E(x)\in E(a)\iff x<a$ ist $E$ ein Ordnungsisomorphismus und folglich mit $A$ auch $X$ wohlgeordnet.

Äquivalent nur mit Fundierungsaxiom (Definition I)

Satz

Eine Menge $X$ ist Ordinalzahl genau dann, wenn jedes Element von $X$ auch Teilmenge von $X$ ist und $X$ bezüglich der Mengeninklusion $\subseteq$ total geordnet ist.

Bemerkung: Sofern man, wie in der Kapiteleinleitung angegeben, das Fundierungsaxiom der Zermelo-Fraenkel-Mengenlehre nicht voraussetzt, gilt die eine Richtung des Satzes nicht allgemein. Der nachfolgende Beweis verwendet daher an entscheidender Stelle das Fundierungsaxiom.

Beweis

Sei $X$ eine Ordinalzahl. Die erste Bedingung des Satzes ist gleichbedeutend mit Transitivität. Da Elemente von $X$ gemäß (2) ihrerseits Ordinalzahlen sind, folgt für solche aus $a\in b$ stets auch $a\subset b$. Da eine der Aussagen $a\in b$ , $a=b$, $b\in a$ zutrifft, gilt $a\subseteq b$ oder $b\subseteq a$, d. h. die partielle Ordnung $\subseteq$ ist total.

Sei nun umgekehrt $X$ eine transitive und durch $\subseteq$ total geordnete Menge. Betrachte die Menge $A:=X\setminus \mathrm {On}$ der nicht-ordinalen Elemente. Angenommen $A$ ist nicht leer. Das Fundierungsaxiom behauptet dann die Existenz eines $a\in A$ mit $a\cap A=\emptyset$. Wegen (5) gibt es Ordinalzahlen, die nicht Element von $a$ sind, wegen (4) gibt es hierunter eine kleinste. Sei also $z$ die kleinste Ordinalzahl mit $z\notin a$. Somit gilt $y\in a$ für jede kleinere Ordinalzahl, wegen (2) also für jedes $y\in z$. Mit andern Worten gilt $z\subseteq a$, aber wegen $a\notin \mathrm {On}$ ist gewiss $a\neq z$. Es gibt also ein Element $b\in a$ mit $b\notin z$. Wegen der Transitivität von $X$ gilt auch $b\in X$, aber wegen $a\cap A=\emptyset$ muss $b\notin A$ gelten. Wir schließen, dass $b$ Ordinalzahl ist. Wegen $b\in a$ und $z\notin a$ ist gewiss $b\neq z$ und wegen $b\notin z$ bleibt gemäß (4) nur die Möglichkeit, dass $z\in b$ gilt. Wegen $z\in b$ und $z\notin a$ ist $b\subseteq a$ gewiss falsch. Aber wegen $b\in a$ und $b\notin b$ (gemäß (1) oder erneut per Fundierungsaxiom) kann auch nicht $a\subseteq b$ gelten. Da weder $a\subseteq b$ noch $b\subseteq a$ gilt, ergibt sich ein Widerspruch zur vorausgesetzten Totalordnung durch $\subseteq$ auf $X$. Somit war die oben gemachte Annahme falsch. Es folgt, dass $A$ leer ist. Demnach ist $X$ eine Menge von Ordinalzahlen und als solche laut (4) durch $\in$ wohlgeordnet. Da $X$ auch transitiv ist, ist $X$ selbst Ordinalzahl.