3 Borel-Determiniertheit

In diesem Vortrag werden wir beweisen, dass alle Borelmengen determiniert sind.

3.1 Unendliche Spiele

Zunächst wiederholen wir noch einmal die benötigten Definitionen für unendliche Spiele:

Definition 3.1 (Spiel) In einem Spiel G(A, X) wählen zwei Spieler I und II abwechselnd Elemente a_{i} einer Menge A. Spieler I gewinnt, wenn die resultierende Folge (a_{n}) in der vorher festgelegten Gewinnmenge X ⊆ A^{ω} liegt. Andernfalls gewinnt Spieler II.

\begin{matrix}I & a_{0} & & a_{2} & & … \\ II & & a_{1} & & a_{3} & & … \end{matrix}

Definition 3.2 (Spiel mit Regeln) Sei T ein Baum über A. Dann bezeichnet G(T, X) das Spiel, in dem die Spieler nur so ziehen dürfen, dass jede Position des Spieles ein Knoten von T ist.

Definition 3.3 (Quasistrategie, Strategie, Siegstrategie) Eine Quasistrategie für Spieler I ist ein nichtleerer gestutzter Teilbaum von T, der in jeder Position, in der I am Zug ist, mindestens einen Zug enthält während sie, wenn II am Zug ist, alle in T möglichen Züge erlaubt. Eine Quasistrategie für I wird Strategie genannt, wenn sie für Spieler I stets genau einen Zug vorschreibt. Eine Strategie σ für Spieler I heißt Siegstrategie, wenn Spieler I, so er ihr folgt, stets gewinnt, d.h. [σ] ⊆ X.

Für Spieler II definiert man die Begriffe analog.

Definition 3.4 (Determiniertheit) Ein Spiel G(A, X) oder G(T, X) heißt determiniert, wenn einer der beiden Spieler eine Gewinnstrategie besitzt. Eine Menge X ⊂ A^{ω} heißt determiniert, wenn das Spiel G(A, X) determiniert ist.

Wir denken uns im Folgenden A stets mit der diskreten Topologie und A^{ω} mit der entsprechenden Produkttopologie versehen. [T] ⊆ A^{ω} trägt die davon induzierten Teilraumtopologie. Man beachte, dass die Topologie auf A^{ω} – und damit auch diejenige auf [T] – metrisierbar ist.

3.2 Determiniertheit offener und abgeschlossener Mengen

Nun werden wir einen Determiniertheitsbeweis für besonders einfache Spiele, bei denen die Siegmenge offen oder abgeschlossen ist, liefern.

Satz 3.5 (Gale-Stewart) Sei T ein nichtleerer gestutzter Baum über A und X ⊆ [T] offen oder abgeschlossen. Dann ist G(T, X) determiniert.

Beweis (Gale-Stewart) Sei X zunächst abgeschlossen. Angenommen, II habe keine Gewinnstrategie. Dann werden wir eine Gewinnstrategie für I konstruieren.

Eine Position P = (a_{0}, … a_{2n−1}), in der I am Zug ist, bezeichnen wir als nichtverloren, wenn für den Spieler II von nun an (d.h. in dem Spiel G(T_{P} , X_{P}), wobei T_{P} = {s|P ⌢ s ∈ T } und X_{P} = {x|P ⌢ x ∈ X}) keine Siegstrategie existiert.

Offenbar ist ∅ nach dieser Definition nichtverloren. Außerdem gibt es in jeder nichtverlorenen Position P einen Zug a_{2n}, so dass jeder mögliche Zug a_{2n+1} von II wieder zu einer nichtverlorenen Stellung P ⌢ (a_{2n}, a_{2n+1}) führt.

Wähle nun (AC!) in jeder nichtverlorenen Position einen solchen Zug. Dies ergibt eine Strategie für I.

Sei nun (a_{n}) ein Spiel, in dem I nach dieser Strategie spielt. Angenommen, I verliert, d.h. (a_{n}) ∈ ∼X. Da ∼X offen ist, muss es eine Basisumgebung geben mit N_{(a_{0},...a_{2n−1})} ∩ [T] ⊆ ∼X. Doch dann ist (a_{0}, … a_{2n−1}) offenbar für I verloren, da II von hier an beliebig weiterspielen kann.

