Seminarvortrag^{∗} über Π_{1}^{1}-Determiniertheit

Michael Bruening Thoralf Räsch Humboldt-Universität zu Berlin

16.Februar 1999

1 Einführung

Determiniertheit von unendlichen Spielen hat Konsequenzen, die auch außerhalb der Mengenlehre von Interesse sind. Sie impliziert gewünschte Regularitätseigenschaften, wie die Lebesgue-Meßbarkeit, die Eigenschaft von Baire und die perfekte Mengen Eigenschaft.

Wir wissen schon dank Gale und Stewart, daß abgeschlossene Spiele determiniert sind. Wir können sogar einen (oder besser gesagt ω_{1}-viele) Schritte weiter gehen und uns überlegen, daß auch Borel-Spiele determiniert sind. Der Grundgedanke des Beweises ist dem folgenden sehr ähnlich; man konstruiert nämlich ein abgeschlossenes Hilfsspiel und nutzt dessen Determiniertheit aus. Aber wie kompliziert darf ein Spiel werden, ohne die Determiniertheitseigenschaft zu verlieren? Wenn wir schon bei den Borel-Spielen sind, dann liegt es natürlich nahe zu fragen, wie es mit der nächsten Ebene in der Hierarchie aussieht: den analytischen Mengen. Äquivalent dazu können wir fragen, ob die co-analytischen Mengen determiniert sind, da Determiniertheit unter Komplementbildung invariant ist. Dieser Frage werden wir hier nachgehen.

Ist es zu erwarten, die Determiniertheit von Π_{1}^{1}-Mengen schon in ZF beweisen zu können? Schauen wir uns an, was wir schon wissen. Man kann zeigen, daß die Determiniertheit einer Stufe in der Hierarchie der Borel- bzw. projektiven Mengen immer die Eigenschaft von Baire in der nächsten Stufe impliziert. Nehmen wir einmal an, wir könnten die Determiniertheit der co-analytischen Mengen wirklich schon in ZF zeigen. Dann wären also die Σ_{2}^{1}-Mengen Baire-meßbar. Andererseits gibt es in L eine Σ_{2}^{1}-Wohlordnung der reellen Zahlen. Das liefert uns aber einen Widerspruch zu dem bekannten Satz von Kuratowski-Ulam.

Überlegen wir uns, was denn reichte, um auch hier die Determiniertheit zu bekommen. Wir werden daher das folgende Theorem zeigen:

Theorem (Martin 1970) Wenn eine meßbare Kardinalzahl existiert, dann sind alle Π_{1}^{1}-Mengen determiniert.

2 M.Bruening, Th. Räsch: Vortrag - Π_{1}^{1}-Determiniertheit

Damit haben wir einen (ersten) sehr schönen Zusammenhang zwischen der Theorie der Großen Kardinalzahlen und der Deskriptiven Mengenlehre gefunden, die anfangs wenig miteinander zu tun haben schienen. Mit dem oben genannten Resultat von Martin haben wir eine Möglichkeit gefunden, zumindest das Problem der Π_{1}^{1}-Determiniertheit mit Hilfe der Theorie der Großen Kardinalzahlen abschätzen zu können. Aber ist Meßbarkeit die beste Abschätzung in dieser Hierarchie? Aufgrund des obigen Gegenbeispiels für L muss eine hinreichende Bedingung für Π_{1}^{1}- Determiniertheit mindestens V ≠ L implizieren; aber dafür reicht uns schon 0^{♯}. Und tatsächlich, Martin und Harrington haben (jeweils eine Richtung) gezeigt, daß die gleichzeitige Existenz der Sharps für alle reellen Zahlen äquivalent ist mit der Π_{1}^{1}-Determiniertheit.

∗Seminar Große Kardinalzahlen und Deskriptive Mengenlehre im WS 1998/99 unter Leitung von Herrn Dipl.-Math. Benedikt Löwe.

Wir werden zunächst ein Hilfsmittel definieren: die κ-homogenen Bäume. Mit deren Hilfe wird es uns möglich sein, unser Ziel in zwei Teilschritten zu erreichen. Wir werden im Lemma 4.1 zeigen, daß für eine co-analytische Menge eine Suslin-Darstellung existiert mit Hilfe eines Baumes, der sich als κ-homogen entpuppen wird für ein meßbares κ. Das Lemma 3.1 wird dann die Determiniertheit dieser Menge sichern.

In Abschnitt 5 werden wir das Resultat noch wie folgt verfeinern.

Theorem (Martin) Für alle reellen Zahlen a ∈ ^{ω}ω impliziert die Existenz von a^{♯} die Determiniertheit von Π_{1}^{1}(a)-Mengen.

2 Grundlagen

In diesem Abschnitt fassen wir einige bekannte Tatsachen zusammen, die wir zwar benutzen werden, aber nicht beweisen wollen. Beweise findet man in der Standard-Literatur zu diesem Thema, etwa in [Ka], [Mo] und [Ke].

Für einen Baum T auf ω × κ sei

