Das Auswahlaxiom

Das letzte Axiom unserer Liste, das „C“, gehört wieder der Axiomatik von Zermelo an.

(AC) Auswahlaxiom

Ist x eine Menge, deren Elemente nichtleer und paarweise disjunkt sind,

so existiert eine Menge y,

die mit jedem Element von x genau ein Element gemeinsam hat.

Die Abkürzung AC steht für engl. axiom of choice.

Das Auswahlaxiom ist ein Axiom im besten Sinne, da es unserer Intuition über den Mengenbegriff entspringt …

Die Menge der Punkte bildet eine Auswahlmenge y für x.

… und doch nimmt es aufgrund seines Charakters eine Sonderstellung unter den ZFC Axiomen ein. Die Auswahlmenge y, die das Axiom garantiert, ist „dunkel“, während die Mengen der anderen Existenzaxiome „hell“ sind:

Wir „sehen“ die Menge Z₀ ={ ∅, { ∅ } , … } , die dem Unendlichkeitsaxiom genügt. Und die anderen Existenzaxiome (LM), (PA), (VER), (AUS) und (ERS) können wir als Instanzen des Komprehensionsaxioms schreiben, und wir sehen sie vor uns, sobald wir ihre definierende Eigenschaft kennen, so etwa für { x, y } = { z | z = x oder z = y } oder ℘(x) = { z | z ⊆ x }. (Wobei wir ℘(x) nur sehen, wenn wir einen Bereich von V überblicken können, der alle Teilmengen von x umfasst. Das Potenzmengenaxiom ist eher sammelnd denn erzeugend, und in diesem Sinne ist die Potenzmenge einer Menge halbhell und halbdunkel.)

Ein vergleichbares Sehen einer Auswahlmenge y für x ist dagegen nur in Spezialfällen möglich. Wir können die Menge y im Allgemeinen nicht in der Form y = { z | ℰ(z) } schreiben, es sei denn, alle a  ∈  x besitzen ausgezeichnete Elemente: Gibt es eine Eigenschaft ℰ(z) mit:

„für alle a  ∈  x existiert genau ein z  ∈  a mit ℰ(z)“,

so können wir eine Auswahlmenge y mit Hilfe von ℰ(z) sichtbar machen:

y = { z  ∈  ⋃ x | ℰ(z) }.

y existiert aufgrund des Vereinigungsaxioms und des Aussonderungsschemas.

Unsere Intuition gibt uns keinen Hinweis, dass stets ausgezeichnete Elemente innerhalb jedes a  ∈  x vorhanden sind. Und somit brauchen wir ein neues Axiom, um eine Auswahlmenge für beliebige x garantieren zu können. Die Auswahlmenge, die uns das Axiom liefert, ist allerdings in keiner Weise mehr eindeutig bestimmt, sie ist zufällig, sie ist „dunkel“. In einem sehr natürlichen Modell der Mengenlehre, dem konstruktiblen Universum L von Gödel, sind tatsächlich immer ausgezeichnete Elemente vorhanden, und wir können das Auswahlaxiom dann in diesem Modell auf der Basis der übrigen Axiome beweisen, da wir in diesem Modell für jedes x eine sichtbare Auswahlmenge definieren können.

Berühmt ist die populäre Formulierung durch Bertrand Russell: Gegeben eine unendliche Menge von Schuhpaaren, können wir ohne Auswahlaxiom eine Menge definieren, die von jedem Paar genau einen Schuh enthält, z. B. die Menge aller linken Schuhe. Dagegen brauchen wir für eine unendliche Menge von Sockenpaaren das Auswahlaxiom, da wir keine Möglichkeit haben, zwischen linken und rechten Socken zu unterscheiden.

Zermelo hat sein Axiom der „simultanen Auswahl“ in seinen Beweisen des Wohlordnungssatzes von 1904 und 1908 substantiell verwendet, und es als allgemeines Prinzip isoliert. Sein Beweis von 1904 hat eine kontroverse und weitgehend irrationale Diskussion um die Legitimation einer „simultanen Auswahl“ hervorgerufen. Heute ist das Auswahlaxiom ein fundamentaler und unumstrittener Bestandteil der Axiomatik der Mengenlehre. Es gibt aber mittlerweile interessante Modelle der Mengenlehre, in denen lediglich abgeschwächte Formen des Auswahlaxioms, sonst aber alle übrigen Axiome − und andere − gelten.

Die Formulierung von (AC) über paarweise disjunkte Mengen ist sehr einfach und anschaulich. Häufig werden aber Auswahlfunktionen gebraucht:

Übung

Zeigen Sie, dass (AC) auf der Basis der übrigen Axiome jeweils äquivalent ist zu:

(i)	Ist M eine Menge mit ∅  ∉  M, so existiert eine Funktion f : M → ⋃ M mit f (x)  ∈  x für alle x  ∈  M.

(ii)	Ist g eine Funktion mit g(x) ≠ ∅ für alle x  ∈  dom(g), so existiert eine Funktion f mit dom(f) = dom(g) und f (x)  ∈  g(x) für alle x  ∈  dom(f).

(iii)

Jede Äquivalenzrelation besitzt ein vollständiges Repräsentantensystem.

Die Aussage (ii) kann man auch so formulieren: Es gilt ⨉_{i  ∈  I} A_i ≠ ∅ für alle Mengen I ≠ ∅, falls A_i ≠ ∅ für alle i  ∈  I.

Wissen wir, dass eine Menge M nichtleer ist, so ist für „Sei also x  ∈  M beliebig.“ natürlich kein Auswahlaxiom notwendig. Allgemein zeigt man durch Induktion nach |M| ohne Auswahlaxiom, dass für ℕ-endliche Mengen M mit ∅  ∉  M immer eine Auswahlfunktion wie in (i) existiert, oder dass das kartesische Produkt von endlich vielen nichtleeren Mengen immer nichtleer ist.

