First, this question is strictly in the context of Reverse Mathematics where various set comprehension and various axiom of choice may not be available.

Question: Over $\text{RCA}_0$, if one has $\Sigma_1^0$-DET in Baire Space, does one have $\Pi_1^0$-DET in Baire Space? (Games in Baire Space are the only kind considered in Simpson's book).

For example, it is clear that $\Sigma_1^0$-DET in Cantor space implies $\Pi_1^0$-DET in Cantor Space. Given a $\Pi_1^0$ formula $\varphi(f)$. Consider the new $\Sigma_1^0$ game $\neg\varphi(0*f)$ and $\neg\varphi(1*f)$.

Case 1: If there exists an $i$ ($i = 0$ or $i = 1$) such that Player II has a winning strategy $T'$ in $\neg\varphi(i*f)$, then Player I has a winning strategy $S$ for $\varphi(f)$ where $S$ plays $i$ on the first move and then follows $T'$.

Case 2 : If player I has a winning strategy $S'$ for $\neg\varphi(0*f)$ and a winning strategy $S''$ for $\neg\varphi(1*f)$, then player II has a winning $T$ for $\varphi(f)$ which is described as follows, if Player I plays $0$, then player II follows $S'$ and if Player I plays $1$, then Player II follows $S''$.

Note that the above does not require the axiom of choice because in the second case, I constructed $T$ by merely combining two strategies $S'$ and $S''$.

This argument would not hold for games in Baire Space since the analog for case II would be that for all $i \in \mathbb{N}$, player I has a winning strategy $S_i'$ for $\neg\varphi(i*f)$. However, now I can not combine all these strategy together to get a winning strategy for $\varphi(f)$.

It seems that I may have heard that this fact is true even for games in Baire Space. If this claim known to be true and how is it proved. Thanks for any help you can provide.


Given a formula $\phi(f)$, where $f$ ranges over Baire space, let $\psi(f)$ be defined as $\lnot \phi(f')$, where $f'(n) = f(n+1)$. So, basically, in game $\psi$ the first move is ignored, after which player II gets the first move to try to make $\phi(f')$ hold (really the second move of the game), while player I gets the second move (really the third) and the first player tries to make $\phi(f')$ not hold. The complexities of $\phi$ and $\psi$ will be complementary in the arithmetical or analytical hierarchy, and the roles of the two players are also reversed.

Suppose that player I has a winning strategy $s$ in game $\psi$, which means that $\psi(s(g))$ holds for any $g \in \mathbb{N}^\mathbb{N}$. Then player II can win $\phi$ by just using this strategy and pretending that the two players have swapped roles. In particular, when player I has played a finite sequence $\sigma$, player II will simply compute the number $s(\sigma) \in \mathbb{N}$ and play this number. This gives a strategy $s^*$ for player II in game $\phi$.

Say player I plays an infinite sequence of moves $g$ in game $\phi$. Then $\psi(s(g))$ will hold, by definition of $s$, so $\phi(s(g)')$ will not hold. But $s^*(g) = s(g)'$ so $\phi(s^*(g))$ will not hold, i.e., player II will win game $\phi$ using strategy $s^*$ against $g$.

Similarly, if player II has a winning strategy $s$ in game $\psi$, which gives a way to make $\phi(f')$ hold, then player I can win game $\phi$, by using the winning strategy for $\psi$ and pretending that the two players have swapped roles. Now the strategy $s^*$ for player I is defined from $s$ by arbitrarily letting $s^*(\sigma) = s(0 * \sigma)$; the choice of $0$ won't matter because $s$ is a winning strategy for II in game $\psi$.

Say player II plays an infinite sequence $g$ against $\phi$. Then $\phi(s(0 * g)')$ will hold because $s$ is winning for player II in game $\psi$. Again $s^*(g) = s(0 * g)'$, although the calculation is different because $s^*$ is now a strategy for player I. Since $\phi(s^*(g))$ holds, player I will win game $\phi$ when II plays $g$.

This shows that determinacy respects complementary classes all the way up the arithmetical and analytical hierarchies. Comparing this to the argument in the question, the trick is to just discard the first move rather than trying to do anything with it.

  • $\begingroup$ Thanks. Ignoring the first move is very clever. $\endgroup$ – William Dec 22 '11 at 6:14
  • $\begingroup$ I can't take credit for it, this is just a standard proof. $\endgroup$ – Carl Mummert Dec 22 '11 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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