T_{s} := {u ∈ ^{lh(s)}κ | ⟨s, u⟩ ∈ T } für s ∈ ^{<ω}ω
T_{(x)} := {u ∈ ^{<ω}κ | ⟨x ↾ lh(u), u⟩ ∈ T } für x ∈ ^{ω}ω.

Definition 2.1 Eine Menge A ist κ-Suslin, wenn ein Baum T auf ω × κ existiert, so daß A = p[T] gilt.

Lemma 2.2 Eine Teilmenge A des Baireschen Raumes ist genau dann abgeschlossen, wenn ein Baum T auf ω mit A = [T] existiert.

Korollar 2.3 Wenn A eine analytische Menge ist, dann existiert ein Baum T auf ω × ω mit A = p[T].

Lemma 2.4 Sei G ein Spiel mit der Eigenschaft, daß wenn einer der beiden Spieler verliert, das schon zu einem endlichen Zeitpunkt feststeht. Dann ist G determiniert.

Korollar 2.5 (Gale, Stewart 1953) Abgeschlossene Spiele sind determiniert.

Lemma 2.6 Sei Γ eine beliebige Stufe in der Hierarchie der Borel- bzw. projektiven Mengen. Dann ist Γ genau dann determiniert, wenn ¬Γ determiniert ist. Dabei bezeichnet ¬Γ die Menge der Komplemente von Mengen aus Γ.

Theorem 2.7 (Rowbottom 1964) Sei U ein normaler Ultrafilter auf κ und f : [κ]^{<ω} ⟶ γ für ein γ < κ. Dann gibt es ein A ∈ U, das für f homogen ist.

Theorem 2.8 (Absolutheitslemma von Shoenfield) Für alle a ∈ ^{ω}ω ist jede Σ_{2}^{1}(a) – und damit auch jede Π_{2}^{1} – Relation für transitive Modelle von ZF+DC, die alle Ordinalzahlen und a enthalten, absolut.

Zunächst bringen wir die dem Beweis zugrunde liegende Definition.

Definition 2.9 (κ-homogene Bäume) Sei κ eine Kardinalzahl und T ein Baum auf ω × κ. Dann heißt ⟨T, ⟨U_{s} | T_{s} ≠ ∅, s ∈ ^{<ω}ω⟩⟩ ein κ-homogener Baum, falls folgende Eigenschaften erfüllt sind:

(a) U_{s} ist ein ω_{1}-vollständiges Maß auf T_{s} für T_{s} ≠ ∅.

(b) Falls s ⊆ t, beide Element von ^{<ω}ω, dann ist U_{s} die Projektion von U_{t}, d.h.

X ∈ U_{s} ⟷ {u ∈ T_{t} | u ↾ lh(s) ∈ X} ∈ U_{t}

(c) Falls x ∈ p[T], dann ist ⟨U_{x↾n} |n < ω⟩ abzählbar vollständig, d.h. für ⟨X_{n} |n < ω⟩ ∈ ∏_{n<ω} U_{x↾n} existiert ein d ∈ ^{ω}κ mit d ↾ n ∈ X_{n} für alle n.

Bemerkung 2.10 Eigentlich werden wir die Eigenschaft (b) nicht benutzen, obwohl wir sie trotzdem aus unserer Konstruktion bekommen werden. Sie wird aber in Verallgemeinerungen des Beweises benötigt, wo mit Ultraprodukten gearbeitet wird. Betrachten wir nun die Ultraprodukt-Einbettungen π_{s} : V ⟶ Ult(V, U_{s}).

Die Eigenschaft (b) verlangt eine gewisse Kohärenz der Ultrafilter, die uns Einbettungen σ_{s,t} für s ⊆ t liefert, die jeweils das folgende kommutative Diagramm erfüllen:

\xymatrix{V \ar[dr]_{π_{s}} \ar[rr]^{π_{t}} &  & Ult(V, U_{t}) \\  & Ult(V, U_{s}) \ar[ur]_{σ_{s,t}}}

Erst mit Eigenschaft (b) können wir dann den direkten Limes M_{x}^{∗} des gerichteten Systems bilden, gegeben durch einen unendlichen Zweig x ∈ ^{ω}ω in dem Baum ^{<ω}ω, nämlich

⟨⟨Ult(V, U_{x↾n}) | n < ω⟩, ⟨σ_{x↾m,x↾n} | m ≤ n⟩⟩,

so daß wir das folgende Bild erhalten:

\xymatrix{ &  & V \ar[d]_{π_{x↾n}} \ar[dr]_{π_{x↾(n+1)}} \ar[dll] \ar[drrr] \\ Ult(V, U_{∅}) \ar[r] & ⋯ \ar[r] & Ult(V, U_{x↾n}) \ar[r] & Ult(V, U_{x↾(n+1)}) \ar[r] & ⋯ \ar[r] & M_{x}^{∗}}

Die Bedingung (c) besagt dann gerade, daß M_{x}^{∗} für jede reelle Zahl x fundiert ist.

