MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is related to a previous question of mine:

Determinacy interchanging the roles of both players

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.

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

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:

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.

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

This leaves us with the following possible situations:

(I'd draw a table here, but unfortunately I don't know how to edit it; I tried html without sucess)

  1. W for I and L for II
  2. L for I and W for II
  3. N for I and N for II
  4. N for I and WL for II
  5. N for I and WN for II
  6. N for I and LN for II
  7. N for I and WLN for II
  8. WL for I and N for II
  9. WN for I and N for II
  10. WN for I and LN for II
  11. LN for I and N for II
  12. LN for I and WN for II
  13. WLN for I and N for II

My question is, could one find examples (prove the existence of subsets of sequences of naturals) for each situation only assuming ZFC?

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.

share|cite|improve this question
If I'm getting this correctly, the set of periodic sequences is an example for 12. (Thus non-periodic leads to 10.) If only the odd-position subsequences are required to be periodic, it will be 13 instead (7 for even-position subsequences). 3, 6, and 11, if provable, require the axiom of choice, since AD would rule them out (assuming ZFC+AD is consistent). – Sebastian Reichelt Jul 28 '10 at 22:38
Oops, I meant ZF+AD, of course. – Sebastian Reichelt Jul 29 '10 at 6:26
up vote 7 down vote accepted

4 is not possible, the others that you list are.

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 Determinacy interchanging the roles of both players

$1$. (and equivalently 2). As you said, taking $A=\omega^\omega$ works.

$3$. Can be done in ZFC.

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

$5$. (and equivalently 6). Can be done in ZFC.

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

$8$. Take $A=\{x\in\omega^\omega:x(0)=0\}$.

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

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

$13$. Take $A=\{x\in\omega^\omega:x(0)=0\}\cup\{x\in\omega^\omega:x(0)=1,x(1)=0\}$.

share|cite|improve this answer
provably (in ZF). The simple argument I give for 4 shows that. – Justin Palumbo Jul 29 '10 at 19:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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