Das Auswahlaxiom wird für die meisten weitergehenden Resultate über Mächtigkeiten gebraucht. Eine Ausnahme bildet der Satz von Cantor-Bernstein, der sich ohne Verwendung von (AC) beweisen lässt. Dagegen ist für einen Beweis des Vergleichbarkeitssatzes das Auswahlaxiom unverzichtbar. Selbst den Satz, dass die abzählbare Vereinigung von abzählbaren Mengen wieder abzählbar ist, kann man nicht ohne eine Form von (AC) beweisen. In den beiden ersten Abschnitten haben wir das Auswahlaxiom darüber hinaus an mehreren Stellen wesentlich benutzt, und durch „ein …“ darauf hingewiesen. Diese Ausdrucksweise „g(y) = ‚ein x  ∈  M mit ℰ(x, y)‘“ ist in der axiomatischen Mengenlehre nur eine bequeme Sprechweise für g(y) = f({ x  ∈  M | ℰ(x, y)}), wobei f eine Auswahlfunktion wie in (i) der Übung oben ist, die man zu Beginn des Beweises auf ℘(M) − { ∅ } fixiert (vgl. etwa Zermelos Beweis des Wohlordnungssatzes). Dieses Präludium der Fixierung einer Auswahlfunktion lenkt aber i. A. nur ab, es genügt, wenn man während des Beweises sicherstellt, dass für alle y ein x  ∈  M mit ℰ(x, y) existiert. Man führt also Beweise üblicherweise ganz wie gehabt mit „ein …“.

Vorsicht ist geboten bei der Rekursion über alle Ordinalzahlen. Dort ist 𝒢(α) = „ein …“ i.a. nicht erlaubt, da wir in ZFC i.a. keine definierbare Auswahloperation ℱ auf V − { ∅ } haben. Im Beweis des Rekursionssatzes wird eine feste Operation ℱ gebraucht. Läuft die Rekursion über eine Wohlordnung (d. h. eine Menge), so ist „ein …“ möglich, da man dann eine Auswahlfunktion benutzen kann. Allgemein macht z. B. 𝒢(α) = „ein x  ∈  V_α + 1 − V_α“ in ZFC keinen Sinn.

Übung

Lokalisieren Sie die Verwendung von (AC) in den Beweisen von:

(i)	\|M\| ≤ \|N\| oder \|N\| ≤ \|M\| für alle Mengen M, N.

(ii)	⋃ { A_n \| n  ∈  ℕ } ist abzählbar, falls alle A_n abzählbar sind.

(iii)

„|M| ≤ |N|“ gdw „es existiert ein f : N → M surjektiv“.

(iv)	M ist (Dedekind-)endlich gdw „\|M\| = \|n\| für ein n  ∈  ℕ“.

Das Auswahlaxiom kommt in vielen Bereichen der Mathematik wesentlich zum Einsatz, zumeist in Gestalt eines Maximalprinzips.

Hier noch einmal eine kleine Liste für den notwendigen Einsatz des Auswahlaxioms, vgl. auch die Diskussion von Maximalprinzipien in 2. 5: „jede Äquivalenzrelation hat ein vollständiges Repräsentantensystem“, „jeder Vektorraum hat eine Basis“, Satz von Hahn-Banach, Satz von Tychonov, Existenz- und Eindeutigkeitssatz des algebraischen Abschlusses eines Körpers, Kompaktheitssatz der Logik, Satz von Tarski über die Existenz von Ultrafiltern, Primidealtheorem für Boolesche Algebren.

Es ist zudem verantwortlich für die Existenz von nicht Lebesgue-messbaren Teilmengen von ℝ, und für andere „paradoxe“ Konstruktionen, die der Maßtheorie i. A. den Zugang zur vollen Potenzmenge einer Menge, deren Teilmengen sie gerne messen möchte, verwehren.

In der Mengenlehre ist (AC) unter anderem äquivalent (über den anderen Axiomen) zum Wohlordnungssatz, zum Vergleichbarkeitssatz, zum Satz von Zermelo-Zorn und zum Multiplikationssatz.

Zermelo (1908b):

„Axiom VI. Ist T eine Menge, deren sämtliche Elemente von 0 verschiedene Mengen und untereinander elementenfremd sind, so enthält ihre Vereinigung 𝔖T mindestens eine Untermenge S₁, welche mit jedem Element von T ein und nur ein Element gemein hat.

(Axiom der Auswahl.)“

Damit sind alle Axiome von ZFC vorgestellt. Es gibt alternative Axiomatisierungen − das System NBG von Neumann-Bernays-Gödel und das System MK von Morse-Kelley −, die sich aber von ZFC nicht durch den Gehalt der Axiome unterscheiden, sondern durch die liberalere Behandlung von Klassen, also von Zusammenfassungen { x | ℰ(x) }. In diesen Systemen ist jedes Objekt eine Klasse, und die Klassen, die Elemente einer anderen Klasse sind, sind die Mengen. Jede Menge ist eine Klasse, aber nicht umgekehrt. Die Mengen sind dann gerade die „kleinen“ Klassen des Systems. In diesen Systemen kann man also offiziell über Objekte { x | ℰ(x) } reden, während wir Klassen in ZFC nur als bequeme Sprechweise verwenden werden (hierzu und zu NBG und MK siehe 3. 3). Insgesamt verfolgen diese alternativen Systeme eine zur Zermelo-Fraenkel-Axiomatik recht ähnliche Interpretation der Paradoxien.

Wir listen die Axiome von ZFC mit einer Beschreibung ihres Charakters noch einmal in anderer Anordnung auf.