Der Beweis für offenes X läuft analog. Dabei müssen nur die Rollen der beiden Spieler vertauscht werden.

□

3.3 Der Satz von Martin, Hilfsspiele

Satz 3.6 (Martin) Sei T ein nichtleerer gestutzter Baum über A und X ⊆ [T] eine Borelmenge. Dann ist das Spiel G(T, X) determiniert.

Die Idee des Beweises für dieses Resultat (wie für viele andere Determiniertheitsaussagen) ist es, dem Spiele G(T, X) ein Hilfsspiel G(T^{∗}, X^{∗}) zuzuordnen, von dem bekannt ist, dass es determiniert ist, normalerweise ein abgeschlossenes oder offenes Spiel. Dabei muss zu jeder Gewinnstrategie für einen Spieler im Spiel G(T^{∗}, X^{∗}) eine Gewinnstrategie für den entsprechenden Spieler im Spiel G(T, X) existieren. Meistens wird in G(T^{∗}, X^{∗}) im Wesentlichen ein Verlauf von G(T, X) gespielt, mit dem Unterschied, dass in jedem Zug zusätzliche Objekte gespielt werden, die die Siegmenge einfacher gestalten sollen, z.B. abgeschlossen oder offen. Dann gibt es eine natürliche Projektion von T^{∗} nach T.

In unserem Fall werden die obigen Ideen durch das Konzept der Überdeckung eines Spieles formalisiert.

Definition 3.7 (Überdeckung – Covering) Sei T ein nichtleerer gestutzter Baum über einer Menge A. Eine Überdeckung von T ist ein Tripel (T̃, π, φ), für das gilt:

1. T̃ ist ein nichtleerer gestutzter Baum (über einer Menge Ã).

2. π : T̃ ⟶ T ist monoton mit l(π(s)) = l(s). Somit induziert π eine stetigen Funktion von [T̃] nach [T], man schreibt auch π : [T̃] ⟶ [T].

3. φ bildet Strategien für Spieler I (resp. II) in T̃ auf Strategien für Spieler I (resp. II) in T ab, so dass für alle n φ(σ̃)|n nur von σ̃|n abhängt. (m ≤ n ⇒ φ(σ̃|m) = φ(σ̃|n)|m und φ(σ̃) ist definiert durch φ(σ̃)|n = φ(σ̃|n) für jedes n.)

4. Wenn σ̃ eine Strategie für Spieler I (resp. II) in T̃ ist und x ∈ [T] wurde gemäß φ(σ̃) gespielt (x ∈ [φ(σ̃)]), so gibt es ein x̃ ∈ [T̃], das gemäß σ̃ gespielt wurde (x̃ ∈ [σ̃]), so dass π(x̃) = x.

Bemerkung 3.8 Man kann ein Spiel G(T, X) durch das Spiel G(T̃, X̃) simulieren, wenn (T̃, π, φ)eine Überdeckung von T ist und X̃ = π^{−1}(X). Insbesondere bedeutet dies, dass das Bild einer Siegstrategie σ̃ in T̃ stets eine Siegstrategie σ := φ(σ̃) in G(T, X) ist. Gäbe es nämlich einen Spielverlauf x ∈ [σ], der in einer Niederlage endet, so gäbe es nach 4) x̃ ∈ [σ̃] mit π(x̃) = x, der wegen der Definition von X̃ ebenfalls in einer Niederlage endet, im Widerspruch dazu, dass σ̃ eine Siegstrategie ist.

Aus technischen Gründen benötigen wir noch eine Verstärkung des Konzeptes der Überdeckung:

Definition 3.9 (k-Überdeckung – k-Covering) Sei k ∈ ω. Die Überdeckung (T̃, π, φ) ist eine k-Überdeckung, falls T |2k = T̃|2k und π|(T̃|2k) die Identität ist.

Intuitiv bedeutet das, das in dem Hilfspiel G(T̃, X̃) die ersten k Züge jedes Spielers identisch mit denen im Spiel G(T, X).

Definition 3.10 (Entwirrung – Unravelling) Eine Überdeckung (T̃, π, φ) von T entwirrt X ⊆ [T], wenn π^{−1}(X) offen und abgeschlossen ist.

3.4 Der Beweis

