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) Bearbeiten

Satz Bearbeiten

Die Menge   ist genau dann Ordinalzahl, wenn für jedes   die Menge   [entweder] ein Element von   oder identisch mit   ist und für jede Teilmenge   von   die Vereinigung der Elemente von   [entweder] ein Element von   oder identisch mit   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 Bearbeiten

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

Umgekehrt erfülle jetzt   die Zermelo-Definition. Sei  . Dann ist   gemäß (7) eine Ordinalzahl und nach Voraussetzung   oder  . Im ersten Fall sind wir fertig. Im zweiten Fall setze  . Gemäß (6) ist auch   Ordinalzahl und nach Voraussetzung   oder  . Im ersten Fall sind wir wieder fertig. Der zweite Fall führt dagegen wegen   über   auf   im Widerspruch zu (1).

Von Neumann, 1923 (Definition III) Bearbeiten

Satz Bearbeiten

Eine Menge   ist genau dann Ordinalzahl, wenn es eine Wohlordnung < auf   gibt mit  .

Beweis Bearbeiten

Sei zunächst   Ordinalzahl. Nach Voraussetzung ist   Wohlordnung auf  . Sei  . Dann ist   und mit (3) folgt  .

Sei nun umgekehrt   eine Von-Neumann-Ordinalzahl und < die zugehörige Wohlordnung. Wegen   ist jedes Element   von   auch Teilmenge, also ist   transitiv. Für   gilt  , d. h. die Relationen   und < stimmen überein, so dass auch   eine Wohlordnung auf   ist.

Gödel, 1937 (Definition IV) Bearbeiten

Satz Bearbeiten

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

Beweis Bearbeiten

Ist   Ordinalzahl, so ist laut (2) auch jedes Element Ordinalzahl und folglich transitiv. Ist   eine nichtleere Teilmenge, setze man  . Dann gilt  , denn für   würde   und   folgen im Widerspruch zur Minimalität von  .

Sei nun umgekehrt   Gödel-Ordinalzahl. Sei

 .

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

Robinson, 1937 (Definition V) Bearbeiten

Satz Bearbeiten

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

Beweis Bearbeiten

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

Sei nun umgekehrt   eine Robinson-Ordinalzahl. Zu zeigen ist, dass   durch   wohlgeordnet ist. Für   ist   ausgeschlossen, da   fundiert ist. Somit gilt für   genau eine der Beziehungen  ,   oder  . Für   mit   und   folgt so zunächst  . Ferner muss die Menge   fundiert sein. Wegen   und   bleibt nur die Möglichkeit  , was  , also   bedeutet. Somit ist   eine Totalordnung auf  . Falls   nicht leer ist, gibt es ein   mit  . Da für   dann stets   folgt, ist   minimales Element von  , d. h.   ist wohlgeordnet.

Bernays, 1941 (Definition VI) Bearbeiten

Satz Bearbeiten

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

Beweis Bearbeiten

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

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

Moderne Variante (Definition VIII) Bearbeiten

Satz Bearbeiten

Ordinalzahlen sind genau die Bilder der Funktionen   für wohlgeordnete Mengen  .

Beweis Bearbeiten

Sie zunächst   Ordinalzahl, also durch   wohlgeordnet. Dann ist das wie im Satz definierte   die Identität: Ansonsten sei   minimal mit  . Dann folgt  , also ein Widerspruch. Somit ist   das Bild dieser Abbildung  .

Sei umgekehrt   eine beliebige wohlgeordnete Menge und   wie im Satz. Zu zeigen ist, dass   eine Ordinalzahl ist. Ist  , so   für ein  , also   für ein   mit  , folglich  . Somit ist   transitiv. Wegen   ist   ein Ordnungsisomorphismus und folglich mit   auch   wohlgeordnet.

Äquivalent nur mit Fundierungsaxiom (Definition I) Bearbeiten

Satz Bearbeiten

Eine Menge   ist Ordinalzahl genau dann, wenn jedes Element von   auch Teilmenge von   ist und   bezüglich der Mengeninklusion   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 Bearbeiten

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

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