Maximalprinzipien

In den Beweisen des Vergleichbarkeitssatzes (1.5) und des Wohlordnungssatzes haben wir die Existenz der gesuchten Objekte durch den Nachweis gezeigt, dass bestmögliche Approximationen an diese Objekte existieren. Die hier verwendete Argumentation lässt sich in abstrakten Prinzipien bündeln. Im Satz über die Existenz von Zielen in Zermelosystemen haben wir schon ein Beispiel kennengelernt, zwei weitere Varianten werden wir nun besprechen, den Satz von Zermelo-Zorn und das Maximalitätsprinzip von Hausdorff.

Der Satz von Zermelo-Zorn wird unter dem Pseudonym „Zornsches Lemma“ an verschiedenen Stellen in der mathematischen Praxis gerne eingesetzt (etwa im Beweis der Existenz von Basen in beliebigen Vektorräumen, im Beweis des Produktsatzes von Tychonov in der Topologie, im Existenzbeweis des algebraischen Abschlusses eines Körpers in der Algebra, im Beweis des Satzes von Hahn-Banach in der Funktionalanalysis). Zur Formulierung brauchen wir den Begriff der partiellen Ordnung, den wir bei der Einführung der linearen Ordnungen schon kurz erwähnt haben:

Definition (partielle Ordnung)

Sei M eine Menge, und sei < ⊆ M × M. 〈 M, < 〉 heißt eine partielle Ordnung auf M, falls < irreflexiv und transitiv auf M ist.

Eingeführt wurde der Begriff der partiellen Ordnung von Hausdorff 1914. Er gehört heute zum Grundbestand des mathematischen Wortschatzes.

Hausdorff (1914):

„Nehmen wir an, zwischen je zwei verschiedenen Elementen a, b einer Menge A bestehe jetzt nicht mehr, wie bei den [linear] geordneten Mengen, eine und nur eine von zwei Beziehungen (a < b, a > b), sondern eine und nur eine von drei Beziehungen

a < b, a > b, a ∥ b,

die wir lesen wollen: a vor b, a nach b, a unvergleichbar mit b. Von den beiden ersten setzen wir dieselben Eigenschaften wie im Falle geordneter Mengen voraus, was für die dritte Beziehung notwendig ihre Symmetrie zur Folge hat [d. h. a ∥ b folgt b ∥ a] …

Eine solche Menge heißt eine teilweise geordnete Menge; die geordneten Mengen sind Spezialfälle der teilweise geordneten, nämlich wenn Paare unvergleichbarer Elemente nicht existieren …“

Man nennt Elemente a, b einer partiellen Ordnung mit a ∥ b, d. h. non(a < b) und non(b < a) auch inkompatibel. Umgangssprachlich ist ein Analogon zur mathematischen partiellen Ordnung gut bekannt: „Man kann Äpfel nicht mit Birnen vergleichen“, aber ein Apfel kann größer sein als ein anderer. Die Ergebnisse von olympischen Spielen mit ihren Dutzenden von Sportarten bilden ein Beispiel für eine sinnvolle partiell geordnete Struktur. Jeder Baum gibt ein schöneres.

Wir verwenden die Schreibweisen für lineare Ordnungen auch für partielle Ordnungen. So meint A ≤ x etwa „a ≤ x für alle a  ∈  A“, und x ist dann eine obere Schranke von A ⊆ M in der partiellen Ordnung 〈 M, < 〉.

Partielle Ordnungen haben eine netzartige Struktur. Die beiden wichtigsten Beispiele sind die Inklusion ⊂ auf einer beliebigen Menge M, d. h. a < b falls a ⊂ b für a, b  ∈  M, sowie die umgekehrte Inklusion ⊃ auf einer Menge M, d. h. a < b falls a ⊃ b für a, b  ∈  M. (Häufig ist M = ℘(N) für eine Menge N.)

Weiter definieren wir:

Definition (Ziele und Ketten in einer partiellen Ordnung)

Sei 〈 M, < 〉 eine partielle Ordnung.

(a)	x  ∈  M heißt ein Ziel oder ein maximales Element von 〈 M, < 〉, falls kein y  ∈  M existiert mit x < y.

(b)	K ⊆ M heißt eine Kette oder linear geordnete Teilmenge von 〈 M, < 〉, falls 〈 K, <\|K 〉 eine lineare Ordnung ist.

Ist 〈 M, < 〉 = 〈 ℘(ℕ), ⊂ 〉, so ist ℕ das einzige Ziel von 〈 M, < 〉. Die partiellen Ordnungen 〈 ℕ, < 〉 und 〈 { x ⊆ ℕ | x endlich }, ⊂  〉 haben keine Ziele. Im Allgemeinen sind Ziele in einer partiellen Ordnung in einer Vielzahl vorhanden:

