Entschlossenheit - Determinacy

Bestimmtheit ist ein Teilgebiet der Mengenlehre , einem Zweig der Mathematik , der die Bedingungen untersucht, unter denen der eine oder andere Spieler eines Spiels eine Gewinnstrategie hat, und die Konsequenzen der Existenz solcher Strategien. Alternativ und ähnlich ist "Bestimmung" die Eigenschaft eines Spiels, bei dem eine solche Strategie existiert.

Die in der Mengenlehre untersuchten Spiele sind normalerweise Gale- Stewart-Spiele – Zwei-Spieler-Spiele mit perfekter Information, in denen die Spieler eine unendliche Abfolge von Zügen machen und es kein Remis gibt. Das Gebiet der Spieltheorie untersucht allgemeinere Arten von Spielen, einschließlich Spiele mit Remis wie Tic-Tac-Toe , Schach oder unendliches Schach , oder Spiele mit unvollkommenen Informationen wie Poker .

Grundbegriffe

Spiele

Die erste Art von Spiel, die wir betrachten werden, ist das Zwei-Spieler-Spiel mit perfekter Information der Länge ω , bei dem die Spieler natürliche Zahlen spielen . Diese Spiele werden oft als Gale-Stewart-Spiele bezeichnet.

Bei dieser Art von Spiel gibt es zwei Spieler, oft I und II genannt , die abwechselnd natürliche Zahlen spielen, wobei I zuerst spielt. Sie spielen "für immer"; das heißt, ihre Spiele werden durch die natürlichen Zahlen indiziert. Wenn sie fertig sind, entscheidet eine vorgegebene Bedingung, welcher Spieler gewonnen hat. Diese Bedingung muss durch keine definierbare Regel spezifiziert werden ; es kann einfach eine beliebige (unendlich lange) Nachschlagetabelle sein , die angibt , wer bei einer bestimmten Spielfolge gewonnen hat.

Man betrachte formaler eine Teilmenge A des Baire-Raums ; Denken Sie daran, dass letztere aus allen ω-Folgen natürlicher Zahlen besteht. Dann im Spiel G _A , I spielt eine natürliche Zahl eine ₀ , dann II spielt eine ₁ , dann ich spielt eine ₂ , und so weiter. Dann gewinne ich das Spiel genau dann, wenn

${\displaystyle \langle a_{0},a_{1},a_{2},\ldots\rangle\in A}$

und sonst gewinnt II . A heißt dann die Auszahlungsmenge von G _A .

Es wird davon ausgegangen, dass jeder Spieler alle Züge vor jedem seiner Züge sehen kann und auch die Gewinnbedingung kennt.

Strategien

Informell ist eine Strategie für einen Spieler eine Spielweise, bei der seine Spielzüge vollständig durch die vorhergehenden Spielzüge bestimmt werden. Auch hier muss ein solcher "Weg" nicht in der Lage sein, von einer erklärbaren "Regel" erfasst zu werden, sondern kann einfach eine Nachschlagetabelle sein.

Formaler ausgedrückt ist eine Strategie für Spieler I (für ein Spiel im Sinne des vorhergehenden Unterabschnitts) eine Funktion, die als Argument jede endliche Folge natürlicher Zahlen mit gerader Länge akzeptiert und eine natürliche Zahl zurückgibt. Wenn σ eine solche Strategie ist und <a ₀ ,...,a _2n-1 > eine Folge von Spielzügen ist, dann ist σ (<a ₀ ,...,a _2n-1 >) der nächste Spielzug, den ich machen werde , wenn ich der Strategie folge σ . Die Strategien für II sind genau die gleichen, wobei "ungerade" durch "gerade" ersetzt wird.

Beachten Sie, dass wir noch nichts darüber gesagt haben, ob eine Strategie in irgendeiner Weise gut ist . Eine Strategie könnte einen Spieler anweisen, aggressiv schlechte Züge zu machen, und es wäre immer noch eine Strategie. Tatsächlich ist es nicht einmal notwendig, die Gewinnbedingung für ein Spiel zu kennen, zu wissen, welche Strategien für das Spiel existieren.

