Beweisarchiv: Mengenlehre: Ordinalzahlen: Definitionen

Aus Wikibooks

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.