Determiniertheit und Regularitätseigenschaften

Frank Gerolstein April 24, 2000

0.1 Einleitung

Bemerkung Ausgegangen wird von der Kenntnis des Seminarvortrags über das Theorem von Gale-Stewart.

Lemma 1.1 Zu jedem Spiel mit Regeln G(T, X) gibt es ein äquivalentes Spiel G(A, X′) und umgekehrt.

Satz 1.1 [AC](Gale-Stewart) Sei T ≠ ∅ gestutzt auf A. X ⊆ [T] offen oder abgeschlossen in [T] ⇒ X determiniert.

Konvention Im Folgenden sei X topologischer Raum, M Menge.

Definition 1.1

1. M ⊆ X heißt nirgends dicht, wenn Int(\overline{M}) = ∅

2. M ⊆ X heißt mager, wenn ∀i ∈ ω ∃M_{i} ⊆ X: M_{i} nirgends

dicht ∧ M = ⋃ M_{i}.

Definition 1.2 M hat die Baire-Eigenschaft genau dann, wenn ∃U ∈ T_{x}: M △ U ist mager.

Definition 1.3

1. x ∈ X ist Limespunkt von M genau dann, wenn ∀U ∈ T_{x}: x ∈ U → (M ∩ U) \ {x} ≠ ∅

2. x ∈ X ist isolierter Punkt von M genau dann, wenn x ∈ M ∧ x kein Limespunkt.

3. M ⊆ X heißt perfekt genau dann, wenn M ≠ ∅ ∧ ∼ M ∈ T_{x}∧ M hat keine isolierten Punkte.

Definition 1.4 M hat die perfekte Mengeneigenschaft genau dann, wenn M abzählbar ∨ ∃N ⊆ M: N perfekt.

Definition 1.5 M ist Null genau dann, wenn ∃N: N Borel ∧M ⊆ N ∧ m_{B}(N) = 0

Definition 1.6 M ist lesbegue-meßbar genau dann, wenn ∃N : N Borel ∧ M △ N ist Null.

0.2 Modifizierte Spiele

Definition 2.1 Das G^{∗∗}(A, X)− oder Banach-Mazur-Spiel ist ein modifiziertes Spiel, wobei gelte: ∀i ∈ ω: a_{i} ∈ A^{<ω} \ {∅} Satz 2.1 (Banach-Mazur) Sei X ⊆ [T].

a) I hat Gewinnstrategie in G^{∗∗}(ω, X) genau dann, wenn ∃s ∈ ω^{<ω}: N_{s} \ X mager

b) II hat Gewinnstrategie in G^{∗∗}(ω, X) genau dann, wenn X mager.

Beweis

• b),,⇐” Sei X mager, dann X ⊆ ⋃_{i∈ω} C_{i} wobei alle C_{i} abgeschlossen und nirgends dicht. Definiere nun eine Strategie σ für II so:

σ(s_{0}, ..., s_{2n}) = t mit N_{s_{0}⌢...⌢s_{2n}⌢t} ∪ C_{n} = ∅. Ein solches t existiert, da C_{n} abgeschlossen und damit ∼ C_{n} offen. ⇒ ∀x ∈∼ C_{n} ∃N_{U_{x}} ⊆∼ C_{n} : x ∈ N_{U_{x}} → N_{U_{x}} ∪ C_{n} = ∅. Wähle x ∈∼ C_{n} ∪ N_{s_{0}⌢...⌢s_{2n}} und dann t, so dass N_{t} ⊆ N_{x}. Ein solches x existiert nun, da angenommen ∼ C_{n}∪N_{s_{0}⌢...⌢s_{2n}} = ∅ → C_{n}∪N_{s_{0}⌢...⌢s_{2n}} = N_{s_{0}⌢...⌢s_{2n}} ⇒ ∅ = Int(\overline{C_{n}}) = Int(C_{n}) ⊇ Int(C_{n} ∪ N_{s_{0}⌢...⌢s_{2n}}) = Int(N_{s_{0}⌢...⌢s_{2n}}) = N_{s_{0}⌢...⌢s_{2n}} ≠ ∅ Widerspruch. Dann ist σ aber offenbar Gewinnstrategie für II, da ∀i ∈ ω: x ∉ C_{i} ⇒ x ∉ ⋂ C_{i} ⇒ x ∉ X