Gewinnstrategien

Eine Strategie ist gewinnend, wenn der Spieler, der ihr folgt, unbedingt gewinnen muss, egal was sein Gegner spielt. Wenn beispielsweise σ eine Strategie für I ist , dann ist σ eine Gewinnstrategie für I im Spiel G _{A ,} wenn für eine beliebige Folge natürlicher Zahlen, die von II gespielt werden soll , <a ₁ ,a ₃ ,a ₅ ,. ..>, die von σ erzeugte Spielfolge, wenn II so spielt, nämlich

${\displaystyle \langle\sigma (\langle\rangle),a_{1},\sigma (\langle\sigma (\langle\rangle),a_{1}\rangle),a_{3},\ldots\rangle }$

ist ein Element von A .

Entschlossene Spiele

Eine Spiel(e)-Spiel(e) wird bestimmt, wenn es für alle Instanzen des Spiels eine Gewinnstrategie für einen der Spieler gibt (nicht notwendigerweise derselbe Spieler für jede Instanz). Beachten Sie, dass es keine Gewinnstrategie für beide Spieler für dasselbe Spiel geben kann, denn wenn ja, könnten die beiden Strategien gegeneinander gespielt werden. Das resultierende Ergebnis wäre dann hypothetisch ein Gewinn für beide Spieler, was unmöglich ist.

Bestimmtheit aus elementaren Überlegungen

Alle endlichen Spiele mit perfekter Information, in denen kein Unentschieden stattfindet, werden bestimmt.

Spiele in der realen Welt mit perfekter Information, wie Tic-Tac-Toe , Schach oder unendliches Schach , werden immer in einer endlichen Anzahl von Zügen beendet (bei Schachspielen wird davon ausgegangen, dass die 50-Züge-Regel angewendet wird). Wenn ein solches Spiel so modifiziert wird, dass ein bestimmter Spieler unter einer Bedingung gewinnt, in der das Spiel als Unentschieden bezeichnet worden wäre, dann wird es immer bestimmt. Die Bedingung, dass das Spiel immer zu Ende ist (dh alle möglichen Erweiterungen der endlichen Stellung führen zu einem Gewinn für denselben Spieler) in einer endlichen Anzahl von Zügen entspricht der topologischen Bedingung, dass die Menge A , die die Gewinnbedingung für G _A ergibt, clopen . ist in der Topologie des Baire-Raums .

Wenn beispielsweise die Schachregeln so geändert werden, dass aus Remisen ein Gewinn für Schwarz wird, wird Schach zu einem entschlossenen Spiel. Schach hat übrigens eine endliche Anzahl von Stellungen und eine Remis-für-Wiederholung-Regel. Wenn also mit diesen modifizierten Regeln lange genug gespielt wird, ohne dass Weiß gewonnen hat, kann Schwarz schließlich einen Sieg erzwingen (aufgrund der Modifikation von Remis = Sieg für Schwarz).

Der Beweis, dass solche Spiele bestimmt sind, ist ziemlich einfach: Spieler I spielt einfach, um nicht zu verlieren ; das heißt, Spieler ich spiele , um sicherzustellen , dass Spieler II nicht eine Gewinnstrategie hat , nachdem ich‘ s bewegen. Wenn Spieler I dies nicht kann , bedeutet dies, dass Spieler II von Anfang an eine Gewinnstrategie hatte. Auf der anderen Seite, wenn der Spieler ich kann auf diese Weise spiele, dann ich muß gewinnen, denn das Spiel nach einer endlichen Anzahl von Zügen zu Ende sein wird, und Spieler mir nicht an diesem Punkt verloren haben kann.

