3
$\begingroup$

Let $A, B \subset \omega^\omega$. The Wadge Game $(A, B)$ is played as followed: Player I plays $a_0 \in \omega$. Then Player II plays $b_0 \in \omega$. Then Player I choose $a_1 \in \omega$; afterward player II plays $b_1 \in \omega$. And so on. In the end player I produces a sequence $f = (a_0, a_1, a_2, ...)$ and player II produces a sequence $g = (b_0, b_1, b_2, ...)$.

We say that player II wins if $f \in A$ if and only if $g \in B$. Player I wins otherwise. The game $(A,B)$ is determined if one of the players has a winning strategy in this game.

Suppose that $\Lambda, \Gamma \subset \mathscr{P}(\omega^\omega)$. $(\Gamma, \Lambda)$ wadge determinacy is the statement that for all $A \in \Lambda$ and $B \in \Gamma$, the Wadge game $(A, B)$ is determined.

Define $\neg \Gamma = \{\omega^\omega - A : A \in \Gamma\}$. It is clear that $(\Gamma, \Lambda)$ determinacy implies $(\neg \Gamma, \neg\Lambda)$ determinacy. A winning strategy for player I (respectively player II) in $(A,B)$ is a winning strategy for player I (respectively player II) in the game $(\omega^\omega - A, \omega^\omega - B)$.

My question is does $(\Gamma, \Lambda)$-determinacy implies the determinacy of $(\neg \Gamma, \Lambda)$ or $(\Lambda, \neg\Gamma)$? This appears to be equivalent to whether the determinacy of $(\Gamma,\Lambda)$ implies the determinacy of $(\Lambda, \Gamma)$? Do these classes need to be closed under certain operations for this hold?

The cases I am most interested in is when $\Lambda, \Gamma$ are classes in the Borel Hierarchy, for example $(\Sigma_1^0, \Pi_1^0)$, i.e. (Open, Closed) and whether $(\Sigma_1^0, \Pi_1^0)$ Wadge determinacy is equivalent to $(\Sigma_1^0, \Sigma_1^0)$ Wadge determinacy.

Thanks for any insight anyone can provide.

$\endgroup$
1
  • $\begingroup$ Stopple, as a quick trip to Wikipedia would tell you, yes. This hierarchy is named after William Wadge. I also assume that this is not the same William as the OP... :-) $\endgroup$
    – Asaf Karagila
    Jul 9, 2012 at 18:04

1 Answer 1

1
$\begingroup$

If you are just interested in Borel case, then it is simple. By Martin, every Borel game is determined. For a pair of Borel sets $(A,B)$, the payoff set of the Wadge game $(A,B)$ is also a Borel set. So $(\Sigma^0_1,\Pi^0_1)$ determinacy and $(\Sigma^0_1,\Sigma^0_1)$ determinacy are both true.

$\endgroup$
2
  • 2
    $\begingroup$ So I should be more precise. Martin's result is proved in $ZF$ (maybe choice is needed). I want to work over a very weak system of set theory or second order arithmetic that is not capable of proving Wadge Determinacy. Now given particular determinacy like $(\Sigma_1^0, \Pi_1^0)$ can I use this determinacy to prove $(\Sigma_1^0, \Sigma_1^0)$ determinacy. $\endgroup$
    – William
    Jul 9, 2012 at 3:39
  • $\begingroup$ To clarify your question it might help to specify which weak base theory you are assuming. To make the question nontrivial it would need to be weaker than what was used in the proof of G-delta determinacy in Philip Wolfe's paper "The strict determinateness of certain infinite games." $\endgroup$ Jul 17, 2012 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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