• b),,⇒” Habe nun II Gewinnstrategie σ. Sei p = (s_{0}, ..., s_{2n}) Teilspiel nach σ. Definiere p_{∗} := s_{0} ⌢ ... ⌢ s_{2n} und D_{p} := {x ∈ ω^{ω} | p_{∗} ⊆ x → ∃t ∈ ω^{<ω} : p_{∗} ⌢ t ⌢ σ(p_{∗} ⌢ t) ⊆ x}. D_{p} ist offen und dicht. Offen, da ∀u N_{u} abgeschloffen ist und damit insbesondere ∼ N_{u} offen. Nun ist D_{p} =∼ N_{p_{∗}} ∪ (D_{p} ∩ N_{p_{∗}}). Aber D_{p} ∩ N_{p_{∗}} = ⋃_{t∈T} N_{p_{∗}⌢t⌢σ(p_{∗}⌢t)} f”ur eine geeignete Indexmenge T ⊆ ω^{<ω}, da mit x ∈ N_{p_{∗}⌢t⌢σ(p_{∗}⌢t)} nach Definition auch alle anderen y ∈ N_{p_{∗}⌢t⌢σ(p_{∗}⌢t)} in D_{p} liegen und N_{p_{∗}⌢t⌢σ(p_{∗}⌢t)} ⊆ N_{p_{∗}}. ⇒ D_{p} ist Vereinigung offener Mengen und damit offen. Dicht. Zu zeigen ∀u ∈ ω^{<ω} : N_{u} ∩ D_{p} ≠ ∅. Angenommen N_{u} ∩ D_{p} = ∅, dann ist aber f”ur s_{0} = u, da σ Gewinnstrategie f”ur II, N_{u⌢σ(u)} ⊆ N_{u} und N_{u⌢σ(u)} ⊆ D_{p} ⇒ N_{u⌢σ(u)} ⊆ N_{u} ∩ D_{p}. Widerspruch Für beliebiges x ∈ ⋂_{p} D_{p} definiere rekursiv ein Spiel (s_{i})_{i∈ω}, so dass x = s_{0} ⌢ ... ∧ x ∉ X ⇒ X ⊆ ω^{ω} \ ⋂_{p} Dp = ⋃_{p}(ω^{ω} \ D_{p}). Nun ist aber ω^{ω} \ D_{p} nirgends dicht, da Int(\overline{ω^{ω} \ D_{p}}) = Int(\overline{∼ D_{p}}) = Int(∼ D_{p}) = Int(ω^{ω} \ D_{p}) = ∅ da angenommen, es gäbe x ∈ Int(ω^{ω} \ D_{p}) ⇒ ∃u : x ∈ N_{u} ⊆ Int(ω^{ω} \ D_{p}) ⊆ ω^{ω} \ D_{p} ⇒ N_{u} ∩ D_{p} = ∅. Widerspruch zu D_{p} dicht.

• a) ,,⇐” Sei N_{s} \ X mager für ein s ∈ ω^{<ω} \ {∅} ⇒ I hat Gewinnstrategie σ durch σ(∅) = s und b) ,,⇐”.

• a) ,,⇒” Habe nun I Gewinnstrategie σ mit σ(∅) = s. Dann hat II Gewinnstrategie in G^{∗∗}(ω, N_{s} \ X). Sei dazu nämlich s_{0} erster Zug von I.

1. Fall 1: s⊥s_{0} ⇒ II kann beliebig spielen.

2. Fall 2: s_{0} ⊂ s ⇒ II spielt t, wobei s_{0} ⌢ t = s und spielt wie I σ weiter.

3. Fall 3: s ⊆ s_{0} ⇒ II spielt a ⌢ σ(s ⌢ t ⌢ a) wobei s ⌢ t = s_{0} und spielt wie I σ weiter.

