Nichtdeterminierte Mengen
Bei perfekter Kenntnis der mathematischen Welt ist ein determiniertes Spiel eher langweilig, da einer der beiden Spieler immer gewinnt, kluges Spiel vorausgesetzt. Mit unseren Kenntnissen über nichtreguläre Mengen und den Körper [ S ] eines Baumes S können wir sofort ein − in diesem Sinne − interessantes Spiel P angeben:
Satz (Bernstein-Mengen sind nicht determiniert)
Es gibt ein P ⊆ 𝒞, das nicht determiniert ist.
Genauer gilt: Ist P ⊆ 𝒞 eine Bernstein-Menge, so ist P nicht determiniert.
Beweis
Sei P ⊆ 𝒞 eine Bernstein-Menge, und sei S eine Strategie in Seq2 für I oder II.
Dann ist S ≠ ∅ ein perfekter Baum, also ist [ S ] nichtleer und perfekt.
Wegen P Bernstein-Menge ist also [ S ] keine Teilmenge von P und auch keine Teilmenge von 𝒞 − P. Also ist S keine Gewinnstrategie für Spieler I und auch keine Gewinnstrategie für Spieler II.
Das Argument funktioniert allgemein für abzählbare A mit mindestens zwei Elementen (denn dann ist ℕA ein überabzählbarer polnischer Raum und folglich existiert eine Bernstein-Menge in ℕA). Positiv formuliert zeigt der Beweis:
Korollar (Determiniertheit und Scheeffer-Eigenschaft)
Sei A eine abzählbare nichtleere Menge, und sei P ⊆ ℕA determiniert.
Dann hat P oder ℕA − P die Scheeffer-Eigenschaft.
Diese Beobachtung liefert einen ersten Zusammenhang zwischen Determiniertheit und Regularität.
Für beliebig große Alphabete folgt die Existenz einer nicht determinierten Menge aus der folgenden Monotonie-Eigenschaft:
Satz (Vererbung nicht determinierter Mengen auf größere Alphabete)
Seien A, B Mengen, und sei A ⊆ B. Weiter sei P ⊆ ℕA nicht determiniert.
Dann existiert eine nicht determinierte Menge P′ ⊆ ℕB.
Beweis
Sei GB(P′) = FGB(P, SeqA) das zu GA(P) assoziierte freie Spiel auf B.
Dann ist GB(P′) äquivalent zu GA(P), also nicht determiniert.
Damit erhalten wir nun einen allgemeinen Existenzsatz:
Korollar (Existenz nichtdeterminierter Mengen, allgemeine Form)
Sei A eine Menge mit mindestens zwei Elementen.
Dann existiert ein P ⊆ ℕA, das nicht determiniert ist.
Beweis
O. E. ist { 0, 1 } ⊆ A, und dann folgt die Behauptung aus dem Vererbungssatz und der Existenz einer nicht determinierten Teilmenge von 𝒞.
Wir greifen hier auf die Konstruktion von Bernstein-Mengen und damit auf das Auswahlaxiom zurück. Wir halten ohne Beweis fest, dass sich die Existenz einer nichtdeterminierten Menge P ⊆ ℕA für überabzählbare A sogar ohne Auswahlaxiom zeigen lässt.
Aufgrund der Wichtigkeit des Ergebnisses geben wir noch einen zweiten, etwas direkteren Beweis für die Existenz einer nicht determinierten Menge. Verläuft die Konstruktion einer Bernstein-Menge durch Diagonalisierung aller perfekten Mengen, so werden im folgenden Beweis alle Gewinnstrategien diagonalisiert. Die Konstruktion wiederholt aber im Wesentlichen nur die Konstruktion einer Bernstein-Menge.
Satz (nicht determinierte Mengen aus einer Wohlordnung von 𝒞)
Es existiert ein P ⊆ 𝒞, das nicht determiniert ist.
Genauer gilt: P lässt sich aus einer Wohlordnung auf 𝒞 definieren.
Beweis
Sei <𝒞 eine Wohlordnung von 𝒞 minimaler Länge. Sei
𝒮 = { S | S ist Strategie für I oder II in Seq2 }.
Dann gilt |𝒮 × { 0, 1 }| = 2ω.
Sei h : 𝒞 → 𝒮 × { 0, 1 } bijektiv, und sei < die durch h induzierte Wohlordnung von 𝒮 × { 0, 1 }. Mit <𝒞 hat dann auch < minimale Länge.
Wir definieren durch Rekursion über 〈 𝒮 × { 0, 1 }, < 〉:
f(S, i) = „das <𝒞-kleinste f ∈ [ S ] mit f ∉ { f(S′, j) | (S′, j) < (S, i) }“.
Ein solches f existiert, denn es gilt |[ S ]| = 2ω für alle S ∈ 𝒮 und |{ (S′, j) | (S′, j) < (S, i) }| < 2ω nach minimaler Länge von <.
Wir setzen:
D = { f(S, 0) | S ∈ 𝒮 }.
Dann gilt:
(+) D ist nicht determiniert.
Beweis von (+)
Sei S eine Strategie für I. Dann ist f(S, 1) ∈ [ S ] − D.
Also ist S keine Gewinnstrategie für I.
Sei also S eine Strategie für II. Dann ist f(S, 0) ∈ [ S ] ∩ D.
Also ist S keine Gewinnstrategie für II.
De facto ist 𝒞 − D = { fS, 1 | S ∈ 𝒮 }, was wir im Beweis nicht brauchen.
Die Idee des Beweises ist das sukzessive gegenseitige Ruinieren von Strategien. Eine Strategie „entsteht“ normalerweise durch Analyse eines gegebenen Spiels. Hier „entsteht“ umgekehrt ein Spiel durch eine Analyse aller möglichen Strategien. Die zugehörige Gewinnmenge D ist eine komplexe, aber keineswegs paradoxe Konstruktion. Wie für alle diagonalen Konstruktionen liegt ihrer Existenz die Auffassung zugrunde, dass wir in einer fertigen mathematischen Welt leben, in der wir auf alle Teilmengen einer Menge Zugriff haben, und nicht etwa diese Teilmengen durch unsere Beweise neu erschaffen. Die Irritation, die die Diagonalisierung zuweilen auslöst, ist oft Folge des Vergessens der Anführungszeichen um das Wort „entsteht“ für das Konstrukt eines mathematischen Arguments.
Eine Bedingung von Faust in seinem Pakt mit dem Teufel ist: „Zeig mir ein Spiel, bei dem man nie gewinnt.“ Mephisto antwortet, dass ihn ein solcher Auftrag nicht schrecke. Er kannte wohl obigen Beweis seit seinen Studientagen. Denn zweifellos ist der Teufel ein guter Mathematiker und ein Experte im Spiel mit Gewinnmenge D. Gewinnt eigentlich Gott immer gegen den Teufel in diesem Spiel? Auch er kann keine Gewinnstrategie haben. In diesem 0-1-Spiel öfter zu gewinnen als zu verlieren zeigt den wahren Könner.