Definition 2.11 (homogen Suslin) Eine Teilmenge A ⊆ ^{ω}ω heißt κ-homogen Suslin, falls es einen κ-homogenen Baum ⟨T, ⟨U_{s} | T_{s} ≠ ∅, s ∈ ^{<ω}ω⟩⟩ gibt, so daß A = p[T]. Wir nennen A homogen Suslin, wenn es ein κ gibt, so daß A κ-homogen Suslin ist.

3 Determiniertheit homogener Suslin-Mengen

Wir beweisen in diesem Abschnitt das folgende

Lemma 3.1 Homogene Suslin-Mengen sind determiniert.

Beweis: Wir führen den Beweis direkt. Sei also A ⊆ ^{ω}ω gegeben. Wir betrachten

A, G nun das durch A gegebene Spiel G = G_{A},

Spiel G  I  x_{0}  x_{2}  ... II  x_{1}  ...

wobei Spieler I gewinnt, falls x ∈ A, und zeigen dessen Determiniertheit.

Die Idee des Beweises läßt sich kurz beschreiben. Wir werden zu unserem Spiel G ein abgeschlossenes und daher determiniertes Hilfsspiel G^{∗} definieren. Dann nutzen wir die für G^{∗} gegebene Gewinnstrategie, um eine Gewinnstrategie für den gleichen Spieler in G zu finden. Dabei werden wir Gebrauch von der homogenen Suslin-Darstellung von A machen. Wir gehen im Anschluß an dieses Lemma in der Bemerkung 3.2 darauf etwas näher ein.

T, U_{s} Sei also ⟨T, ⟨U_{s} |T_{s} ≠ ∅, s ∈ ^{<ω}ω⟩⟩ der nach Voraussetzung existierende κ-homogene Baum mit A = p[T].

G^{∗} Sei G^{∗} das folgende Spiel

Spiel G^{∗}  I^{∗}  ⟨x_{0}, y_{0}⟩  ⟨x_{2}, y_{1}⟩  ..._{II_{∗}}  x_{1}  ...

wobei Spieler I gewinnt, falls ⟨x, y⟩ ∈ [T].

Das Spiel G^{∗} stellt nun aber in Bezug auf Determiniertheit kein Problem dar, da die zu Grunde liegenden Menge gerade [T] ist und daher natürlich insbesondere abgeschlossen. Also erhalten wir mit dem Satz von Gale und Stewart:

G^{∗} ist determiniert.

Also existiert für einen Spieler eine Gewinnstrategie. Gehen wir die beiden Fälle durch.

σ^{∗} Fall 1: Spieler I^{∗} hat eine Gewinnstrategie σ^{∗} in G^{∗}.

σ Dann finden wir auch sofort eine Gewinnstrategie σ für den Spieler I in dem Spiel G. Dabei entstehe σ aus σ^{∗}, indem sich Spieler I genau an σ^{∗} orientiert und die für das Spiel G nicht benötigten Werte y_{i} einfach unter den Tisch fallen läßt: Wenn Spieler I eine Partie x spielt, dann hat er auch ein y ∈ ^{ω}κ unter dem Tisch liegen, so daß ⟨x, y⟩ ∈ [T̃], d.h. x ∈ p[T̃] = A.

Es bleibt noch der

τ^{∗} Fall 2: Spieler II^{∗} hat eine Gewinnstrategie τ^{∗} in G^{∗}.

Hier müssen wir etwas mehr arbeiten. Wir definieren eine Strategie τ für den Spieler II aus τ^{∗}. Danach zeigen wir, daß τ für den Spieler II im Spiel G eine Gewinnstrategie ist. Um aber τ^{∗} nutzen zu können, müssen wir eine geeignete Partie in G^{∗} finden. Im Gegensatz zu Fall 1, wo wir zuviel Information hatten, nämlich die y_{i}-Werte, fehlen uns diese hier. Wie wählen wir die Werte y_{i} geeignet aus, so daß wir eine vernünftige Strategie τ bekommen? An dieser Stelle nutzen wir die Maße U_{s}, die wir bisher nicht benötigt haben.

Wir definieren τ induktiv über die Länge des Spiels. Sei also im n-ten Zug Spieler II an der Reihe; Spieler I spielte daher gerade das Paar ⟨x_{2n}, y_{n}⟩. Dann sei die Antwort τ(x ↾ (2n + 1)) von Spieler II, gegeben durch τ

τ(x ↾ (2n + 1)) := dasjenige k < ω mit X_{n}^{(k)} ∈ U_{x↾n}, (3.1)

wobei X_{n}^{(k)} := {y ∈ T_{x↾n} | τ^{∗}(x ↾ (2n + 1), y) = k}. X_{n}^{(k)}

Aufgrund der Eigenschaften der U_{s} ist (3.1) korrekt definiert. (Die Existenz folgt aus der ω_{1}-Vollständigkeit. Induktiv über n < ω schließt man aus der Annahme des Falls 2 zusammen mit der obigen Definition, daß T_{x↾n} ≠ ∅ ist.)