Dieser Beweis verlangt nicht, dass das Spiel immer in endlich vielen Zügen zu Ende ist, sondern dass es immer dann in endlich vielen Zügen zu Ende ist, wenn II gewinnt. Diese Bedingung, topologisch ist, dass der Satz A wird geschlossen . Diese Tatsache – dass alle abgeschlossenen Spiele bestimmt sind – wird als Gale-Stewart-Theorem bezeichnet . Beachten Sie, dass auch alle offenen Spiele durch Symmetrie bestimmt werden. (Eine Partie ist offen, wenn ich nur gewinnen kann, indem ich in einer endlichen Anzahl von Zügen gewinne.)

Bestimmtheit von ZFC

David Gale und FM Stewart haben bewiesen, dass die offenen und geschlossenen Spiele bestimmt sind. Die Determiniertheit für die zweite Ebene der Borel-Hierarchiespiele wurde 1955 von Wolfe gezeigt. In den folgenden 20 Jahren ergaben weitere Untersuchungen mit immer komplizierteren Argumenten, dass die dritte und vierte Ebene der Borel-Hierarchie bestimmt sind.

1975 bewies Donald A. Martin , dass alle Borel- Spiele bestimmt sind; das heißt, wenn A eine Borel-Teilmenge des Baire-Raums ist, dann wird G _A bestimmt. Dieses Ergebnis, bekannt als Borel-Bestimmung , ist das bestmögliche in ZFC beweisbare Determinationsergebnis in dem Sinne, dass die Bestimmtheit der nächsthöheren Wadge-Klasse in ZFC nicht beweisbar ist.

1971, bevor Martin seinen Beweis erhielt, zeigte Harvey Friedman , dass jeder Beweis der Borelschen Determiniertheit das Ersetzungsaxiom in wesentlicher Weise verwenden muss, um das Potenzmengen-Axiom transfinit oft zu wiederholen . Friedmans Arbeit liefert ein stufenweises Ergebnis, das detailliert beschreibt, wie viele Iterationen des Powerset-Axioms notwendig sind, um die Determiniertheit auf jeder Ebene der Borel-Hierarchie zu garantieren .

Für jede ganze Zahl n beweist ZFC\P die Bestimmtheit in der n- ten Ebene der Differenzenhierarchie von Mengen, aber ZFC\P beweist nicht, dass für jede ganze Zahl n die n- te Ebene der Differenzenhierarchie von Mengen bestimmt ist. Siehe umgekehrte Mathematik für andere Beziehungen zwischen Determiniertheit und Subsystemen der Arithmetik zweiter Ordnung . ${\displaystyle \mathbf {\Pi} _{3}^{0}}$ ${\displaystyle \Pi_{3}^{0}}$

Bestimmtheit und große Kardinäle

Es besteht eine enge Beziehung zwischen Bestimmtheit und großen Kardinälen . Im Allgemeinen beweisen stärkere große Kardinal-Axiome die Bestimmtheit größerer Punktklassen , die höher in der Wadge-Hierarchie sind , und die Bestimmtheit solcher Punktklassen beweist wiederum die Existenz von inneren Modellen von etwas schwächeren großen Kardinal-Axiomen als die, die verwendet werden, um die Bestimmtheit von . zu beweisen die Punkteklasse an erster Stelle.

Messbare Kardinäle

Es folgt aus der Existenz eines messbaren Kardinals , dass jedes analytisches Spiel (auch genannt Σ ¹ ₁ Spiel) bestimmt wird , oder äquivalent , dass jeder coanalytic (oder Π ¹ ₁ ) Spiel bestimmt wird. ( Definitionen finden Sie unter Projektive Hierarchie .)

Eigentlich ist ein messbarer Kardinal mehr als genug. Ein schwächeres Prinzip — die Existenz von 0 ^# reicht aus, um koanalytische Bestimmtheit zu beweisen, und noch etwas mehr: Das genaue Ergebnis ist, dass die Existenz von 0 ^# der Bestimmtheit aller Ebenen der Differenzhierarchie unterhalb der ω ² -Ebene entspricht, dh ω·n- Π ¹ ₁ Bestimmtheit für jede . ${\displaystyle n}$

