AD VERSUS AC

PHILIPP ROHDE Seminar Deskriptive Mengenlehre Wintersemester 1999/2000

1 Einführung von AD

In den bisherigen Referaten haben wir gesehen, daß viele ”gute“ Mengen determiniert^{1} sind. Zu diesen Mengen gehören offene und abgeschlossene Mengen (Gale-Stewart 1953). 1955 konnte Philip Wolfe zeigen, daß die Σ_{2}^{0}-Mengen determiniert sind und 1964 bewies Morton Davis die Determiniertheit der Σ_{3}^{0}-Mengen. Wir haben auch schon gesehen, daß alle Borel-Mengen, d.h. alle Δ_{1}^{1}-Mengen determiniert sind (Donald Martin 1975). Nach diesen Ergebnissen drängt sich die Frage auf, ob dies für alle Mengen gilt. Aber David Gale und Frank Stewart zeigten schon in ihrem Artikel von 1953, daß in ZFC die Existenz einer nichtdeterminierten Teilmenge der reellen Zahlen^{2} bewiesen werden kann. Für dieses Resultat ist ganz wesentlich AC verantwortlich:

(1.1) Satz (Gale-Stewart 1953): ZFC ⊢ es existiert eine Menge A ⊆ ω^{ω}, die nicht determiniert ist.

Beweis: Eine Strategie für Spieler I im Spiel G_{ω}(A) ist eine Funktion σ : ⋃_{n∈ω} ω^{2n} → ω.

Da \overline{\overline{⋃_{n∈ω} ω^{2n}}} = ℵ_{0} und \overline{\overline{ω^{ω}}} = 2^{ℵ_{0}}, gibt es also insgesamt 2^{ℵ_{0}} verschiedene Strategien für Spieler I in diesem Spiel und genauso viele für Spieler II. Sei nun (σ_{α} | α < 2^{ℵ_{0}}) eine Aufzählung der Strategien für Spieler I und (τ_{α} | α < 2^{ℵ_{0}}) derjenigen für Spieler II (AC !). Definiere nun rekursiv a_{α} und b_{α} wie folgt: x_{0}, y_{0} ∈ ω^{ω} seien so gewählt, daß

b_{0} :≡ σ_{0} ∗ y_{0} ≠ x_{0} ∗ τ_{0} ≡: a_{0}.

Sind nun {a_{β} | β < α} und {b_{β} | β < α} für 1 ≤ α < 2^{ℵ_{0}} bereits definiert, dann wähle mit Hilfe von AC x_{α}, y_{α} ∈ ω^{ω}, so daß gilt:

b_{α} :≡ σ_{α} ∗ y_{α} ∉ {a_{β} | β < α} und
a_{α} :≡ x_{α} ∗ τ_{α} ∉ {b_{β} | β ≤ α}.

Da die Funktion y ↦ σ_{α} ∗ y für y ∈ ω^{ω} injektiv ist, gilt \overline{\overline{\{σ_{α} ∗ y | y ∈ ω^{ω}\}}} = 2^{ℵ_{0}} > \overline{\overline{\{a_{β} | β < α\}}}. Es existiert also stets ein derartiges y_{α} bzw. aus analogen Gründen ein derartiges x_{α}. Aufgrund der Definitionen sind die so konstruierten Mengen A :≡ {a_{α} | α < 2^{ℵ_{0}}} und B :≡ {b_{α} | α < 2^{ℵ_{0}}} disjunkt. Das Spiel G(A) kann aber nicht determiniert sein, denn es gilt:

(1) Zu jeder Strategie σ für Spieler I existiert ein α < 2^{ℵ_{0}} mit σ_{α} = σ und ein Spielverlauf y_{α} ∈ ω^{ω} für Spieler II, so daß σ_{α}∗y_{α} ∉ A. Also ist σ keine Gewinnstrategie für Spieler I.

1Zur Erinnerung: Eine Menge A ⊆ X^{ω} heißt determiniert, wenn im zugehörigen Spiel G_{X}(A) einer der beiden Spieler eine Gewinnstrategie besitzt.

2Wie in der Deskriptiven Mengenlehre üblich, werden die reellen Zahlen ℝ mit dem nulldimensionalen Baire-Raum ω^{ω} identifiziert. Tatsächlich ist ω^{ω} aber nur homöomorph zu der Menge der irrationalen Zahlen 𝕀. Dies ist aber für fast alle Betrachtungen der Deskriptiven Mengenlehre unerheblich, da ℚ = ℝ\𝕀 abzählbar, also bzgl. des Lebesgue-Maßes eine Nullmenge und außerdem eine magere Menge ist. Darüber hinaus ist die Borel-Hierarchie auf ℝ und auf 𝕀 ab der dritten Stufe identisch.

(2) Zu jeder Strategie τ für Spieler II existiert ein α < 2^{ℵ_{0}} mit τ_{α} = τ und ein Spielverlauf x_{α} ∈ ω^{ω} für Spieler I, so daß x_{α} ∗τ_{α} ∈ A. Also ist τ keine Gewinnstrategie für Spieler II.