Wir zeigen nun die folgende

Behauptung: τ ist eine Gewinnstrategie für Spieler II in G.

Beweis der Behauptung: Angenommen, das wäre nicht der Fall; dann gibt es eine Partie x ∈ ^{ω}ω in dem Spiel G, welche entsprechend τ gespielt wurde und trotzdem x ∈ A = p[T] gilt, d.h. Spieler II hat verloren.

Wenn diese Partie entsprechend τ gespielt wurde, dann bedeutet das gerade, daß Spieler II seine Züge genau wie in (3.1) gewählt hat. Das heißt nun aber wiederum, daß

X_{n}^{(x_{2n+1})} ∈ U_{x↾n} für alle n < ω. (3.2)

Wegen der abzählbaren Vollständigkeit der Maße ⟨U_{s} | s ∈ ^{<ω}ω⟩ existiert dann aber ein d ∈ ^{ω}κ mit d

d ↾ (n + 1) ∈ X_{n}^{(x_{2n+1})} für alle n < ω. (3.3)

Schauen wir uns nun die folgende Partie von G^{∗} an:

Spiel G^{∗}  I^{∗}  ⟨x_{0}, d_{0}⟩  ⟨x_{2}, d_{1}⟩  ..._{II_{∗}}  x_{1}  ...

Diese Partie ist entsprechend τ^{∗} gespielt, (3.4)

denn x_{2n+1} = τ^{∗}(x ↾ (2n + 1), d ↾ (n + 1)) wegen (3.3) und der Definition von X_{n}^{(k)} für beliebiges n < ω.

Nach unserer Annahme ist x ∈ A = p[T]. Außerdem gilt d ↾ n ∈ T_{x↾n}, d.h. ⟨x ↾ n, d ↾ n⟩ ∈ T, für alle n < ω. Also gewinnt Spieler I nach der Gewinnstrategie τ^{∗} für II^{∗}. Widerspruch! ⊠(Behauptung)

Damit ist τ doch wie gewünscht. ⊠(Fall 2)

Unser Ziel ist erreicht; das Spiel G ist determiniert. ⊠(Lemma 3.1)

Bemerkung 3.2 Wir sehen an diesem Beweis genau, wo wir die homogene Suslin-Darstellung von A benötigt haben: Unser eigentliches Ziel ist es, Π_{1}^{1}-Mengen A zu betrachten. Wir können einen Baum T finden, so daß A = p[T] gilt. Diese Eigenschaft war die einzig nötige, um das Hilfsspiel G^{∗} zu definieren und den Fall 1 zu beweisen. Wenn wir uns den Fall 2 genauer anschauen, dann stellt sich gerade am Anfang das Problem, wie wir die nötigen y_{i} bereitstellen können, so daß wir die Gewinnstrategie τ^{∗} ausnutzen können. Genau an dieser Stelle haben wir die homogene Suslin-Darstellung unserer Menge A ausgenutzt. Mit Hilfe der Maße U_{s} war es uns möglich geworden, derart Werte y_{i} zu wählen, so daß die damit definierte Strategie τ eine Gewinnstrategie für den Spieler II wurde.

4 Eine Darstellung von Π_{1}^{1}-Mengen

Unser eigentliches Ziel erreichen wir nun mit dem folgenden Lemma.

Lemma 4.1 Wenn κ meßbar, dann ist jede Π_{1}^{1}-Menge κ-homogen Suslin.

Beweis: Als erstes analysieren wir, was wir schon über die Darstellung von Π_{1}^{1}- Mengen wissen. Hierfür werden wir die Meßbarkeit von κ gar nicht benötigen. Sei

A, B also κ ≥ ω_{1} und A eine beliebige co-analytische Menge. Setze B := ^{ω}ω \ A ∈ Σ_{1}^{1}.

Dann gibt es eine abgeschlossene Menge C, so daß x ∈ B ⟷ ∃y ∈ ^{ω}ω (⟨x, y⟩ ∈ C).

T Natürlich läßt sich C als Menge von Zweigen durch einen geeigneten Baum T auf ω × ω darstellen, d.h. C = [T], also gilt:

B = p[T]. (4.1)

Daher erhalten wir sofort die folgenden Äquivalenzen:

(4.2)  x ∈ B ⟷ ∃y ∈ ^{ω}ω (⟨x, y⟩ ∈ [T])
⟷ ∃y ∈ ^{ω}ω (y ∈ [T_{(x)}])
⟷ ⟨T_{(x)}, ⊃⟩ ist nicht fundiert,

Also

x ∈ A ⟷ ⟨T_{(x)}, ⊃⟩ ist fundiert. (4.3)

Entwickeln wir die rechte Bedingung weiter, um einen Baum zu bekommen, der zwar bzgl. der Menge A die gleiche Eigenschaft wie T hat, aber der zu einem κ-homogenen Baum erweitert werden kann. Dazu benötigen wir die sogenannte Kleene-Brower

