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, Gewinnstrategie) 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 Gewinnstrategie, 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 Gewinnmenge 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 Gewinnstrategie 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 Gewinnmenge 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 Gewinnstrategie σ̃ in T̃ stets eine Gewinnstrategie σ := φ(σ̃) 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 Gewinnstrategie 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.

□

3.5 Beweise der Lemmata

Nun werden wir noch die beiden Lemata beweisen und damit den Beweis vervollständigen. Beweis (Existenz inverser Grenzwerte) (1) Definiere s ∈ T_{∞} ⇔ s ∈ T_{i} für i mit l(s) ≤ 2(k + i) unabhängig von i. Dann ist T_{∞} nichtleer und gestutzt.

(2) Dann definiert man π_{∞,i}(s) = s falls l(s) ≤ 2(k + i) und π_{∞,i}(s) = π_{i+1} ∘ ⋯ π_{j}(s) falls 2(k + i) < l(s) ≤ 2(k + j) unabhängig von j. Monotonie und Längenerhaltung vererben sich von π_{i} auf π_{∞,j}.

(3) Die Zusatzbedingung für eine (k + i)-Überdeckung ist offenbar erfüllt.

(4) Ähnlich definiert man φ_{∞,i}(σ_{∞})|2(k + i) = σ_{∞}|2(k + i) und φ_{∞,i}(σ_{∞})|2(k + j) = φ_{i+1} ∘ ⋯ φ_{j}(σ_{∞}|2(k + j)) für j > i konsistent für verschiedene j.

(5) Sei nun x_{i} ∈ [φ_{∞,i}(σ∞)] ein Spielverlauf in T_{i}. Nach den Überdeckungseigenschaften gibt es dann x_{i+1} ∈ [φ_{∞,i+1}(σ∞)], x_{i+2} ∈ [φ_{∞,i+2}(σ∞)], … mit π_{i+1}(x_{i+1}) = x_{i}, π_{i+2}(x_{i+2}) = x_{i+1}, …

Dann konvergieren die x_{i} gegen ein x_{∞}. Nun stimmen σ_{∞} und φ_{∞,j}(σ_{∞}) auf Sequenzen der Länge bis 2(k + j) überein, so dass man x_{∞} ∈ [σ_{∞}] erhält. Nach der Definition von π_{∞,i} und x_{∞} folgt dann π_{∞,i}(x_{∞}) = x_{i}.

□

Beweis (Lemma 3.12) (1) Seien k, T und X fest und sei T_{X} := {s ∈ T |∃x ∈ X(s ⊆ x)}. Damit ist T_{X} ⊆ T. Das Spiel G(T, X) hat die Form

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

(2) Die k-Überdeckung (T̃, π, φ), die wir definieren werden, ist ein Hilfsspiel, in dem die Spieler neben den üblichen Zügen x_{0}, x_{1}, ..., zusätzliche Züge machen werden. Zuerst werden wir dieses Hilfsspiel informell beschreiben. Die möglichen Züge definieren dann den Baum T̃.

(3) In den Spielen auf T̃ starten die Spieler mit den Zügen x_{0}, x_{1}, ..., x_{2k−2}, x_{2k−1}, so dass (x_{0}, ..., x_{i}) ∈ T für i ≤ 2k − 1.

(4) In seinem nächsten Zug spielt I (x_{2k}, Σ_{I})

\begin{matrix}I & x_{0} & & … & & x_{2k−2} & & (x_{2k}, Σ_{I}) \\ II & & x_{1} & & … & & x_{2k−1} \end{matrix}

mit: (x_{0}, ..., x_{2k}) ∈ T und Σ_{I} ist eine Quasistrategie für I in T_{(x_{0},...,x_{2k})} mit der Konvention, dass II zuerst bei Spielen auf T_{(x_{0},...,x_{2k})} zieht. In seinem nächsten Zug hat II zwei Optionen:

(5) Option 1. Er spielt (x_{2k+1}, u),

\begin{matrix}I & x_{0} & & … & & x_{2k−2} & & (x_{2k}, Σ_{I}) \\ II & & x_{1} & & … & & x_{2k−1} & & (x_{2k+1}, u) \end{matrix}

so dass (x_{0}, ..., x_{2k+1}) ∈ T und u ist eine Sequenz mit gerader Länge mit u ∈ T_{(x_{0},...,x_{2k+1})} und u ∈ (Σ_{I})_{(x_{2k+1})}\T_{X}_{(x_{0},...,x_{2k+1})}.

Wenn II diese Option wählt, spielen I und II von da an x_{2k+2}, x_{2k+3}, ... mit (x_{0}, ..., x_{j}) ∈ T für alle j. Dabei müssen die folgenden Züge aber konsistent mit u sein, also u ⊆ (x_{2k+2}, x_{2k+3}, ...). Damit ist das Spiel im Prinzip schon entschieden, da II mit u dafür sorgt, dass das Spiel nicht in X endet (Σ_{I} war nicht ”gut genug“).

(6) Option 2. Er spielt (x_{2k+1}, Σ_{II}),

\begin{matrix}I & x_{0} & & … & & x_{2k−2} & & (x_{2k}, Σ_{I}) \\ II & & x_{1} & & … & & x_{2k−1} & & (x_{2k+1}, Σ_{II}) \end{matrix}

so dass (x_{0}, ..., x_{2k+1}) ∈ T und Σ_{II} eine Quasistrategie für II in (Σ_{I})_{(x_{2k+1})} mit Σ_{II} ⊆ (T_{X})_{(x_{0},...,x_{2k+1})}.

Wenn II diese Option wählt, spielen I und II von da an x_{2k+2}, x_{2k+3}, ... mit (x_{2k+2}, x_{2k+3}, ..., x_{l}) ∈ Σ_{II} für alle l ≥ 2k + 2. Auch hier ist das Spiel schon entschieden, da durch Σ_{II} gewährleistet wird, dass das Spiel in X endet.

(7) Damit besteht T̃ aus allen endlichen Sequenzen der Form

(x_{0}, ..., x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, u), x_{2k+2}, ..., x_{l})
(x_{0}, ..., x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, Σ_{II}), x_{2k+2}, ..., x_{l})

mit den obigen Beschränkungen. Offensichtlich ist T̃ nicht leer und gestutzt.

(8) Die Definition der Abbildung π ist klar:

π(x_{0}, ..., x_{2k−1}, (x_{2k}, •), (x_{2k+1}, •), x_{2k+2}, ..., x_{l}) = (x_{0}, ..., x_{l})

Damit erfüllt π die Bedingungen, die in der Definition einer Überdeckung gestellt werden.

(9) Offenbar stimmen die Bäume in den ersten k Zügen beider Spieler überein und π bildet dort identisch ab. Damit sind die Zusatzbedingungen für eine k-Überdeckung erfüllt.

(10) Es gilt: x̃ ∈ π^{−1}(X) ⇔ II spielte nach Option 2. Daraus folgt, dass π^{−1}(X) offen und abgeschlossen ist. Daher entwirrt die (noch fertig zu definierende) Überdeckung die Menge X.

(11) Schließlich müssen wir noch φ definieren und die fehlenden Bedingungen (iii), (iv) dafür verifizieren, dass (T̃, π, φ) muss eine Überdeckung von T ist. Für eine gegebene Strategie σ̃ auf T̃ werden wir σ = φ(σ̃) beschreiben, so dass für jeden Verlauf x ∈ [σ] einen Verlauf x̃ ∈ [σ̃] mit π(x̃) = x existiert (iv). Aus der Beschreibung wird dann hervorgehen, dass σ|n nur von σ̃|n abhängt (iii).

(12) Fall 1: σ̃ ist eine Strategie für II in T̃.

Während der ersten k Züge folgt σ einfach σ̃. Anschließend gibt σ̃ in T̃ einen Zug (x_{2k}, Σ_{I}) vor. Dann soll σ den Zug x_{2k} vorschreiben. Spieler II möge nun in T den Zug x_{2k+1} machen. Betrachte nun das Spiel G(Σ_{I(x_{2k+1})}, [Σ_{I(x_{2k+1})}]\X_{(x_{0},...x_{2k+1})}). Da X abgeschlossen ist, ist dieses Spiel offen und daher nach dem Satz von Gale und Stewart determiniert. Unterscheide nun, ob in diesem Spiel I oder II eine Gewinnstrategie besitzen.

(13) Fall 1.1: I besitzt in diesem Spiel eine Gewinnstrategie.

Dann folgt I dieser Strategie, bis eine kürzeste Position gerader Länge u = (x_{2k+2}, … x_{2l−1}) erreicht ist mit u ∉ T_{X(x_{0},...x_{2k+1})}. Dann ist

(x_{0}, ..., x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, u), x_{2k+2}, ..., x_{2l−1})

eine zulässige Stellung in T̃. Von nun an soll σ wieder σ̃ kopieren.

(14) Fall 1.2: II besitzt in diesem Spiel eine Gewinnstrategie.

Sei Σ_{II} seine kanonische Quasistrategie. (Die Gewinnmenge von II ist abgeschlossen.) Dann wäre (x_{2k+1}, Σ_{II}) ein legaler Zug in II in T̃. Daher soll σ so weiterverlaufen, wie σ̃ wenn II diesen Zug spielt – solange II mitspielt und seine Züge mit Σ_{II} verträglich sind. Zieht II jedoch einen mit Σ_{II} unverträglichen Zug, so besitzt I von dort an eine Gewinnstrategie im Hilfsspiel, und wir landen in Fall 1.1.

(15) Sei nun x ∈ [φ(σ̃)] ein Spielverlauf in T, in dem I gemäß σ = φ(σ̃) gespielt hat. Weiterhin sei (x_{2k}, Σ_{I}) der Zug, den σ̃ in der Position (x_{0}, … x_{2k−1}) vorschreibt. Unterscheide nun, ob x ∈ X oder x ∉ X.

(16) x ∉ X: Dann steht dies bereits nach einer endlichen Zugfolge (x_{0}, … x_{2l−1}) fest. Dann ist mit u = (x_{2k+1}, … x_{2l−1}) die Folge

(x_{0}, … x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, u), x_{2k+2,...})

ein Spielverlauf gemäß σ̃ in T̃, der von π auf x = (x_{0}, …) abgebildet wird.

(17) x ∈ X: Dann ist II während des ganzen Spiels seiner kanonischen Quasistrategie Σ_{II} in G(Σ_{I(x_{2k+1})}, [Σ_{I(x_{2k+1})}]\X_{(x_{0},...x_{2k+1})}) gefolgt. Also ist

(x_{0}, … x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, Σ_{II}), x_{2k+2,...})

ein passender Spielverlauf in T̃.

(18) Fall 2: σ̃ ist eine Strategie für II in T̃.

Wieder folgt σ die ersten 2k Züge einfach σ̃. Danach spielt I x_{2k} (in dem Spiel auf T). Definiere S = {Σ_{I}|Σ_{I} ist eine Quasistrategie für I in T_{(x_{o},...,x_{2k})}} und U = {(x_{2k+1})^{⌢}u ∈ T_{(x_{o},...,x_{2k})}|u hat gerade Länge, und es gibt Σ_{I} ∈ S so dass σ̃ von II verlangt, auf (x_{2k}, Σ_{I}) mit (x_{2k+1}, u) zu antworten}.

Damit ist Ũ = {x ∈ [T_{(x_{o},...,x_{2k})}]|∃(x_{2k+1}^{⌢}u ∈ U(x ⊇ (x_{2k+1}^{⌢}u)} als Vereinigung von offen Basisumgebungen eine offene Menge in [T_{(x_{o},...,x_{2k})}].

Wir betrachten nun das Spiel auf T_{(x_{o},...,x_{2k})}, wobei II zuerst spielt und genau dann gewinnt, wenn (x_{2k+1}, x_{k+2}, ...) ∈ Ũ. Dieses Spiel ist wie das in Fall 1 determiniert, da Ũ offen ist.

(19) Fall 2.1: II hat eine Gewinnstrategie in diesem Spiel.

σ folgt dann (in dem Spiel auf T) dieser Gewinnstrategie für II, bis (x_{2k+1}, x_{k+2}, ...x_{2j−1}) ∈ U. Sei u = (x_{2k+2}, ..., x_{2j−1}) und Σ_{I} der Zeuge dafür, dass u ∈ U (siehe Definition von U). Damit kann σ wieder σ̃ ab der Stelle (x_{0}, ..., x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, u), x_{2k+2}, ..., x_{2j−1}) folgen. Dann ist π(x̃) = x klar.

(20) Fall 2.2: I hat eine Gewinnstrategie in diesem Spiel.

Sei Σ_{I} seine kanonische Quasistrategie. Angenommen, I spielt im Spiel auf T̃ den Zug (x_{2k}, Σ_{I}). Dann kann σ̃ von II nicht fordern, etwas der Form (x_{2k+1}, u) zu spielen, da dann x_{2k+1}^{⌢}u ∈ U gelten würde, was aber den Regeln von T̃ (x_{2k+1}^{⌢}u ∈ Σ_{I}) nach dem widerspricht, dass keine Sequenz von Σ_{I} in U sein kann.

Also verlangt σ̃ von II dann, (x_{2k+1}, Σ_{II}) zu spielen. Also spielt II nach σ dieses x_{2k+2}. Dann folgt σ einfach σ̃ auf (x_{0}, ..., x_{2k−1}, (x_{2k}, Σ_{I}), (x_{2k+1}, Σ_{II}), x_{2k+2}, ..., x_{2j}) solange wie I mitarbeitet, so dass (x_{2k+2}, ..., x_{2j}) ∈ Σ_{II}. Spielt aber I für irgendein j ≥ k + 1 x_{2k} mit (x_{2k+2}, ..., x_{2j}) ∉ Σ_{II}, gilt zudem (x_{2k+2}, ..., x_{2j}) ∉ Σ_{I}. Läuft nämlich I mit diesem Zug aus Σ_{II} heraus, muss er auch aus Σ_{I} herauslaufen, da Σ_{II} eine Quasistrategie in Σ_{I} ist und damit alle möglichen Züge von I innerhalb Σ_{I} berückichtigt. Damit sind wir aber wieder in Fall 2.1.

□

Damit ist der Beweis der Borel-Determiniertheit vollständig.

Literatur

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

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