Von einem messbaren Kardinal können wir dies sehr leicht auf ω ² - Π ¹ ₁ Determiniertheit verbessern . Aus der Existenz meßbarer Kardinäle kann man die Bestimmtheit mehrerer Ebenen der Differenzhierarchie über Π ¹ ₁ beweisen .

Nachweis der Bestimmtheit durch scharfe Gegenstände

Für jede reelle Zahl r ist die Bestimmtheit äquivalent zur Existenz von r ^# . Um zu veranschaulichen, wie große Kardinäle zu Bestimmtheit führen, hier ein Beweis für die Existenz von r ^# . ${\displaystyle \Sigma_{1}^{1}(r)}$${\displaystyle \Sigma_{1}^{1}(r)}$

Sei A eine Teilmenge des Baire-Raums. A = p[ T ] für einen Baum T (konstruierbar aus r ) auf (ω, ω). (Das heißt x∈A iff von einigem y , ist ein Weg durch T .) ${\displaystyle \Sigma_{1}^{1}(r)}$${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...)}$

Gegeben ein partielles Spiel s sei der Teilbaum von T, der mit s konsistent ist, vorbehaltlich max(y ₀ ,y ₁ ,...,y _len(s)-1 )<len(s). Die zusätzliche Bedingung stellt sicher, dass sie endlich ist. Konsistenz bedeutet, dass jeder Pfad durch die Form hat, wo ein Anfangssegment von s ist . ${\displaystyle T_{s}}$${\displaystyle T_{s}}$${\displaystyle T_{s}}$${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i},y_{i}))}$${\displaystyle (x_{0},x_{1},...,x_{i})}$

Um zu beweisen, dass A bestimmt ist, definieren Sie das Hilfsspiel wie folgt:
Spieler 2 muss zusätzlich zu den gewöhnlichen Zügen eine Abbildung von in Ordinalzahlen (unterhalb einer ausreichend großen Ordinalzahl κ ) so spielen, dass ${\displaystyle T_{s}}$

• jeder neue Zug erweitert das vorherige Mapping und
• die Ordnung der Ordnungszahlen stimmt mit der Kleene-Brouwer-Ordnung am überein .${\displaystyle T_{s}}$

Denken Sie daran, dass die Kleene-Brouwer-Ordnung wie die lexikographische Ordnung ist, außer dass, wenn s richtig t erweitert, dann s < t ist . Es ist eine Wohlordnung, wenn der Baum wohlbegründet ist.

Das Hilfsspiel ist geöffnet. Beweis: Wenn Spieler 2 nicht auf einer endlichen Stufe verliert, dann ist die Vereinigung aller (das ist der Baum, der dem Spiel entspricht) begründet, und das Ergebnis des Nicht-Hilfsspiels ist also nicht in A. ${\displaystyle T_{s}}$

Somit wird das Hilfsspiel bestimmt. Beweis: Berechnen Sie durch transfinite Induktion für jede Ordinalzahl α die Menge der Positionen, bei denen Spieler 1 einen Gewinn in α-Schritten erzwingen kann, wo eine Position mit Spieler 2 zum Ziehen verliert (für Spieler 2) in α-Schritten genau dann, wenn für jeden Zug das resultierende Position verliert in weniger als α Schritten. Eine Strategie für Spieler 1 besteht darin, α mit jeder Position zu reduzieren (z. B. das kleinste α auswählen und Gleichstände durch die geringste Bewegung lösen), und eine Strategie für Spieler 2 besteht darin, die geringste (eigentlich würde jede funktionierende) Bewegung zu wählen, die nicht führt an eine Position mit einem zugewiesenen α. Beachten Sie, dass L ( r ) die Menge der Gewinnpositionen sowie die oben angegebenen Gewinnstrategien enthält.

Eine Gewinnstrategie für Spieler 2 im Originalspiel führt zu einer Gewinnstrategie im Hilfsspiel: Der der Gewinnstrategie entsprechende Teilbaum von T ist begründet, so dass Spieler 2 Ordinalzahlen nach der Kleene-Brouwer-Reihenfolge des Baumes wählen kann. Trivialerweise ergibt eine Gewinnstrategie für Spieler 2 im Hilfsspiel eine Gewinnstrategie für Spieler 2 im Originalspiel.