Übung

Bestimmen Sie die Ziele der folgenden partiellen Ordnungen:

(i)	〈 ℘(ℕ) − { ℕ }, ⊂ 〉,

(ii)	〈 (℘(ℕ))², < 〉, wobei < für alle x₁, x₂, y₁, y₂ ⊆ ℕ definiert ist durch: (x₁, x₂) < (y₁, y₂), falls x₁ ⊂ y₁ und x₂ ⊂ y₂.

Das „Zornsche Lemma“ garantiert die Existenz von Zielen für eine Vielzahl von partiellen Ordnungen. Der Beweis ergibt sich leicht aus dem Satz über die Existenz von Zielen in Zermelosystemen.

Satz (Satz von Zermelo-Zorn, „Zornsches Lemma“)

Sei 〈 M, < 〉 eine partielle Ordnung. Für alle Ketten K in M existiere eine obere Schranke in M, d. h. ein x  ∈  M mit K ≤ x.

Dann existiert für alle x₀  ∈  M ein Ziel x von M mit x₀ ≤ x.

Beweis

Wir setzen 𝒵 = { K ⊆ M | K ist eine Kette in M }. Dann gilt:

(+) 𝒵 ist ein Zermelosystem.

Beweis von (+)

Sei 𝒦 ⊆ 𝒵 eine Kette in 𝒵, und sei K = ⋃ 𝒦. Wir zeigen, dass K  ∈  𝒵. Seien also x₁, x₂  ∈  K, und seien K₁, K₂  ∈  𝒦 mit x₁  ∈  K₁ und x₂  ∈  K₂. Wegen 𝒦 Kette in 𝒵 gilt K₁ ⊆ K₂ oder K₂ ⊆ K₁. Also gilt x₁, x₂  ∈  K₂ oder x₁, x₂  ∈  K₁. In beiden Fällen gilt dann aber x₁ ≤ x₂ oder x₂ ≤ x₁, da K₁ und K₂ Ketten in M sind. Also ist K Kette in M, d. h. K  ∈  𝒵.

Wegen { x₀ }  ∈  𝒵 und 𝒵 Zermelosystem existiert also ein Ziel K  ∈  𝒵 mit { x₀ } ⊆ K. Dann ist K eine Kette in M. Nach Voraussetzung existiert also ein x  ∈  M mit K ≤ x. Dann ist aber x₀ ≤ x und es gilt:

(++) x ist ein Ziel von M.

Beweis von (++)

Andernfalls gibt es ein y  ∈  M mit x < y. Dann ist aber wegen K ≤ x die Kette K ∪ { y } eine echte Obermenge von K, im Widerspruch zu K Ziel von 𝒵.

Die leere Menge gilt als linear geordnete Teilmenge (also als Kette), hat also unter der Voraussetzung an die partielle Ordnung eine obere Schranke x  ∈  M. Damit ist immer M nichtleer, falls die obere Schranken-Bedingung für Ketten erfüllt ist.

Umgekehrt folgt aus dem Zornschen Lemma der Satz über die Existenz von Zielen in Zermelosystemen: Ist 𝒵 ein Zermelosystem, so erfüllt 〈 𝒵, ⊂ 〉 die Voraussetzung des Zornschen Lemmas, und jedes Ziel von 〈 𝒵, ⊂ 〉 ist ein Ziel von 𝒵.

Ein Beispiel für eine partielle Ordnung, deren Träger kein Zermelosystem bildet, für die aber dennoch die Schrankenbedingung gilt, ist etwa 〈 ℱ, ⊂ 〉 mit ℱ = { X ⊆ ℝ | X ist abgeschlossen }.

Historisch ist das „Zornsche Lemma“ für Zermelosysteme formuliert worden. Es findet sich in einer Arbeit von Max Zorn aus dem Jahre 1935. Das Prinzip wird dort ohne Beweis angegeben, was zu einer Art Tradition in der Mathematik geworden ist. Es hat reinen Werkzeugcharakter, daher auch die Bezeichnung „Lemma“. Es ermöglicht, gewisse Beweise auch ohne Kenntnis der Wohlordnungstheorie führen zu können. Der Beweis des Satzes von Zermelo-Zorn ruht aber vollkommen auf der etwa dreißig Jahre früher entwickelten Technik von Zermelo − in den Varianten von 1904 mit Wohlordnungen wie im Beweis des Wohlordnungssatzes oben, und von 1908 ohne Wohlordnungen wie in 1.5 −, sodass die heute weitverbreitete Namensgebung nicht ganz glücklich erscheint. Man sagt ja auch Satz von Cantor-Bernstein, ohnehin schon Dedekind verschluckend. Warum also nicht Satz von Zermelo-Zorn? Den meisten Mathematikern ist heute Zermelo bestenfalls als „Mister Z“ der Zermelo-Fraenkel-Axiomatik bekannt. Es geht nicht so sehr um Ruhm und Ehre. Ungenaue Zuordnungen von Mensch und Begriff vernebeln die Geschichte.