⇒ N_{s} \ X ist mager nach b) ,,⇒”.

qed

Definition 2.2 Sei X ⊆ ω^{ω}. Definiere O_{X} := ⋃{N_{s} | s ∈ ω^{<ω} ∧ N_{s} \ X mager}.

Korollar 2.1 Sei X ⊆ ω^{ω}. G^{∗∗}(ω, X \ O_{X}) ist determiniert → X hat Baire-Eigenschaft.

Beweis Angenommen I hat Gewinnstrategie in G^{∗∗}(ω, X \ O_{X}) ⇒ ∃t ∈ ω^{<ω} : N_{t}\(X\O_{X}) mager ⇒ N_{t}\X mager ⇒ N_{t} ⊆ O_{X} ⇒ N_{t}\(X\O_{X}) = N_{t} ⇒ N_{t} mager. Widerspruch. ⇒ II hat Gewinnstrategie ⇒ X \ O_{X} mager. Aber O_{X} \ X mager nach Definition von O_{X} ⇒ X hat Baire-Eigenschaft.

qed

Definition 2.3 Das G^{∗}(A, X)-Spiel ist ein modifiziertes Spiel, wobei ∀i ∈ ω : a_{2i} ∈ A^{<ω} ∧ a_{2i+1} ∈ A.

Satz 2.2 Sei X ⊆ [T].

a) I hat Gewinnstrategie in G^{∗}(2, X) ⇔ ∃Y ⊆ X : Y perfekt

b) II hat Gewinnstrategie in G^{∗}(2, X) ⇔ X ist abzählbar.

Beweis

– b) ,,⇐” Sei (a_{i})_{i∈ω} Abzählung von X. Dann definiere σ(s_{2i}) = s_{2i+1} so dass ∀s ∈ 2^{ω} : s_{0} ⌢ ... ⌢ s_{2i+1} ⌢ s ≠ a_{i}. Offenbar ist σ Gewinnstrategie für II, da ∀i ∈ ωa_{i} ≠ s_{0} ⌢ ... ⇒ s_{0} ⌢ ... ∉ X.

– b) ,,⇒” Habe nun II Gewinnstrategie σ. Sei p = (s_{0}, ..., s_{2n+1}) Teilspiel nach σ. Definiere p_{∗} := s_{0} ⌢ ... ⌢ s_{2n+1} und C_{p} := {x ∈ ω^{ω} | p_{∗} ⊆ x → ∃t ∈ ω^{<ω} : p_{∗} ⌢ t ⌢ σ(p_{∗} ⌢ t) ⊆ x}. Dann gilt ∀p: x ∈ 2^{ω} \ C_{p} ⇔ p_{∗} ⊆ x ∧ ∀t ∈ ω^{<ω} : p_{∗} ⌢ t ⌢ σ(p_{∗} ⌢ t) ⊈ x. Falls nun x ∈ 2^{ω} \ C_{p} existiert, dann gibt es x_{p} mit x_{p} ∈ 2^{ω} \ D_{p} ∧ | p_{∗} |= m ∧ x_{p} |_{m}= p_{∗}. Dann ist x_{p}(m) = 1 − σ(p ⌢ ∅) und rekursiv für e > m x_{p}(e) = 1 − σ(p ⌢ x_{p}(m) ⌢ ... ⌢ x_{p}(e − 1)) und definiere x_{p} = x_{p}(ω) := p ⌢ x_{p}(m) ⌢ x_{p}(m + 1) ⌢ ... falls existent; x_{p}(ω) = ∅ sonst. Dann ist X ⊆ ⋃_{p} x_{p}(ω). Es gibt aber eine kanonische Abzählung der Positionen und für jede Position nur eine endliche Anzahl an möglichen Teilspielen. ⇒ X abzählbar.