Es bleibt zu zeigen, dass unter Verwendung von r ^# die oben erwähnte Gewinnstrategie für Spieler 1 im Hilfsspiel in eine Gewinnstrategie im Originalspiel umgewandelt werden kann. r ^# gibt eine echte Klasse I von ( L ( r ),∈, r ) nicht unterscheidbaren Ordinalzahlen. Durch Ununterscheidbarkeit, wenn κ und die Ordnungszahlen in der Hilfsreaktion in I sind , dann hängen die Züge von Spieler 1 nicht von den Hilfszügen (oder von κ ) ab, und so kann die Strategie in eine Strategie für das ursprüngliche Spiel umgewandelt werden ( da Spieler 2 eine endliche Anzahl von Schritten mit Ununterscheidbaren aushalten kann). Angenommen, Spieler 1 verliert im ursprünglichen Spiel. Dann ist der einem Theaterstück entsprechende Baum wohlbegründet. Daher kann Spieler 2 das Hilfsspiel gewinnen, indem er Hilfszüge verwendet, die auf den Ununterscheidbaren basieren (da die Reihenfolge der Unsichtbaren die Kleene-Brouwer-Reihenfolge des Baumes überschreitet), was dem Gewinn von Spieler 1 im Hilfsspiel widerspricht.

Woodin-Kardinäle

Gibt es einen Woodin-Kardinal mit einem messbaren Kardinal darüber, dann gilt Π ¹ ₂ Bestimmtheit. Allgemeiner gesagt , wenn es n Woodin-Kardinäle mit einem messbaren Kardinal über allen gibt, dann gilt Π ¹ _n+1 Bestimmtheit. Aus Π ¹ _n+1 Bestimmtheit folgt, dass es ein transitives inneres Modell gibt, das n Woodin-Kardinäle enthält.

${\displaystyle \Delta_{2}^{1}}$(Lichtgesichts-) Bestimmtheit ist äquikonsistent mit einem Woodin-Kardinal. Wenn Determiniertheit gilt, dann erfüllt L[ x ] für einen Turing-Kegel von x (d. h. für jedes reelle x mit ausreichend hohem Turing-Grad ) die OD-Determinität (d. h. die Bestimmtheit von Spielen auf ganzen Zahlen der Länge ω und ordinal-definierbarer Auszahlung) , und in HOD ist ^{L[ x ]} ein Woodin-Kardinal. ${\displaystyle \Delta_{2}^{1}}$ ${\displaystyle \omega_{2}^{L[x]}}$

Projektive Determiniertheit

Wenn es unendlich viele Woodin-Kardinäle gibt, dann gilt projektive Determiniertheit; das heißt, jedes Spiel, dessen Gewinnbedingung eine projektive Menge ist, wird bestimmt. Aus der projektiven Bestimmtheit folgt, dass es für jede natürliche Zahl n ein transitives inneres Modell gibt, das erfüllt, dass es n Woodin-Kardinäle gibt.

Axiom der Bestimmtheit

Das Axiom der Determiniertheit oder AD besagt, dass jedes Zwei-Spieler-Spiel mit perfekter Information der Länge ω, in dem die Spieler Naturals spielen, bestimmt ist.

AD ist von ZFC nachweislich falsch; Mit dem Auswahlaxiom kann man die Existenz eines unbestimmten Spiels beweisen. Wenn es jedoch unendlich viele Woodin-Kardinäle mit einem Messbaren über allen gibt, dann ist L(R) ein Modell von ZF , das AD genügt.

Folgen der Bestimmtheit

Regularitätseigenschaften für Mengen von reellen Zahlen

Wenn A eine Teilmenge von Baire Raum , so dass das Banach-Mazur Spiel für A ermittelt wird , dann entweder II hat eine Gewinnstrategie, wobei in diesem Fall A ist mager , oder ich eine Gewinnstrategie, wobei in diesem Fall A ist comeager auf einig offene Nachbarschaft.

