Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let me refer to Jech's "Set Theory" Chap. 33 Determinacy:

"With each subset A of $\omega^\omega$ we associate the following game $G_A$, played by two players I and II. First I chooses a natural number $a_0$, then II chooses a natural number $b_0$, then I chooses a1, then II chooses b1, and so on. The game ends after $\omega$ steps; if the resulting sequence $<a_0, b_0, a_1, b_1, ...>$ is in A, then I wins, otherwise II wins.

A strategy (for I or II) is a rule that tells the player what move to make depending on the previous moves of both players. A strategy is a winning strategy if the player who follows it always wins. The game $G_A$ is determined if one of the players has a winning strategy.

The Axiom of Determinacy (AD) states that for every subset A of $\omega^\omega$, the game $G_A$ is determined."

Now, there is some apparent lack of symmetry in the definition of the $G_A$ game: the player who plays first (I) attempts for a sequence in A.

What happens if we interchange the roles of both players? I. e. if we let the player who plays first attempt for a sequence not in A? Let us call this game $G'_A$

Is it the case that for every subset A, A is determined wrt $G_A$ iff A is determined wrt $G'_A$?

share|improve this question
1  
In what axiom system are you asking this question? The game $G'_A$ is just the standard game played on $\omega^\omega \backslash A$, so under Determinacy this is trivially true. –  Oliver Jul 22 '10 at 16:34
    
I forgot to mention it. In ZFC. –  Marc Alcobé García Jul 23 '10 at 7:11

2 Answers 2

up vote 6 down vote accepted

The answer is no. The game $G'(A)$ you describe is just the same as the complementary game $G(A^c)$ from I's point of view. So the question is: if one of the players has a winning strategy in $G(A)$, does one of the players have a winning strategy in $G(A^c)$? Using AC one can construct a set $A$ for which this is not the case.

We do a recursive construction, much as in the usual recursive construction of a nondetermined set. The main difference is set out in advance a strategy $\sigma$ for I to be a winning strategy for $A$. Fix any strategy $\sigma$ for I (so it takes a finite sequences of even length as input and gives natural numbers as output). For a given infinite sequence $y$ of moves for II we let $\sigma*y$ denote the member of $\omega^\omega$ resulting when I follows $\sigma$ and II plays out $y$.

Set $Z=\{\sigma*y:y\in\omega^\omega\}$. We will make sure $Z\subseteq A$, then certainly $\sigma$ will be a winning strategy for I in $G(A)$.

So we also define $\langle a_\alpha\rangle_{\alpha<2^\omega}$ and $\langle b_\alpha\rangle_{\alpha<2^\omega}$ so that no $a_\alpha$ is equal to any $b_\beta$ and both sets are disjoint from $Z$. Let $\langle\sigma_\alpha\rangle_{\alpha<2^\omega}$ enumerate all of I's strategies and let $\\langle\tau_\alpha\rangle_{\alpha<2^\omega}$ all of II's strategies. Suppose $\\langle a_\beta\rangle_{\beta<\alpha}$ and $\langle b_\beta\\rangle_{\beta<\alpha}$ have been defined. First consider $\sigma_\alpha$; if it equals $\sigma$ we don't do anything. Otherwise it disagrees with $\sigma$ on some $s$; there are $2^\omega$ many $x$ which are extensions of $s$, for each such $x$ we have $\sigma_\alpha*x\not\in Z$ so pick one which also isn't equal to an $a$ or a $b$ so far and make it $a_\alpha$.

Next consider $\tau_\alpha$. There are continuum many $x$ that I can play so that $\tau_\alpha*x$ does not land in $Z$ (just have $x$ give a first move different from that prescribed by $\sigma$). Using a cardinality argument we get some $x$ such that $\tau_\alpha*x$ is not in $Z$ and not equal to anything chosen so far, and set it equal to $b_\alpha$.

At the end let $A$ equal $Z$ together with the set of $a_\alpha$. Then $\sigma$ is a winning strategy for I in $G(A)$ because every play according to $\sigma$ lands in $Z$. But no strategy wins $A^c$. We've made sure that for every strategy for I there is a play which equals an $a_\alpha$ and thus lands in $A$ and so that strategy cannot be winning in $G(A^c)$. And similarly we've made sure that for every strategy for II there is a play equalling one of the $b_\beta$ and thus landing in $A^c$ and not winning for II in $G(A^c)$.

share|improve this answer
    
There was an error in the part of the argument considering the $\tau_\alpha$. I have corrected it. –  Justin Palumbo Jul 27 '10 at 19:39

There is a general construction that swaps players in a game by ignoring the first move. Given $A$, define a set $B$ such that $x \in B$ if and only if $\sigma(x) \in A$, where $\sigma$ is the one-sided shift that discards the first element. That is, $(\sigma x)(n) = x(n+1)$. Now player II has a winning strategy $s_{II}$ for game $G_B$ (in the usual sense) if and only if player I would have a winning strategy $s'_{I}$ for the game $G'_A$ in the reversed sense. The strategies can be defined from each other in the following concrete way.

  • $s_{II}(\tau) = s'_I(\sigma(\tau))$, where $\sigma$ is again a left shift
  • $s_{I}'(\tau) = s_{II}(0\smallfrown\tau)$, where $0$ is any fixed, legal first move for player I

So if $B$ is determined, in the usual sense, then $A$ is determined in the opposite sense. The nice thing about this construction is that $B$ has the same classification as $A$ in the arithmetical and analytical hierarchies. So if we have a typical fragment of determinacy that shows $G(A)$ is determined, that same fragment will show that $G(B)$ is determined, and then the strategy translation above will show that $G'(A)$ is determined.

As Oliver pointed out, the game $G'(A)$ is also the same as the game $G(A^c)$. The construction I sketched here is better known in that light. It lets us prove that determinacy for closed sets is equivalent to determinacy for open sets, that determinacy for $\Pi^1_1$ sets is equivalent to determinacy for $\Sigma^1_1$ sets, etc., relative to very weak axiom systems.

Justin Palumbo's answer shows that if you look at games one set at a time, instead of looking at determinacy for reasonable pointclasses, then things are much more messy.

share|improve this answer
    
There is a subtlety here... It is true that if $\Gamma$ is a pointclass closed under continuous substitution then determinacy of sets in $\Gamma$ holds if and only if determinacy of sets whose complement lies in $\Gamma$ holds. But the question was about arbitrary sets. Under AC it is possible to construct using a diagonal argument a set $A$ such that $G(A)$ is determined and $G(A^c)$ is not. So I think actually the answer to the OPs question as stated is no... –  Justin Palumbo Jul 22 '10 at 20:56
    
You're right; I misread the question as being about pointclasses (about why we don't consider both variations of the game). I'm going to clarify that in my answer. Marc Alcobé García, please consider accepting Justin Palumbo's answer instead of this one. –  Carl Mummert Jul 22 '10 at 22:44

Your Answer

 
discard

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.