– a) ,,⇐” Es gäbe Y ⊆ X ∧Y perfekt. Definiere T := {x |_{n}| x ∈ Y ∧n ∈ ω}. Definiere eine Strategie σ für I, so dass s_{0} ⌢ ... ⌢ s_{2i} ⌢ 0 ∈ T ∧ s_{0} ⌢ ... ⌢ s_{2i} ⌢ 1 ∈ T. Ein solches s_{2i} existiert stets, da Y keine isolierten Punkte enthält. Da ∀n ∈ ω s_{0} ⌢ ... |_{n}∈ T, folgt s_{0} ⌢ ... |_{n} ist nicht verloren für I. Da Y abgeschlossen ist, folgt Y ist determiniert ⇒ I hat Gewinnstrategie in G^{∗}(ω, Y) ⇒ I hat Gewinnstrategie in G^{∗}(ω, X).

– a) ,,⇒” Sei σ Gewinnstrategie für I. Definiere Y := {σ ∗ y | y ∈ 2^{ω}}. Dann ist Y offenbar eine perfekte Teilmenge von X, wie man sich leicht anhand einer Skizze verdeutlicht.

qed

Definition 2.4 Definiere b̃_{n}^{k} : n + 1 → 2 durch b̃_{n}^{k}(i) := k mod 2, falls i = n und b̃_{n}^{k}(i) = 1 − k mod 2, sonst. b_{n}^{k} := b̃_{n}^{k}(0) ⌢ ... ⌢ b̃_{n}^{k}(n) ψ : ω^{ω} → 2^{ω} ψ(x) := b_{x(0)}^{0} ⌢ b_{x(1)}^{1} ⌢ ...

Bemerkung Das Bild von ψ sind alle x ∈ 2^{ω}, die nicht irgendwann konstant werden. ψ ist Homöomorphismus auf dem Bild. B ⊆ 2^{ω} perfekt genau dann, wenn ψ^{−1}(B) perfekt und B ⊆ 2^{ω} abzählbar genau dann, wenn ψ^{−1} abzählbar. ⇒ A ⊆ ω^{ω} determiniert ⇔ G^{∗}(2, ψ′′A) determiniert.

Korollar 2.2 Sei X ⊆ ω^{ω}. G^{∗}(2, ψ′′X) determiniert genau dann, wenn X die perfekte Mengeneigenschaft hat.

Beweis Klar.

Definition 2.5 a) Seien ε > 0 und eine Bijektion G : ω → {A ⊆ 2^{ω} | A = ⋃_{i∈I} N_{s(i)} ∧ I endlich} fixiert. Dann ist das G^{ε}(ω, X)- oder Überdeckungsspiel ein modifiziertes Spiel mit Regeln, wobei

1. ∀i ∈ ω : a_{2i} ∈ {0, 1} ∧ a_{2i+1} ∈ ω

2. m_{L}(G(a_{2i})) < \frac{ε}{2^{2i+3}}

3. X ⊆ 2^{ω}

b) Spieler I gewinnt in G^{ε}(ω, X) genau dann, wenn x_{I} ∈ X ∧ x_{I} ∉ ⋃_{i(ω)} G(a_{2i+1}).

Satz 2.3 (Mycielski, Swierczkowski) Sei X ⊆ [T].

a) I hat Gewinnstrategie in G^{ε}(ω, X) ⇒ ∃B ⊆ X : m_{L}(B) > 0

b) II hat Gewinnstrategie in G^{ε}(ω, X) ⇒ ∃B ∈ T_{X} : X ⊆ B ∧ m_{L}(B) < ε.

Beweis

∗ a) Habe I Gewinnstrategie σ. Definiere B := {(σ ∗ y)_{I} | y ∈ ω^{ω}}. Offenbar B ⊆ X, da σ Gewinnstrategie. Zu zeigen m_{L}(B) > 0. Angenommen m_{L}(B) = 0. Nun ist B = ⋂_{i∈I} N_{i} für I geeignet und damit abgeschlossen. Es gilt ohne Beweis 1) jede offene Menge ist disjunkte Vereinigung basisoffener Mengen