Dies bedeutet nicht ganz, dass A die Eigenschaft von Baire hat , aber es kommt nahe: Eine einfache Modifikation des Arguments zeigt, dass, wenn Γ eine adäquate Punktklasse ist, so dass jedes Spiel in Γ bestimmt ist, dann hat jede Menge von reellen Zahlen in Γ die Eigentum von Baire.

Tatsächlich ist dieses Ergebnis nicht optimal; indem wir das entfaltete Banach-Mazur-Spiel betrachten, können wir zeigen, dass die Bestimmtheit von Γ (für Γ mit hinreichenden Abschlusseigenschaften) impliziert, dass jede Menge von reellen Zahlen, die die Projektion einer Menge in ist, die Eigenschaft von Baire hat. So impliziert beispielsweise die Existenz eines messbaren Kardinals Π ¹ ₁ Bestimmtheit, was wiederum impliziert, dass jede Σ ¹ ₂ Menge von reellen Zahlen die Eigenschaft von Baire besitzt.

Mit dem anderen Spielen bedenkt, können wir zeigen , dass Π ¹ _n impliziert Determination , dass jeder Σ ¹ _{n + 1} Satz von reellen Zahlen die Eigenschaft Baireschen hat, ist Lebesgue meßbar (in der Tat universell messbar ) und hat die perfekte Set - Eigenschaft .

Periodizitätssätze

• Der erste Periodizitätssatz impliziert, dass für jede natürliche Zahl n , wenn Δ ¹ _{2 n +1} Bestimmtheit gilt, dann Π ¹ _{2 n +1} und Σ ¹ _{2 n +2} die Eigenschaft der Vorwell-Ordnung haben (und dass Σ ¹ _{2 n +1} und Π ¹ _{2 n + 2} haben nicht haben die prewellordering Eigenschaft, sondern die haben Trennungseigenschaft ).
• Der zweite Periodizitätssatz besagt , dass für jede natürliche Zahl n , wenn Δ ¹ _{2 n +1} Bestimmtheit gilt, Π ¹ _{2 n +1} und Σ ¹ _{2 n} die Skaleneigenschaft haben . Insbesondere wenn projektive Bestimmtheit gilt, dann hat jede projektive Relation eine projektive Uniformisierung .
• Der dritte Periodizitätssatz liefert eine hinreichende Bedingung dafür, dass ein Spiel eine definierbare Gewinnstrategie hat.

Anwendungen auf die Entscheidbarkeit bestimmter Theorien zweiter Ordnung

1969 bewies Michael O. Rabin , dass die Theorie zweiter Ordnung von n Nachfolgern entscheidbar ist . Eine Schlüsselkomponente des Beweises erfordert den Nachweis der Bestimmtheit von Paritätsspielen , die in der dritten Ebene der Borel-Hierarchie liegen .

Watsche Entschlossenheit

Wadge-Bestimmbarkeit ist die Aussage, dass für alle Paare A , B von Teilmengen des Baire-Raums das Wadge-Spiel G( A , B ) bestimmt ist. In ähnlicher Weise ist für eine Punktklasse Γ, Γ Wadge-Bestimmtheit die Aussage, dass für alle Mengen A , B in Γ das Wadge-Spiel G( A , B ) bestimmt ist.

Die Wadge-Bestimmung impliziert das semilineare Ordnungsprinzip für die Wadge-Ordnung . Eine weitere Konsequenz der Wadge-Bestimmung ist die perfekte Mengeneigenschaft .

Im Allgemeinen ist die -Wadge-Determinität eine Folge der Bestimmtheit boolescher Kombinationen von Mengen in Γ. In der projektiven Hierarchie , Π ¹ ₁ ist Wadge Determination entspricht Π ¹ ₁ Determination, wie bewiesen , Leo Harrington . Dieses Ergebnis wurde durch Hjorth erweitert , um das zu beweisen Π ¹ ₂ (Prinzip semilinearem Bestellung und in der Tat für Wadge Determiniert Π ¹ ₂ ) bereits impliziert Π ¹ ₂ Determination.

