I recently learned about three determinacy theorems, and I am curious about the reverse mathematical-strength of (the countable analogs of) these theorems.
These theorems are Zermelo's Theorem (Zermelo 1913), the Open Determinacy Theorem (Gale-Stewart 1953) and the Borel Determinacy Theorem (Martin 1974).
For reference, here are statements of each of these theorems. Let $A$ be any set, and let $G_A$ be any Gale-Stewart game on $A$. Endow $A$ with the discrete topology and $A^\omega$ with the product topology.
- Zermelo's Theorem states that, if $A$ is finite, then $G_A$ is determined.
- The Open Determinacy Theorem states that, if the payoff set for $G_A$ is an open or closed subset of $A^\omega$, then $G_A$ is determined.
- The Borel Determinacy Theorem states that, if the payoff set for $G_A$ is a Borel subset of $A^\omega$, then $G_A$ is determined.
I understand that the reverse mathematics of these theorems has been studied to some extent. In particular, the Open Determinacy Theorem is equivalent to AC under ZF (Question on Gale-Stewart Theorem and Axiom of Choice) and that the Borel Determinacy Theorem requires "repeated use" of the Axiom of Replacement (https://en.wikipedia.org/wiki/Borel_determinacy_theorem) (Friedman 1971).
I am curious about where these theorems lie in the hierarchy of subsystems of second-order arithmetic, if we restrict these theorems to countable sets $A$. Does anyone know the answer to this question, or a source I could look to for more information?
Thank you!
One of the earliest results in reverse mathematics was Steel's $1972$ proof that each of clopen and open determinacy is equivalent to $\mathsf{ATR}_0$. This should in my opinion be surprising, since $(i)$ every computable clopen game has a hyperarithmetic winning strategy but $(ii)$ there are computable open games without hyperarithmetic winning strategies. I'm aware of three proofs of this result, one via $\Sigma^1_1$-Separation (this is the proof presented in Simpson's book), one via Harrison orders/overspill (I don't recall where this is written up), and one via a "tree of strategies" (see the end of this old answer of mine).
As we climb up the determinacy hierarchy we rise rapidly in strength. $\mathsf{Z}_2$ cannot even prove $\Delta^0_4$ determinacy; the best it can do is prove that finite Boolean combinations of $\Sigma^0_3$ games are determined. This latter principle is schematic, and so itself constitutes a hierarchy; the relationship between the $n\Sigma^0_3$-determinacy hierarchy and the usual $\Pi^1_k$-comprehension hierarchy is subtle and was established by Montalban/Shore 1, 2.
We can go below $\mathsf{ATR}_0$ if we replace games on $\omega$ by games on $\{0,1\}$ (that is, move from games in Baire space to games in Cantor space); for example, clopen determinacy in Cantor space is equivalent to $\mathsf{WKL}_0$. See e.g. Nemoto.