Wenn eine Überdeckung (T̃, π, φ) von T die Menge X entwirrt, so ist nach dem Satz von Gale und Stewart G(T̃, X̃) determiniert und aus Bemerkung 3.8 folgt dann, dass auch G(T, X) determiniert ist. Also genügt es, folgende Version des Satzes von Martin zu beweisen:

Satz 3.11 (Martin) Sei T ein nichtleerer gestutzter Baum und X ⊆ [T] eine Borelmenge, dann gibt es für jedes k ∈ ω eine k-Überdeckung von T die X entwirrt.

Wir formulieren den Satz für k-Überdeckungen statt nur für Überdeckungen, um einen induktiven Beweis führen zu können.

Lemma 3.12 Sei T ein nichtleerer gestutzter Baum und X ⊆ [T] sei abgeschlossen, dann gibt es für jedes k ∈ ω eine k-Überdeckung von T die X entwirrt.

Lemma 3.13 (Existenz inverser Grenzwerte) Sei k ∈ ω. Sei (T_{i+1}, π_{i+1}, φ_{i+1}) für i ∈ ω eine (k+i)-Überdeckung von T_{i}. Dann gibt es einen gestutzten Baum T_{∞} und π_{∞,i} sowie φ_{∞,i}, so dass für alle i ∈ ω (T_{∞}, π_{∞,i}, φ_{∞,i}) eine (k+i)-Überdeckung von T_{i} ist und es gilt π_{i+1} ∘π_{∞,i+1} = π_{∞,i} und φ_{i+1} ∘ φ_{∞,i+1} = φ_{∞,i}.

Mit Hilfe dieser beiden Lemmata werden wir nun den Satz von Martin beweisen. Beweis (Martin) Wir zeigen durch Induktion über 1 ≤ ξ < ω_{1}, dass es für alle T, k ∈ ω und X ⊆ [T] in Σ_{ξ}^{0}([T]) eine k-Überdeckung von T gibt, die X entwirrt.

Eine k-Überdeckung, die X entwirrt, entwirrt auch ∼X, also gilt obiges für ξ = 1.

Angenommen, die Behauptung gilt für alle η < ξ. Damit gibt es für jedes T, jedes Y ∈ Π_{η}^{0}([T]) und für jedes k eine k-Überdeckung, die ∼Y entwirrt, also auch Y selbst.

Sei nun X ∈ Σ_{ξ}^{0}([T]) und k ∈ ω. Dann ist X = ⋃_{i∈ω} X_{i} mit X_{i} ∈ Π_{ξ_{i}}^{0}([T]), ξ_{i} < ξ. Sei (T_{1}, π_{1}, φ_{1}) eine k-Überdeckung von T_{0} = T, die X_{0} entwirrt. Dann ist π_{1}^{−1}(X_{i}) ∈ Π_{ξ_{i}}^{0}([T_{1}]) auch für i ≥ 1, da Σ_{ξ}^{0}, Π_{ξ}^{0} unter stetigen Urbildern abgeschlossen sind.

Rekursiv definieren wir nun (T_{i+1}, π_{i+1}, φ_{i+1}) als eine (k + i) - Überdeckung von T_{i}, die π_{i}^{−1} ∘π_{i−1}^{−1} ∘…∘π_{1}^{−1}(X_{i}) entwirrt. Sei nun (T_{∞}, π_{∞,i}, φ_{∞,i}) der inverse Grenzwert. Dann entwirrt (T_{∞}, π_{∞,0}, φ_{∞,0}) jedes X_{i}. Damit ist π_{∞,0}^{−1}(X) = ⋃_{i} π_{∞,0}^{−1}(X_{i}) offen in [T_{∞}].

Schließlich sei nach Lemma 3.12 (T̃, π, φ) eine k-Überdeckung von T_{∞}, die π_{∞,0}^{−1}(X) entwirrt. Damit ist (T̃, π_{∞,0} ∘ π, φ_{∞,0} ∘ φ) eine k-Überdeckung von T, die X entwirrt.

□

Die Beweise der beiden Lemmata führen wir in der nächsten Woche vor.

Literatur

[1] A. Kechris: Classical Descriptive Set Theory, Springer 1994

[2] D. Martin: Proving Determinacy, Preprint 1998