5. Der Wohlordnungssatz

Nachdem wir nun die möglichen Beziehungen von Wohlordnungen untereinander vollständig geklärt haben, ist die natürlichste Frage an dieser Stelle die nach der Existenz von Wohlordnungen auf beliebigen Mengen:

Kann jede Menge wohlgeordnet werden, d. h. existiert für jede Menge M eine Wohlordnung < auf M?

Wenn man etwa an die reellen Zahlen denkt, so ist keineswegs klar, wie eine Wohlordnung der reellen Zahlen aussehen soll. Cantor hat die Wohlordenbarkeit jeder Menge zunächst als Denkgesetz postuliert, später hat er intuitive − und mit den Methoden der Nachfolgegeneration streng zu rechtfertigende − Argumente für die Wohlordenbarkeit jeder Menge gegeben.

Cantor (1883b):

„Der Begriff der wohlgeordneten Menge weist sich als fundamental für die ganze Mannigfaltigkeitslehre aus. Dass es immer möglich ist, jede wohldefinierte Menge in die Form einer wohlgeordneten Menge zu bringen, auf dieses, wie mir scheint, grundlegende und folgenreiche, durch seine Allgemeingültigkeit besonders merkwürdige Denkgesetz werde ich in einer späteren Abhandlung zurückkommen.“

Der erste strenge Beweis der Wohlordenbarkeit jeder beliebigen Menge gelang Ernst Zermelo im Jahre 1904. Er hat, gemessen am dreiseitigen Umfang der Veröffentlichung, für ein enormes Aufsehen in der mathematischen Welt gesorgt, wobei auch viele unsachliche Reaktionen nicht ausblieben.

Satz (Wohlordnungssatz von Ernst Zermelo)

Sei M eine Menge. Dann existiert eine Wohlordnung < auf M.

Wir geben unten den originalen Beweis. Alle bekannten Beweise beruhen auf der Idee eines erschöpfenden Aufzählens aller Elemente der zugrunde liegenden Menge.

Es zeigt sich in der axiomatischen Entwicklung der Mengenlehre, dass der Wohlordnungssatz zu einem ausgezeichneten Axiom auf der Basis der übrigen Axiome äquivalent ist, nämlich dem Auswahlaxiom (dem Axiom, das Auswahlakte „ein …“ ermöglicht). Insofern ist die Bezeichnung „Denkgesetz“ für den Wohlordnungssatz nicht unzutreffend.

Nun also zum Beweis des Wohlordnungssatzes!

Beweis

Für jede nichtleere Teilmenge A von M sei

γ(A) = „ein x  ∈  A“.

[D. h. wir fixieren eine Funktion γ : ℘(M) − { ∅ } → M mit γ(A)  ∈  A für alle A  ∈  dom(γ) = ℘(M) − { ∅ }.]

Eine Wohlordnung 〈 A, < 〉 heißt eine γ-Menge, falls gilt:

(i)

A ⊆ M,

(ii)	für alle x  ∈  A ist x = γ(M − A_x),

wobei wieder A_x = { y  ∈  A | y < x } das durch x bestimmte Anfangsstück der Wohlordnung 〈 A, < 〉 bezeichnet. Insbesondere ist also γ(M) das kleinste Element jeder γ-Menge 〈 A, < 〉 mit A ≠ ∅. Weiter ist jedes Anfangsstück einer γ-Menge wieder eine γ-Menge.

Die Idee ist: Die γ-Mengen sind die Anfangsstücke einer bestimmten Wohlordnung von M, nämlich derjenigen Wohlordnung, die durch Abtragen von M gemäß γ entsteht. γ liefert uns an jeder Stelle des Abtragens ein Element aus dem Resthaufen, solange dieser noch nicht aufgebraucht ist.

Eine γ-Menge archiviert also bis zu einem bestimmten Zeitpunkt den Verlauf eines Prozesses, der ohne Willkür verläuft. Mit dieser Interpretation ist dann die folgende Aussage keine Überraschung:

(+)	Sind 〈 A, < 〉 und 〈 B, < 〉 zwei verschiedene γ-Mengen, so ist die eine ein Anfangsstück der anderen.

Beweis von (+)

Nach dem Vergleichbarkeitssatz für Wohlordnungen sei ohne Einschränkung 〈 A, < 〉 ≡ 〈 B′, < 〉, wobei 〈 B′, < 〉 ein Anfangsstück von 〈 B, < 〉 oder gleich 〈 B, < 〉 sei. Sei

π : A → B′

der zugehörige Ordnungsisomorphismus. Es genügt zu zeigen, dass π = id_A. Hierzu sei

X = { x  ∈  A | π(x) ≠ x }.

Annahme X ≠ ∅. Seien dann

x = „das kleinste Element von X“,

z = π(x).

Nach minimaler Wahl von x ist dann A_x = B′_z. Da 〈 A, < 〉 und 〈 B′, < 〉 γ-Mengen sind, gilt also

x = γ(M − A_x) = γ(M − B′_z) = z, Widerspruch! Dies zeigt (+).

Sei nun Γ = { 〈 A, < 〉 | 〈 A, < 〉 ist eine γ-Menge }, und sei

〈 N, < 〉 = ⋃ Γ.

⋃ Γ ist eine Wohlordnung nach (+). Weiter gilt:

(++) 〈 N, < 〉 ist eine γ-Menge.

Beweis von (++)

Offenbar gilt N ⊆ M. Sei x  ∈  N. Dann existiert eine γ-Menge 〈 A, < 〉 mit x  ∈  A, also gilt x = γ(M − A_x). Aber A_x = N_x für alle x  ∈  A, und damit

x = γ(M − N_x).

Also ist 〈 N, < 〉 eine γ-Menge.

(+++) Es gilt N = M.

Beweis von (+++)

Annahme M − N ≠ ∅. Sei x = γ(M − N) und sei 〈 N′, <′ 〉 die Wohlordnung 〈 N, < 〉, enderweitert um das Element x, d. h.

〈 N′, <′ 〉 = 〈 N, < 〉 + { x }.

Dann ist 〈 N′, <′ 〉 eine γ-Menge mit x  ∈  N′, im Widerspruch zu x  ∉  N und der Definition von N als Vereinigung der Träger aller γ−Mengen.

Also ist 〈 N, < 〉 eine Wohlordnung auf M.

Zermelo hat 1908 einen weiteren Beweis des Wohlordnungssatzes gegeben, der die Theorie der Wohlordnungen nicht voraussetzt. Der Beweis des Vergleichbarkeitssatzes in 1.5 folgt der Struktur dieses zweiten Zermeloschen Beweises des Wohlordnungssatzes.

Die Stärke des Wohlordnungssatzes wollen wir noch mit einem neuen Beweis des Vergleichbarkeitssatzes für Mächtigkeiten demonstrieren:

Beweis des Vergleichbarkeitssatzes mit Hilfe des Wohlordnungssatzes

Seien M, N Mengen. Wir zeigen |M| ≤ |N| oder |N| ≤ |M|.

Nach dem Wohlordnungssatz existieren Wohlordnungen 〈 M, < 〉 und 〈 N, < 〉 von M und N. Weiter gilt nach dem Vergleichbarkeitssatz für Wohlordnungen:

〈 M, < 〉 ⊲ 〈 N, < 〉 oder 〈 M, < 〉 ≡ 〈 N, < 〉 oder 〈 N, < 〉 ⊲ 〈 M, < 〉.

Im ersten Fall existiert ein Ordnungsisomorphismus f von M auf ein Anfangsstück von N. Dann ist f : M → N injektiv, also gilt |M| ≤ |N|.

Analog gilt im zweiten Fall |M| = |N| und im dritten |N| ≤ |M|.

Dies zeigt die Behauptung.