Algebra Seminar talk
2022-07-01
Mira Tartarotti
Borel Determinacy
Abstract:
An infinite game is played between two players (I and II), who take turns making moves. Each move is an element of a fixed set A. After infinitely many moves have been played, the game ends and the result is an infinite sequence in $A$, the history of all played moves. Player I has won the game if this infinite sequence is in a pre-defined set $X\subseteq A^\omega$, called the payoff set.
We call such a game determined if one of the players has a winning strategy.
In the first part of the talk (10:15-11:45), I will give an introduction to these games, as well as so-called "game with rules". Finally, I will present a proof of the determinacy of all games with closed or open payoff sets.
For the second part of the talk (13:30-15:00), I will present a proof of the determinacy of Borel games (games with Borel payoff sets), using transfinite induction over the Borel hierarchy, by showing that all Borel games can be, in some sense, reduced to games with clopen payoff sets. The most difficult part of this proof and main part of the talk will be the base step of the induction.
The proof I will present is from the 1985 paper "A Purely Inductive Proof of Borel Determinacy" by Donald A. Martin.