Auswahlaxiom

Definition

Sei ${\displaystyle A}$ eine Menge nichtleerer Mengen. Dann heißt

${\displaystyle F\colon A\to \bigcup _{X\in A}X}$

eine Auswahlfunktion für ${\displaystyle A}$, falls jedem Element ${\displaystyle X\in A}$ ein Element ${\displaystyle F(X)\in X}$ zugeordnet wird. ${\displaystyle F}$ wählt also aus jeder Menge ${\displaystyle X}$ in ${\displaystyle A}$ genau ein Element aus.

Beispiele

• Sei ${\displaystyle A=\{\{0,2\},\{1,2,5,7\},\{4\}\}}$. Die auf ${\displaystyle A}$ durch

${\displaystyle F(\{0,2\})=2,\quad F(\{1,2,5,7\})=2,\quad F(\{4\})=4}$

definierte Funktion ${\displaystyle F}$ ist eine Auswahlfunktion für ${\displaystyle A}$.

• Für eine endliche Menge ${\displaystyle A=\{A_{1},\ldots ,A_{n}\}}$ von nichtleeren Mengen ist es trivial, eine Auswahlfunktion anzugeben: Man wählt aus jeder Menge irgendein bestimmtes Element aus, was problemlos möglich ist; dazu braucht man das Auswahlaxiom nicht. Ein formaler Beweis würde Induktion über die Größe der endlichen Menge verwenden.
• Für die Potenzmenge der natürlichen Zahlen ohne die leere Menge ist eine Auswahlfunktion ${\displaystyle F\colon {\mathcal {P}}(\mathbb {N} )\setminus \{\emptyset \}\to \mathbb {N} }$ gegeben durch das Minimum der Menge, also ${\displaystyle F(X)=\min X}$. Die Existenz eines Minimums ist aufgrund der Wohlordnung der natürlichen Zahlen gegeben.
• Für die Menge aller beschränkten, nichtleeren, reellen Intervalle ist eine Auswahlfunktion gegeben, indem man auf den Mittelpunkt abbildet.

Motivation

Im Allgemeinen ist es nicht möglich, zu jeder Menge eine Auswahlfunktion anzugeben. Für welche Fälle das Auswahlaxiom relevant ist, sei an den folgenden Beispielen verdeutlicht:

• Man kann schon für eine allgemeine abzählbare Menge von zweielementigen Mengen in ZF (nicht ZFC, d. h. ohne das Auswahlaxiom) die Existenz einer Auswahlfunktion nicht beweisen.
• Dasselbe gilt etwa für die Existenz einer Auswahlfunktion für die Menge aller nichtleeren Teilmengen der reellen Zahlen.

Aussage

Das Auswahlaxiom lautet dann: Für jede Menge nichtleerer Mengen gibt es eine Auswahlfunktion. Äquivalente Formulierungen sind:

• Die Potenzmenge einer beliebigen Menge ohne die leere Menge hat eine Auswahlfunktion (Zermelo 1904).
• Sei ${\displaystyle A}$ eine Menge von paarweise disjunkten nichtleeren Mengen. Dann gibt es eine Menge ${\displaystyle C}$, die mit jedem ${\displaystyle X\in A}$ genau ein gemeinsames Element hat (Zermelo 1907, ZF).
• Sei ${\displaystyle I}$ eine beliebige Indexmenge und ${\displaystyle \left(A_{i}\right)_{i\in I}}$ eine Familie von nichtleeren Mengen ${\displaystyle A_{i}}$, dann existiert eine Funktion ${\displaystyle F}$ mit Definitionsbereich ${\displaystyle I}$, die jedem ${\displaystyle i\in I}$ ein Element von ${\displaystyle A_{i}}$ zuordnet: ${\displaystyle F(i)\in A_{i}}$.
• Sind ${\displaystyle A}$ und ${\displaystyle B}$ Mengen und ${\displaystyle R\subseteq A\times B}$ eine Relation zwischen ${\displaystyle A}$ und ${\displaystyle B}$, so folgt aus ${\displaystyle \forall a\in A:\exists b\in B:(a,b)\in R}$, dass ${\displaystyle \exists f\colon A\to B:\forall a\in A:(a,f(a))\in R}$ (d. h., jede linkstotale Relation umfasst eine Abbildung).

Schwächere Aussagen

Gelegentlich werden auch Abschwächungen des Auswahlaxioms diskutiert. Beispielsweise:

• das abzählbare Auswahlaxiom (CC, für countable choice, auch bezeichnet mit AC_ω oder ACN), das besagt, dass eine Auswahlfunktion existiert, wenn die Mengenfamilie abzählbar ist,
• das Axiom der abhängigen Auswahl (DC, für dependent choice), das – den Funktionsbegriff verallgemeinernd – eine Aussage über eine Relation trifft.
• unique choice/non-choice: Sind ${\displaystyle A}$ und ${\displaystyle B}$ Mengen und ${\displaystyle R\subseteq A\times B}$ eine Relation zwischen ${\displaystyle A}$ und ${\displaystyle B}$, so folgt aus ${\displaystyle \forall a\in A:\exists !b\in B:(a,b)\in R}$, dass ${\displaystyle \exists f\colon A\to B:\forall a\in A:(a,f(a))\in R}$. In populären Formalisierungen der Mathematik ist dies eine Trivialität (Funktionen sind einfach Relationen mit der im Antezedens genannten Eigenschaft), in allgemeineren Kontexten handelt es sich jedoch um eine nichttriviale Aussage.

Stärkere Aussagen

Das Auswahlaxiom folgt, wie Wacław Sierpiński 1947 bewies, aus der verallgemeinerten Kontinuumshypothese. Auch das von Gödel formulierte Konstruierbarkeitsaxiom ist stärker als das Auswahlaxiom.

Innerhalb von Klassentheorien, wie etwa der Neumann-Bernays-Gödel-Mengenlehre, lässt sich das Auswahlaxiom auch auf Klassen ausdehnen.