7
$\begingroup$

Given a set $A \subseteq \omega^\omega$, let $G_A$ denote the Gale-Stewart game with payoff set $A$ (so player $I$ wants the real built over the course of play to be in $A$ and player $II$ wants it not to be). Notice that the set of (not necessarily winning) strategies for player $I$ is simply the set of functions mapping finite sequences of natural numbers of even length to $\omega$ and the set of (not necessarily winning) strategies for $II$ is the same with "even" replaced by "odd". Thus, via some coding, in both cases if we wanted to, we could think of these sets as homeomorphic copies of Baire space itself. Now suppose that $A$ is determined for one of the players, say $I$. Then in the space of strategies for $I$, let $W(A)$ be the set of winning strategies. My question is about the relationship between the topological complexity of $A$ and $W(A)$.

Let me give a few naive examples to motivate what I mean. First, let $A = \omega^\omega$. In this case, not only does $I$ have a winning strategy for $G_A$ but of course any strategy that $I$ plays is winning. Therefore in this case $A \cong W(A) \cong \omega^\omega$. A (very) slightly less trivial example is as follows. Let $n \in \omega$ and let $U_n$ be the basic open set of all sequences whose first element is $n$. Then of course $I$ wins $G_{U_n}$ and the set $W(A)$ is the basic open set of all strategies whose first move is $n$. Therefore again $A$ and $W(A)$ have the same topological complexity. My main question is whether these naive examples are simply naive, or whether there is a general theorem to be mined from it.

Question 1: Is there a general theorem dictating the relationship between the topological complexity of $A$ and $W(A)$? What about if we restrict the possible $A$'s to "nice" sets (e.g. the Borels)?

Of course similar a similar question can be asked for measure:

Question 2: Is there a general theorem dictating the relationship between the measure theoretic properties of $A$ and $W(A)$? For instance, if $A$ is measurable, then is $W(A)$? What about the converse? Can one of $A$ and $W(A)$ be null and the other have positive measure?

I'm thinking of these questions in the context of ZFC but given the relationship between determinacy and inner model theory I would also be interested to hear if anything more interesting happens if we assume large cardinals or axioms related to games such as $AD^{L(\mathbb R)}$.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Corey, one issue is that it can happen that huge parts of $A$ do not matter for the purpose of $W(A)$; for example, perhaps if player I starts with $6$, it is a bad move, since II can reply $7$ and thereby definitely win, but meanwhile the rest of $A$ extending $7$ apart from this can be essentially arbitrary, without affecting $W(A)$, since a winning strategy for I will never have her start with $7$. Perhaps this idea can be turned into a counterexample for question 2. $\endgroup$
    – Joel David Hamkins
    Commented Jan 12, 2018 at 21:36
  • $\begingroup$ I think I see conceptually what you mean, but can you explain a little more for how $A$ can be arbitrary without affecting $W(A)$? Couldn't having $A$ be arbitrary allow $W(A)$ to be so as well? $\endgroup$
    – Corey Bacal Switzer
    Commented Jan 12, 2018 at 21:53
  • $\begingroup$ I mean that in the neighborhood of (6,5), say, we can make nearly arbitrary changes to $A$ without affecting $W(A)$ at all, since player I never wants to play $6$, since $(6,7)$ is winning for II, and if player I does play $6$, then player II should play $7$. For truly arbitrary changes, we should do a similar thing again, giving the other player a chance to win, and then make arbitrary changes in the neighborhood of $(6,5,2)$, say. $\endgroup$
    – Joel David Hamkins
    Commented Jan 12, 2018 at 22:03
  • 1
    $\begingroup$ The larger point is that there can be huge regions of $A$ that do not affect strategic thinking, because of how they sit in the game space. Winning strategies would never enter that region, since in order to do so, they'd have to open themselves to a win for the opponent in order to get there. $\endgroup$
    – Joel David Hamkins
    Commented Jan 12, 2018 at 22:07

1 Answer 1

Reset to default
3
$\begingroup$