Weitere allgemeine Spiele

Spiele, bei denen die gespielten Objekte keine natürlichen Zahlen sind

Bestimmtheit von Spielen auf Ordinalzahlen mit ordinal definierbarer Auszahlung und Länge ω impliziert, dass es für jede reguläre Kardinalzahl κ >ω keine ordinaldefinierbaren disjunkten stationären Teilmengen von κ aus Ordinalzahlen der Kofinalität ω gibt. Die Konsistenzstärke der Determinationshypothese ist unbekannt, wird aber voraussichtlich sehr hoch sein.

Spiele auf Bäumen gespielt

Lange Spiele

Die Existenz von ω ₁ Woodin-Kardinälen impliziert, dass für jede abzählbare Ordinalzahl α alle Spiele auf ganzen Zahlen der Länge α und projektiver Auszahlung bestimmt sind. Grob gesagt entsprechen α Woodin-Kardinäle der Bestimmtheit von Spielen auf reellen Zahlen der Länge α (mit einer einfachen Auszahlungsmenge). Unter der Annahme eines Limits von Woodin-Kardinälen κ mit o( κ )= κ ⁺⁺ und ω Woodin-Kardinälen über κ sind Spiele mit variabler abzählbarer Länge, bei denen das Spiel endet, sobald seine Länge relativ zur Spiellinie zulässig ist, und mit projektiver Auszahlung bestimmt. Unter der Annahme, dass eine bestimmte Iterabilitätsvermutung beweisbar ist, impliziert die Existenz eines messbaren Woodin-Kardinals die Bestimmtheit offener Spiele der Länge ω ₁ und der projektiven Auszahlung. (In diesen Spielen wird eine Gewinnbedingung für den ersten Spieler in einer zählbaren Phase ausgelöst, sodass die Auszahlung als Realwert codiert werden kann.)

Bezogen auf ein Woodin-Limit von Woodin-Kardinälen und ein Messbares darüber ist es konsistent, dass jedes Spiel auf ganzen Zahlen der Länge ω ₁ und ordinal definierbarer Auszahlung bestimmt wird. Es wird vermutet, dass die Determinationshypothese mit einem Woodin-Limit von Woodin-Kardinälen äquikonsistent ist. ω ₁ ist insofern maximal, als es unbestimmte Spiele auf ganzen Zahlen der Länge ω ₁ +ω und ordinal definierbarer Auszahlung gibt.

Spiele mit unvollkommener Information

In jedem interessanten Spiel mit unvollkommenen Informationen ist eine Gewinnstrategie eine gemischte Strategie : Das heißt, sie gibt eine gewisse Wahrscheinlichkeit unterschiedlicher Reaktionen auf dieselbe Situation. Wenn die optimalen Strategien beider Spieler gemischte Strategien sind, kann das Ergebnis des Spiels nicht sicher bestimmend sein (wie es bei reinen Strategien der Fall ist , da diese deterministisch sind ). Aber die Wahrscheinlichkeitsverteilung der Ergebnisse auf gegensätzliche gemischte Strategien kann berechnet werden. Ein Spiel, das gemischte Strategien erfordert, wird als bestimmt definiert , ob eine Strategie existiert, die einen minimalen Erwartungswert (über mögliche Gegenstrategien) liefert , der einen gegebenen Wert überschreitet. Entgegen dieser Definition sind alle endlichen Nullsummenspiele für zwei Spieler eindeutig bestimmt. Die Bestimmtheit unendlicher Spiele unvollkommener Information (Blackwell-Spiele) ist jedoch weniger klar.

