# Gale-Stewart game

Let's look at the Gale-Stewart game on $\mathbb N^{\mathbb N}$ space (it consists of infinite sequences of natural numbers). There are 2 players: $A$ and $B$. They write one natural number by turns (A begins). We also have set $C\subset \mathbb N^{\mathbb N}$. If the infinite sequence $\omega$, which players got during the game, is in $C$, the player $A$ wins, in other case the player $B$ is winner. The Gale-Stewart theorem shows that every open set is determined. But what about examples? Which player has winning strategy in special cases? For example, if $C$ is finite ($C=\{c_1, c_2, \dots, c_n\}$), than player $B$ has a winning strategy. On his $k$-th turn he should write natural number $t$, such as the $k$-th number in $a_k$ is not equal to $t$. Then he will win in $2n$ turns. What if $C$ is a countable set? Which other special cases exist? I know the fact that the first player can win only if cardinality of $C$ is continuum. At what set $C$ player $A$ can win? Thanks for help.

• If $C$ is countable, you can construct a winning strategy for $B$ by a diagonal argument. – Michael Greinecker May 29 '18 at 11:55

First of all, note that strictly speaking you've left the realm of the Gale-Stewart theorem since no (nonempty) finite or countable subsets of $\mathbb{N}^\mathbb{N}$ are open. There are however theorems extending the Gale-Stewart theorem, which prove determinacy for broader classes of games - the big one of course being Borel determinacy. And determinacy can be pushed even further under set-theoretic assumptions. In particular, countable sets are $\Sigma^0_2$ (or $F_\sigma$), and all $\Sigma^0_2$ games are determined.

As to your specific question: if $C$ is countable, $B$ wins in the same way they do if $C$ is finite: writing $C=\{c_i: i\in\mathbb{N}\}$, have player $B$ on their $n$th turn play a number not equal to the $2n$th bit of $c_n$.

• Yes, thanks. I know that my example doesn't go under the realm of the Gale-Stewart theorem, but I'm interested in some certain examples. Thank you for answer. As I understand it is easy to show that if $C$ is a set of points Cantor set, which a written in ternary numeral system, than it is easy win for $B$. He only has to write 1 one time. Are there any more special cases? When does the player $A$ wins? – J. Smith May 29 '18 at 12:32