Abstractly, $W(A)$ is of the form $\forall^{\mathbb R} A \vee \forall^{\mathbb R} \lnot A$; in fact, if $I$ has a winning strategy for $A$, then $W(A)$ is $\forall^{\mathbb R} A$, and if $II$ has a winning strategy for $A$, then $W(A)$ is $\forall^{\mathbb R} \lnot A$. As Joel points out, though, $W(A)$ may be of much simpler complexity than $A$, as $A$ may contain some irrelevant "noise," e.g. $A$ may contain a copy of a Vitali set even though $A$ is determined, so like in most other cases of descriptive set theory it should be a question concerning pointclasses rather than individual sets. For example we now have that if $A$ is Borel, then $W(A)$ is coanalytic, if $A$ is $\Pi^1_n \cup \Sigma^1_n$, then $W(A)$ is $\Pi^1_{n+1}$ or even $\Pi^1_n$, etc. Does this answer your Question 1?

Concerning your Question 2, all coanalytic sets are Lebesgue measurable, so we get that $W(A)$ is always Lebesgue measurable if $A$ is Borel; also, if all $\Pi^1_n$ sets are determined, then all $\Pi^1_{n+1}$ sets are Lebesgue measurable, so that from this hypothesis we get that $W(A)$ is always Lebesgue measurable if $A$ is $\Pi^1_n$. But as above, $W(A)$ can be pretty simple even though $A$ itself is not contained in a model of determinacy, so there is no converse here. Finally, if $A$ is null, then $W(A)$ is null by Fubini; again, no converse here.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is great thanks! One follow up question: given Joel's comment about "noise" and your observation using Fubini, can one show more generally that if $\mu$ is Lebesgue measure then $\mu(W(A)) \leq \mu (A)$ (assuming we have measurability)? $\endgroup$
    – Corey Bacal Switzer
    Commented Jan 17, 2018 at 19:51
  • $\begingroup$ My last sentence was foolish. $\emptyset$ is null, but $W(\emptyset)={\mathbb R}$ is not null. What I meant was that if $A$ is null and $I$ wins $A$, then $W(A)$ is null. The proof of this seems to be straightforward using that if $A$ is null, then $\{ (\sigma,x) : \sigma * x \in A \}$ is null. $\endgroup$
    – Ralf Schindler
    Commented Jan 18, 2018 at 9:56
  • $\begingroup$ More generally, $A \subset {\mathbb R}$ and $B = \{ (\sigma,x) : \sigma * x \in A \} \subset {\mathbb R}^2$ have the same Lebesgue measure, but if $\sigma$ is a w.s. for $I$, then $\{ \sigma \} \times {\mathbb R} \subset B$, and then $\mu(W(A)) \leq \mu(A)$. $\endgroup$
    – Ralf Schindler
    Commented Jan 18, 2018 at 10:06
  • $\begingroup$ A related interesting question, BTW, is: how may we pick an element from $W(A)$? More precisely: assume $\Gamma$ is a given determined pointclass, $\Gamma^* \supset \Gamma$, and $A \in \Gamma$, may we pick a w.s. $\sigma$ for $A$ s.t. $\{ \sigma \} \in \Gamma^*$? This of course only makes sense for lightface pointclasses. E.g., if $A$ is lightface $\Pi^1_1$, then there is a w.s. which is recursive in $0^\#$, i.e., in this case we may take $\Gamma^* =$ lightface $\Delta^1_3$. Etc. $\endgroup$
    – Ralf Schindler
    Commented Jan 18, 2018 at 10:28
  • $\begingroup$ Thanks! Could we also think of this question in terms of selectors? What I mean is if $\Gamma$ is a given determined point class, what can we say about the complexity of a "winning strategy selector" for $\Gamma$? That is, a relation $R \subseteq \Gamma \times \omega^\omega$ such that for each $A \in \Gamma$ there is exactly one $x \in \omega^\omega$ such that $ARx$ and $x$ codes a winning strategy for $A$. In the example you gave it seems that using the universal Turing machine with $0^\sharp$ as an oracle one could construct such a selector with complexity lightface $\Delta^1_3$. $\endgroup$
    – Corey Bacal Switzer
    Commented Jan 19, 2018 at 17:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .