The determinacy of context-free games. (English) Zbl 1349.03038

Finkel, Olivier

J. Symb. Log. 78, No. 4, 1115-1134 (2013).

Summary: We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of \(\omega\)-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton \(\mathcal {A}\) and a Büchi automaton \(\mathcal {B}\) such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game \(W(L(\mathcal {A}), L(\mathcal {B}))\); (2) There exists a model of ZFC in which the Wadge game \(W(L(\mathcal {A}), L(\mathcal {B}))\) is not determined. Moreover these are the only two possibilities, i.e., there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game \(W(L(\mathcal {A}), L(\mathcal {B}))\).

MSC:

03D05	Automata and formal grammars in connection with logical questions
03E15	Descriptive set theory
03E60	Determinacy principles
91A44	Games involving topology, set theory, or logic