2) für jede lebesgue-meßbare Menge A und ε ∈ ℜ^{+} gibt es eine abgeschlossene Menge C und eine offene Menge O, so dass C ⊆ A ⊆ O ∧ m_{L}(O \ C) < ε. ⇒ m_{L}(O \ B) < ε ⇒ ∃ Abzählung O = ⋃_{i∈ω} N_{s(i)} ⊇ B ∧ m_{L}(N_{s(i)}) < \frac{ε}{2^{2i+3}} da m_{L}(⋃_{i∈ω} N_{s(i)}) < ε

∗ b) Habe II Gewinnstrategie σ. Für jedes s ∈ 2^{<ω} \ {∅} mit | s |= n+1 sei d(s) die Antwort von II im Spiel nach σ. Dann, da σ Gewinnstrategie, muss ∀x ∈ X ∃ n ∈ ω : x ∈ N_{d(x|_{n+1})} gelten. Definiere nun O := ⋃{N_{d(s)} | s ∈ 2^{<ω} \ {∅}} ⇒ X ⊆ O ⇒ da σ Gewinnstrategie, folgt II den Regeln und damit m_{L}(N_{d(s)}) < \frac{ε}{2^{2n+3}} . Nun gibt es aber 2^{n+1} solcher s der Länge n + 1. ⇒ m_{L}(O) ≤ ∑_{n∈ω} \frac{ε}{2^{2n+3}} ∗ 2^{n+1} = \frac{1}{2} ∗ ∑_{n∈ω} \frac{ε}{2^{n+1}} = \frac{1}{2}ε < ε. Offenbar ist O als Vereinigung offener Mengen offen.

qed

Definition 2.6 Sei A ⊆ ω^{ω}. B ⊆ ω^{ω} heißt minimale Überdeckung von A genau dann, wenn A ⊆ B ∧ B lebesgue-meßbar ∧ ∀ Z ⊆ B \ A : Z lebesgue-meßbar → m_{L}(Z) = 0.

Korollar 2.3 Sei A ⊆ ω^{ω}, B minimale Überdeckung von A. Falls ∀ε > 0 : det(G^{ε}(ω, B \ A)) gilt, dann ist A lebesgue-meßbar.

Beweis Nach Wahl von B folgt II hat Gewinnstrategie für alle ε. ⇒ B \ A ⊆ G ∩ m_{L}(G) = O.

qed

AD ∀X ∈ ℘(ℜ) : det(X)

Lemma 2.1 [AD] ∀X ∈ ℘(ℜ) : X ist lebesgue-meßbar, hat Baire-Eigenschaft und perfekte Mengen-Eigenschaft.

Beweisskizze Nimm das modifizierte Spiel. Dieses ist enthalten in einem Spiel auf A = ω ∪ {⊥} ∪ ω × {⊥}. Dieses ist äquivalent zu einem Spiel mit Regeln auf A = ω ∪ {⊥} ∪ ω × {⊥}, wobei die Regeln am Beispiel des G^{∗∗}(ω, X)-Spiels lauten:

1. Falls ein Spieler ein Element aus ω × {⊥} spielt, ist der einzig legale Antwortzug ⊥ zu spielen.

2. I darf nicht mit ⊥ eröffnen.

3. Falls ein Spieler ein Element aus ω zieht, darf der Antwortzug nicht ⊥ sein.

Dabei soll ein Element aus ω×⊥ bedeuten, dass der Spieler seinen Zug durch eine weitere Zahl fortsetzen will. Ein Element aus ω bedeutet, dass nun der andere Spieler am Zug ist, und ⊥ ist ein Zug, der nichts bewirkt. Da ω∪{⊥}∪ω×{⊥} abzählbar, ist das äquivalent zu einem Spiel mit Regeln auf A = ω. Dies ist nach Lemma 1.1 äquivalent zu einem Spiel ohne Regeln auf A = ω ⇒ mit AD und den vorherigen Korollaren 2.1, 2.2 und 2.3 die Behauptung.

qed

0.3 Determiniertheit und Regularitätseigenschaften

Konvention Im Folgenden sei F ⊆ ω^{ω} × X die Gewinnmenge.

