Determinacy interchanging the roles of both players

Question

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 $a_1$, then II chooses $b_1$, and so on. The game ends after $\omega$ steps; if the resulting sequence $\langle a_0, b_0, a_1, b_1, ...\rangle$ 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$?

Answer 1

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 all of the $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)$.

Answer 2

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.

Answer 3

Suppose $G_B$ is undetermined for some set $B\subset\omega^\omega.$ Define a set $A\subset\omega^\omega$ so that $(x_0,x_1,x_2,\dots)$ belongs to $B$ iff either $x_0=0$ or else $x_0\ne0$ and $(x_1,x_2,\dots)\in A.$ Then $G_A$ is determined (as a win for the first player) while $G'_A$ is undetermined.