You are not logged in | Log in

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
Language of the talk
English
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.