Subsets of sequences of natural numbers vs. strategies under ZFC - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T07:07:42Z http://mathoverflow.net/feeds/question/33706 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33706/subsets-of-sequences-of-natural-numbers-vs-strategies-under-zfc Subsets of sequences of natural numbers vs. strategies under ZFC Marc Alcobé García 2010-07-28T20:09:52Z 2010-07-29T01:17:18Z <p>This question is related to a previous question of mine:</p> <p><a href="http://mathoverflow.net/questions/32966/determinacy-interchanging-the-roles-of-both-players" rel="nofollow">http://mathoverflow.net/questions/32966/determinacy-interchanging-the-roles-of-both-players</a></p> <p>Given any set A of sequences of natural numbers, every strategy (no matter for which player) is either winning (W), or losing (L), or neither(N) for A.</p> <p>So depending on A, the set of all strategies available for any of both players can be, a priori, of any of the seven kinds: W (all winning), L (all losing), N (all neither), WL (some winning and the rest losing), WN (some winning and the rest neither), LN (some losing and the rest neither) and WLN (some winning, some losing, and the rest neither).</p> <p>This makes a total of 49 situations (now taking into account both players). Of course, not all of them are possible because we have the following restrictions:</p> <p>a. If one player has a winning (losing) strategy, the other one cannot have a winning (losing) strategy. b. If one player has only winning (losing) strategies, the other one only has losing (winning) strategies.</p> <p>I don't know of any other restrictions (not derivable from them, for example it follows that if one player is WL for A, the other one can only be N).</p> <p>This leaves us with the following possible situations:</p> <p>(I'd draw a table here, but unfortunately I don't know how to edit it; I tried html without sucess)</p> <ol> <li>W for I and L for II</li> <li>L for I and W for II</li> <li>N for I and N for II</li> <li>N for I and WL for II</li> <li>N for I and WN for II</li> <li>N for I and LN for II</li> <li>N for I and WLN for II</li> <li>WL for I and N for II</li> <li>WN for I and N for II</li> <li>WN for I and LN for II</li> <li>LN for I and N for II</li> <li>LN for I and WN for II</li> <li>WLN for I and N for II</li> </ol> <p>My question is, could one find examples (prove the existence of subsets of sequences of naturals) for each situation only assuming ZFC?</p> <p>Some are obvious, like the empty set for 2 or the set of all sequences for 1, or like the set of all sequences with a 1 in the odd positions for 8, but others may be not.</p> http://mathoverflow.net/questions/33706/subsets-of-sequences-of-natural-numbers-vs-strategies-under-zfc/33728#33728 Answer by Justin Palumbo for Subsets of sequences of natural numbers vs. strategies under ZFC Justin Palumbo 2010-07-28T22:58:04Z 2010-07-28T22:58:04Z <p>4 is not possible, the others that you list are.</p> <p>By observing that a strategy is winning for player X in the game $G(A)$ if and only if it is losing for X in $G(A^c)$ we can reduce the total number of games necessary to construct by noting some equivalences. For example, if there is a game of the form 5, then by taking the complement we get a game of the form 6. This also tells us that games for 3,5,6,9,11 cannot be constructed in ZF alone since they (are equivalent to) games where neither player has a winning strategy. The others (not 4) can be realized by simple games that can be described in ZF. I'll describe these simple games below. Those that require some choice I'll just indicate it; the diagonalization is no harder than the one described at <a href="http://mathoverflow.net/questions/32966/determinacy-interchanging-the-roles-of-both-players" rel="nofollow">http://mathoverflow.net/questions/32966/determinacy-interchanging-the-roles-of-both-players</a></p> <p>$1$. (and equivalently 2). As you said, taking $A=\omega^\omega$ works.</p> <p>$3$. Can be done in ZFC.</p> <p>$4$. Not possible. Suppose $G(A)$ were such a game. Let $\tau_0$ be a winning strategy for II, and $\tau_1$ a losing strategy. Consider the strategy $\tau$ where when I plays 0, II follows $\tau_0$, and otherwise II follows $\tau_1$. Then $\tau$ falls under the neither category.</p> <p>$5$. (and equivalently 6). Can be done in ZFC.</p> <p>$7$. Take $A$ to be $\{x\in\omega^\omega:x(1)=0\}$ (an example of a neither strategy for II: respond to 0 with 0, respond to 1 with 1).</p> <p>$8$. Take $A=\{x\in\omega^\omega:x(0)=0\}$.</p> <p>$9$. (and equivalently 11). This can be done in ZFC (in fact you can check a game in which I has a winning strategy. and the complementary game is not determined is necessarily of this form, so existence here follows from the earlier question).</p> <p>$10$. (and equivalently 12). Take $A=\{x\in\omega^\omega:x(0)\not=0\}\cup\{x\in\omega^\omega:x(0)=0,x(1)=0\}$. (IIs losing strategy is to always play 0)</p> <p>$13$. Take $A=\{x\in\omega^\omega:x(0)=0\}\cup\{x\in\omega^\omega:x(0)=1,x(1)=0\}$.</p>