Determinacy
Sommersemester 2025
Universität Hamburg
Fachbereich Mathematik

Infinite two-player perfect information games are connected to many topics in the foundations of mathematics: central concepts from analysis and topology can be reformulated in game-theoretic terms using infinite two-player perfect information games. Examples are the concepts of Lebesgue measurability, the property of Baire, as well as the perfect set property.

The central game-theoretic notion is the concept of determinacy: the full axiom of determinacy $\mathsf{AD}$ (“all infinite two-player perfect information games with natural number moves are determined”) contradicts the axiom of choice $\mathsf{AC}$, but definable fragments of $\mathsf{AD}$ can be proved in $\mathsf{ZFC}$ or extensions of $\mathsf{ZFC}$. The axiom of determinacy itself yields an interesting alternative foundations of mathematics.

We shall treat a selection of the following topics:

• Basic theory of determinacy. Applications in topology and measure theory. Incompatibility of $\mathsf{AC}$ and $\mathsf{AD}$. Basics of descriptive set theory: the Borel hierarchy and the projective hierarchy. Periodicity Theorems.
• Proving determinacy. Open determinacy. Low-level Borel games. Borel determinacy. Proving determinacy from large cardinals. Introduction to large cardinals: inaccessible cardinals and measurable cardinals. Proving $\Pi^1_1$-determinacy from a measurable cardinal.
• The axiom of determinacy. Combinatorial consequences: $\aleph_1$ and $\aleph_2$ are measurable. Infinite exponent partition relations.
• Stronger axioms of determinacy. The axiom of real determinacy. Inconsistent extensions of the axiom of determinacy. Long games.
• The Wadge hierarchy. Definition and structure theory of the Wadge hierarchy under $\mathsf{AD}$.

Vorlesung I: 10. April 2025. Geom H5.
Einleitung. Begriff der Determinierheit. Abgrenzung zur Spieltheorie (Modellieren rationalen Verhaltens). Besondere Eigenschaften der mengentheoretischen Spiele. Beispiel: Matching Game.
§1. Definitionen. Zugmenge, Spielverlauf, Positionen, Länge einer Position, Auszahlungsmenge, Gewinn, Verweben von Folgen, Strategien, Gewinnstrategien, Strategien mit verbundenen Augen. Äquivalenz von Gewinn und Gewinn gegen Gegner mit verbundenen Augen. Bäume, Wurzel, Konkatenation, Verzweigungspunkt, perfekte Bäume, Äste. Die Menge der Äste durch einen perfekten Baum hat mindestens Kardinalität $2^{\aleph_0}$. Strategien als Bäume. Eine Menge, für die I eine Gewinnstrategie hat, muß Kardinalität mindestens $2^{\aleph_0}$ haben. Für abzählbare Mengen hat II eine Gewinnstrategie.
Vorlesungsnotizen.

Vorlesung II: 17. April 2025. Geom H5.
Für Mengen mit Kardinalität $<2^{\aleph_0}$ hat Spieler II eine Gewinnstrategie. Kardinalität nicht-determinierter Mengen. Spiele mit Regeln. Regelbäume.
§2. Nicht-determinierte Mengen. Bernsteinfolgen. Bernsteinmengen. Der Satz von Bernstein. Anwendung: Existenz einer überabzählbaren Menge ohne perfekte Teilmenge. Historischer Hintergrund: Versuche, die Kontinuumshypothese über die Existenz von perfekten Teilmengen zu beweisen. Anwendung: Existenz einer nicht-determinierten Menge. Das Axiom der Determinierheit als Alternative zum Auswahlaxiom.
§3. Satz von von Neumann. Endliche Spiele. Rückwärtsinduktion. Färbungen von Bäumen. Beweis des Satzes von von Neumann.
Vorlesungsnotizen.

Vorlesung III: 24. April 2025. Geom H5. §4. Spiele mit endlichem Horizont. Spiele mit endlichem Horizont. Rekursive Definition einer Färbung in $\omega$ Schritten. Beispiel eines Spiels, bei dem diese Definition keine totale Funktion ergibt. Transfinite rekursive Definition. Alle Spiele mit endlichem Horizont sind determiniert: farberhaltende Strategien sind Gewinnstrategien.
§5. Satz von Gale und Stewart. Mengen mit halbendlichem Horizont. Beispiel eines Spiels, bei dem es farberhaltende Strategien gibt, die keine Gewinnstrategien sind. Der Rang einer Position. Alle Spiele mit halbendlichem Horizont sind determiniert: Farberhaltende und rangreduzierende Strategien sind Gewinnstrategien.
Vorlesungsnotizen.