1969 bewies David Blackwell , dass einige "unendliche Spiele mit unvollkommener Information" (jetzt "Blackwell-Spiele" genannt) bestimmt sind, und 1998 bewies Donald A. Martin , dass die gewöhnliche (perfekte Informationsspiel) Determiniertheit für eine fett gedruckte Punktklasse die Blackwell-Determinität für die Punktklasse. Dies in Kombination mit dem Borelschen Determinationssatz von Martin impliziert, dass alle Blackwell-Spiele mit Borel-Auszahlungsfunktionen bestimmt sind. Martin vermutete, dass die gewöhnliche Bestimmtheit und die Blackwell-Bestimmung für unendliche Spiele in einem starken Sinne äquivalent sind (dh dass die Blackwell-Bestimmung für eine fett gedruckte Punktklasse wiederum die gewöhnliche Bestimmtheit für diese Punktklasse impliziert), aber bis 2010 wurde nicht bewiesen, dass die Blackwell-Bestimmung impliziert Perfekte-Informationsspiel-Bestimmtheit.

Quasistrategien und Quasidetermination

Siehe auch

• ω-Automat
• Gelöstes Spiel
• Streng entschlossenes Spiel
• Topologisches Spiel

Fußnoten

1. ^ Dies setzt voraus, dassIversucht, den Schnittpunkt der wiedergegebenen Nachbarschaften als Singleton zu erhalten, dessen eindeutiges Element ein Element vonA ist. Einige Autoren machen dies stattdessen zum Ziel für SpielerII; diese Verwendung erfordert eine entsprechende Änderung der obigen Bemerkungen.

Verweise

• Gale, David und Stewart, FM (1953). Kuhn, HW; Tucker, AW (Hrsg.). Unendliche Spiele mit perfekten Informationen . Beiträge zur Spieltheorie, Band II . Annalen der Mathematikstudien 28. Princeton University Press. S. 245–266. ISBN 9780691079356.CS1-Wartung: mehrere Namen: Autorenliste ( Link )
• Harrington, Leo (Januar 1978). "Analytische Bestimmtheit und 0#". Die Zeitschrift für symbolische Logik . 43 (4): 685–693. doi : 10.2307/2273508 . JSTOR  2273508 .
• Hjorth, Greg (Januar 1996). " Π ¹ ₂ Wattegrade" . Annalen der reinen und angewandten Logik . 77 : 53–74. doi : 10.1016/0168-0072(95)00011-9 .
• Jech, Thomas (2002). Mengenlehre, dritte Jahrtausendausgabe (überarbeitet und erweitert) . Springer. ISBN 978-3-540-44085-7.
• Martin, Donald A. (1975). "Borel-Bestimmung". Annalen der Mathematik . Zweite Serie. 102 (2): 363–371. doi : 10.2307/1971035 . JSTOR  19711035 .
• Martin, Donald A. und John R. Steel (Jan. 1989). „Ein Beweis der projektiven Bestimmtheit“ . Zeitschrift der American Mathematical Society . 2 (1): 71–125. doi : 10.2307/1990913 . JSTOR  1990913 .
• Moschovakis, Yiannis N. (1980). Deskriptive Mengenlehre . Nordholland. ISBN 978-0-444-70199-2.
• Woodin, W. Hugh (1988). „Superkompakte Kardinäle, Mengen von reellen Zahlen und schwach homogene Bäume“ . Proceedings of the National Academy of Sciences of the United States of America . 85 (18): 6587–6591. Bibcode : 1988PNAS...85.6587W . doi : 10.1073/pnas.85.18.6587 . PMC  282.022 . PMID  16593979 .
• Martin, Donald A. (2003). „Ein einfacher Beweis, dass Determiniertheit Lebesgue Messbarkeit impliziert“. Zerreißen. Sem. Matte. Univ. Pol. Turin . 61 (4): 393–399. ( PDF )
• Wolfe, P. (1955). "Die strikte Bestimmtheit gewisser unendlicher Spiele" . Pacific J. Math . 5 (5): Ergänzung I:841–847. doi : 10.2140/pjm.1955.5.841 .

Externe Links

• "Large Cardinals and Determinacy" in der Stanford Encyclopedia of Philosophy