Der übliche Weg in der Mathematik wäre nun gewesen, in ZFC nach weiteren determinierten Mengen zu suchen und diese von den nicht-determinierten Mengen abzugrenzen. Statt dessen aber wählten die polnischen Mathematiker Jan Mycielski und Hugo Steinhaus 1962 einen diametral entgegengesetzten Weg: sie postulierten die Determiniertheit aller Teilmengen der reellen Zahlen in Form eines neuen Axioms, heute bekannt^{3} als das Axiom of Determinacy:

(1.2) Definition: AD :⟺ jede Menge A ⊆ ω^{ω} ist determiniert.

Mycielski und Steinhaus war die Unvereinbarkeit von AD mit AC bekannt. Tatsächlich trägt ihre Arbeit den Titel A mathematical axiom contradicting the axiom of choice [17]. Ihre Absicht war es aber nicht, eine ernsthafte Alternative zu ZFC anzugeben, sondern lediglich die Eigenschaften einer Theorie zu untersuchen, in der die bekannten ”pathologischen“ Konsequenzen des Auswahlaxioms - zumindest ad hoc - nicht mehr gegeben sind (z.B. das Banach-Tarski-Paradoxon^{4}).

AD ist ebenfalls eine Verallgemeinerung eines im Endlichen gültigen Sachverhalts, denn endliche Versionen der hier betrachteten Spiele sind determiniert (Zermelo 1927, von Neumann 1928). Allerdings unterscheidet sich die Art der Verallgemeinerung ins Unendliche gänzlich von derjenigen, die AC ausdrückt (vgl. [5]).

(1.3) Satz: (ZF + AD) ⊢ jede Menge A ⊆ ω^{ω} ist Lebesgue-meßbar, besitzt die Baire-Eigenschaft und die Perfekte-Mengen-Eigenschaft.

Beweis: Siehe das 2. Referat ”Determiniertheit und Regularitätseigenschaften“.

Die Lebesgue-Meßbarkeit von Mengen aus determinierten Punktklassen wurden von Jan Mycielski und Stanisław Swierczkowski 1964 gezeigt. Der Beweis der Baire-Eigenschaft solcher Mengen geht auf ein Spiel von Stanisław Mazur zurück. Stefan Banach hat einen Beweis 1935 gefunden, aber nie veröffentlicht. Der erste publizierte Beweis aus dem Jahr 1957 stammt von John Oxtoby. Die Perfekte-Mengen-Eigenschaft dieser Mengen wurde ebenfalls 1964 von Morton Davis bewiesen.

2 Konsequenzen aus AD

Unter AD muß man aber nicht ganz auf AC verzichten, denn es gilt eine abgeschwächte Form des Auswahlaxioms. Dazu die folgende

(2.1) Definition: (1) AC_{ω}(X) :⟺ jede abzählbare Familie nicht-leerer Teilmengen

von X besitzt eine Auswahlfunktion^{5}.

(2) AC_{ω} :⟺ ∀X (AC_{ω}(X)).

(2.2) Satz (Mycielski 1964): (ZF + AD) ⊢ AC_{ω}(ω^{ω}), d.h. jede abzählbare Familie von nicht-leeren Teilmengen der reellen Zahlen besitzt eine Auswahlfunktion.

Diese abgeschwächte Form des Auswahlaxioms genügt für viele wichtige Resultate der Analysis (z.B. die Äquivalenz von Stetigkeit und Folgenstetigkeit bei reellen Funktionen).

3In den frühen Schriften findet sich noch häufig der Begriff Determinateness. Seit den Siebzigern hat sich aber der Begriff Determinacy durchgesetzt.

4Das Paradoxon von Banach und Tarski besagt, daß in ZFC die Einheitssphäre in zwei disjunkte Teile zerlegt werden kann, die beide das Maß der Einheitssphäre haben. Dafür und für ähnliche Konstruktionen ist die Existenz einer nicht-Lebesgue-meßbaren Menge verantwortlich. In der Welt von AD sind nach Satz (1.3) aber alle Mengen Lebesgue-meßbar.

5Zur Erinnerung: Ist {A_{i} | i ∈ I} ⊆ X eine Familie nicht-leerer Teilmengen von X, dann ist f : {A_{i} | i ∈ I} → ⋃_{i∈I} A_{i} eine Auswahlfunktion, falls ∀i ∈ I (f(A_{i}) ∈ A_{i}) gilt.

Beweis: Als Beweis konstruieren wir ein Spiel, bei dem Spieler I im ersten Zug die Menge nennt, aus der ausgewählt werden soll. Spieler II muß dann versuchen, durch sein Spiel ein Element dieser Menge zu konstruieren. Aus der Determiniertheit des Spiels folgt, daß Spieler II eine Gewinnstrategie haben muß und damit haben wir die gewünschte Auswahl. Sei also X = {X_{n} | n ∈ ω} eine Familie nicht-leerer Teilmengen von ω^{ω}. Definiere A :≡ {x ∈ ω^{ω} | x_{II} ∉ X_{x(0)}}, d.h. Spieler I gewinnt das Spiel G_{ω}(A), wenn Spieler II kein Element aus der durch den ersten Zug von I festgelegten Menge X_{x(0)} spielen kann. Aber Spieler II kann auf jeden Fall nach und nach ein Element der nicht-leeren Menge X_{x(0)} konstruieren und damit die Partie gewinnen, d.h. Spieler I kann keine Gewinnstrategie besitzen. Da aber AD gilt, muß demnach Spieler II eine Gewinnstrategie τ besitzen, d.h. es gilt: ∀x ∈ ω^{ω} ((x ∗ τ)_{II} ∈ X_{x(0)}). Durch diese Strategie τ ist also eine Auswahlfunktion durch

