Axiom of determinacy
The axiom of determinacy is the assertion that a certain type of two-player games of perfect information (i.e. games in which the players alternate moves which are known to both players, and the outcome of the game depends only on this list of moves, and not on chance or other external factors) are determined, that is, there is an "optimal strategy" that allows one player to win regardless of the other player's strategy. That strategy is called a winning strategy for that player.
The axiom of determinacy is incompatible with the axiom of choice. More precisely, it is incompatible with the existence of a well-ordering of the reals. The AD is, however, not known to be inconsistent with ZF set theory. AD is furthermore a very powerful axiom, as ZF+AD implies the consistency of ZF, ZF+Con(ZFC), and much more - it is in fact close of being a large cardinal axiom, as Woodin proved that it was equiconsistent with the existence of infinitely many Woodin cardinals. [1]
It follows from large cardinal axioms (in particular from the existence of infinitely many Woodins with a measurable above them all [1]) that the AD is true in $L(\mathbb{R})$, the constructible universe obtained by starting with the transitive closure of the set of all reals (i.e. $L_0(\mathbb{R})=TC(\{\mathbb{R}\})$). This assertion, generally refered to as $L(\mathbb{R})$-determinacy, AD$^{L(\mathbb{R})}$ [1] or quasi-projective determinacy [2] is not known to be inconsistent with ZFC. $L(\mathbb{R})$-determinacy is furthermore equiconsistent with AD (in $V$). A particular case of this is the axiom of projective determinacy which states that every projective set is determined, projectivity being a weak form of definability (more precisely definability in second-order arithmethic).
Contents
- 1 Type of games that are determined
- 2 Refuting the axiom of determinacy from a well-ordering of the reals
- 3 Other known limitations of determinacy
- 4 Implications of the axiom of determinacy
- 5 Determinacy of $L(\mathbb{R})$
- 6 Axiom of projective determinacy
- 7 Axiom of real determinacy
- 8 Consistency strength of determinacy hypotheses
- 9 Read more
- 10 References
Type of games that are determined
Given a set $S$ of infinite sequences of order-type (length) $\omega$ (i.e, a subset of the Baire Space $\omega^{\omega}$), the payoff set, the game begins as such: Player I says a natural number $n_0$, then Player II says a natural number $n_1$, and so on, until a sequence of order-type $\omega$ is constructed. At this point, a natural number $n_i$ has been given for every natural number $i$. Player I wins if $(n_0,n_1,n_2...)\in S$, Player II wins otherwise. Since $\omega^\omega$ and the set $\mathbb{R}$ of the real numbers are in bijection with the other, we shall often identify the elements of $\omega^\omega$ as the real numbers, like if $\omega^\omega$ and $\mathbb{R}$ were equal. Thus the game considered here produces a real number.
A strategy for player I (resp. player II) is a function $\Sigma$ with domain the set of sequences of integers of even (odd) length such that for each $a\in dom(\Sigma)$, $\Sigma(a)\in\omega$. A run of the game (partial or complete) is said to be according to a strategy $\Sigma$ for player player I (player II) if every initial segment of the run of odd (nonzero even) length is of the form $a\frown⟨\Sigma(a)⟩$ for some sequence $a$. A strategy $\Sigma$ for player player I (player II) is a winning strategy if every complete run of the game according to $\Sigma$ is in (out of) $S$. We say that a set $S\subset\omega^\omega$ is determined if there exists a winning strategy for one of the players
The axiom of determinacy states that every payoff set $S\subset\omega^\omega$ is determined [3]. It is possible to show that every finite or countable payoff set is determined, so this equivalent to the assertion that every uncountable payoff set is determined.
Refuting the axiom of determinacy from a well-ordering of the reals
As stated above, the axiom of determinacy is not compatible with the axiom of choice, that is, within ZFC we can prove that axiom of determinacy fails. We outline a construction of an undetermined game starting from a well-ordering of continuum.
A strategy for either player is a function with countable domain (a subset of the set of all finite sequences of integers) to $\omega$, so there are $2^{\aleph_0}$ many strategies for player I and $2^{\aleph_0}$ continuum many strategies for player II. Let $\{s^{I}_\alpha:\alpha<2^{\aleph_0}\}, \{s^{II}_\alpha:\alpha<2^{\aleph_0}\}$ be enumerations of strategies for the respective players. We shall now construct, by transfinite recursion, two disjoint sets of sequences $\{a_\alpha:\alpha<2^{\aleph_0}\}, \{b_\alpha:\alpha<2^{\aleph_0}\}\subseteq\omega^\omega$ such that $\{a_\alpha:\alpha<2^{\aleph_0}\}$ is not determined.
Suppose that, for some $\beta<2^{\aleph_0}$, $\{a_\alpha:\alpha<\beta\},\{b_\alpha:\alpha<\beta\}$ have already been constructed. Take strategy $s^I_\beta$. There are continuum many possible plays according to this strategy (since player II can play in arbitrary way at any of their turns), so not all of them can be already contained in $\{a_\alpha:\alpha<\beta\}$ (which has cardinality $|\beta|<2^{\aleph_0}$). Therefore, using well-ordering of continuum, we can pick one of these plays and define it to be $b_\beta$. Similarly, we can pick $a_\beta$ according to strategy $s^{II}_\beta$ which is not already in $\{b_\alpha:\alpha\leq\beta\}$. This way the sets $\{a_\alpha:\alpha<2^{\aleph_0}\},\{b_\alpha:\alpha<2^{\aleph_0}\}$ are clearly disjoint.
Letting $A=\{a_\alpha:\alpha<2^{\aleph_0}\}$, we now claim the game with payoff set $A$ is undetermined. Indeed, suppose player I has a winning strategy. This must be one of the strategies $s^I_\beta$. By construction, player II can arrange the play so that the resulting play is $b_\beta$ (since we have chosen it so that it's consistent with strategy $b_\beta$), which is not an element of $A$, contradicting the assumption that $s^I_\beta$ is a winning strategy. Analogously, for any strategy $s^{II}_\beta$ for player II, player I can force the play to be $a_\beta\in A$. Therefore no strategy for either player is a winning strategy and it follows that the game is undetermined.
Other known limitations of determinacy
Assuming the axiom of choice there is a non-determined game of length $\omega$. However, choice isn't known to contradict the determinacy of all definable games of length $\omega$.
With or without assuming choice, there is a non-determined game of length $\omega_1$ and a a non-determined definable game of length $\omega_1+\omega$. There is also a non-determined game of length $\omega$ with moves in $\omega_1$ (i.e. the payoff sets are subsets of $\omega_1^\omega$ instead of subsets of $\omega^\omega$. There is a non-determined game of length $\omega$ with moves in $\mathcal{P}(\mathbb{R})$, and using choice one can show there is such a game that is definable. [1]
Definable games of length $\omega$ with moves in $\mathbb{R}$ are provably determined from large cardinal axioms. Determinacy of such games that are projective follows from the existence of sufficiently many Woodin cardinals.
By a result of Woodin, if there is an iterable model of ZFC with a countable (in $V$) Woodin cardinal which is a limit of Woodin cardinals, then it is consistent (even with choice) that all ordinal-definable games of length $\omega_1$ are determined. This is only a consistency result, not a proof of "all ordinal-definable games of length $\omega_1$ are determined".
Implications of the axiom of determinacy
Assume ZF+AD. Most of the following results can be found in [4], in [3] or in [2]:
- The axiom of countable choice restrained to countable sets of reals is true.
- In $L(\mathbb{R})$ the axiom of dependent choice is true.
- The reals cannot be well-ordered. Thus the full axiom of choice fails.
- Every set of reals is Lebesgue measurable. Thus the Banach-Tarski paradox fails.
- It follows by a theorem of Raisonnier that $\omega_1\not\leq 2^{\aleph_0}$ (yet $\omega_1\not\geq2^{\aleph_0}$).
- Furthermore, it implies $2^{\aleph_0}$ can be partitioned in more than $2^{\aleph_0}$ many pairwise disjoint nonempty subsets.
- Every set of reals has the Baire property.
- Every set of reals is either countable or has a perfect subset.
- Thus a form of the continuum hypothesis holds, i.e. every set of reals is either countable or has cardinality $2^{\aleph_0}$.
- Other forms of CH however fail, in particular $2^{\aleph_0}\neq\aleph_1$.
- There are no free ultrafilters on $\omega$. Every ultrafilter on $\omega$ is principal. Thus every ultrafilter is countably complete ($\aleph_1$-complete).
- $\omega_1$, $\omega_2$, and $\omega_{\omega+1}$ and $\omega_{\omega+2}$ are all measurable cardinals.
- The club filter on $\omega_1$ is an ultrafilter. Every subset of $\omega_1$ either contains a club or is disjoint from one.
- The club filter on $\omega_2$ restrained to sets of cofinality $\omega$ is $\omega_2$-complete.
- $\omega_n$ is singular for every $n>2$ and has cofinality $\omega_2$ and is Jonsson, also $\aleph_\omega$ is Rowbottom.
- $0^{\#}$ exists, thus the axiom of constructibility (V=L) fails.
- In fact, $x^{\#}$ exists for every $x\in\mathbb{R}$ (thus $V\neq L[x]$).
- The strong partition property, $\omega_1\rightarrow(\omega_1)^{\omega_1}_2$, holds. In fact, $\omega_1\rightarrow(\omega_1)^{\omega_1}_{2^{\aleph_0}}$ and $\omega_1\rightarrow(\omega_1)^{\omega_1}_\alpha$ for every $\alpha<\omega_1$.
- If there is a surjection $\mathbb{R}\to\alpha$, then there is surjection $\mathbb{R}\to\mathcal{P}(\alpha)$ (this is Moschovakis' coding lemma).
- Hall's marriage theorem fails for infinite graphs. For example there is there is a 2-regular bipartite graph on $\mathbb{R}$ with no perfect matching.
- There is no Hamel basis of $\mathbb{R}$ over $\mathbb{Q}$.
Let $\Theta$ be the supremum of the ordinals that $\mathbb{R}$ can be mapped onto. Under $AC$ this is just $(2^{\aleph_0})^{+}$ but under AD it is a limit cardinal, in fact an aleph fixed point, and DC implies it has uncountable cofinality. In $L(\mathbb{R})$ it is also regular and thus weakly inaccessible. It is conjectured that under AD the cofinality function is nondecreasing on singular cardinals below $\Theta$.
Determinacy of $L(\mathbb{R})$
See also: Constructible universe
Recall that a formula $\varphi$ is $\Delta_0$ if and only if it only contains bounded quantifiers (i.e. $(\forall x\in y)$ and $(\exists x\in y)$). Let $def(X)=\{Y\subset X : Y$ is first-order definable by a $\Delta_0$ formula with parameters only from $X\cup\{X\}\}$. Then let:
- $L_0(X)=TC(\{X\})$
- $L_{\alpha+1}(X)=def(L_\alpha(X))$
- $L_\lambda(X)=\bigcup_{\alpha<\lambda}L_\alpha(X)$ for limit $\lambda$
- $L(X)=\bigcup_{\alpha\in Ord}L_\alpha(X)$
where $TC({X})$ is the smallest transitive set containing $X$, the elements of $X$, the elements of the elements of $X$, and so on. $L(X)$is always a model of ZF, but not necessarily of the axiom of choice.
$L(X,Y)$ is used as a shortcut for $L(\{X,Y\})$. $L(X,\mathbb{R})$ with $X\subset\mathbb{R}$ is different from $L(\mathbb{R})$ whenever $X$ is not constructible from the reals, i.e. $X\not\in L(\mathbb{R})$ (if any such set exists; it is consistent with ZF+AD that they do not).
$L(\mathbb{R})$-determinacy, also known as AD$^{L(\mathbb{R})}$ [1] or quasi-projective determinacy [2] is the assertion that every set of reals in $L(\mathbb{R})$ is determined. Equivalently, "$L(\mathbb{R})$ is a model of ZF+AD".
$L(\mathbb{R})$-determinacy appears to be a very "natural" statement in that, empirically, every natural extension of ZFC (i.e. not made specifically to contradict this) that is not proved consistent by AD seems to imply $L(\mathbb{R})$-determinacy or some weaker form of determinacy. [3] This is often considered to be an argument toward the "truth" of $L(\mathbb{R})$-determinacy.
Assuming ZF+DC, in $L(\mathbb{R})$ AD follows from three of its consequences: [3]
- Every set of reals is Lebesgue measurable.
- Every set of reals has the Baire property.
- Every $\Sigma^1_2$ set of reals can be uniformized.
In $L(\mathbb{R})$, the axiom of determinacy is equivalent to the axiom of Turing determinacy [3], i.e. the assertion that payoff sets closed under Turing equivalence are determined.
Busche and Schindler showed that, if there is a model of ZF in wich every uncountable cardinal is singular (thus has cofinality $\aleph_0$), then the axiom of determinacy holds in the $L(\mathbb{R})$ of some forcing extension of $HOD$ [3]. This notably follows from the existence of a proper class of strongly compact cardinals.
Assume that there is $\omega_1$-dense ideal over $\omega_1$; then $L(\mathbb{R})$-determinacy holds. [4] This result is due to Woodin.
The following holds in $L(\mathbb{R})$ assuming $L(\mathbb{R})$-determinacy: [1][5]
- Every uncountable cardinal $<\Theta$ is Jónsson, also if it is regular or has cofinality $\omega$ then it is Rowbottom.
- Every regular cardinal $<\Theta$ is measurable (note that $2^{\aleph_0}\not\leq\Theta$), also $\Theta$ is a limit of measurable cardinals.
- $\Theta$ is weakly $\Theta$-Mahlo (and thus weakly $\Theta$-inaccessible), but it is not weakly compact.
- $\omega_1$ is <$\Theta$-supercompact, i.e. it is $\gamma$-supercompact for all $\gamma<\Theta$.
- $\Theta$ is Woodin in the model $HOD^{L(\mathbb{R})}$.
Axiom of projective determinacy
Main article: Projective determinacy
Axiom of real determinacy
The axiom of real determinacy (AD$_\mathbb{R}$) is the assertion that if payoff sets contains real numbers instead of natural numbers, then every payoff set is still determined. This is strictly stronger than AD, and ZF+AD$_\mathbb{R}$ proves ZF+AD consistent.
AD$_\mathbb{R}$ is equivalent (over ZF) to AD plus the axiom of uniformization (which is false in $L(\mathbb{R})$). AD$_\mathbb{R}$ is also equivalent to determinacy for games of length $\omega^2$. In fact, AD_$\mathbb{R}$ is equivalent to the assertion that every game of bounded countable length is determined. It is however possible to show (in ZF) that there are non-determined games of length $\aleph_1$.
Solovay showed that ZF+AD$_\mathbb{R}$+"$\Theta$ has uncountable cofinality" (which follows from ZF+AD$_\mathbb{R}$+DC) proves ZF+AD$_\mathbb{R}$ consistent; it is therefore consistent with ZF+AD$_\mathbb{R}$ that $\Theta$ has cofinality $\omega$ and that DC is false. [3]
Steel showed that under AD$_\mathbb{R}$, in a forcing extension there is a proper class model of ZFC in which there exists a cardinal $\delta$ of cofinality $\aleph_0$ which is a limit of Woodin cardinals and <$\delta$-strong cardinals. [3]
Under AD_$\mathbb{R}$, $\omega_1$ is <$\Theta$-supercompact, i.e. for every ordinal $\gamma<\Theta$ there is a normal fine ultrafilter on the set of all subsets of $\gamma$ of size $\aleph_1$. AD suffices for this result to hold in $L(\mathbb{R})$, but is not known to suffice for it to hold in $V$. [3]
A set $\Gamma\subset\mathcal{P}(\mathbb{R})$ is a Wadge initial segment of $\mathcal{P}(\mathbb{R})$ if for every $X\in\Gamma$, if $Y\leq_W X$ (i.e. $Y$ is Wadge reducible to $X$) then $Y\in\Gamma$. Under suitable large cardinal assumptions, there exists a Wadge initial segment $\Gamma\subset\mathcal{P}(\mathbb{R})$ such that $L(\Gamma,\mathbb{R})$ is a model of "AD$^{+}$, AD$_\mathbb{R}$ and $\Gamma=\mathcal{P}(\mathbb{R})$" (see AD+). Furthermore, whenever $\mathcal{M}$ is an inner model such that $\mathbb{R}\subset\mathcal{M}$ and $\mathcal{M}$ is a model of "AD$^{+}$ and AD$_\mathbb{R}$", one has $\Gamma\subset\mathcal{M}$. (see the 'Read more' section)
Consistency strength of determinacy hypotheses
The following theories are equiconsistent: [4][6]
- ZF+AD
- ZF+AD+DC
- ZFC+AD$^L(\mathbb{R})$
- ZFC+AD$^OD(\mathbb{R})$
- ZFC+"the non-stationary ideal over $\omega_1$ is $\omega_1$-dense"
- ZFC+"there exists infinitely many Woodin cardinals"
- ZF+DC+"$\omega_1$ is $\mathcal{P}(\omega_1)$-strongly compact"
- ZF+DC+"$\omega_1$ is $\mathbb{R}$-strongly compact and $\Theta>\omega_2$"
- ZF+DC+"$\omega_1$ is $\mathbb{R}$-strongly compact and $\omega_2$-strongly compact"
- ZF+DC+"$\omega_1$ is $\mathbb{R}$-strongly compact and Jensens's square principle fails for $\omega_1$"
Where DC is the axiom of dependent choice and $\omega_1$ being $X$-strongly compact means that there exists a fine measure on the set of all subsets of $X$ of cardinality $\aleph_1$.
Projective determinacy is a little weaker: it is equiconsistent with ZFC plus, for all n, an axiom saying "there are n Woodin cardinals". Since ZFC can only use finitely many of its axioms, this axiom schema does not allow ZFC to prove that there exists infinitely many Woodins, despite making it able to prove every particular instance of "there exists at least n Woodin cardinals".
Koellner annd Woodin showed that the following theories are also equiconsistent: [1]
- ZFC+$\Delta^1_2$-determinacy
- ZFC+OD-determinacy
- ZFC+"there exists a Woodin cardinal"
And so are Z$_3$+lightface $\Delta^1_2$-determinacy and MK+"Ord is Woodin" where Z$_3$ is third-order arithmetic and MK is Morse-Kelley set theory. It is also conjectured that Z$_2$+$\Delta^1_2$-determinacy and ZFC+"Ord is Woodin" are equiconsistent, where Z$_2$ is second-order arithmetic and "Ord is Woodin" is expressed as an axiom scheme.
Finally, Trang and Wilson proved that the following theories are equiconsistent: [6]
- ZF+DC+AD$_\mathbb{R}$
- ZF+DC+"$\omega_1$ is $\mathcal{P}(\mathbb{R})$-strongly compact"
- ZF+DC+"$\omega_1$ is $\mathbb{R}$-strongly compact and $\Theta$ is singular"
- ZF+DC+"$\omega_1$ is $\mathbb{R}$-strongly compact and $\Theta$-strongly compact"
As are the following theories:
- ZF+AD$_\mathbb{R}$
- ZF+DC$_{\mathcal{P}(\omega_1)}$+"$\omega_1$ is $\mathbb{R}$-strongly compact and $\Theta$ is singular"
Read more
- "Is there a natural inner model of AD$_\mathbb{R}$?" [3]
- "Limitations of determinacy hypotheses in ZFC" [4]
- "Counterintuitive consequences of the Axiom of Determinacy?" [5]
References
- Koellner, Peter and Woodin, W Hugh. Chapter 23: Large cardinals from Determinacy. Handbook of Set Theory , 2010. www bibtex
- Maddy, Penelope. Believing the axioms. II. J Symbolic Logic 53(3):736--764, 1988. www DOI bibtex
- Larson, Paul B. A brief history of determinacy. , 2013. www bibtex
- Kanamori, Akihiro. The higher infinite. Second, Springer-Verlag, Berlin, 2009. (Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition) www bibtex
- Jackson, Steve; Ketchersid, Richard; Schlutzenberg, Farmer; Woodin, W Hugh. Determinacy and Jónsson cardinals in $L(\mathbb{R})$. , 2015. arχiv DOI bibtex
- Trang, Nam and Wilson, Trevor. Determinacy from Strong Compactness of $\omega_1$. , 2016. arχiv bibtex