Skip to main content
pointclasses
Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

YesThere 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 not only is $G_A$ determined if and only So if we have a typical fragment of determinacy that shows $G_A'$$G(A)$ is determined, but thethat same fragment of determinacy shows the secondwill show that $G(B)$ is determined if, and then the firststrategy 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.

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

The nice thing about this construction is that $B$ has the same classification as $A$ in the arithmetical and analytical hierarchies. So not only is $G_A$ determined if and only if $G_A'$ is determined, but the same fragment of determinacy shows the second is determined if the first is.

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.

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.

add note
Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

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

The nice thing about this construction is that $B$ has the same classification as $A$ in the arithmetical and analytical hierarchies. So not only is $G_A$ determined if and only if $G_A'$ is determined, but the same fragment of determinacy shows the second is determined if the first is.

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.

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

The nice thing about this construction is that $B$ has the same classification as $A$ in the arithmetical and analytical hierarchies. So not only is $G_A$ determined if and only if $G_A'$ is determined, but the same fragment of determinacy shows the second is determined if the first is.

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

The nice thing about this construction is that $B$ has the same classification as $A$ in the arithmetical and analytical hierarchies. So not only is $G_A$ determined if and only if $G_A'$ is determined, but the same fragment of determinacy shows the second is determined if the first is.

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.

Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

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

The nice thing about this construction is that $B$ has the same classification as $A$ in the arithmetical and analytical hierarchies. So not only is $G_A$ determined if and only if $G_A'$ is determined, but the same fragment of determinacy shows the second is determined if the first is.