f : X → ⋃_{n∈ω} X_{n}; X_{n} ↦ ((n, 0, 0, 0, …) ∗ τ)_{II}

gegeben.

Eine weitere angenehme, aber nicht selbstverständliche Tatsache ist, daß die Regularität von ℵ_{1} in ZF + AD erhalten bleibt. Um dies zeigen zu können, benötigen wir die folgenden Aussagen:

(2.3) Proposition: Äquivalent sind:

(1) AC_{ω}(ω^{ω})

(2) für jede Menge X gilt: wenn eine surjektive Abbildung f : ω^{ω} → X existiert, dann gilt AC_{ω}(X).

Beweis: (1) ⇒ (2) : Sei X eine Menge, f : ω^{ω} → X eine surjektive Abbildung und {X_{n} | n ∈ ω} eine abzählbare Familie nicht-leerer Teilmengen von X. Aufgrund der Surjektivität von f ist {f^{−1}[X_{n}] | n ∈ ω} eine abzählbare Familie nicht-leerer Teilmengen von ω^{ω}. Wegen AC_{ω}(ω^{ω}) existiert also eine Auswahlfunktion

g : {f^{−1}[X_{n}] | n ∈ ω} ⟶ ⋃_{n∈ω} f^{−1}[X_{n}] mit ∀n ∈ ω ( g(f^{−1}[X_{n}]) ∈ f^{−1}[X_{n}] ).

Daraus folgt:

∀n ∈ ω (f (g(f^{−1}[X_{n}])) ∈ f [f^{−1}[X_{n}]] ⊆ X_{n}).

Durch

h : {X_{n} | n ∈ ω} ⟶ ⋃_{n∈ω} X_{n}; h(X_{n}) :≡ f (g(f^{−1}[X_{n}]))

ist also die gewünschte Auswahlfunktion definiert.

(2) ⇒ (1) : Wähle einfach f :≡ Id_{ω^{ω}}.

(2.4) Proposition: (ZF+AC_{ω}(ω^{ω})) ⊢ es existiert eine surjektive Abbildung f : ω^{ω} → ω_{1}^{ω}.

Beweis: Sei f_{1} : ω × ω → ω eine Bijektion [Satz von Hessenberg]. Für n, m ∈ ω und x ∈ ω^{ω} sei (x)_{n}(m) :≡ x(f_{1}(n, m)). Wir können mit Hilfe von (x)_{n} abzählbare Teilmengen von ω^{ω} durch ein Element von ω^{ω} kodieren, d.h. die Abbildung f_{2} : ω^{ω} → (ω^{ω})^{ω}; x ↦ ((x)_{n} | n ∈ ω) ist bijektiv. Wir können ebenfalls die ”Informationen“ einer abzählbaren Ordinalzahl durch ein Element von ω^{ω} kodieren, d.h. es existiert eine surjektive Abbildung f_{3} : ω^{ω} → ω_{1}. Definiere nun die Abbildung

f : ω^{ω} → ω_{1}^{ω}; x ↦ (f_{3}((x)_{n}) | n ∈ ω).

Es bleibt zu zeigen, daß f surjektiv ist. Sei dazu (α_{n} | n ∈ ω) ∈ ω_{1}^{ω}. Wegen der Surjektivität von f_{3} ist {f_{3}^{−1}[{α_{n}}] | n ∈ ω} eine abzählbare Familie nicht-leerer Teilmengen von ω^{ω}. Mit AC_{ω}(ω^{ω}) wählen wir nun für alle n ∈ ω ein x_{n} ∈ f_{3}^{−1}[{α_{n}}]. Da f_{2} surjektiv ist, existiert zu der Folge (x_{n} | n ∈ ω) ∈ (ω^{ω})^{ω} ein x ∈ ω^{ω} mit ∀n ∈ ω ((x)_{n} = x_{n}). Damit gilt:

f(x) = (f_{3}((x)_{n}) | n ∈ ω) = (f_{3}(x_{n}) | n ∈ ω) = (α_{n} | n ∈ ω).

Also ist f surjektiv.

Aus den beiden Propositionen folgt das

(2.5) Korollar: AC_{ω}(ω^{ω}) ⟶ AC_{ω}(ω_{1}^{ω}).

(2.6) Satz: (ZF + AC_{ω}(ω^{ω})) ⊢ ℵ_{1} ist regulär.