<_{KB} Ordnung auf ^{<ω}ω. Setze

s <_{KB} t :⟷ s ⊃ t ∨ ∃i (s ↾ i = t ↾ i ∧ s(i) < t(i))

Dann gilt:

⟨T, ⊃⟩ ist fundiert ⟷ ⟨T, <_{KB}⟩ ist fundiert. (4.4)

Beweis von (4.4): Die Richtung (←) ist offensichtlich erfüllt, da <_{KB} eine Erweiterung von ⊃ ist. Für die andere Richtung (→) beweisen wir die Kontraposition. Sei also ⟨t_{i} | i < ω⟩ eine <_{KB}-absteigende Folge mit t_{i} ∈ T. Es genügt dann, einen unendlichen Zweig in T zu finden. Wir definieren einen Kandidaten durch

x(n) := min{t_{i}(n) | lh(t_{i}) > n ∧ ∀m < n(t_{i}(m) = x(m))}

Falls diese Definition für alle natürlichen Zahlen n korrekt durchgeführt werden kann, dann hätten wir einen solchen Zweig gefunden. Überzeugen wir uns also davon, daß diese Definition nicht zusammenbricht. Induktiv nehmen wir nun an, daß x ↾ n 4 EINE DARSTELLUNG VON Π_{1}^{1}-MENGEN 7

für ein n > 0 definiert werden kann. Also existiert ein i < ω mit t_{i} ↾ n = x ↾ n. Wir unterscheiden zwei Fälle:

Fall A: lh(t_{i}) > n. Dann ist x(n) als Minimum einer nicht-leeren Menge definiert. Fall B: lh(t_{i}) = n. Betrachten wir dann t_{i+1}. Wegen t_{i+1} <_{KB} t_{i} haben wir wiederum zwei Fälle, wobei der erste nicht eintreten kann. Fall B.1: ∃j < n(t_{i} ↾ j = t_{i+1} ↾ j ∧ t_{i+1}(j) < t_{i}(j)). Das würde aber der Minimalität von x(j) widersprechen. Fall B.2: t_{i+1} ⊃ t_{i}. Dann existiert aber auch t_{i+1}(n) und somit ist x(n) definiert.

⊠ (4.4)

Nun können wir unsere Äquivalenzen von (4.3) weiterführen.

(4.5)  x ∈ A ⟷ ⟨T_{(x)}, ⊃⟩ ist fundiert
⟷ ⟨T_{(x)}, <_{KB}⟩ ist fundiert
⟷ ⟨^{<ω}ω, <_{x}⟩ ist fundiert

wobei <_{x} definiert ist durch <_{x}

s <_{x} t ⟷  (s, t ∈ T_{(x)} ∧ s <_{KB} t) ∨
(s ∉ T_{(x)} ∧ t ∈ T_{(x)}) ∨
(s, t ∉ T_{(x)} ∧ s ≺ t)

Dabei bezeichne ≺ eine beliebige lineare Ordnung von^{<ω}ω vom Typ ω mit s ⊂ t ⟶ s ≺ t. Weil <_{x} eine Erweiterung von <_{KB} ist und eine unendliche <_{x}-absteigende Folge schon bis auf endlich viele in T_{(x)} liegen muß, gilt auch die zuletzt behauptete Äquivalenz.

Bevor wir mit dieser neuen Ordnung weiterarbeiten, halten wir zwei einfach zu beweisende Eigenschaften fest.

<_{x} ist linear. (4.6)

(4.7) Falls x ↾ n = y ↾ n, so gilt T_{(x)} ↾ ^{<n}ω = T_{(y)} ↾ ^{<n}ω und daher auch <_{x}↾ ^{<n}ω =<_{y}↾ ^{<n}ω.

Sei nun ⟨s_{i} | i < ω⟩ die zu ≺ gehörige monotone Aufählung von ^{<ω}ω. Dann können wir eine entscheidene aber offensichtliche Beobachtung machen.

(4.8) ⟨^{<ω}ω, <_{x}⟩ ist fundiert gdw. es existiert g ∈ ^{ω}κ mit (s_{i} <_{x} s_{j} ⟷ g(i) ∈ g(j)) für i, j < ω.

Dafür werden wir “g erhält die Ordnung von <_{x} modulo der Aufzählung ⟨s_{i}|i < ω⟩” schreiben. Setze nun C := {⟨x, y⟩ ∈ ^{ω}ω ×^{ω}κ | ∀i, j (s_{i} <_{x} s_{j} ⟷ y(i) ∈ y(j))}. C C ist abgeschlossen.

Es existiert also ein Baum T̃ mit C = [T̃]; wir können T̃ sogar genau beschreiben:

T̃
(4.9)  ⟨u, v⟩ ∈ T̃ :⟷ ∀x ∈ ^{ω}ω [ u ⊂ x →
∀i, j < lh(v) ( s_{i} <_{x} s_{j} ↔ v(i) ∈ v(j) ) ]

