Beweisarchiv: Mengenlehre: Wohlordnungssatz

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

Aus dem Auswahlaxiom folgt der Wohlordnungssatz[Bearbeiten]

Voraussetzung[Bearbeiten]

Die Axiome von ZFC

Behauptung[Bearbeiten]

Jede Menge hat eine Wohlordnung

Beweis[Bearbeiten]

Sei eine beliebige Menge. Dann ist eine Menge nichtleerer Mengen und folglich gibt es eine Auswahlfunktion

mit für alle . Zu jeder Relation definiere

Für Relationen definiere

Die so definierte zweistellige Relation auf ist reflexiv, transitiv und antisymmetrisch, d. h. eine Halbordnung. Sei schließlich

Angenommen, die Menge lässt sich nicht wohlordnen. Dann gilt für stets , folglich ist definiert. Wenn Wohlordnung auf ist, dann ist Wohlordnung auf . (Anschaulich: Das neu hinzugenomme Element von , das nicht von abgedeckt wurde, wird als größer als alle bisherigen Elemente deklariert). Somit ist eine Abbildung . Für gilt nach Konstruktion stets . Der Form halber setzen wir zu einer Abbildung fort, indem wir für alle setzen. Wir definieren eine Abbildung von der Klasse der Ordinalzahlen nach durch transfinite Rekursion vermöge

Durch transfinite Induktion zeigt man jetzt die Aussage:

: Für ist und für ist .
Zum Beweis der Aussage sei vorausgesetzt, dass für alle bereits gilt.
Betrachte die Relation auf der Menge . Für jedes Element gibt es dann ein mit . Für je zwei Elemente kann man sogar ein gemeinsames mit finden (wähle zu zunächst einzeln und bilde das Maximum). Für jedes solche gilt . Da jedes , Totalordnung auf ist, folgt dann, dass Totalordnung auf ist.
Ist nicht leer und etwa ein Element, so gibt es ein mit . Da und somit Wohlordnung auf ist, sei . Für mit gilt dann entweder und folglich , oder für ein mit . Aus folgt dann wiederum wegen . Somit ist für alle , , mithin sogar Wohlordnung auf .
Insbesondere gilt dann .
Sei jetzt . Falls , so auch , und falls , so , also , mithin . Falls und , so für ein mit . Es muss sogar gelten, denn sonst . Aus folgt dann , mithin ist Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikibooks.org/v1/“:): {\displaystyle I(w)\le I<S(I) = I(v)} .
Somit gilt für alle Ordinalzahlen .

Mittels der so definierten Abbildung setze

Wegen ist injektiv, d. h. es gibt eine Umkehrabbildung , so dass auf die Identität ist. Dann enthält aber die Menge sämtliche Ordinalzahlen. Dies widerspricht der Tatsache, dass eine echte Klasse ist.

Die Annahme, dass die Menge sich nicht wohlordnen lässt, muss also falsch sein. Damit ist der Wohlordnungssatz bewiesen.

Aus dem Wohlordnungssatz folgt das Auswahlaxiom[Bearbeiten]

Voraussetzung[Bearbeiten]

Die Axiome von ZF und der Satz:

Jede Menge hat eine Wohlordnung

Behauptung[Bearbeiten]

Jede Menge nichtleerer Mengen hat eine Auswahlfunktion

Beweis[Bearbeiten]

Sei eine Menge nichtleerer Mengen. Wegen des Wohlordnungssatzes gibt es eine Wohlordung von . Da jedes Element von eine nichtleere Teilmenge von ist, hat ein kleinstes Element bzgl. der Wohlordnung. Folgende Funktion ist dann eine Auswahlfunktion von A:

Aus dem Lemma von Zorn folgt der Wohlordnungssatz[Bearbeiten]

Voraussetzung[Bearbeiten]

Die Axiome von ZF und der Satz:

Jede nichtleere halbgeordnete Menge, in der jede Kette eine obere Schranke hat, enthält ein maximales Element.

Behauptung[Bearbeiten]

Jede Menge hat eine Wohlordnung

Beweis[Bearbeiten]

Sei eine Menge. Zu einer Relation sei und . Auf sei die folgende Relation definiert:

.

Diese Relation ist reflexiv, da für stets gilt. Da aus auch folgt, ergibt sich auch, dass transitiv ist. Insgesamt handelt es sich also um eine Halbordnung. Auch die Menge

aller Wohlordnungen auf Teilmengen von ist auf diese Weise halbgeordnet. Wegen ist nicht leer.

Sei eine Kette. Setze . Man sieht leicht und . Es folgt . Sei , , . Dann ist für ein . Da gewiss nicht gelten kann, ist , also , mithin . Es folgt für alle .

Sei nicht leer. Für beliebiges gibt es dann ein mit . Insbesondere ist dann nichtleere Teilmenge von und enthält ein kleinstes Element . Da für jedes wegen erst recht folgt, ist auch kleinstes Element von . Somit ist Wohlordnung auf und daher obere Schranke von in .

Also erfüllt die Voraussetzung des Lemmas von Zorn. Sei demnach ein maximales Element. Falls existiert, ist eine Wohlordnung von mit im Widerspruch zur Maximalität von . Daher muss gelten, d. h. ist eine Wohlordnung auf .