Beweis: Angenommen, ℵ_{1} wäre singulär. Dann existieren Teilmengen A_{n} ⊆ ω_{1} mit ∀n ∈ ω (\overline{\overline{A_{n}}} ≤ ℵ_{0}) und ℵ_{1} = ⋃_{n∈ω} A_{n}. Für jedes n ∈ ω ist die Menge der Abzählungen von A_{n} eine Teilmenge von A_{n}^{ω} ⊆ ω_{1}^{ω}. Mit Hilfe von AC_{ω}(ω_{1}^{ω}) wählen wir nun für alle n ∈ ω eine Abzählung von A_{n}. Damit wäre aber auch ℵ_{1} = ⋃_{n∈ω} A_{n} als abzählbare Vereinigung abzählbarer Mengen selbst abzählbar^{6}. Widerspruch, denn ℵ_{1} ist auch in dieser Situation als kleinste nicht abzählbare Kardinalzahl definiert.

(2.7) Satz (Mycielski 1964): (ZF+AD) ⊢ ω_{1} ≰ 2^{ℵ_{0}}, d.h. es existiert keine überabzählbare, wohlordenbare Menge reeller Zahlen^{7}.

Beweis: Wir werden zeigen, daß bei der gegenteiligen Annahme eine Teilmenge der reellen Zahlen existiert, die nicht die Perfekte-Mengen-Eigenschaft besitzt, also weder abzählbar ist noch eine perfekte Teilmenge enthält. Das steht aber im Widerspruch zu Satz (1.3). Angenommen also, es gilt ω_{1} ≤ 2^{ℵ_{0}} (⋆). Wir machen eine Fallunterscheidung. Fall (i): Es gilt zusätzlich 2^{ℵ_{0}} ≰ ω_{1}. In ZF besitzt jede perfekte Teilmenge der reellen Zahlen die Kardinalität 2^{ℵ_{0}} (Cantor 1884). Wegen unserer zusätzlichen Annahme gibt es demnach keine perfekte Teilmenge in einer überabzählbaren, wohlordenbaren Menge. Da aber wegen (⋆) eine überabzählbare, wohlordenbare Menge reeller Zahlen existiert, kann diese Menge also nicht die Perfekte-Mengen-Eigenschaft besitzen. Fall (ii): Es gilt zusätzlich 2^{ℵ_{0}} ≤ ω_{1}, dann wäre nach dem Satz von Cantor-Bernstein ω^{ω} bijektiv abbildbar auf ω_{1} und damit die reellen Zahlen wohlordenbar. Dann existiert aber in ZF eine Teilmenge A ⊆ ω^{ω} der Kardinalität 2^{ℵ_{0}}, so daß für jede perfekte Menge P ⊆ ω^{ω} gilt: P ∩ A ≠ ∅ und P \ A ≠ ∅ (Bernstein 1908). Also ist weder A abzählbar, noch enthält A eine perfekte Teilmenge.

(2.8) Satz (Mycielski 1964): Kon(ZF + AD) ⟶ Kon(ZFC + ∃κ (κ ist unerreichbar)).

Beweis: Der Beweis besteht aus mehreren Teilen:

(1) ω_{1} ≰ 2^{ℵ_{0}} ⟶ ∀a ∈ ω^{ω} (ω_{1}^{L[a]} < ω_{1}). Beweis: Wie führen einen Widerspruchsbeweis. Sei a ∈ ω^{ω} gegeben. Da L[a] ein inneres ZFC-Modell^{8} ist, gilt ω_{1}^{L[a]} ≤ ω_{1}. Außerdem erfüllt L[a] die GCH (Beweis analog zu L), d.h. es gilt (2^{ℵ_{0}})^{L[a]} = ℵ_{1}^{L[a]}. Somit besitzt P(ω)^{L[a]} = P(ω)∩L[a] eine Wohlordnung in L[a] mit

Ordnungstyp ω_{1}^{L[a]}. Wäre nun ω_{1}^{L[a]} = ω_{1}, dann würde gelten: ω_{1} = ω_{1}^{L[a]} = (2^{ℵ_{0}})^{L[a]} ≤ 2^{ℵ_{0}}, also ω_{1} ≤ 2^{ℵ_{0}}.

(2) (ZF + ω_{1} ist regulär + ∀a ∈ ω^{ω} (ω_{1}^{L[a]} < ω_{1})) ⊢ ∀a ∈ ω^{ω} (ω_{1} ist unerreichbar in L[a]). Beweis: Angenommen, es gibt ein a ∈ ω^{ω}, so daß ω_{1} nicht unerreichbar in L[a] ist. ω_{1} ist nach Voraus. in V regulär und damit auch in L[a] (”κ ist regulär“ ist abwärts-absolut). Wegen (GCH)^{L[a]} gilt für Lim(κ): λ < κ → 2^{λ} = λ^{+} < κ. Also muß ω_{1} Nachfolgerkardinalzahl in L[a] sein: ω_{1} = (α^{+})^{L[a]}. Da α abzählbar (in V) ist, existiert ein b ∈ ω^{ω}, so daß α abzählbar in L[b] ist (wähle z.B. die Kodierung b einer Wohlordnung von ω mit Ordnungstyp α m.H. der Funktion f_{3} in (2.4). Es gilt b ∈ L[b]). Sei nun c ∈ ω^{ω} so gewählt, daß c sowohl a als auch b durch Operationen in L kodiert (z.B. c :≡ a∗b). Dann kann b in L[c] wieder dekodiert werden, also gilt b ∈ L[c] und daraus folgt, daß α in L[c] ebenfalls abzählbar ist. Analog gilt a ∈ L[c] und damit L[a] ⊆ L[c]. Angenommen, es existiert eine Kardinalzahl β in L[c], so daß α < β < ω_{1} gilt. Dann wäre β auch eine Kardinalzahl in L[a] (Kardinalzahl zu sein ist abwärts-absolut) im Widerspruch zu der Annahme, daß ω_{1} der Nachfolger von α in L[a] ist. Also kann in L[c] keine Kardinalzahl zwischen dem abzählbaren α und ω_{1} existieren, d.h. es gilt: ω_{1}^{L[c]} = ω_{1}.