Wir geben noch einen zweiten Beweis des Satzes von Zermelo-Zorn, der fast zeilenweise dem Zermeloschen Beweis des Wohlordnungssatzes folgt.

Zweiter Beweis des Satzes von Zermelo-Zorn

Sei ℘(M)* = { A ⊆ M | es existiert ein x  ∈  M mit A < x }. Für A  ∈  ℘(M)* sei

σ(A) = „ein x  ∈  M mit A < x“.

Damit ist σ : ℘(M)* → M eine Funktion, die uns − im Falle der Existenz − echte obere Schranken für Teilmengen von M liefert. Wir nehmen weiter σ(∅) = x₀ an. Eine Wohlordnung 〈 A, < 〉 heißt eine σ-Menge, falls gilt:

(i)

A ⊆ M,

(ii)	für alle x  ∈  A ist x = σ(A_x), wobei A_x = { y  ∈  A \| y < x } für x  ∈  A.

Wie im Beweis des Wohlordnungssatzes zeigt man, dass die Vereinigung 〈 N, < 〉 aller σ-Mengen eine σ-Menge ist.

Sei nun x eine obere Schranke für N, also N ≤ x. Eine solche Schranke existiert nach Voraussetzung an 〈 N, < 〉, denn N ist eine linear geordnete (sogar wohlgeordnete) Teilmenge von M. Andererseits gilt N  ∉  dom(σ):

Denn andernfalls ist N < σ(N), und dann ist

〈 N′, <′ 〉 = 〈 N, < 〉 + { σ(N) }

eine σ-Menge. Folglich N′ ⊆ N nach Definition von N. Also gilt σ(N)  ∈  N, Widerspruch!

Wegen N  ∉  dom(σ) existiert keine echte obere Schranke für N. Andererseits gilt N ≤ x nach Wahl von x. Also ist x ein maximales Element von M. Weiter gilt x₀ ≤ x.

Übung

Beweisen Sie den Wohlordnungssatz mit Hilfe des Satzes von Zermelo-Zorn (oder mit Hilfe des Satzes über die Existenz von Zielen in Zermelosystemen).

Das Hausdorffsche Maximalitätsprinzip

Hausdorff hat bereits 1914 ein sehr hochwertiges Maximalitätsprinzip betrachtet [Hausdorff 1914, S. 140f]. Das Prinzip handelt nicht von Zielen in partiellen Ordnungen, sondern von maximalen Ketten in ihnen. Es folgt durch Konstruktion einer zweiten partiellen Ordnung, bestehend aus den Ketten der ersten, leicht aus dem Satz von Zermelo-Zorn, und umgekehrt ergibt sich der Satz von Zermelo-Zorn leicht aus diesem Kettenprinzip.

Satz (Hausdorffs Maximalprinzip)

Sei 〈 M, < 〉 eine partielle Ordnung. Dann existiert eine maximale Kette in M, d. h. es gibt ein N ⊆ M mit der Eigenschaft:

(i)	〈 N, <\|N 〉 ist linear geordnet.

(ii)	Für kein N′ ⊆ M mit N ⊂ N′ ist 〈 N′, <\|N′ 〉 linear geordnet.

Übung

(a)

Beweisen Sie das Hausdorffsche Prinzip:

(i)	analog zum Beweis des Wohlordnungssatzes,

(ii)	mit Hilfe des Satzes über Zermelosysteme.

(b)	Beweisen Sie den Satz von Zermelo-Zorn mit Hilfe des Hausdorffschen Prinzips.

Hausdorff (1914):

„Eine teilweise [partiell] geordnete Menge A hat (vollständig) geordnete [linear geordnete] Teilmengen, z. B. mindestens die aus einem Element bestehenden. Eine geordnete Teilmenge, die in keiner anderen geordneten Teilmenge als echte Teilmenge enthalten ist, also nicht durch Hinzunahme anderer Elemente zu einer geordneten Teilmenge erweitert werden kann, nennen wir eine größte [maximale] geordnete Teilmenge. Die Existenz solcher werden wir zu beweisen haben.“

Schließlich erwähnen wir noch ein weiteres Maximalitätsprinzip, bekannt als Teichmüller-Tukey Lemma [Teichmüller 1939], [Tukey 1940].

Satz (Teichmüller-Tukey-Lemma)

Sei T eine nichtleere Menge. Für alle x gelte:

