2
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – J. Smith May 29 '18 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.