What statements are equivalent to the Axiom of Determinacy?

Question

We know the big statements equivalent to the axiom of choice (Zorn's Lemma, Well-Ordering Theorem, etc...). So what about the axiom of determinacy?

Answer 1

I give an example (perhaps the best-known example) below, but let me first discuss equiconsistency rather than straight equivalence. Usually an equiconsistency is really the sort of result you are after anyway: You want to establish that certain statements in the universe where choice holds correspond to determinacy, which implies the failure of choice.

The result here is that $\mathsf{ZF}+\mathsf{AD}$ is equiconsistent with $\mathsf{ZFC}+$ the existence of infinitely many Woodin cardinals.

Indeed, starting with the large cardinals we can proceed to construct what we call the derived model (the argument is due to Woodin): If $\delta$ is the supremum of the first $\omega$ Woodin cardinals, we pass to the extension by forcing with $\operatorname{Col}(\omega,<\delta)$. Say that $G$ is generic for this forcing over $V$. Now, instead of looking at the reals of $V[G]$ we only consider $\mathbb R^*_G=\bigcup_{\alpha<\delta}\mathbb R\cap V[G\upharpoonright\alpha]$. Then $L(\mathbb R^*_G)$ is a model of $\mathsf{AD}$.

Conversely, if $\mathsf{AD}$ holds, then $L(\mathbb R)$ is again a model of determinacy and, letting $\Theta^{L(\mathbb R)}$ denote the supremum of the ordinals $\alpha$ such that there exists in $L(\mathbb R)$ a surjection $f\!:\mathbb R\to\alpha$, we see that $\Theta^{L(\mathbb R)}$ is a Woodin cardinal in $\mathrm{HOD}^{L(\mathbb R)}$. The argument (once again, due to Woodin) can be generalized to obtain for any $n<\omega$ inner models of $L(\mathbb R)$ where choice holds and there are $n$ Woodin cardinals. Using a variant of Prikry forcing we can pass to a forcing extension where there is an inner model of choice with $\omega$ Woodin cardinals.

(The derived model theorem has been much generalized since. It is a key tool for passing from models with large cardinals to models of determinacy. By considering not just $L(\mathbb R^*_G)$ but also certain subsets of $\mathbb R^*_G$ we obtain models of strong versions of determinacy.)

Since we live in a universe with choice, if we are looking for equivalences, perhaps rather than determinacy the assumption to consider is $\mathsf{AD}^{L(\mathbb R)}$. However, the equiconsistency above is not an equivalence between the large cardinals mentioned and this assumption: It is consistent that $\mathsf{AD}$ fails in $L(\mathbb R)$ and yet there are $\omega$ Woodin cardinals in $V$ and, similarly, there is no inner model of $L(\mathbb R)$ where choice holds and there are $\omega$ Woodin cardinals.

The key technique for proving consistency strength lower bounds is the core model induction, introduced by W. Hugh Woodin in the early 1990s. One of Woodin's earliest applications of the technique was precisely to establish the equivalence of $\mathsf{AD}^{L(\mathbb R)}$ with some of its descriptive set-theoretic consequences. Namely:

(Assuming, say $\mathsf{ZF}+\mathsf{DC}$.) In $L(\mathbb R)$, $\mathsf{AD}$ holds if and only if all sets of reals are Lebesgue measurable and have the property of Baire, and all $\mathbf{\Delta}^2_1$ sets of reals can be uniformized.

I think this is fascinating because it shows that (at least in $L(\mathbb R)$) determinacy is really a statement of real analysis. Note that no games are mentioned in the conclusion.

Another early application of the core model induction was another equiconsistency result, namely that $\mathsf{ZF}+\mathsf{AD}$ is equiconsistent with the existence of an $\omega_1$-dense ideal on $\omega_1$. The ideal assumption implies $\mathsf{AD}^{L(\mathbb R)}$. Conversely, assuming $\mathsf{AD}^{L(\mathbb R)}$, and forcing over $L(\mathbb R)$ with what is called $\mathbb Q_{\rm max}$ produces a model of choice where there is an $\omega_1$-dense ideal (in fact, the nonstationary ideal is $\omega_1$-dense).

These two results, the equivalence and the equiconsistency just mentioned, are interesting also from a technical point of view. Indeed, most applications of the core model induction require that we pass to a certain forcing extension where we can find nicely behaved structures allowing us to carry out the inner model-theoretic arguments that the induction requires. The end result of this is that we establish determinacy not just in $V$ but in certain forcing extensions. This is in general not possible if our assumptions are not stronger than determinacy. The two examples above actually allow us to argue within $V$, which in turns allows us to conclude with an equiconsistency (or an equivalence) rather than merely an implication.

Since $L(\mathbb R)$ is much better understood than arbitrary models of determinacy, it is perhaps not surprising that other equivalences are known assuming not just $\mathsf{AD}$ but also that $V=L(\mathbb R)$. Let me mention another interesting example of this kind: In $L(\mathbb R)$, $\mathsf{AD}$ is equivalent to the apparently weaker statement that Turing determinacy holds. An easy but extremely useful consequence of determinacy, first established by Tony Martin, is that any set of reals that is Turing invariant contains a cone or is disjoint from one (that $A\subseteq\mathbb R$ is Turing invariant means that whenever $x\in A$ and $y\equiv_T x$ then $y\in A$. Here, $y\equiv_T x$ if and only if $y\le_T x$ and $x\le_T y$, where $\le_T$ is the relation of Turing-reducibility. A cone is a set of the form $\{x\in\mathbb R\mid y\le_T x\}$ for some real $y$). What is surprising is that assuming that this is the case (we say that Martin's cone measure is an ultrafilter on the Turing degrees), we can easily prove that every Turing invariant set of reals is determined. This is called Turing determinacy. It is open whether Turing determinacy implies determinacy in general, but Woodin proved (in the 1980s, I believe) that it does in $L(\mathbb R)$. There are now stronger results. This is one of the basic results about determinacy that remains unpublished. Richard Ketchersid and I noticed a few years ago that $\omega$-board determinacy (obviously a weakening of determinacy) implies Turing determinacy and therefore, in $L(\mathbb R)$, is equivalent to determinacy. In an $\omega$-board game, we are given $A\subseteq\mathbb R$ and players I and II alternate playing simultaneously on $\omega$ many boards the usual game for $A$. Player I wins if and only if one of the $\omega$ many reals so produced is in $A$. Otherwise II wins. We say that $\omega$-board determinacy holds if and only if one of the players has a winning strategy.

Mention of $\mathbb Q_{\rm max}$ above brings up another equivalence in $L(\mathbb R)$: The usefulness of the theory of $\mathbb P_{\rm max}$ and its variants depends essentially on the existence of so-called $A$-iterable conditions for every set of reals $A\in L(\mathbb R)$. It turns out that this is also equivalent to determinacy in $L(\mathbb R)$.

Another famous examples is the equivalence in $L(\mathbb R)$ of determinacy and the existence of arbitrarily large partition cardinals below $\Theta$. This is a nice argument of Woodin and Alekos Kechris that involves a careful analysis of scales. This sort of analysis is also a crucial component of modern core model inductions.

(A famous open problem is whether $\mathsf{AD}$ is equivalent to the apparently stronger $\mathsf{AD}^+$. The equivalence holds in all natural models of determinacy.)