Also ist ⟨u, v⟩ genau dann in T̃, wenn v die Ordnung von <_{x} modulo ⟨s_{i} | i < ω⟩ erhält für alle Erweiterungen x von u. Offensichtlich leistet T̃ das gewünschte. Aus unseren bisherigen Äquivalenzen (4.5) zusammen mit (4.8) bekommen wir jetzt:

x ∈ A ⟷ ∃y ∈ ^{ω}κ ⟨x, y⟩ ∈ [T̃], also A = p[T̃]. (4.10)

Mit ihr werden wir jetzt zum Ziel kommen, indem wir die Meßbarkeit von κ ins Spiel bringen. Wir möchten betonen, daß wir diese κ-Suslin-Darstellung von A auch ohne die Meßbarkeit von κ bekommen.

U Sei also U ein normaler Ultrafilter auf κ. Wir werden jetzt im zweiten Teil des Beweises Maße ⟨U_{s} | T̃_{s} ≠ ∅, s ∈ ^{<ω}ω⟩ finden, so daß T̃ zusammen mit ⟨U_{s} | T̃_{s} ≠ ∅⟩ ein κ-homogener Baum ist. Damit wäre der Beweis komplett.

Dazu benötigen wir als erstes die folgende

U^{(n)} Bemerkung 4.2 U^{(n)} ist ein κ-vollständiger Ultrafilter auf [κ]^{n}, wobei

A ∈ U^{(n)} ⟷ ∃B ∈ U [B]^{n} ⊆ A für A ∈ [κ]^{n}.

Einfaches Nachrechnen bestätigt schnell die Filtereigenschaften. Für den Nachweis der zusätzlichen Ultrafiltereigenschaft hilft der Satz von Rowbottom (Theorem 2.7) angewendet auf die charakteristische Funktion eines beliebigen X ⊆ [κ]^{n}.

Definiere nun Bijektionen für s ∈ ^{<ω}ω wie folgt:

π_{s}

π_{s} : T̃_{s} ⟶ [κ]^{lh(s)} gegeben durch π_{s}(t) := rng(t).

Die Injektivität von π_{s} bekommen wir aus der ordnungserhaltenden Eigenschaft in (4.9).

Setze dann

U_{s} U_{s} := {π_{s}^{−1}′′A | A ∈ U^{(lh(s))}} für s ∈ ^{<ω}ω, T̃_{s} ≠ ∅,

d.h. A ∈ U_{s} ⟷ π′′_{s}A ∈ U^{(lh(s))}.

Wir zeigen jetzt, daß die so definierte Maßfolge das gewünschte leistet.

Behauptung: Durch ⟨U_{s} | T̃ ≠ ∅⟩ wird T̃ zu einem κ-homogenen Baum.

Beweis der Behauptung: Wir zeigen die Eigenschaften entsprechend der Definition 2.9.

zu (a). U_{s} ist ein ω_{1}-vollständiges Maß auf T̃_{s} nach der oben stehenden Bemerkung 4.2.

zu (b). U_{s} ist Projektion von U_{t} für s ⊆ t, d.h. X ∈ U_{s} ⟷ {u ∈ T̃_{t} | u ↾ lh(s) ∈ X} ∈ U_{t}. Das folgt aus den folgenden Äquivalenzen

X ∈ U_{s} ⟷ π′′_{s}X ∈ U^{(lh(s))} ⟷ ∃B ∈ U [B]^{lh(s)} ⊆ π′′_{s}X und {u ∈ T̃_{t} | u ↾ lh(s) ∈ X} ∈ U_{t} ⟷ ∃B ∈ U [B]^{lh(t)} ⊆ π′′_{t}{u ∈ T̃_{t} | u ↾ lh(s) ∈ X}.

zu (c). Wir wollen die abzählbare Vollständigkeit zeigen. Sei also x ∈ p[T̃], A_{n} ∈ U_{x↾n} für jedes n < ω. Wir suchen nach einem d ∈ ^{ω}κ, so daß für jedes n < ω gilt: d ↾ n ∈ A_{n}.

Wir wollen jetzt erneut den Satz von Rowbottom anwenden. Setze dazu f : [κ]^{<ω} ⟶ 2 wie folgt: f(a) = 1 ⟷ a ∈ π′′_{x↾lh(a)}A_{lh(a)}. Dann existiert ein für f homogenes B ∈ U. Es muß f′′[B]^{n} = {1} für alle n < ω gelten. Angenommen, es gelte nicht. Dann gilt [B]^{n} ∩ π′′_{x↾n}A_{n} = ∅ nach Definition von f. Aber beide am Durchschnitt beteiligten Mengen liegen im Ultrafilter U^{(n)}. Widerspruch!

