In the proof that there is a payoff set $X$ such that the Gale-Stewart game is not determined(see here, Proposition 3.1.). enter image description here

I don't know why $X$, the set of all outcomes generated by a fixed strategy of one player, constitutes a perfect set. I can see it's true, if the fixed strategy is a constant function. The trouble for me is why it's true in general.


Suppose that Player I uses the strategy $\sigma:\bigcup_{n\in\omega}{}^{2n}\{0,1\}\to\{0,1\}$. A game $\alpha=\langle \alpha_k:k\in\omega\rangle$ is possible iff $\alpha_{2k}=\sigma(\alpha\upharpoonright 2k)$ for each $k\in\omega$. Let $A$ be the set of possible games.

Clearly $A\ne\varnothing$. Suppose that $\alpha=\langle \alpha_k:k\in\omega\rangle\in A$. For $n\in\omega$ let $$B_n(\alpha)=\left\{\beta\in{}^\omega\{0,1\}:\beta\upharpoonright 2n=\alpha\upharpoonright 2n\right\}\;,$$ and let $$V_n(\alpha)=\{\beta\in B_n(\alpha):\beta_{2n+1}\ne\alpha_{2n+1}\}\;.$$

Then $V_n(\alpha)\cap A\ne\varnothing$, so choose $\beta^n\in V_n(\alpha)\cap A$. Clearly $\beta^n\in B_n(\alpha)\setminus\{\alpha\}$, and $\{B_n(\alpha):n\in\omega\}$ is a nbhd base at $\alpha$, so $\left\langle\beta^n:n\in\omega\right\rangle$ is a sequence in $A\setminus\{\alpha\}$ converging to $\alpha$, and $\alpha$ is not an isolated point of $A$. This shows that $A$ is dense-in-itself.

Finally, suppose that $\left\langle\alpha^n:n\in\omega\right\rangle$ is a convergent sequence in $A$ with limit $\alpha\in{}^\omega\{0,1\}$. Then for each $n\in\omega$ there is an $m\in\omega$ such that $\alpha^k\upharpoonright n=\alpha\upharpoonright n$ for each $k\ge m$; it follows that $\alpha_{2k}=\sigma(\alpha\upharpoonright 2k)$ for each $k\in\omega$ and hence that $\alpha\in A$, so $A$ is closed.

The argument for the case in which Player II’s strategy is fixed is entirely similar.

  • $\begingroup$ Perhaps mentioning that the set $A$ is just a copy of Cantor's set may further clarify the matter. $\endgroup$ – Andrés E. Caicedo Apr 5 '13 at 0:20
  • $\begingroup$ Thank you as always,sir. Hope you don't mind a quesion about notation. What is the difference between ${}^\omega\{0,1\}$ and $\{0,1\}^{\omega}$? $\endgroup$ – Metta World Peace Apr 5 '13 at 3:14
  • 1
    $\begingroup$ @MettaWorldPeace: You’re welcome. As for the notation, like some others with a set-theoretic background, I tend to use ${}^AB$ for the set of functions from $A$ to $B$. It didn’t really matter here, but had I written $2$ instead of $\{0,1\}$, it would have avoided a potential ambiguity: $2^\omega$ is the cardinal number, ${}^\omega2$ the set of functions. $\endgroup$ – Brian M. Scott Apr 5 '13 at 3:54

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.