6Dieses Argument kann erst angewandt werden, wenn man für jedes A_{n} eine konkrete Abzählung auswählen kann. Es reicht nicht, ”nur“ zu wissen, daß jedes A_{n} abzählbar ist. Für diese Wahl ist das Auswahlaxiom - zumindest in abgeschwächter Form - notwendig.

7Ohne AC ist der Vergleich zweier Kardinalzahlen nicht unproblematisch, da nicht jede Menge wohlordenbar ist. So ist z.B. gar nicht klar, ob 2^{ℵ_{0}} überhaupt eine Kardinalzahl ist. Es muß also zwischen ”Kardinalzahl“ und ”Kardinalität“ unterschieden werden. Hier wird κ ≤ λ in dem Sinne verwendet, daß eine injektive Einbettung von κ nach λ existiert.

8Zur Definition und Eigenschaften der Klasse L[a] der relativ zu a konstruktiblen Mengen vergleiche [8] und [14].

(3) (ZF + ω_{1} ist regulär + ∀a ∈ ω^{ω} (ω_{1}^{L[a]} < ω_{1})) ⊢ ∃κ (κ ist unerreichbar)^{L[a]}.

Außerdem gilt ZF ⊢ (AC)^{L[a]} (Beweis analog zu L).

(4) Wegen (3.2) und (2.7) folgt also insgesamt:

Kon(ZF + AD) ⟶ Kon (ZFC + ∃κ (κ ist unerreichbar)) .

3 Erweiterungen von AD

Eine Erweiterung von AD wurde 1966 ebenfalls von Mycielski eingeführt:

(3.1) Definition: AD_{ℝ} :⟺ das Spiel G_{ω^{ω}}(A) ist determiniert für jede Menge A ⊆ (ω^{ω})^{ω}.

Im Gegensatz zu den Spielen G_{ω}(A), in denen die Spieler abwechselnd ω natürliche Zahlen spielen, werden im Spiel G_{ω^{ω}}(A) abwechselnd ω reelle Zahlen gespielt. Offensichtlich gilt: AD_{ℝ} → AD, d.h. AD_{ℝ} ist eine Erweiterung von AD. Auf die Frage, ob AD_{ℝ} tatsächlich eine stärkere Bedingung als AD ist, wird weiter unten noch einmal eingegangen. Für AD_{ℝ} gilt eine analoge Abschwächung des Auswahlaxioms: AC_{ω^{ω}}(ω^{ω}), d.h. jede ω^{ω}-indizierte Familie nicht-leerer Teilmengen der reellen Zahlen besitzt eine Auswahlfunktion.

Die Spiele G_{α}(A) für eine abzählbare Ordinalzahl α lassen sich mit Hilfe einer Bijektion auf das Spiel G_{ω}(A) zurückführen, so daß die Forderung AD_{α} für ein α < ω_{1} nichts neues ergibt. Jede andere Erweiterung von AD im Sinne AD_{X} für ein überabzählbares, wohlordenbares X - also die Forderung, daß das Spiel G_{X}(A) für alle A ⊆ X^{ω} determiniert ist - ist aber schon inkonsistent mit ZF:

(3.2) Satz (Mycielski 1964): ZF ⊢ es existiert eine Menge A ⊆ ω_{1}^{ω}, so daß G_{ω_{1}}(A) nicht determiniert ist.

Beweis: Man kann o.E. annehmen, daß AD gilt: ist AD falsch, so existiert nach Definition ein Menge A ⊆ ω^{ω} ⊆ ω_{1}^{ω}, die nicht determiniert ist. Sei nun A ⊆ ω_{1}^{ω} wie folgt definiert: x ∈ A ⇔ x(0) ≥ ω und x_{II} ist keine bijektive Aufzählung von x(0) = {ξ | ξ < x(0)}, d.h.: sind ⟨x(1), x(3), x(5), … ⟩ die Züge von Spieler II, dann ist f : {x(1), x(3), x(5), … } → {ξ | ξ < x(0)} keine Bijektion. Angenommen, G_{ω_{1}}(A) ist determiniert. Da x(0) < ω_{1} abzählbar ist und Spieler I nach seinem ersten Zug keinen Einfluß mehr auf den Verlauf des Spiels hat, muß es Spieler II sein, der eine Gewinnstrategie τ besitzen, d.h. x_{II} ist dann eine bijektive Aufzählung von x(0). Für jedes x ∈ ω_{1}^{ω} mit x(0) ≥ ω ist dann {(m, n) | m, n ∈ ω ∧ x ∗ τ(2m + 1) < x ∗ τ(2n + 1)} ⊆ ω × ω eine Wohlordnung vom Ordnungstyp z(0). M.a.W. finden wir für jedes α ∈ ω_{1} - falls Spieler I α in seinem ersten Zug spielt - über die Strategie τ eine Wohlordnung vom Ordnungstyp α. Diese Wohlordnungen mit abzählbaren Ordnungstyp können wir als reelle Zahl kodieren. Mit Hilfe von τ und dieser Kodierung erhalten wir also eine Injektion ω_{1} → ω^{ω}, d.h. es existiert eine überabzählbare, wohlordenbare Menge reeller Zahlen im Widerspruch zu Satz (2.7). Also kann G_{ω_{1}}(A) nicht determiniert sein.

In diesem Beweis ist zu erkennen, daß sich AD in bestimmten Situationen wie ein Auswahlprinzip verhält: über ein Spiel gelangen wir zu einer Wohlordnung. Dabei wurde in dem Beweis keinesfalls eine ”konkrete“ nicht-determinierte Menge angegeben, in diesem Sinne ist der Beweis also inkonstruktibel.

AD_{ℝ} wird aber durch diesen Satz nicht erfaßt, da die reellen Zahlen aufgrund von Satz (2.7) nicht wohlordenbar sind.

Frage: Wie sieht es mit AD_{P(ℝ)}, AD_{P(P(ℝ))} usw. aus? Sind diese Forderungen auch schon inkonsistent mit ZF? Diese werden ebenfalls nicht durch den obigen Satz abgedeckt, da auch P(ℝ), P(P(ℝ)) usw. nicht wohlordenbar sind [aus einer Wohlordnung von P(X) läßt sich natürlich eine für X gewinnen]. Und wenn sie nicht schon inkonsistent mit ZF sind, werden es dann auch immer stärkere Forderungen?

In seinem Artikel [22] bewies Solovay, daß AD_{ℝ} eine stärkere Behauptung als AD ist, indem er zeigte, daß

(ZF + AD_{ℝ}) ⊢ Kon(ZF + AD)

gilt. Daraus folgt nach Gödels zweitem Unvollständigkeitssatz: wenn ZF + AD konsistent ist, dann kann aus ZF + AD nicht AD_{ℝ} gefolgert werden. Ein Ansatz für die letzte der oben genannten Frage wäre es nun, diesen Beweis für AD_{P(ℝ)} zu verallgemeinern.

Versucht man andererseits, die Beschreibung der Spiele zu erweitern, so kann man bei den hier betrachteten Zwei-Personen-Nullsummen-Spielen mit perfekter Information drei verschiedene Parameter verändern: die Komplexität der Auszahlungsmenge, die Komplexität der einzelnen Züge und die Länge des Spiels.

Der Komplexität der Auszahlungsmenge ist in ZFC beim Spiel G_{ω}(A) eine Grenze gesetzt: wir haben schon gesehen, daß Δ_{1}^{1} die letzte Stufe der projektiven Hierarchie ist, von deren Elementen wir direkt beweisen können, daß sie determiniert sind. Für die Determiniertheit der Elemente der höheren Stufen sind weitere Reichhaltigkeitsannahmen (z.B. ”es existiert eine meßbare Kardinalzahl“) notwendig.

Einige Autoren haben sich mit Spielen mit einer größeren Länge beschäftigt. G_{X}^{α}(A) ist dann das Spiel, bei dem die Spieler abwechselnd Elemente von X spielen, so daß eine Folge der Länge α entsteht. AD_{X}^{α} wird dann entsprechend definiert. Nun konnte aber Mycielski und Blass zeigen, daß der Länge der Spiele durch ω_{1} eine Grenze gesetzt ist:

(3.3) Satz: AD_{ω}^{ω_{1}} ist inkonsistent mit ZF.

Beweisskizze: Es genügt zu zeigen, daß AD_{ω}^{ω_{1}} ⟶ AD_{ω_{1}}^{ω} gilt, denn dann kann der Satz (3.2) angewendet werden. Um ein Spiel G_{ω_{1}}^{ω} zu einem Spiel G_{ω}^{ω_{1}} zu machen, kann man folgenden Trick anwenden: da die Spieler im letzteren Spiel insgesamt ω_{1} Züge zur Verfügung haben, kann jeder Spieler in seinem Spielverlauf ω abzählbare Ordinalzahlen hintereinander kodieren. Um z.B. α < ω_{1} zu kodieren, kann ein Spieler α-mal die 0 und dann eine 1 spielen. Auf diese Weise kann jeder Spieler ω-oft hintereinander ein α < ω_{1} kodiert spielen, so daß alle ω Züge des ersten Spiels erfaßt werden. M.a.W. wird das Spiel der Länge ω und Zügen aus ω_{1} auf ein Spiel (mit bestimmten Regeln) der Länge ω_{1} mit Zügen aus ω zurückgeführt. Die Regeln dieses Spiels können dann wie üblich aufgelöst werden, so daß aus der Dererminiertheit des längeren Spiels die des kürzeren folgt.