Da x ∈ A = p[T̃], ist nach (4.5) <_{x} fundiert. Sei also d : ω ⟶ B eine Einbettung von <_{x} modulo ⟨s_{i} | i < ω⟩ in ∈↾ B, d.h. ⟨x ↾ n, d ↾ n⟩ ∈ T̃ für jedes n < ω. Nach der Homogenität von B gilt [B]^{n} ⊆ π′′_{x↾n}A_{n} für jedes n < ω. Aber π_{x↾n}(d ↾ n) = rng(d ↾ n) ∈ [B]^{n}. Also d ↾ n ∈ A_{n} für alle n < ω.

Damit sind alle geforderten Eigenschaften nachgewiesen. ⊠(Behauptung)

Also ist unsere Menge A κ-homogen Suslin. ⊠(Lemma 4.1)

5 Eine Verfeinerung

Für Π_{1}^{1}-Determiniertheit ist die Existenz einer meßbaren Kardinalzahl, obwohl hinreichend, keine notwendige Bedingung. In diesem Abschnitt beweisen wir ein feineres Resultat, nämlich das folgende

Theorem 5.1 (Martin) Für alle reellen Zahlen a ∈ ^{ω}ω impliziert die Existenz von a^{♯} die Determiniertheit von Π_{1}^{1}(a)-Mengen.

Somit bekommen wir auch Π_{1}^{1}-Determiniertheit aus der Existenz der Sharps für die reellen Zahlen, also aus einer schwächeren Annahme als Meßbarkeit.

Wir werden die folgende Charakterisierung von a^{♯} benutzen.

Definition 5.2 (a^{♯}) Für eine reelle Zahl a ∈ ^{ω}ω behauptet a^{♯} die Existenz eines normalen ω_{1}-vollständigen L[a]-Ultrafilters U, also

⟨L[a], U⟩ ⊧ “U ist ein normales Maß.” (5.1)

Wir setzen jetzt einiges voraus und beschreiben dann, wie der Beweis laufen wird.

Voraussetzung: Sei a ∈ ^{ω}ω, a^{♯} existent und A ⊂ ^{ω}ω eine Π_{1}^{1}(a)-Teilmenge. Weiter a, A sei M := ⟨L[a], U⟩, wobei U der von a^{♯} gelieferte ω_{1}-vollständige L[a]-Ultrafilter ist,

M, U

und κ mit:

M ⊧ “U ist ein Maß auf κ.” (5.2)

Insbesondere ist dann κ ≥ ω_{1}^{V} und a ∈ M wegen der ω_{1}-Vollständigkeit von U. Wenn wir von “A in M” reden, so meinen wir A^{M}. Es gilt auch A^{M} = A∩M wegen der Absolutheit von Π_{1}^{1}(a)-Aussagen für Modelle, die a enthalten (Absolutheitslemma von Shoenfield).

Wir wollen zeigen, daß A determiniert ist. Wie im Abschnitt 3 betrachten wir natürlich das Spiel G_{A}. In V steht uns aber diesmal keine meßbare Kardinalzahl zur Verfügung, also haben wir auch keine κ-homogene, sondern nur eine κ-Suslin-Darstellung von A. Damit können wir keine Gewinnstrategie für II aus einer für II^{∗} herleiten, wie wir es im Abschnitt 3 gemacht haben.

Aber es gibt fast eine κ-homogene Suslin-Darstellung von A in M aufgrund des Prädikats U von M. Allerdings sind die wie im Abschnitt 4 definierten Maße keine Elemente von M. Wir können aber trotzdem in M über sie reden: “X ∈ U^{(n)}” und “X ∈ U_{s}” können als Formeln in M ausdrückt werden^{1}. Das wird uns für die folgenden Argumente reichen.

1“X ∈ U^{(n)}” bzw. “X ∈ U_{s}” kann als eine zweistellige Formel φ(X, n) bzw. ψ(X, s) mit Parametern aus M wie folgt geschrieben werden:

φ(X, n) := X ⊆ [κ]^{n} ∧ ∃B ∈ U [B]^{n} ⊆ X bzw.

ψ(X, s) := ∃n ∃Y ( n = lh(s) ∧ Y = π′′_{s}X ∧ φ(Y, n) )

Wir werden also die κ-Suslin-Darstellung von A in M zusammen mit den oben erwähnten Formeln und einigen Absolutheitsargumenten benutzen, um die Determiniertheit von A in V zu zeigen.

Schauen wir uns also die Lage an. Wir haben eine Π_{1}^{1}(a)-Menge A in V und eine Menge A^{M} in M nach derselben Definition. In M existiert derselbe κ-Suslin-Baum T̃ auf ω × κ wie in V, d.h. T̃ = T̃^{M}, und es gilt A = p[T̃] sowohl in V als auch in T̃

M. (Dabei sei T̃ wie im vorigen Abschnitt aufgebaut.)

Wir werden nun in V die Spiele G_{A} und G_{A}^{∗} betrachten — wie wir es im Abschnitt 3 gemacht haben — zusätzlich aber auch das Spiel G_{A}^{∗} in M. G_{A}^{∗} ist natürlich abgeschlossen, also determiniert (sowohl in V als auch in M).

