6. Zum Auswahlaxiom

Sei M eine Menge von nichtleeren paarweise disjunkten Mengen und sei weiter g = 〈 Xi | i  ∈  I 〉 eine Folge von nichtleeren Mengen. Eine Menge N ⊆ ⋃ M ist eine Auswahlmenge für M, falls N ∩ x genau ein Element enthält für alle x  ∈  M, und eine Funktion f auf I ist eine Auswahlfunktion für g, falls f (i)  ∈  Xi für alle i  ∈  I gilt. Das Auswahlaxiom garantiert die Existenz von Auswahlmengen und Auswahlfunktionen.

Äquivalenzen zum Auswahlaxiom

 Einige Äquivalenzen zum Auswahlaxiom sind:

Satz (einige Äquivalenzen zum Auswahlaxiom)

Äquivalent zu (AC) in der Theorie ZF sind:

(WS)Wohlordnungssatz: Jede Menge lässt sich wohlordnen.
(HM)Hausdorffs Maximalprinzip: Jede partielle Ordnung besitzt eine maximale lineare Teilordnung.
(ZL)Zornsches Lemma: Jede partielle Ordnung, in der jede linear geordnete Teilmenge eine obere Schranke besitzt, besitzt ein maximales Element.
(VS)Vergleichbarkeitssatz für Mächtigkeiten: Für alle M, N gilt |M| ≤ |N| oder |N| ≤ |M|.
(MS)Multiplikationssatz: Für alle unendlichen M ist |M × M| = |M|.

 Wir zeigen den Satz in gestraffter Form. Dabei betrachten wir mehr Implikationen als nötig.

Beweis

(AC) ↷ (WS): 

Sei M eine Menge, und sei f eine Auswahlfunktion auf ℘(M) − { ∅ }. Wir definieren rekursiv für α  ∈  On solange möglich:

xα  =  f (M − { xβ | β < α }).

Es gibt γ < |M|+, sodass xγ nicht definiert ist (da M = { xβ | β < γ }). Wir erhalten eine Wohlordnung <M auf M via „xα <M xβ  gdw  α < β“.

(WS) ↷ (AC): 

Sei M eine Menge wie in (AC). Sei < eine Wohlordnung von M. Dann ist { min(x) | x  ∈  M } eine Auswahlmenge für M.

(WS) ↷ (ZL): 

Sei 〈 P, <P 〉 wie im Zornschen Lemma. Sei < eine Wohlordnung von P. Wir definieren rekursiv für α  ∈  On solange möglich:

pα  =  „das <-kleinste p  ∈  P mit: p > pβ für alle β < α“.

Dann existiert ein letztes definiertes pγ (mit γ < |P|+), und pγ ist maximal in P. (Die obere Schranken-Bedingung garantiert, dass pλ für alle Limiten λ definiert ist, falls pα für alle α < λ definiert ist.)

(WS) ↷ (HM): 

Sei P eine partielle Ordnung, und sei 〈 xα | α < γ 〉 eine Aufzählung von P (mit (WS)). Wir definieren rekursiv für α < γ:

g(α) =  1,falls {xβ|β<α,g(β)=1}∪{xα}linearinP0,sonst.

Dann ist { xα | α < γ, g(α) = 1 } eine maximale linear geordnete Teilmenge von P.

(ZL) ↷ (HM) und (HM) ↷ (ZL): 

Einfach.

(AC) ↷ (VS) und (AC) ↷ (ZL): 

Für Beweise, die den Wohlordnungsbegriff nicht verwenden, siehe „Einführung“, 1. 5.

(ZL) ↷ (VS): 

Sei P = { f | f ist injektiv, dom(f) ⊆ M, rng(f) ⊆ N }, geordnet durch Inklusion. Dann ist die Bedingung des Zornschen Lemmas erfüllt. Ist f  ∈  P maximal, so ist dom(f) = M oder rng(f) = N. Also bezeugt f oder f −1 die Vergleichbarkeit von M und N.

(AC) ↷ (MS): 

In ZF gilt |W × W| = |W| für alle unendlichen Wohlordnungen, wie wir mit Hilfe der Γ-Funktion gezeigt haben. Mit (AC) ist jede Menge M wohlordenbar, und damit folgt die Behauptung.

(ZL) ↷ (MS): 

Mehrere Anwendungen des Zornschen Lemmas liefern (MS) ohne Verwendung von Wohlordnungen (siehe „Einführung“, 1. 12).

(VS) ↷ (AC): 

Sei M eine Menge, und sei 〈 H, < 〉 die Hartogs-Wohlordnung von M. Dann ist der Fall |H| ≤ |M| ausgeschlossen, also gilt |M| ≤ |H|. Eine Injektion von M nach H induziert eine Wohlordnung auf M.

(MS) ↷ (WS): 

Sei M eine o. E. unendliche Menge, und sei 〈 H, < 〉 die Hartogs-Wohlordnung von M. Dann gilt

|M + H| =  |(M + H)2|
=  |M2 + 2 × M × H + H2|
≤  |M × H|

Sei also f : M + H → M × H injektiv. Das Argument von Bernstein liefert nun eine Injektion von M nach H oder eine Injektion von H nach M. Der zweite Fall ist ausgeschlossen, und eine Injektion f : M → H induziert eine Wohlordnung auf M.

 Die Rekursionen über Ordinalzahlen können hier durchweg durch Rekursionen entlang geeigneter Hartogs-Wohlordnungen ersetzt werden. Damit ruhen die Argumente nicht wesentlich auf dem Ersetzungsschema.

Übung

Die folgenden Aussagen sind äquivalent zu (AC) in ZF:

(i)

Für jede Menge M existiert ein N ⊆ M mit den Eigenschaften:

(a)

Die Elemente von N sind paarweise disjunkt und nichtleer.

(b)

Ist x  ∈  M − N, x ≠ ∅, so existiert ein y  ∈  N mit x ∩ y ≠ ∅.

(ii)

Für alle Folgen 〈 Mi | i  ∈  I 〉 existiert eine Folge 〈 Ni | i  ∈  I 〉 mit den Eigenschaften:

(a)

⋃i  ∈  I Ni = ⋃i  ∈  I Mi

(b)

Ni ⊆ Mi für alle i

(c)

Ni ∩ Nj = ∅ für alle i ≠ j.

Der hierarchische Wohlordnungssatz

 Eine bemerkenswerte Äquivalenz zum Auswahlaxiom ist die Vererbung der Wohlordenbarkeit einer Menge auf ihre Potenzmenge:

Satz (hierarchischer Wohlordnungssatz)

Äquivalent zu (AC) in der Theorie ZF ist die Aussage:

(#)  Die Potenzmenge jeder wohlordenbaren Menge ist wohlordenbar.

 Wir nennen die Aussage (#) den hierarchischen Wohlordnungssatz, weil sie genügt, um die Wohlordenbarkeit jeder Stufe der von Neumann-Hierarchie zu zeigen. Der Nachfolgerschritt von Vα zu Vα + 1 = ℘(Vα) ist durch (#) abgedeckt. Im Limesschritt können wir Vλ nicht so ohne weiteres wohlordnen, denn Wohlordnungen auf allen Vα, α < λ, lassen sich i. A. nicht einfach zusammenfügen. Der folgende Beweis zeigt aber, dass wir dennoch über den Limesschritt kommen, indem wir eine zusätzliche Wohlordnung auf ℘(κ) für ein großes, von λ abhängiges κ heranziehen.

Beweis

Aus (AC) folgt in der Wohlordnungssatz und damit (#). Wir nehmen also (#) an und zeigen (AC). Es genügt, durch Induktion nach α  ∈  On zu zeigen:

(+)  Jedes Vα ist wohlordenbar.

Denn ist M wohlordenbar und M  ∈  Vα, so ist M ⊆ Vα und damit wohlordenbar nach (+).

Induktionsanfang α = 0: 

∅ ist eine Wohlordnung auf V0.

Induktionschritt von α nach α + 1: 

Nach I. V. ist Vα wohlordenbar. Nach Voraussetzung (#) ist dann auch Vα + 1 = ℘(Vα) wohlordenbar.

Limesschritt λ: 

Nach Induktionsvoraussetzung ist jedes α < λ wohlordenbar, also existiert |Vα| für alle α < λ. Wir setzen nun:

κ  =  (supα < λ |Vλ|)+.

Nach Voraussetzung (#) existiert eine Wohlordnung <* von ℘(κ). Mit Hilfe dieser Wohlordnung konstruieren wir nun rekursiv Wohlordnungen <α von Vα für alle α < λ.

Rekursionsanfang α = 0: 

Wir setzen <0 = ∅.

Rekursionsschritt von α nach α + 1: 

Sei η = o. t.(〈 Vα, <α 〉), und sei g : Vα → η der zugehörige Isomorphismus. Sei h : ℘(Vα) → ℘(η) ⊆ ℘(κ) definiert durch

h(x)  =  g″x  für alle x ⊆ Vα.

Wir definieren nun:

<α + 1  =  „die von h und <* induzierte Wohlordnung auf Vα + 1“,

d. h. wir setzen für x, y  ∈  Vα + 1: 

x <α + 1 y,  falls  h(x) <* h(y). 

Rekursionsschritt δ, δ Limes: 

Für alle x, y  ∈  Vδ = ⋃α < δ Vα definieren wir:

x  <δ  y,  falls  rang(x) < rang(y)  oder 
rang(x) = rang(y)  und  x <rang(x) + 1 y.

Dann ist <δ eine Wohlordnung von Vδ.

Damit haben wir eine Folge 〈 <α | α < λ 〉 von Wohlordnungen <α auf Vα konstruiert. Wir setzen nun für alle x, y  ∈  Vλ:

x  <  y,  falls  rang(x) < rang(y)  oder 
rang(x) = rang(y)  und  x <rang(x) + 1 y.

Dann ist < eine Wohlordnung auf Vλ (Ende des Limesschritts).

Das Axiom der mehrfachen Auswahl

 Wir betrachten folgende Abschwächung des Auswahlaxioms:

Das Axiom der mehrfachen Auswahl (MC)

Sei M eine Menge paarweise disjunkter nichtleerer Mengen. Dann existiert eine Menge N mit der Eigenschaft:

Für alle x  ∈  M ist N ∩ x endlich und nichtleer.

 Die Bezeichnung (MC) steht hier für „multiple choice“. Das Prinzip ist äquivalent zur folgenden funktionalen Form: Für alle Folgen 〈 Mi | i  ∈  I 〉 von nichtleeren Mengen existiert eine Funktion f auf I derart, dass f (i) eine endliche nichtleere Teilmenge von Mi ist für alle i  ∈  I.

 Es ist überraschend, dass das Prinzip der mehrfachen Auswahl äquivalent zum Auswahlaxiom ist. Der Weg führt über den hierarchischen Wohlordnungssatz, und damit wird das Fundierungsaxiom (und das Ersetzungsschema) ganz wesentlich zum Beweis der Äquivalenz verwendet.

Satz (weitere Äquivalenzen zum Auswahlaxiom)

Äquivalent zu (AC) in der Theorie ZF sind:

(i)

Das Prinzip (MC).

(ii)

Die Existenz von maximalen Antiketten:

Jede partielle Ordnung besitzt eine maximale Antikette.

(iii)

Der lineare Wohlordnungssatz:

Jede linear ordenbare Menge ist wohlordenbar.

(iv)

Der hierarchische Wohlordnungssatz:

Die Potenzmenge jeder wohlordenbaren Menge ist wohlordenbar.

Beweis

Nach dem hierarchischen Wohlordnungssatz genügt es, in ZF die Implikationen (i) ↷ (ii), (ii) ↷ (iii) und (iii) ↷ (iv) zu zeigen.

(i)  ↷  (ii):  Sei 〈 P, < 〉 eine partielle Ordnung. Sei κ der Ordnungstyp der Hartogs- Wohlordnung von ℘(P). Wir definieren eine Funktion

f  :  κ → { X ⊆ P | X ist Antikette in P }

rekursiv solange möglich durch:

f (α)  =  „eine echte Erweiterung der Antikette ⋃β < α f (β)“.

Dann bricht die Rekursion ab (denn andernfalls wäre f : κ → ℘(X) injektiv), und folglich ist ⋃rng(f) eine maximale Antikette in P.

Die Rekursion ist gerechtfertigt nach (MC): Sei nämlich g eine Funktion, die jedem X ⊆ P, X ≠ ∅, ein endliches nichtleeres g(X) ⊆ X zuordnet. Wir setzen nun g′(X)  =  { p  ∈  g(X) | p ist minimal in g(X) }.

Für alle nichtmaximalen Antiketten X in P ist dann

X  ∪  g′({ p  ∈  P − X | X ∪ { p } ist eine Antikette in P })

eine echte Antikettenerweiterung (um endlich viele Elemente). ]

(ii)  ↷  (iii):  Sei 〈 M, <M 〉 eine lineare Ordnung. Wir definieren eine partielle Ordnung 〈 P, < 〉 durch:

P  =  { (X, x) | X ⊆ M und x  ∈  X },

(X, x)  <  (Y, y),  falls  X = Y und x  <M  y.

Sei nun f ⊆ P eine maximale Antikette in P. Dann gilt:

(a)

f ist eine Funktion  (nach Linearität von <M)

(b)

dom(f)  =  ℘(M) − { ∅ }  (nach Maximalität von f)

(c)

f (X)  ∈  X für alle nichtleeren X ⊆ M  (nach Konstruktion von P)

Also ist f eine Auswahlfunktion auf den nichtleeren Teilmengen von M, und damit lässt sich M wohlordnen.

(iii)  ↷  (iv): 

Sei M eine wohlordenbare Menge. Wir zeigen, dass sich ℘(M) wohlordnen lässt. Nach Voraussetzung genügt es zu zeigen, dass sich ℘(M) linear ordnen lässt. Sei hierzu 〈 M, < 〉 eine Wohlordnung von M. Wir ordnen nun ℘(M) lexikographisch, d. h. wir setzen für X, Y ⊆ M:

X  <  Y,  falls  X ≠ Y und minM(X Δ Y)  ∈  Y,

wobei wie üblich X Δ Y = X − Y ∪ Y − X.

Basen in Erzeugendensystemen

 Wir diskutieren schließlich noch ein instruktives Beispiel aus der Theorie der Vektorräume. Eine einfache transfinite Induktion oder Anwendung des Zornschen Lemmas zeigt, dass jedes Erzeugendensystem eines Vektorraumes eine Basis des Vektorraumes als Teilmenge enthält. Umgekehrt kann man aus dieser Aussage das Auswahlaxiom gewinnen. Genauer gilt:

Satz ((AC) und Basen in Erzeugendensystemen)

Äquivalent zu (AC) in der Theorie ZF ist:

(#)Es existiert ein Körper K derart, dass jedes Erzeugendensystem G ⊆ V eines K-Vektorraumes V eine Basis enthält.
Beweis

Wir zeigen (MC). Sei hierzu M eine Menge von paarweise disjunkten nichtleeren Mengen, wobei o. E. jedes Element von M unendlich ist.

Sei nun K ein Körper wie in (#). Wir nennen eine K-wertige Funktion g fast konstant, falls ein endliches E ⊆ dom(g) und ein α  ∈  K existieren, sodass g(x) = α für alle x  ∈  dom(g) − E.

Sei N = ⋃ M. Wir setzen:

V =  „der K-Vektorraum aller g : N → K, für die es ein X  ∈  M gibt mit:
g|X ist fast konstant und g|(N − X) ist konstant gleich 0“.
G =  { v  ∈  V | es gibt ein X  ∈  M, ein xv  ∈  X und ein α  ∈  K mit:
v(xv)  ≠  α,  v(x)  =  α  für alle x  ∈  X − { xv }
v(x)  =  0  für alle x  ∈  N − X  }.

Nach Voraussetzung (#) existiert eine Basis B ⊆ G von V. Für alle X  ∈  M seien 1X  ∈  V die 0-1-wertige Indikatorfunktion von X, und F(X) sei die eindeutig bestimmte endliche Teilmenge von B, sodass

1X  =  ∑v  ∈  F(X) α(v) v  für gewisse α(v)  ∈  K − { 0 }.

Dann ist A = { xv | v  ∈  F(X), X  ∈  M } eine (MC)-Auswahlmenge von M.

Schwache Formen des Auswahlaxioms

 Wir betrachten die beiden folgenden Prinzipien:

Abzählbares Auswahlaxiom (ACω)

Sei M eine abzählbare Menge paarweise disjunkter nichtleerer Mengen. Dann existiert eine Auswahlmenge für M.

Prinzip der abhängigen Auswahl (DC)

Sei M eine nichtleere Menge, und sei R eine zweistellige Relation auf M mit der Eigenschaft:

(+)  Für alle x  ∈  M existiert ein y  ∈  M mit y R x.

Dann existiert eine Folge 〈 xn | n  ∈  ω 〉 in M mit:  xn + 1 R xn  für alle n  ∈  ω.

 Wir nennen 〈 xn | n  ∈  ω 〉 auch eine unendliche R-absteigende Folge in M. Die Bezeichnung (DC) steht für „dependent choice“. Das Axiom erlaubt uns, abzählbar oft ein Element aus M zu wählen, das mit dem letzten gewählten Element in der Relation R steht. Die Wahl von xn + 1 hängt von der Wahl von xn ab. Für partielle Ordnungen 〈 P, < 〉, die die Voraussetzung (+) erfüllen, erhalten wir

x0  >  x1  >  …  >  xn  >  … in P.

 Das abzählbare Auswahlaxiom folgt direkt aus (AC). Auch (DC) ist leicht mit (AC) beweisbar: Ist R auf M wie in (DC) und x0  ∈  M beliebig, so definieren wir:

xn + 1  =  „ein x  ∈  M mit x R xn“  für alle n  ∈  ω.

Dann ist 〈 xn | n  ∈  ω 〉 wie gewünscht.

 Zwischen den beiden Axiomen besteht folgender Zusammenhang:

Satz ((DC) impliziert das abzählbare Auswahlaxiom)

In ZF + (DC) gilt (ACω).

Beweis

Sei M eine abzählbare Menge von nichtleeren paarweise disjunkten Mengen. Ohne Einschränkung ist M unendlich. Sei also 〈 Xn | n  ∈  ω 〉 eine Aufzählung von M ohne Wiederholungen. Sei

F  =  { 〈 x0, …, xn 〉 | n  ∈  ω und xi  ∈  Xi für alle i ≤ n }.

Für s, t  ∈  F sei s < t, falls s ein Anfangsstück von t ist (d. h. s = t|dom(s)). Dann erfüllt < auf F die Voraussetzung (+) von (DC). Also existiert eine Folge 〈 sn | n  ∈  ω 〉 in F mit sn < sn + 1 für alle n  ∈  ω. Wir setzen dann:

A  =  ⋃n  ∈  ω rng(sn).

Dann ist A eine Auswahlmenge für M.

 Mit Hilfe von Modellkonstruktionen kann man dagegen zeigen, dass (DC) in ZF + (ACω) nicht beweisbar ist (ein Ergebnis von Jensen (1966)).

 Wir untersuchen die beiden Prinzipien und ihre typische Verwendung nun noch etwas genauer. Zuerst bemerken wir, dass (DC) folgende Verstärkung zulässt:

Übung

In ZF + (DC) gilt:

Sind M und R wie in (DC), und ist x*  ∈  M beliebig, so existiert eine Folge 〈 xn | n  ∈  ω 〉 in M mit: x0 = x* und xn + 1 R xn für alle n.

 Den Kern des Prinzips der abhängigen Auswahl bringt folgende Äquivalenz ans Licht:

Satz ((DC) und nicht wohlfundierte Relationen)

Die folgenden Aussagen sind äquivalent über ZF:

(i)

(DC).

(ii)

Ist R eine nicht wohlfundierte Relation auf M, so existiert eine Folge 〈 xn | n  ∈  ω 〉 in M mit xn + 1 R xn für alle n  ∈  ω.

Beweis

(i) ↷ (ii):  Ist R nicht wohlfundiert, so existiert ein nichtleeres N ⊆ M ohne R-minimales Element. Also erfüllt R ∩ N2 die Bedingung (+) von (DC), und somit gibt es eine unendliche R-absteigende Folge in N ⊆ M.

(ii) ↷ (i):  Sei R eine Relation auf M wie in (DC). Dann ist M eine nichtleere Teilmenge von M, die kein R-minimales Element besitzt. Also ist R nicht wohlfundiert. Nach Voraussetzung (ii) existiert also eine unendliche R-absteigende Folge.

 Die Lesart „es gibt keine unendliche absteigende  ∈ -Folge“ des Fundierungsaxioms benutzt also das Prinzip der abhängigen Auswahl.

 In vielen Fällen ist eine Anwendung von (DC) natürlich und intuitiv, eine nähere Betrachtung zeigt dann aber, dass (ACω) genügt. Ein instruktives Beispiel für dieses Phänomen ist der folgende Satz, dessen Beweis wir in zwei Versionen führen:

Satz

In ZF + (ACω) gilt das Lemma von König.

Erster Beweis

Wir zeigen das Lemma von König zunächst in ZF + (DC). Sei also 〈 T, < 〉 ein Baum der Höhe ω mit endlichen Stufen (oder gleichwertig: jeder Knoten von T hat höchstens endlich viele Nachfolger). Ohne Einschränkung hat T eine Wurzel s0. Wir definieren nun rekursiv für alle n  ∈  ω:

sn + 1  =  „ein Nachfolger s von sn mit: { t  ∈  T | s ≤ t } ist unendlich“.

[ Diese Rekursion ist durch (DC) gerechtfertigt: Die Wahl des nächsten Knotens hängt vom bislang konstruierten Knoten ab. Formal sei

R  =  { (t2, t1)  ∈  T2 | t2  ∈  sucT(t1) und { t  ∈  T | t2 ≤ t } ist unendlich }.

Sei M = rng(R) (= rng(R) ∪ dom(R)). Dann ist R ⊆ M2 wie in (DC). ]

Dann ist { sn | n  ∈  ω } ein unendlicher Zweig von T.

Zweiter Beweis

Wir geben nun noch ein Argument in ZF + (ACω). Es genügt zu zeigen:

(#)  T ist abzählbar.

Denn dann können wir T aufzählen als 〈 ti | i  ∈  ω 〉 und in obiger Rekursion „ein Nachfolger s von sn mit …“ durch „der erste in der Aufzählung erscheinende Nachfolger s von sn mit …“ ersetzen.

Zum Beweis von (#) sei

Mn  =  { g | g : n → T= n ist bijektiv }  für alle n  ∈  ω.

Dann ist Mn ≠ ∅ für alle n  ∈  ω. Nach (ACω) existiert also eine Folge 〈 gn | n  ∈  ω 〉 mit gn  ∈  Mn für alle n  ∈  ω. Aus dieser Folge erhalten wir leicht eine (stufenweise) Aufzählung des Baumes.

 In der Tat ist das Lemma von König äquivalent zu einer schwachen endlichen Version von (ACω). Wir betrachten hierzu:

Endliches abzählbares Auswahlaxiom (ACω, fin)

Sei M eine abzählbare Menge paarweise disjunkter nichtleerer und endlicher Mengen. Dann existiert eine Auswahlmenge für M.

Satz

In ZF sind äquivalent:

(i)

(ACω, fin).

(ii)

Das Lemma von König.

Beweis

(i) ↷ (ii):  Für den oben gegebenen Beweis von (#) „T ist abzählbar“ genügt (ACω, fin), denn alle Stufen T= n sind endlich, und weiter sind dann auch alle Mengen Mn = { g | g : n → T= n ist bijektiv } endlich.

(ii) ↷ (i):  Sei 〈 Mn | n  ∈  ω 〉 eine Folge von nichtleeren endlichen Mengen. Weiter sei T = { g | dom(g)  ∈  ω und g(i)  ∈  Mi für alle i  ∈  dom(g) }. Dann ist T versehen mit der echten Inklusion ein Baum wie im Lemma von König. Sei also { sn | n  ∈  T } ein unendlicher Zweig von T. Dann ist f = ⋃n  ∈  ω sn eine Funktion auf ω mit f (i)  ∈  Mi für alle i  ∈  ω.

 Zu den schwächsten Versionen einer Auswahl gehören die folgenden Prinzipien, die für jede metamathematische natürliche Zahl n ≥ 2 definiert sind:

Abzählbares Auswahlaxiom für Paarmengen (ACω, n)

Sei M eine abzählbare Menge paarweise disjunkter Mengen, die alle genau n Elemente enthalten. Dann existiert eine Auswahlmenge für M.

Offenbar gilt (ACω) ↷ (ACω, fin) und (ACω, fin) ↷ (ACω, n) für alle n ≥ 2. Wir werden später ein Modell von ZF konstruieren, in dem das Auswahlaxiom für abzählbare viele Paarmengen verletzt ist. Damit ist jeder Satz, der (ACω, 2) impliziert, nicht in ZF beweisbar (es sei denn ZF ist widerspruchsvoll).

 Den Einsatz der abzählbaren Auswahl illustriert der folgende Satz:

Satz

In ZF + (ACω) gilt:

(i)

Jede unendliche Menge ist Dedekind-unendlich.

(ii)

Die abzählbare Vereinigung von abzählbaren Mengen ist abzählbar.

(iii)

ω1 ist eine reguläre Kardinalzahl.

Beweis

zu (i): 

Sei M eine unendliche Menge. Wir zeigen, dass |ℕ| ≤ |M| gilt (dies ist äquivalent zur Dedekind-Unendlichkeit von M in ZF). Sei

Mn  =  { g : n → M | g ist injektiv } für alle n  ∈  ω.

Wegen M unendlich ist Mn nichtleer für alle n  ∈  ω. Nach (ACω) gibt es also eine Funktion f auf ω mit f (n)  ∈  Mn für alle n  ∈  ω, und dann ist ⋃n  ∈  ω rng(f (n)) eine abzählbar unendliche Teilmenge von M.

zu (ii): 

Sei 〈 Mn | n  ∈  ω 〉 eine Folge von abzählbaren Mengen.

Wir nehmen der Einfachheit halber an, dass jedes Mn unendlich ist.

Für n  ∈  ω sei, mit (ACω):

gn  =  „ein bijektives g : ω → Mn“.

Die Cantorsche Diagonalaufzählung von { gn(m) | n, m  ∈  ω } ist dann eine Bijektion zwischen ω und ⋃n  ∈  ω Mn.

zu (iii): 

Sei 〈 αn | n  ∈  ω 〉 eine Folge in ω1, und sei α* = supn  ∈  ω αn.

Dann ist α* < ω1, da sonst ω1 eine abzählbare Vereinigung von abzählbaren Mengen wäre, also nach (ii) abzählbar wäre. Also ist cf (ω1) > ω und damit cf (ω1) = ω1.

 Man kann in der Tat Modelle von ZF konstruieren, in denen cf (ω1) = ω gilt.

 Explizit halten wir fest:

Satz (lineare Ordenbarkeit und endliche Auswahl)

In ZF + „Jede Menge lässt sich linear ordnen“ gilt:

Ist M eine Menge von paarweise disjunkten nichtleeren endlichen Mengen, so existiert eine Auswahlmenge für M.

Beweis

Sei N = ⋃ M, und sei < eine lineare Ordnung auf M. Dann ist die Menge { min<(x) | x  ∈  M } eine Auswahlmenge für M.

Das Auswahlaxiom für wohlordenbare Mengen

 Wir betrachten schließlich noch folgende Abschwächung des Auswahlaxioms, bei der die Grundmenge nicht beliebig, sondern wohlordenbar ist. Die Auswahl erfolgt hier intuitiv entlang einer Wohlordnung, also „Schritt für Schritt“:

Auswahlaxiom für wohlordenbare Mengen (ACWO)

Sei M eine Menge von paarweise disjunkten nichtleeren Mengen, und sei M wohlordenbar. Dann existiert eine Auswahlmenge für M.

 Wie üblich ist das Prinzip äquivalent zu einer Form mit Auswahlfunktionen.

 Offenbar impliziert (ACWO) das abzählbare Auswahlaxiom. Überraschenderweise gilt aber stärker auch der folgende Satz von Jensen (1967):

Satz ((ACWO) impliziert (DC))

In ZF + (ACWO) gilt (DC).

Beweis

Nach obiger Äquivalenz zum Prinzip (DC) genügt es zu zeigen:

(#)Sei E eine Relation auf einer Menge M derart, dass keine unendliche E-absteigende Kette in M existiert. Dann ist E wohlfundiert.

Sei also E auf M wie in (#). Wir beobachten:

(+)  Ist W ⊆ M wohlordenbar, so ist E|W wohlfundiert.

[ Denn andernfalls existiert ein A ⊆ W ohne ein E-minimales Element.

Mit Hilfe einer Wohlordnung auf W können wir dann (ohne (AC)) eine unendliche E-absteigende Kette in A ⊆ M definieren, im Widerspruch zur Voraussetzung aus E. ] 

Wir definieren nun eine Funktion r : M → On durch:

r(x)  =  sup { rangE|W(x) | W ⊆ M ist wohlordenbar und x  ∈  W }.

Wir zeigen, dass für alle x  ∈  M gilt:

(++)  r(x)  =  max { rangE|W(x) | W ⊆ M ist wohlordenbar und x  ∈  W }.

Beweis von (++)

Dies ist klar, falls r(x) keine Limesordinalzahl ist. Sei also r(x) = λ ein Limes. Für α < λ sei

G(α)  =  { g | g ist eine injektive Funktion,  dom(g)  ∈  On,
x  ∈  rng(g) ⊆ M,  α ≤ rangE|rng(g)(x) }.

Nach (ACWO) gibt es eine Funktion H auf λ mit H(α)  ∈  G(α) für alle α < λ.

Wir setzen:

W  =  ⋃α < λ rng(H(α)).

Dann ist W eine wohlordenbare Teilmenge von M (wir betrachten hierzu ∑α < λ 〈 rng(H(α)), <α 〉 und streichen Wiederholungen, wobei <α die von H(α) induzierte Wohlordnung ist für alle α < λ). Dann ist rangE|W(x) ≥ rangE|rng(H(a)) ≥ α für alle α < λ, also gilt rangW|E(x) = λ, denn ≤ gilt nach Definition von λ = r(x). Dies zeigt (++).

Wir zeigen schließlich:

(+++)  Für alle x, y  ∈  M mit x E y gilt r(x) < r(y).

Hieraus folgt die Wohlfundiertheit von E, denn für alle nichtleeren A ⊆ M ist jedes x  ∈  r−1″(α) mit α = min(r″A) ein E-minimales Element von A.

Beweis von (+++)

Seien x, y  ∈  M mit x E y. Nach (++) existiert ein wohlordenbares W ⊆ M derart, dass x  ∈  W und r(x) = rangE|W(x). Sei W′ = W ∪ { y }. Dann ist W′ ⊆ M wohlordenbar und es gilt:

r(x)  =  rangE|W(x)  =  rangE|W′(x)  <  rangE|W′(y)  ≤  r(y).

Kontinuumshypothese und Auswahlaxiom

 Die allgemeine Kontinuumshypothese können wir in ZF so formulieren:

Allgemeine Kontinuumshypothese (GCH)

Seien M, N Mengen mit |M| ≤ |N| ≤ |℘(M)|. Dann gilt |M| = |N| oder |M| = |℘(M)|.

Eine alternative Formulierung von (GCH) in ZF ist: „Für alle α  ∈  On ist |2ℵα| = |ℵα + 1|.“ In ZF gilt aber |2ℵα| = |℘(α)| für alle α  ∈  On. Weiter ist der hierarchische Wohlordnungssatz äquivalent zur Aussage: „Für alle α  ∈  On existiert ein β  ∈  On mit |℘(ℵα)| = |ℵβ|.“ Damit impliziert die alternative Formulierung von (GCH) den hierarchischen Wohlordnungssatz und damit (AC) nach dem obigen Ergebnis.

 Wir zeigen, dass die (GCH) in dieser Formulierung den Wohlordnungssatz und damit das Auswahlaxiom impliziert ([ Sierpiński 1947 ]).

 Wir brauchen einige Notationen. Für eine Menge M sei wieder

℘ 0(M)  =  M,  ℘ n + 1(M)  =  ℘(℘ n(M))  für alle n  ∈  ω.

Für alle X, Y setzen wir:

X  +  Y  =  X × { 1 } ∪ Y × { 2 }

2X  =  X  +  X

Xi  =  X × { i }  für i = 1, 2

 Wir zeigen vorab zwei Hilfssätze in ZF.

Lemma (Hilfssatz 1)

Gilt |℘(2X)| = |X  +  Y| für X und Y, so gibt es ein surjektives s : Y → ℘(X).

Beweis

Wir identifizieren ℘(2X) = ℘(X1 ∪ X2) mit dem Produkt ℘(X1) × ℘(X2). Sei b : X + Y → ℘(X1) × ℘(X2) bijektiv, und sei

pr1(b, X)  =  { Q1  ∈  ℘(X1) | es gibt x, Q2 mit b(x) = 〈 Q1, Q2 〉 }.

Wegen |X1| < |℘(X1)| ist pr1(b, X) ≠ ℘(X1). Sei R ⊆ X1 mit R  ∉  pr1(b, X). Wegen { R } × ℘(X2) ⊆ b″(X + Y) gilt

b″Y  ⊇  { R } × ℘(X2).

Mit |X2| = |X| folgt die Behauptung.

Lemma (Hilfssatz 2)

Sei A eine Menge, und sei B = ℘((A × { 0 }) ∪ ω).

Dann gilt |2℘ n(B)| = |℘ n(B)| für alle n  ∈  ω.

Beweis

Sei A′ = A × { 0 }. Dann gilt A′ ∩ ω = ∅ und:

|2B|  =  |℘(A′ + ω + 1)|  =  |℘(A′ + ω)|  =  |B|.

Weiter ist |B| ≤ |B + 1| ≤ |2B| = |B|, also |B| = |B + 1|, und damit:

|2 × B2|  =  |B + 12|  =  |B2|.

Also gilt |2℘(B)| = |℘(B)|. Induktiv zeigt dieses Argument:

|2℘ n(B)|  =  |℘ n(B)|  für alle n  ∈  ω.

 Damit können wir nun zeigen:

Satz (Satz von Sierpiński)

In ZF + (GCH) gilt der Wohlordnungssatz.

Beweis

Sei A beliebig, und sei B = ℘(A × { 0 } ∪ ω) (vgl. Hilfssatz 2). Es genügt, eine Wohlordnung von B zu finden. Sei hierzu 〈 W, < 〉 die Hartogs-Wohlordnung von B. Dann ist W ⊆ ℘ n + 1(B) für ein geeignet großes n  ∈  ω (bei guter Organisation genügt n = 4). Nach Hilfssatz 2 ist

|℘ n(B)|  ≤  |W + ℘ n(B)|  ≤  |℘ n + 1(B) + ℘ n + 1(B)|  =  |℘ n + 1(B)|.

Nach (GCH) gilt also:

(I)  |W + ℘ n(B)|  =  |℘ n + 1(B)|  oder  (II)  |W + ℘ n(B)|  =  |℘ n(B)|.

Im Fall (I) gibt es nach Hilfssatz 1 wegen |℘ n + 1(B)| = |℘(2℘ n(B))| ein surjektives s : W → ℘ n + 1(B). Wir definieren f : ℘ n + 1(B) → W durch

f (x)  =  „das <W-kleinste w mit s(w) = x“  für alle x  ∈  ℘ n + 1(B).

Dann ist f injektiv, und mit (I) gilt also |W| ≤ |℘ n + 1(B)| ≤ |W|.

Also ist ℘ n + 1(B) gleichmächtig zu W und also wohlordenbar. Wegen |B| ≤ |℘ n + 1(B)| ist dann aber auch B wohlordenbar.

Im Fall (II) gilt |W| ≤ |℘ n(B)|. Es gilt wieder

|℘ n − 1(B)| ≤ |W + ℘ n − 1(B)| ≤ |℘ n(B)|,

und wir erhalten erneut eine Fallunterscheidung (I)′ und (II)′ (mit um eins verkleinerten Indizes). Im Fall (I)′ ist B wohlordenbar, und im Fall (II)′ ist |W| ≤ |℘ n − 1(B)|.

Eine Iteration des Arguments zeigt: B ist wohlordenbar oder es gilt |W| ≤ |℘ 1(B)|. Nach Definition von W gilt aber non(|W| ≤ |B|). Wegen (GCH) gilt also |W| = |℘(B)|. Also kann ℘(B) und damit auch B wohlgeordnet werden.

 Wir beweisen noch einen für sich interessanten allgemeinen Satz von Specker (1954), aus dem wir obiges Resultat über (GCH) und (AC) als Korollar erhalten, wenn wir heranziehen, dass der Multiplikationssatz das Auswahlaxiom impliziert.

Satz (Satz von Specker)

In ZF gilt: Sei M eine Menge mit mindestens fünf Elementen.

Dann gilt non(|℘(M)| ≤ |M2|).

Beweis

Annahme nicht. Sei also f : ℘(M) → M2 injektiv. Wir erzeugen einen Widerspruch durch die rekursive Konstruktion einer injektiven Folge 〈 xα | α  ∈  On 〉 mit xα  ∈  M für alle α  ∈  On.

Hierzu sei P : On → V derart, dass P(α) eine Bijektion von α × α nach α ist für alle α  ∈  On. Wir schreiben auch Pα statt P(α). Weiter sei <e eine Wohlordnung von [ M ]<ω. Schließlich sei f (∅) = (y0, y1), und es seien y2, y3, y4  ∈  M beliebig. Damit können wir nun rekursiv definieren:

Für alle α ≤ 4 sei xα = yα.

Rekursionsschritt für 5 ≤ α < ω:

Wir setzen:

X  =  „das <e-kleinste X′ ⊆ { x0, ..., xα − 1 } mit X′  ∉  f −1″ { x0, ..., xα − 1 }2“.

Ein solches X′ existiert, denn es gilt α2 < 2α für 5 ≤ α < ω, wie man leicht durch Induktion zeigt.

Sei f (X) = (a, b)  ∉  { x0, ..., xα − 1 }2. Wir setzen:

xα =  a,falls a∉{x0,...,xα−1}b,falls b∉{x0,...,xα−1}

Rekursionsschritt für α  ∈  On, ω  ≤  α:

Wir definieren g : α → ℘(M) durch:

g(β) =  f−1(xγ,xδ),mitPα(β)=(γ,δ),falls (xγ,xδ)∈rng(f)∅sonst.

Dann gilt f −1″{ xβ | β < α }2 = rng(g). Für die Diagonalisierung von rng(g), nämlich

D  =  { xβ | xβ  ∉  g(β) }

gilt D  ∉  rng(g) = f −1″{ xβ | β < α }2. Sei f (D) = (a, b).

Wir setzen:

xα =  a,falls a∉{xβ|β<α}b,falls b∉{xβ|β<α}

 Dieser Satz behauptet nicht, dass in ZF die Ungleichung |M2| < |℘(M)| gilt. In der Tat lässt sich in ZF alleine |M2| ≤ |℘(M)| nicht zeigen, obwohl eine „fast-injektive“ Funktion f : M2 → ℘(M) existiert, nämlich f ((x,y)) = { x, y } für x, y  ∈  M.

 Der Satz von Specker enthält den Satz von Cantor: Denn es gilt |M| ≤ |℘(M)| und aus |℘(M)| = |M| würde |℘(M)| ≤ |M| ≤ |M2| folgen.

Übung

Für alle unendlichen M und alle n  ∈  ω gilt:

|n · M|  =  |⋃i < n M × { i }|  ≤  |℘(M)|.

[ Seien x0, x1, ...., x2n  ∈  M paarweise verschieden. Wir setzen:

f(x, i)  =  { x, x2, x4, ..., x2i }, falls  x  ∉  { x2, x4, ..., x2i }
f(x, i)  =  { x0, xk − 1, x2, x4, ..., x2i }, falls  x = x2k für ein 1 ≤ k ≤ i ]
Korollar

In ZF gilt: Sei M eine unendliche Menge und n  ∈  ω. Dann gilt

|n · M|  =  |⋃i < n M × { i }| < |℘(M)|.

Insbesondere ist also |M + 1| = |M ∪ { M }| < |℘(M)|.

Beweis

Es gilt |n · M| ≤ |℘(M)| (vgl. die Übung oben). Wegen M unendlich ist weiter |n · M| ≤ |M2|. Aus der Annahme |n · M| = |℘(M)| folgt also |℘(M)| ≤ |M2|, im Widerspruch zum Satz.

 Damit können wir nun wieder das Auswahlaxiom aus (GCH) herleiten:

Korollar

In ZF + (GCH) gilt der Multiplikationssatz und damit das Auswahlaxiom.

Beweis

Sei M eine unendliche Menge. Dann gilt nach dem Korollar:

|M| ≤ |2 · M| < |℘(M)|.

Nach (GCH) gilt also |M| = |2 · M|. Hieraus folgt |℘(M)2| = |℘(M)| durch Konstruktion einer Bijektion oder durch kurze Rechnung:

|℘(M)2|  =  |(M2)2|  =  |2(M2)|  =  |2 · M2|  =  |M2|  =  |℘(M)|.

Also gilt:

|M|  ≤  |M2|  ≤  |℘(M)2|  =  |℘(M)|.

Nach (GCH) gilt also |M| = |M2| oder |M2| = |℘(M)|. Nach obigem Satz ist aber der zweite Fall unmöglich. Also gilt |M| = |M2|.

Irreguläre Teilmengen von ℝ

 Das Auswahlaxiom führt zur Existenz von Teilmengen von ℝ, die zuweilen als „pathologisch“ und „unerwünscht“ bezeichnet worden sind. Wir betrachten zwei Beispiele und zeigen die zugehörigen Irregularitäts-Resultate, wobei wir eine gewisse Vertrautheit des Lesers mit der Lebesgue- und Baire-Messbarkeit voraussetzen.

 Zunächst betrachten wir:

Definition (Vitali-Menge)

Ein V ⊆ ℝ heißt eine Vitali-Menge, falls V ein vollständiges Repräsentantensystem für die folgende Äquivalenzrelation ist:

x ∼ y,  falls  x − y  ∈  ℚ  für alle x, y  ∈  ℝ.

 Die Existenz von Vitali-Mengen folgt direkt aus der Existenz von vollständigen Repräsentantensystemen, also aus einer elementaren Äquivalenz des Auswahlaxioms.

Satz (Lebesgue-Unmessbarkeit von Vitali-Mengen)

Sei V eine Vitali-Menge. Dann ist V nicht Lebesgue-messbar.

Beweis

Annahme doch. V kann keine Lebesgue-Nullmenge sein, da sonst aufgrund der σ-Additivität und der Translationsinvarianz des Lebesgue-Maßes λ

λ(ℝ)  =  λ(⋃q  ∈  ℚ V + q)  =  ∑q  ∈  ℚ λ(V + q)  =  ∑q  ∈  ℚ λ(V)  =  0

gelten würde, wobei V + q = { x + q | x  ∈  V } die Translation von V um q ist.

Also ist λ(V) > 0, und dann gibt es ein n  ∈  ℕ, sodass W = V ∩ [ − n, n ] ein positives Lebesgue-Maß besitzt. Dann ist aber mit Q = ℚ ∩ [ 0, 1 ]:

∞ =  ∑q  ∈  Q λ(W)  =  ∑q  ∈  Q λ(W + q)
=  λ(⋃q  ∈  Q W + q)
≤  λ([ − n, n + 1 ])  <  ∞,

Widerspruch.

 Unser zweites Beispiel für „pathologische“ Mengen ist:

Definition (Bernstein-Menge)

Ein B ⊆ ℝ heißt eine Bernstein-Menge, falls gilt:

(i)

|B| = |ℝ| = |2ω|.

(ii)

Weder B noch ℝ − B enthält eine nichtleere perfekte Teilmenge.

 Statt nichtleere perfekte Teilmenge kann man in der zweiten Bedingung nach dem Satz von Cantor-Bendixson gleichwertig überabzählbare abgeschlossene Teilmenge fordern.

 Die Existenz einer Bernstein-Menge in ZFC ist etwas schwieriger zu zeigen (vgl. „Einführung“, 2. 12): Mit (AC) existiert eine Aufzählung 〈 Pα | α < 2ω 〉 aller nichtleeren perfekten Mengen. Wir gehen nun diese Aufzählung rekursiv ab und wählen an jeder Stelle zwei neue (bislang ungewählte) verschiedene reelle Zahlen xα, yα  ∈  Pα. Dann ist B = { xα | α < 2ω } eine Bernstein-Menge. Bernstein-Mengen sind so konstruiert, dass sie die Scheeffer-Eigenschaft verletzen. Dabei hat eine Menge P von reellen Zahlen die Scheeffer-Eigenschaft, falls P abzählbar ist oder eine nichtleere perfekte Teilmenge enthält. Bernstein-Mengen sind aber auch Gegenbeispiele zur maßtheoretischen und topologischen Messbarkeit:

Satz (Unmessbarkeit von Bernstein-Mengen)

Sei B eine Bernstein-Menge. Dann ist B weder Lebesgue-messbar noch Baire-messbar.

Beweis

B ist nicht Lebesgue-messbar:

Annahme doch. Ohne Einschränkung ist dann λ(B) > 0 (sonst arbeiten wir mit ℝ − B). Lebesgue-messbare Mengen lassen sich bzgl. ihres Maßes beliebig genau durch abgeschlossene Teilmengen approximieren. Also gibt es ein abgeschlossenes A ⊆ B mit λ(A) > 0. Dann ist aber A überabzählbar und abgeschlossen, also gibt es ein nichtleeres perfektes P ⊆ A nach dem Satz von Cantor-Bendixson, im Widerspruch zu B Bernstein-Menge.

B ist nicht Baire-messbar:

Dann existiert eine offene Menge U mit B Δ U = (B − U) ∪ (U − B) mager. Ohne Einschränkung ist U ≠ ∅ (sonst arbeiten wir wieder mit ℝ − B). Seien nun Nn, n  ∈  ω, nirgendsdicht mit U − B = ⋃n  ∈  ω Nn. Wir können nun leicht eine Folge 〈 Is | s ist eine endliche 0-1-Folge 〉 konstruieren (durch Rekursion über |s|), sodass für alle f : ω → 2 gilt:

(i)

If|n ist ein kompaktes Intervall positiver Länge,

(ii)

〈 If|n | n  ∈  ω 〉 ist ⊂-absteigend gegen eine Einermenge { xf },

(iii)

If|n  ⊆  U − Nn  für alle n  ∈  ω.

Dann ist aber P = { xf | f : ω → 2 } ⊆ U − ⋃n  ∈  ω Nn ⊆ B perfekt, im Widerspruch zu B Bernstein-Menge.

 Zu den berühmtesten und interessantesten „pathologischen“ Konsequenzen des Auswahlaxioms gehören weiter die Paradoxa von Hausdorff und Banach-Tarski über sog. „paradoxe“ Zerlegungen der Kugeloberfläche und der Vollkugel im dreidimensionalen Kontinuum. Wir dürfen − um Wiederholungen zu vermeiden − den Leser hier auf die ausführliche Darstellung in den „Reellen Zahlen“ verweisen. Dort werden auch weitere irreguläre Mengen und die übergeordnete Regularitätseigenschaft der Determiniertheit diskutiert.

Bemerkungen

 Das Auswahlaxiom hat bei seiner Einführung und Popularisierung durch Ernst Zermelo große Kontroversen ausgelöst, wurde danach aber zu einem festen Bestandteil der axiomatischen Mengenlehre. Es ist sicherlich ein besonderes Axiom. Alle Axiome von ZF mit Ausnahme der regulierenden Axiome (Ext) und (Fun) fordern die Existenz einer eindeutig bestimmten Menge oder sie lassen sich als Instanzen des Komprehensionsschemas schreiben, z. B. ist das Potenzmengenaxiom die Aussage: Für alle x ist { y | y ⊆ x }  ∈  V. Das Auswahlaxiom ist ein Reichhaltigkeitsaxiom, lässt sich aber nicht in dieser Weise formulieren.

 Eine genauere Untersuchung der verschiedenen Formen und Abschwächungen des Auswahlaxioms, ihrer Einsatz-Möglichkeiten und Einsatz-Notwendigkeiten erscheint gerechtfertigt. Derartige Untersuchungen beleuchten das Prinzip, und ein gewisser Überblick und ein Gefühl für die Rolle, die das Axiom spielt, gehören zum Grundverständnis von ZFC. Auf der anderen Seite kann man eine Sensibilisierung in Bezug auf Auswahlakte auch übertreiben. Es ist keineswegs angemessen, die Rolle eines Wachhundes zu übernehmen und jedesmal zu bellen, wenn irgendwo in der Mathematik (AC) verwendet wird. Der Einsatz des Auswahlaxioms ist zuweilen sogar geeignet, um den tragenden Kern eines Argumentes deutlich zu machen. Definieren wir z. B. f (x) = „ein y mit φ(y)“, so muss der Rest des Beweises mit der Information auskommen, dass f (x) die Eigenschaft φ erfüllt. Der Auswahlakt stellt hier klar heraus, was wirklich gebraucht wird, und erleichtert so das Lesen eines Beweises. Ist er vermeidbar, so kann man dies am Ende noch anmerken. Letztendlich ist das Auswahlaxiom einfach ein natürliches Mitglied einer konsequenten und charakterstarken Axiomatik, und es hat viele allgemeinmathematisch unverzichtbare und mengentheoretisch begrüßenswerte Auswirkungen.

 Für den Autor ist die Bezeichnung „pathologisch“ für gewisse Konsequenzen des Auswahlaxioms eine reine Sprechweise, und keinerlei Hinweis auf einen zu kurierenden Defekt. Es ist hochinteressant, dass das Lebesgue-Maß nicht auf der vollen Potenzmenge von ℝ konstruiert werden kann. Aber warum ist es intuitiv oder auch nur wünschenswert, dass jede Menge Lebesgue-messbar ist? Man kann in ZFC auf einem reichhaltigen Teilbereich von ℘(ℝ) σ-additiv und symmetrieinvariant messen, und damit kann die axiomatische Mengenlehre die Erfahrungen der physikalischen und mathematischen Analysis bestätigen, erläutern und absichern. Die Extension des regulären Bereiches genauer zu bestimmen ist eine spannende Angelegenheit. Der Bereich der unmessbaren Mengen wird mit ganz anderen Methoden entdeckt und untersucht als der der messbaren Mengen, und er bleibt seiner Natur entsprechend viel dunkler als z. B. das gut ausleuchtbare Feld der Borel-Mengen. Aber dies spricht nicht gegen das Auswahlaxiom.

 Wer (AC) ablehnt und nicht angibt, genau welche Mengen wohlordenbar sind, raubt der Axiomatik an Klarheit. Wer nur in ZF arbeitet und Implikationen schwacher Formen des Auswahlaxioms untersucht, findet interessante Zusammenhänge und mathematische Struktur, aber auch hier bleibt dann die Frage offen, für welche Mengen eine Auswahlmenge existiert und für welche nicht.

 Für die metamathematische Untersuchung von ZFC ist eine Auszeichnung der Theorie ZF unabdingbar. Wir werden im nächsten Abschnitt zeigen, dass das Auswahlaxiom nicht für Widersprüche von ZFC verantwortlich sein kann: Ist ZF widerspruchsfrei, so ist auch ZFC widerspruchsfrei. Um dies zu beweisen, werden wir in ZF arbeiten und ein Klassenmodell von ZFC konstruieren, nämlich Gödels konstruktibles Universum L. Da wir nur ZF zur Verfügung haben, ist es notwendig zu wissen, dass wir wichtige Teile der axiomatischen Mengenlehre − etwa die Ordinalzahltheorie samt Rekursion − ohne Auswahlaxiom etablieren können. Denn nur dann können wir sie zur Konstruktion des Modells L innerhalb der Theorie ZF heranziehen.

 Insgesamt wird sich durch die Untersuchung von L ergeben, dass das Auswahlaxiom für einen riesengroßen Teilbereich des mengentheoretischen Universums − der Klasse L − automatisch gilt. Die Axiomatik ZF garantiert sogar, dass sich die Klasse L durch eine Formel der Sprache der Mengenlehre wohlordnen lässt, und damit können in L Auswahlakte „f (x) = ‚ein x mit φ(x)‘“ immer und uniform durch „f (x) = ‚das L-kleinste x mit φ(x)‘“ ersetzt werden. Dieses Ergebnis ist vielleicht der wichtigste Beitrag zur ganzen Diskussion um (AC): Das Auswahlaxiom ist ein beweisbarer Satz in L, und es gilt in L in einer stärksten Form. Zudem kann man in ZFC nicht zeigen, dass der Teilbereich L echt ist, dass es also eine Menge x gibt mit x  ∈  V − L. Die Theorie ZFC fordert nicht, dass V die Klasse L transzendiert. (Diese Aussagen gelten wie immer unter der Voraussetzung der Widerspruchsfreiheit von ZFC oder gleichwertig der von ZF. Andernfalls ist ja alles beweisbar.) Die Aussage „V = L“ ist inkompatibel mit großen Kardinalzahlaxiomen. Die Meinung, dass durch die großen Kardinalzahlaxiome V = L widerlegt ist, wird nicht von allen Mengentheoretikern geteilt. Das Licht, das L auf das Auswahlaxiom wirft, wird von dieser Diskussion nicht getrübt.

 Den schwachen abzählbaren Formen des Auswahlaxioms kommt eine weitere wichtige Bedeutung zu: Ein in der modernen Mengenlehre intensiv untersuchtes Prinzip ist das Axiom der Determiniert (AD), das allen Teilmengen von ℝ gute Regularitätseigenschaften aufnötigt. Unter (AD) sind alle Teilmengen von ℝ Lebesgue-messbar, Baire-messbar, und haben die Scheeffer-Eigenschaft. (Siehe z. B. „Reelle Zahlen“.)

 In der Theorie ZF + (AD) ist nun zwar (AC) beweisbar falsch, aber andererseits ist das Prinzip (ACω) beweisbar richtig. Gewöhnlich wird aber etwas stärker in ZF + (AD) + (DC) argumentiert, und die wichtigsten Modelle von ZF + (AD), die in ZFC mit Hilfe starker großer Kardinalzahlaxiome konstruiert worden sind, erfüllen in der Tat das Axiom der abhängigen Auswahl. Durch das Axiom der Determiniertheit erhält also (DC) zusätzliches Gewicht. Das Axiom der Determiniertheit wird insgesamt nicht als Alternative zu (AC) gesehen und propagiert, die vorherrschende Sicht der Dinge ist: In ZFC erweitert um große Kardinalzahlaxiome existiert ein kanonisches Modell von ZF + (AD). (Konkret ist dies das Modell L(ℝ), das über den reellen Zahlen konstruierte konstruktible Universum.)

Zusätzliches

 Das Auswahlaxiom und seine Varianten lassen sich in vielerlei Hinsicht weiter untersuchen: Wie hängen die schwachen Formen des Auswahlaxioms untereinander zusammen? Welche Formen genügen für welche Anwendungen? Welche Sätze der allgemeinen Mathematik implizieren (AC) oder Abschwächungen?

 Die Untersuchung solcher Fragen ist ein klassisches Teilgebiet der Mengenlehre seit Arbeiten von Tarski, Sierpiński und anderen. Sie ist aber nicht jedermanns Sache, und speziell für die, denen das Auswahlaxiom als unproblematisch gilt und die von der abstrakten infinitären Mengenlehre keine konstruktiven Charakterzüge erwarten, wird dieses Gebiet vielleicht als unattraktiv und verzichtbar erscheinen. Andere wiederum werden seine Vielfalt und Eigenartigkeit schätzen. Wir präsentieren einige Fragestellungen und Ergebnisse in den folgenden Übungen. Der Leser möge sich die ihn ansprechenden Themen heraussuchen. Sie sind in jedem Falle geeignet, das Auge für das Auswahlaxiom und seinen Einsatz weiter zu schulen.

Übung

In ZF gilt:

(i)

Es gibt ein surjektives f : ℝ → ω1.

(ii)

Existieren abzählbare Mn ⊆ ℝ mit ℝ = ⋃n  ∈  ω Mn, so gilt cf (ω1) = ω.

(iii)

Ist |ω1| ≤ |ℝ|, so ist ℝ keine abzählbare Vereinigung von abzählbaren Mengen.

(iv)

Es gibt keine abzählbaren An ⊆ ω2 mit ω2 = ⋃n  ∈  ω An.

[ zu (i):  Es gilt |ℝ| = |℘(ω)| = |℘(ω × ω)|. Ist α < ω1, so existiert eine Wohlordnung < ⊆ ω × ω (auf ω oder einem Element von ω) des Ordnungstyps α.

zu (ii):  mit Hilfe von (i).

zu (iii):  Es gilt |ℝ| = |ω2|. Sei 〈 An | n  ∈  ω 〉 eine Zerlegung von ω mit |An| = ω für alle n  ∈  ω. Aus |ω1| ≤ |ω2| folgt die Existenz eines injektiven g : ω1 → ω2 derart, dass { g(α)|An | α < ω1 } überabzählbar ist für alle n  ∈  ω. Sind nun Mn ⊆ ω2 abzählbar für alle n  ∈  ω, so sei f : ω → 2 definiert durch

f|Mn  =  g(αn)|Mn für alle n  ∈  ω,

wobei

αn  =  „das kleinste α < ω1 mit g(α)|Mn  ∉  Mn“.

Dann ist f  ∉  ⋃n  ∈  ω Mn.

zu (iv):  Annahme doch. Sei dann αn = o. t.(〈 An, < 〉) für n  ∈  ω, und sei

α  =  ∑n  ∈  ω αn.

Dann existiert eine Surjektion f : α → ω2, im Widerspruch zu α ≤ ω1. ]

Übung

Die folgenden Aussagen sind äquivalent zu (ACω) in ZF:

(i)

Für alle surjektiven g : M → ℕ gibt es ein h : ℕ → M mit g ∘ h = idℕ.

(ii)

Für alle f : ℕ → C und alle surjektiven g : B → C existiert ein h : ℕ → B mit f = g ∘ h.

Übung

Die folgende Aussage ist äquivalent zu (ACω, fin) über ZF:

Die abzählbare Vereinigung von endlichen Mengen ist abzählbar.

[ Ist E endlich, so ist die Menge aller bijektiven f : |E| → E endlich. ]

 Analog ist (ACω, 2) über ZF äquivalent zur Abzählbarkeit einer abzählbaren Vereinigung von Mengen mit jeweils genau zwei Elementen. Allgemein gilt:

Übung

Die folgenden Aussagen sind äquivalent in ZF für alle n ≥ 2:

(i)

Ist M eine abzählbare Menge von Mengen mit jeweils höchstens n Elementen, so ist ⋃ M abzählbar.

(ii)

Ist M eine abzählbare Menge von Mengen mit jeweils genau n Elementen, so ist ⋃ M abzählbar.

(iii)

Für alle 2 ≤ m ≤ n gilt (ACω, m).

(iv)

Es gilt (ACω, ≤ n), wobei (ACω, ≤ n) wie (ACω, n) definiert ist, aber nun „höchstens n Elemente (und mindestens eines)“ die Phrase „genau n Elemente“ ersetzt.

Übung

In ZF gilt:  (ACω, n) impliziert (ACω, m),  falls  m ein Teiler von n ist.

 Für Leser mit erhöhtem kombinatorischen Spieltrieb notieren wir noch:

Übung

Für eine natürliche Zahl n ≥ 2 sei (AC∞, n) wie (ACω, n), wobei nun auf die Abzählbarkeit der Menge M verzichtet wird. Dann gilt in ZF:

(i)

(AC∞, 2) impliziert (AC∞, 4).

(ii)

(AC∞, 2) + (AC∞, 3) impliziert (AC∞, 6).

[ zu (i): Sei M eine Menge von paarweise disjunkten Mengen mit jeweils genau 4 Elementen. Betrachte Auswahlmengen für P = { { A, B } | { A, B } ist eine Zerlegung eines X  ∈  M in 2 Teile mit jeweils genau 2 Elementen } und R = { A | A ist eine Teilmenge eines X  ∈  M mit genau zwei Elementen }.

zu (ii): Sei M eine Menge von paarweise disjunkten Mengen mit jeweils genau 6 Elementen. Betrachte Auswahlmengen für R(2) und R(3), wobei

R(n)  =  { A | A ist eine Teilmenge eines X  ∈  M mit genau n Elementen }.

Mit Hilfe dieser Auswahlmengen genügt es (!), ein N zu finden mit:

Für alle Y  ∈  N ist Y ≠ ∅ und es existiert genau ein X  ∈  M derart, dass Y eine echte Teilmenge von X ist.

Hierzu sei Z = { { A, B, C } | { A, B, C } ist eine Zerlegung eines X  ∈  M in 3 Teile mit jeweils genau zwei Elementen }. Mit Hilfe von (AC∞, 3) und (AC∞, 2) erhalten wir ein f : Z → ⋃M mit

f({ A, B, C })  ∈  A ∪ B ∪ C  für alle { A, B, C }  ∈  Z.

Jedes X  ∈  M hat genau 15 Zerlegungen der Form { A, B, C } mit |A| = |B| = |C| = 2. Wir setzen nun für alle X  ∈  M:

g(X)  =  { x  ∈  X | x erscheint mindestens dreimal im Wertebereich von f }

Dann ist 1 ≤ g(X) ≤ 5 und also N = { g(X) | X  ∈  M } wie gewünscht. ]

 Die folgende Übung zeigt, dass wir bereits in ZF + „Jede Menge von paarweise disjunkten 2-elementigen Mengen besitzt eine Auswahlmenge“ (also (AC∞, 2)) eine Menge reeller Zahlen angeben können, die den Symmetrie-Eigenschaften des Lebesgue-Maßes widerspricht.

Übung

Für s  ∈  ℝ − ℚ ist gs : ℝ → ℝ wohldefiniert durch:

gs(x) =  1,falls x−s∈ℚ−1,falls x+s∈ℚ0,sonst.

Sei G eine Auswahlmenge für { { gs, − gs } | s  ∈  ℝ − ℚ }. Wir setzen:

A  =  { s  ∈  ℝ − ℚ | gs  ∈  G }.

Dann ist A nicht Lebesgue-messbar.

[ Für alle s  ∈  ℝ − ℚ gilt:

(i)

gs = gs + q für alle q  ∈  ℚ,  also:  s  ∈  A  impliziert  s + q  ∈  A für alle q  ∈  ℚ,

(ii)

g− s = − gs,  also:  s  ∈  A  gdw  − s  ∉  A.

Sei I = ] c − a, c + a [ ein Intervall mit c  ∈  ℚ. Sei A′ = A ∩ I, und sei B′ die am Punkt c gespiegelte Menge A′, also B′ = { 2c − p | p  ∈  A′ }. Wegen (i), (ii) gilt B′ = I − A′. Wäre also A Lebesgue-messbar, so wäre λ(A ∩ I) = λ(I)/2 für alle Intervalle I mit rationalem Mittelpunkt. Dies ist ein Widerspruch zur folgenden nicht schwer zu zeigenden Eigenschaft des Lebesgue-Maßes: „Für alle Lebesgue-messbaren P ⊆ ℝ positiven Maßes und alle ρ < 1 gibt es ein Intervall I positiver Länge mit rationalen Endpunkten derart, dass λ(P ∩ I)/λ(I) > ρ.“ ]