Definition 3.1 Ein entfaltetes Spiel G_{u}(A, F) ist die disjunkte Zerlegung der Folgen (y_{n}, a_{n})_{n∈ω} ∈ ω^{ω} ×A^{ω} in die Gewinnmenge F und ∼ F, wobei wir sagen, Spieler I spielt (y_{0}, a_{0}) ∈ ω × A, danach II a_{1} ∈ A, dann I (y_{1}, a_{2}) ∈ ω × A, etc.

Definition 3.2 Spieler I gewinnt genau dann, wenn (y_{n}, a_{n}) ∈ F.

Definition 3.3 Eine Strategie von I ist ein Baum σ ⊆ ω^{ω} ×A^{ω} mit

1. σ ≠ ∅

2. (y_{k}, a_{i})_{i≤2j,k≤j} ∈ σ → ∀a_{2j+1}: (y_{k}, a_{i})_{i≤2j+1,k≤j} ∈ σ

3. (y_{k}, a_{i})_{i≤2j−1,k≤j−1} ∈ σ → ∃!a_{2j} ∃!y_{j}: (y_{k}, a_{i})_{i≤2j,k≤j} ∈ σ

Definition 3.4 Eine Strategie für I heißt Gewinnstrategie für I, falls [σ] ⊆ F.

Bemerkung Die Begriffe Spieler II gewinnt, (Gewinn-)Strategie für II definiert man entsprechend.

Definition 3.5 F heißt determiniert, falls einer der Spieler eine Gewinnstrategie hat.

Satz 3.1 (Kechris, Martin)[AC_{ω}(ω^{ω})] det(Π_{n}^{1}) → Σ_{n+1}^{1} hat Baire-Eigenschaft, perfekte Mengen-Eigenschaft und ist lebesgue-meßbar.

Beweisskizze Sei X Σ_{n+1}^{1}. Wende nun Solovay’s Entfaltungsidee an. Am Beispiel der Baire-Eigenschaft: Setze X̃ := X \O_{X}. Dann ist X̃ ebenfalls Σ_{n+1}^{1}. Wähle F Π_{n}^{1}, so dass X̃ π_{2}F. Da F Π_{n}^{1} ist, gibt es ein Z Π_{n}^{1}, so daßG(ω, Z) äquivalent zu G_{u}^{∗∗}(ω, F) ⇒ G_{u}^{∗∗}(ω, F) ist determiniert.

Fall 1: I hat Gewinnstrategie in G_{u}^{∗∗}(ω, F) ⇒ I hat Gewinnstrategie in G^{∗∗}(ω, X̃) ⇒ ∃s: N_{s} \ X̃ ist mager. Fall 2: II hat Gewinnstrategie G_{u}^{∗∗}(ω, F) ⇒ X̃ mager. Denn definiere D_{p} wie zuvor, wobei die y(i) ignoriert werden. Sei nun x ∈ ⋂ D_{p} ⇒ x ∉ X̃. Angenommen x ∈ X, dann gibt es y ∈ ω^{ω} mit (y, x) ∈ F. Aber dann definiere rekursiv ein Spiel nach σ, so dass y = y(0) ⌢ ... und x Konkatenation der endlichen Sequenzen. Widerspruch zu σ Gewinnstrategie.

⇒ x hat Baire-Eigenschaft.

Perfekte Mengen-Eigenschaft und Lebesgue-Meßbarkeit zeigt man mit analogen Argumenten.

qed

Korollar 3.1 Analytische (Σ_{1}^{1}−)Mengen haben Baire-Eigenschaft, perfekte Mengen-Eigenschaft und sind lebesgue-meßbar.

Beweis Σ_{1}^{1} := {proj_{X}(A) | Xpolnisch ∧ A ⊆ ω^{ω} × X ∧ A ∈ Π_{0}^{1}(ω^{ω} × X)} A analytisch genau dann, wenn ∃F ∈ Π_{1}^{0}(ω^{ω} × X) : F ⊆ ω^{ω} × X ∧ A = proj_{X}(F) ⇒ Π_{0}^{1} = Π_{1}^{0} ⇒ mit Satz 1.1 und Satz 3.1 die Behauptung.

qed