A determinacy theorem proved using Martin's Axiom at the first uncountable cardinal
- Speaker(s)
- Matteo Mio
- Affiliation
- Centre for Mathematics and Computer Science, Amsterdam
- Date
- Nov. 6, 2013, 4:15 p.m.
- Room
- room 5050
- Seminar
- Topology and Set Theory Seminar
Two players games of infinite duration (Gale-Stewart games) have
come to play an important role in Computer Science. A
game, typically played on a graph representing the state-to-state
transitions of a program, is constructed in such a way that Player I
wins if and only if the program exhibits good behavior against any
potentially malicious interaction with an hostile environment
(represented by Player II). Several variants of Gale-Stewart games
(e.g., incorporating probabilistic choices) have been studied to model
larger classes of problems.
In
this talk I will discuss a novel class of games which I introduced in
my PhD thesis. Interestingly, the Determinacy theorem is proven in
ZFC+MA_\aleph_1. I will also report on recent attempts, explored with Henryk Michalewski and PhD students Tomek Gogacz and Michał Skrzypczak, to prove the result in ZFC alone.