Falls I^{∗} eine Gewinnstrategie σ^{∗} in V besitzt, so auch I, nämlich indem er nach σ^{∗} spielt und dabei die y_{i} unter den Tisch fallen läßt.

Falls I^{∗} verliert, so an einer endlichen Stelle. Also muß I^{∗} in M ebenfalls verlieren. (V und M besitzen dieselben endlichen Spielverläufe von G_{A}^{∗}.) G_{A}^{∗} ist aber natürlich

τ^{∗} auch in M determiniert. Also hat II^{∗} in M eine Gewinnstrategie τ^{∗}.

τ Wir definieren nun aus τ^{∗} eine Strategie τ für II in G_{A} genauso wie im Abschnitt 3. Für n < ω sei

τ(x ↾ (2n + 1)) := dasjenige k < ω mit “X_{n}^{(k)} ∈ U_{x↾n}”, (5.3)

wobei X_{n}^{(k)} := {y ∈ T_{x↾n} | τ^{∗}(x ↾ (2n + 1), y) = k}.

Behauptung: τ ist eine Gewinnstrategie für II in V.

Beweis der Behauptung: Angenommen nicht; sei x ∈ ^{ω}ω ∩ V ein Spielverlauf von G_{A} entsprechend τ, so daß II verliert, also derart, daß x ∈ A. Nach der Definition von τ gilt

“X_{n} ∈ U_{x↾n}” für alle n ∈ ω, (5.4)

X_{n} wobei X_{n} := X_{n}^{(x_{2n+1})} = {y ∈ ^{n}κ | τ^{∗}(x ↾ (2n + 1), y) = x_{2n+1}}.

Wir machen jetzt die folgende Annahme, deren Beweis wir im Anschluß bringen werden.

d Annahme: Es gibt eine Funktion d ∈ ^{ω}κ ∩ M, so daß d ↾ n ∈ X_{n} für alle n ∈ ω.

Folglich gilt ⟨x ↾ n, d ↾ n⟩ ∈ T̃ für alle n ∈ ω. Also erhält d die Ordnung von <_{x} modulo ⟨s_{i} | i < ω⟩. Aber das heißt gerade, daß ⟨x, d⟩ ∈ [T̃]. Mit anderen Worten ist ⟨T̃_{(d)}, ⊃⟩ nicht fundiert in V. Also

M ⊧ ⟨T̃_{(d)}, ⊃⟩ ist nicht fundiert (5.5)

nach Absolutheit der Fundiertheit und der Tatsache, daß d ∈ M. Folglich existiert ein z ∈ M mit

M ⊧ z ∈ [T̃_{(d)}]. (5.6)

Insbesondere ist z ∈ A^{M}. Außerdem kann z ∈ M entsprechend τ^{∗} gewählt werden, da ⟨x, d⟩ ein Spielverlauf von G_{A}^{∗} in V entsprechend τ^{∗} ist. Somit ist ⟨z, d⟩ ein Spielverlauf von G_{A}^{∗} in M entsprechend der Gewinnstrategie τ^{∗}, wobei aber II^{∗} verliert. Widerspruch!

Also ist τ doch eine Gewinnstrategie für II in V. ⊠(Behauptung)

Daher ist A determiniert.

Es bleibt noch die Annahme zu zeigen.

Beweis der Annahme: Für jedes n < ω haben wir ein X_{n} mit “X_{n} ∈ U_{x↾n}”. Also existiert für jedes n < ω ein D_{n} ∈ U mit [D_{n}]^{n} ⊆ π′′_{x↾n}X_{n}. Nach ω_{1}-Vollständigkeit von U ist D

D := ⋂_{n<ω} D_{n} ∈ U ⊆ M. (5.7)

Somit gilt

[D]^{n} ⊆ π′′_{x↾n}X_{n} und “π′′_{x↾n}X_{n} ∈ U_{n}”. (5.8)

Aber D ist überabzählbar, also existiert eine Funktion d : ω ⟶ D , die die Ordnung von <_{x} modulo ⟨s_{i} | i < ω⟩ erhält. Somit ist ⟨x, d⟩ ∈ [T̃], d.h. d ↾ n ∈ X_{n} für alle n ∈ ω. Damit ist die Annahme nachgewiesen. ⊠(Annahme)

⊠(Theorem 5.1)

Literatur

[Di] Ditzen, A.: Einführung in die Deskriptive Mengenlehre, Mitschrift einer Vorlesung im WS 1997/98 an der Humboldt-Universität zu Berlin.

[Ha] Harrington, L.A.: Analytic determinacy and 0^{♯} Journal of Symbolic Logic 43 (1978), S.685-693

[Ka] Kanamori, A.: The Higher Infinite. Large Cardinals in Set Theory from Their Beginnings, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-Heidelberg-New York 1994.

[Ke] Kechris, A.S.: Classical Descriptive Set Theory, Springer-Verlag, Berlin-Heidelberg-New York 1994.

[Ma] Martin, D.A.: Measurable Cardinals and Analytic Games, Fundamenta Mathematicae 66 (1970), S.287-291

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