Ein anderes interessantes Ergebnis stammt ebenfalls von Andreas Blass (siehe [2]): AD_{ℝ} ist äquivalent zu AD^{ω^{2}}, also zu der Forderung, daß für alle A ⊆ (ω)^{ω^{2}} die Spiele G_{ω}^{ω^{2}}(A) der Länge ω^{2} determiniert sind.

Zu weiteren Aspekten von ”langen“ Spielen siehe [2], [19] und [23].

4 Algebraische und topologische Konsequenzen aus AD

Es folgen - ohne Beweise - einige Konsequenzen aus AD für die Algebra und die Topologie:

(1) Es existiert ein Vektorraum ohne Basis (Blass 1984).

(2) Es existiert eine Menge ohne Gruppenstruktur (Hajnal-Kertesz 1972).

(3) Es existiert ein ZPE-Ring ohne echtes maximales Ideal (Hodges 1979).

(4) Es existiert eine Familie quasikompakter Räume, deren Produkt nicht quasikompakt ist.

(5) Das Hahn-Banach-Theorem ist falsch (Foreman-Wehrung 1991).

(6) Es existiert keine nicht-triviale Zerlegung der additiven Gruppe ⟨ℝ, +⟩ in direkte Summanden, d.h. ∀S, T ◁ ℝ (S ⊕ T = ℝ ⟶ S = ℝ ∨ T = ℝ) (Felgner-Schulz 1984). Insbesondere besitzt der ℚ-Vektorraum ℝ keine Basis.

Die gegenteiligen Aussagen der Behauptungen (1) bis (4) sind nämlich mit AC äquivalent und aus dem Hahn-Banach-Theorem folgt die Existenz einer nicht-Lebesgue-meßbaren Menge. Eine ausführliche Darstellung und die Beweise finden sich in [21], [6] und [5]. Diese Ergebnisse belegen, warum ZF + AD nie ernsthaft als Alternative zu ZFC angesehen wurde.

5 Ein Modell für ZF + AD

Mycielski stellte 1964 die Frage nach einem inneren Modell für ZF + AD. Solovay und Takeuti bemerkten dazu, daß die ”kanonische“ Möglichkeit für ein Modell L(ℝ) darstellt. L(ℝ) erhält man durch eine analoge Konstruktion der Gödel-Hierarchie, nur beginnt man statt mit der leeren Menge mit der transitiven Hülle der reellen Zahlen:

L_{0}(ℝ) :≡ TC({ℝ})
L_{α+1}(ℝ) :≡ Def(L_{α}(ℝ))
L_{λ}(ℝ) :≡ ⋃_{α<λ} L_{α}(ℝ) für Lim(λ)
L(ℝ) :≡ ⋃_{α∈On} L_{α}(ℝ)

Dies ist das kleinste innere Modell, das jede reelle Zahl (aus V) enthält. Wenn AD gilt, dann auch AD^{L(ℝ)}, denn jede Strategie kann durch eine reelle Zahl kodiert werden und ist damit in L(ℝ) enthalten. Außerdem ist die Eigenschaft, eine Gewinnstrategie für das Spiel G_{ω}(A) mit A ∈ L(ℝ) zu sein absolut für L(ℝ).

Wir haben gesehen, daß aus AD eine abzählbare Version des Auswahlaxioms folgt [Satz (2.2)]. Kechris konnte 1984 zeigen, daß unter der Annahme von AD in dem ”natürlichen“ Modell L(ℝ) auch das stärkere Axiom of Dependent Choice DC gilt. Dieses Axiom wurde 1942 von Paul Bernays eingeführt:

(5.1) Definition: DC :⟺ ∀X∀R (X ≠ ∅ ∧ R ⊆ X × X ∧ ∀x ∈ X∃y ∈ X ((x, y) ∈ R)

⟶ ∃f ∈ X^{ω}∀n ∈ ω ((f(n), f(n + 1)) ∈ R)).

(5.2) Satz (Kechris 1984): AD ⟶ L(ℝ) ⊧ AD + DC.

Aus dem Satz folgt: Kon(ZF+AD) ⟶ Kon(ZF+AD+DC). Andererseits konnte Woodin zeigen, daß Kon(ZF + AD) ⟶ Kon(ZF + AD + ¬AC_{ω}) gilt. Da aber AC_{ω} aus DC folgt, bedeutet dieses Resultat auch: Kon(ZF + AD) ⟶ Kon(ZF + AD + ¬DC), d.h. DC ist unabhängig von ZF + AD.

Ein Resultat von Martin-Steel-Woodin aus dem Jahre 1985 zeigt die Verbindung von AD zu der Existenz gewisser großer Kardinalzahlen und bestimmt die Konsistenzstärke von AD (vgl. [9], 32.16):

