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

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.

share|improve this question
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... :-) –  Asaf Karagila Jul 9 '12 at 18:04
add comment

1 Answer

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.

share|improve this answer
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. –  William Jul 9 '12 at 3:39
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." –  Trevor Wilson Jul 17 '12 at 19:13
add comment

Your Answer


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.