Keine Vorlesung: 1. Mai 2025 (Maifeiertag).

Vorlesung IV: Mittwoch, 7. Mai 2025. (Achtung: Sondertermin!) Zoom. §6. Der Baire-Raum. Metrik auf dem Raum der Spielverläufe. Der Cantor-Raum und der Baire-Raum. $\varepsilon$-Kugeln, offene Mengen, Konvergenz, abgeschlossene Mengen. Baumrepräsentation von abgeschlossenen Mengen. Charakterisierung der Mengen mit halboffenen Horizont.
§7. Ein Überblick über höhere Determiniertheit. Mengen, die weder offen noch abgeschlossen sind. Abzählbare Vereinigungen: $\mathrm{F}_\sigma$- und $\mathrm{G}_\delta$-Mengen. Die Borel-$\sigma$-Algebra und ihre untersten Stufen. Determiniertheitsergebnisse für $\mathrm{F}_\sigma$-Mengen und $\mathrm{G}_{\delta\sigma}$-Mengen (ohne Beweis). Friedman's beweistheoretischer Unmöglichkeitssatz (ohne Beweis). Borel-Determiniertheit (ohne Beweis).
§8. Anwendungen I: die perfekte Mengeneigenschaft. Erinnerung an Bernstein-Mengen und nicht-determinierte Mengen. Die perfekte Mengeneigenschaft. $\mathsf{PSP}$ und die Kontinuumshypothese.
Vorlesungsnotizen.

Keine Vorlesung: 15, Mai 2025.

Vorlesung V: 22. Mai 2025. Zoom. Satz von Cantor-Bendixson (ohne Beweis). Hat jede oder zumindest jede Borel-Menge die perfekte Mengeneigenschaft? Bernsteinmengen haben nicht die perfekte Mengeneigenschaft. Satz von Hausdorff: Borel-Mengen haben die perfekte Mengeneigenschaft. Das perfekte oder asymmetrische Spiel. Spielcharakterisierung der perfekten Mengeneigenschaft. Stetigkeit der Kodierungsfunktion.
§9. Anwendungen II. Die Baire-Eigenschaft und Lebesgue-Meßbarkeit und ihre Spielcharakterisierungen (ohne Definitionen und Beweise). Die Rolle des Auswahlaxioms.
Vorlesungsnotizen.

Keine Vorlesung: 29. Mai 2025 (Himmelfahrt).

Lecture VI: 5 June 2025. Zoom. Filter und Ultrafilter. Fréchetfilter. Triviale Ultrafilter sind Borel. Ultrafilter, die den Fréchetfilter erweitern, sind nicht Borel. Strategiediebstahl: Nash und Hex. Das Ultrafilterspiel: Strategien, welche die Disjunktheitsregel respektieren; komplementäre Strategien. Strategiediebstahl für das Ultrafilterspiel. Ultrafilter und Lebesgue-Meßbarkeit. Flippmengen. Das Auswahlaxiom impliziert, daß Flippmengen existieren, aber sie können nicht Borel sein (ohne Beweis).
Vorlesungsnotizen.

Lecture VII: 12 June 2025. Zoom. Beweis: Das Auswahlaxiom impliziert, dass Flippmengen existieren. Das Banach-Mazur-Spiel. Das Banach-Mazur-Spiel für eine Flippmenge ist nicht determiniert.
§10. Reduktionen und Komplexität. Strukturerhaltende Abbildungen. Reduktion durch strukturerhaltende Abbildungen. Die Reduktionsrelation ist reflexiv und transitiv. Präordnungen. Die assoziierte Äquivalenzrelation einer Präordnung. Die Äquivalenzklassen einer Präordnung sind partiell geoordnet. Beispiele: stetige Reduktionen, Borel-Reduktionen, berechenbare Reduktionen, polynomiell berechenbare Reduktionen.
Vorlesungsnotizen.

Lecture VIII: 19 June 2025. Zoom. Die Mengen $\varnothing$ und $X$ sind unvergleichbar und minimal. Nach unten abgeschlossene Mengen und Kegel. Zusammenhang zwischen der Größe der Menge der Funktionen und Kegeln.
§11. Stetige Funktionen in Cantor- und Baire-Raum. Approximationen. Das Bestimmen von Werten einer Funktion. Charakterisierung der stetigen Funktionen durch Approximationen. Das Funktions-Spiel. Charakterisierung der stetigen Funktionen durch das Funktions-Spiel.
Vorlesungsnotizen.

Lecture IX: 26 June 2025. Zoom.

Lecture X: 3 July 2025. Zoom.

Lecture XI: 10 June 2025. Geom H5.

Lecture XII: 17 June 2025. Geom H5.