Kon(ZF + AD) ⟷ Kon(ZFC + es existieren unendlich viele Woodin-Kardinalzahlen).

Literatur

[1] Bernstein, F.: Zur Theorie der trigonometrischen Reihen. Berichte über die Verhandlungen der Königlich Sächsischen Gesellschaft der Wissenschaften zu Leipzig 60 (1908). S. 325-338.

[2] Blass, A.: The Equivalence of Two Strong Forms of Determinacy. Proccedings of AMS 52 (1975). S. 373-376.

[3] Cantor, G.: De la puissance des ensembles parfaits de points. Acta Mathematica 4 (1884). S. 381-392.

[4] Davis, M.: Infinite Games of Perfect Information. In: Dresher, M.; Shapley, L. S.; Tucker, A. W. (Hrsg.): Advances in Game Theory. Annals of Mathematical Studies, Nr. 52. Princeton University Press, Princeton 1964. S. 85-101.

[5] Felgner, U.; Schulz, K.: Algebraische Konsequenzen des Determiniertheits-Axioms. Archiv der Mathematik 42 (1984). S. 557-563.

[6] Foreman, M.; Wehrung, F.: The Hahn-Banach Theorem implies the Existence of a non-Lebesgue measurable Set. Fundamenta Mathematicae 138 (1991). S. 13-19.

[7] Gale, D.; Stewart, F. M.: Infinite Games with Perfect Information. In: Kuhn, H. W.; Tucker, A. W. (Hrsg.): Constributions to the Theory of Games, Vol. 2. Annals of Mathematical Studies, Nr. 28. Princeton University Press, Princeton 1953. S. 245-266.

[8] Jech, T.: Set Theory. 2. Ausgabe. Perspectives in Mathematical Logic. Springer, Berlin 1997.

[9] Kanamori, A.: The Higher Infinite. Perspectives in Mathematical Logic. Springer, Berlin 1997.

[10] Kechris, A. S.: The Axiom of Determinacy implies Dependent Choices in L(ℝ). Journal of Symbolic Logic 49 (1984). S. 161-173.

[11] Kechris, A. S.; Solovay, R. M.: On the Relative Consistency of Strenght of Determinacy Hypotheses. Transactions of the American Mathematical Society 290 (1985). S. 179-211.

[12] Martin, D. A.: Borel Determinacy. Annals of Mathematics 102 (1975). S. 363-371.

[13] Martin, D. A.; Steel, J. R.: A Proof of Projective Determinacy. Journal of the American Mathematical Society 2 (1989). S. 71-125.

[14] Moschovakis, Y. N.: Descriptive Set Theory. North-Holland, Amsterdam 1980.

[15] Mycielski, J.: On the Axiom of Determinateness. Fundamenta Mathematicae 53 (1964). S. 205-224.

[16] : On the Axiom of Determinateness II. Fundamenta Mathematicae 59 (1966). S. 203-212.

[17] Mycielski, J.; Steinhaus, H.: A Mathematical Axiom contradicting the Axiom of Choice. Bulletin de l’Academie Polonaise des Sciences X (1962). S. 1-3.

[18] Mycielski, J.; Swierczkowski, S.: On the Lebesgue Measurability and the Axiom of Determinateness. Fundamenta Mathematicae 54 (1964). S. 67-71.

[19] Neeman, I.: Games of Countable Length. In: Cooper, S. B.; Truss, J. K. (Hrsg.): Sets and Proofs. Cambridge University Press 1999.

[20] Oxtoby, J. C.: The Banach-Mazur game and Banach Category Theorem. In: Dresher, M.; Tucker, A.; Wolfe, P. (Hrsg.): Constributions to the Theory of Games, Vol. 3. Annals of Mathematical Studies, Nr. 39. Princeton University Press, Princeton 1957. S. 159-163.

[21] Rubin, H.; Rubin, J. E.: Equivalences of the Axiom of Choice, Vol. II. Studies in Logic and the Foundations of Mathematics, Nr. 116. North-Holland, Amsterdam 1985.

[22] Solovay, R. M.: The Independence of DC from AD. In: Kechris, A. S.; Moschovakis, Y. N. (Hrsg.): Cabal Seminar 76-77. Lecture Notes in Mathematics, Nr. 689. Springer, Berlin 1978. S. 171-184.

[23] Steel, J. R.: Long Games. In: Kechris, A. S.; Martin, D. A.; Steel, J. R. (Hrsg.): Cabal Seminar 81-85. Lecture Notes in Mathematics, Nr. 1333. Springer, Berlin 1988. S. 56-97.

[24] Steinwand, H.: Konsequenzen aus dem Axiom der Determiniertheit. Diplomarbeit: Universität Tübingen, Mathematische Fakultät, Tübingen 1998.

[25] von Neumann, J.: Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100 (1928). S. 295-320.

[26] Wolfe, P.: The Strict Determinateness of Certain Infinite Games. Pacific Journal of Mathematics 5 (1955). S. 841-847.

[27] Zermelo, E.: Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. Proceedings of the Fifth Int. Congress of Mathematicians. Cambridge University Press, Cambridge 1913. S. 501-504.