(+) x  ∈  T gdw für jedes endliche y ⊆ x gilt y  ∈  T.

Dann hat T ein Ziel, d. h. es gibt ein x  ∈  T mit der Eigenschaft:

non(x ⊂ y) für alle y  ∈  T.

Übung

(a)	Beweisen Sie das Lemma von Teichmüller-Tukey mit Hilfe des Satzes von Zermelo-Zorn.

(b)	Beweisen Sie den Satz von Zermelo-Zorn oder das Hausdorffprinzip mit Hilfe des Lemmas von Teichmüller-Tukey.

Genug der Maximalprinzipien. Entscheidend für die Mengenlehre ist der Wohlordnungssatz, und das zweite fundamentale mengentheoretische Resultat dieses Kapitels ist der Satz von Hartogs. Die Maximalprinzipien finden in der Mengenlehre etwas weniger Anwendung als anderswo, da hier Wohlordnungen zur Verfügung stehen. Am klarsten und elegantesten werden die Beweise des Wohlordnungs- und Vergleichbarkeitssatzes und der Maximalprinzipien bei Verwendung der Ordinalzahlen und der transfiniten Rekursion, die wir in den beiden folgenden Kapiteln besprechen.

Ernst Zermelos Wohlordnungssatz

„Beweis, dass jede Menge wohlgeordnet werden kann.

(Aus einem an Herrn Hilbert gerichteten Briefe.)

Von E. Zermelo in Göttingen

. . . Der betreffende Beweis ist aus Unterhaltungen entstanden, die ich in der vorigen Woche mit Herrn Erhard Schmidt geführt habe, und ist folgender.

1) Es sei M eine beliebige Menge …

2) Jeder [nichtleeren] Teilmenge M′ [von M] denke man sich ein beliebiges Element m₁′ zugeordnet, das in M′ selbst vorkommt und das ‚ausgezeichnete‘ Element von M′ genannt werden möge. So entsteht eine ‚Belegung‘ γ der Menge M [ ℘(M) − { ∅ } ] mit Elementen der Menge M von besonderer Art … Im Folgenden wird nun eine beliebige Belegung γ zugrunde gelegt und aus ihr eine bestimmte Wohlordnung der Elemente von M abgeleitet.

3) Definition. Als ‚γ-Menge‘ werde bezeichnet jede wohlgeordnete Menge M_γ [ ⊆ M ], welche folgende Beschaffenheit besitzt: ist a ein beliebiges Element von M_γ und A der ‚zugehörige‘ Abschnitt, der aus den vorangehenden Elementen x ≺ a von M_γ besteht, so ist a immer das ‚ausgezeichnete Element‘ von M − A.

4) Es gibt γ-Mengen innerhalb M. So ist z. B. m₁, das ausgezeichnete Element von M′ = M, selbst eine γ-Menge …

5) Sind M_γ′ und M_γ′′ irgend zwei verschiedene γ-Mengen (die aber zu derselben ein für allemal gewählten Belegung gehören!), so ist immer eine von beiden identisch mit einem Abschnitte der anderen …

6) Folgerungen. Haben zwei γ-Mengen ein Element a gemeinsam, so haben sie auch den Abschnitt A der vorangehenden Elemente gemein. Haben sie zwei Elemente a, b gemein, so ist in beiden Mengen entweder a ≺ b oder b ≺ a.

7) Bezeichnet man als ‚γ-Element‘ jedes Element von M, das in irgendeiner γ-Menge vorkommt, so gilt der Satz: Die Gesamtheit L_γ aller γ-Elemente lässt sich so ordnen, dass sie selbst eine γ-Menge darstellt, und umfasst alle Elemente der ursprünglichen Menge M. Die letztere ist damit selbst wohlgeordnet …

Somit entspricht jeder Belegung γ eine ganz bestimmte Wohlordnung der Menge M …

Der vorliegende Beweis beruht auf der Voraussetzung, dass Belegungen γ überhaupt existieren, also auf dem Prinzip, dass es auch für eine unendliche Gesamtheit von Mengen immer Zuordnungen gibt, bei denen jeder Menge eines ihrer Elemente entspricht …

Die Idee, unter Berufung auf dieses Prinzip eine beliebige Belegung γ der Wohlordnung zugrunde zu legen, verdanke ich Herrn Erhard Schmidt; meine Durchführung des Beweises beruht dann auf der Verschmelzung der verschiedenen möglichen ‚γ-Mengen‘, d. h. der durch das Ordnungsprinzip sich ergebenden wohlgeordneten Abschnitte.

Münden i. Hann., den 24. September 1904.“

(Ernst Zermelo 1904, „Beweis, dass jede Menge wohlgeordnet werden kann“ )