Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.
View the Project on GitHub neugierde/cantors-attic
Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar
Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine
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 $\text{AD}$ is, however, not known to be inconsistent with $\text{ZF}$ set theory. $\text{AD}$ is furthermore a very powerful axiom, as $\text{ZF+AD}$ implies the consistency of $\text{ZF}$, $\text{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. (Koellner & Woodin, 2010)
It follows from large cardinal axioms (in particular from the existence of infinitely many Woodins with a measurable above them all (Koellner & Woodin, 2010)) that the $\text{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})=\text{TC}(\{\mathbb{R}\})$). This assertion, generally refered to as $L(\mathbb{R})$-determinacy, $\text{AD}^{L(\mathbb{R})}$ (Koellner & Woodin, 2010) or quasi-projective determinacy ($\text{QPD}$) (Maddy, 1988) is not known to be inconsistent with $\text{ZFC}$. $\text{AD}^{L(\mathbb{R})}$ is furthermore equiconsistent with $\text{AD}$ (in $\text{V}$). A particular case of this is the axiom of projective determinacy ($\text{PD}$) which states that every projective set is determined, projectivity being a weak form of definability (more precisely definability in second-order arithmethic).
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 ($\text{AD}$) states that every payoff set $S\subset\omega^\omega$ is determined (Larson, 2013). 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.
As stated above, the axiom of determinacy is not compatible with the axiom of choice, that is, within $\text{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.
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 $\text{ZFC}$ with a countable (in $\text{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”.
For the rest of this article we use the following conventions:
Assume $\text{ZF+AD}$. Most of the following results can be found in (Kanamori, 2009), in (Larson, 2013) or in [2]:
Let $\Theta$ be the supremum of the ordinals that $\mathbb{R}$ can be mapped onto: $\Theta=\mathrm{sup}\{\alpha\in\mathrm{Ord}:\alpha\preceq 2^{\aleph_0}\}$. Under $\text{AC}$ this is just $(2^{\aleph_0})^{+}$ but under $\text{AD}$ it is a limit cardinal, in fact an aleph fixed point, and $\text{DC}$ implies it has uncountable cofinality. In $L(\mathbb{R})$ it is also regular and thus weakly inaccessible. It is conjectured that under $\text{AD}$ the cofinality function is nondecreasing on singular cardinals below $\Theta$.
It is worth noting that, under $\text{AD}$, $\Theta$ is the least ordinal incomparable with $\mathbb{R}$, i.e. such that $\Theta\not\leq 2^{\aleph_0}$ yet $2^{\aleph_0}\not\leq\Theta$ and $\Theta\not\preceq 2^{\aleph_0}$ yet $2^{\aleph_0}\not\preceq\Theta$
Under $\text{ZF+AD}$, the cardinal $\omega_1$ is <$\Theta$-strongly compact in that for all $\lambda<\Theta$, every $\sigma$-complete filter on $\lambda$ extends to a ultrafilter on $\lambda$ (and every ultrafilter is itself $\sigma$-complete under $\text{AD}$.)
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 $\text{def}(X)=\{Y\subset X : Y$ is first-order definable by a $\Delta_0$ formula with parameters only from $X\cup\{X\}\}$. Then let:
where $\text{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 $\text{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 $\text{ZF+AD}$ that they do not).
$L(\mathbb{R})$-determinacy, also known as $\text{AD}^{L(\mathbb{R})}$ (Koellner & Woodin, 2010) or quasi-projective determinacy (Maddy, 1988) is the assertion that every set of reals in $L(\mathbb{R})$ is determined. Equivalently, “$L(\mathbb{R})$ is a model of $\text{ZF+AD}$”.
$\text{AD}^{L(\mathbb{R})}$ appears to be a very “natural” statement in that, empirically, every natural extension of $\text{ZFC}$ (i.e. not made specifically to contradict this) that is not proved consistent by $\text{AD}$ seems to imply $\text{AD}^{L(\mathbb{R})}$ or some weaker form of determinacy. (Larson, 2013) This is often considered to be an argument toward the “truth” of $\text{AD}^{L(\mathbb{R})}$.
Assuming $\text{ZF+DC+}V=L(\mathbb{R})$, $\text{AD}$ follows from three of its consequences: (Larson, 2013)
In $L(\mathbb{R})$, the axiom of determinacy is equivalent to the axiom of Turing determinacy (Larson, 2013), i.e. the assertion that payoff sets closed under Turing equivalence are determined.
Busche and Schindler showed that, if there is a model of $\text{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 generic extension of $\text{HOD}$ (Larson, 2013). 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 $\text{AD}^{L(\mathbb{R})}$ holds. (Kanamori, 2009) This result is due to Woodin.
The following holds in $L(\mathbb{R})$ assuming $\text{AD}^{L(\mathbb{R})}$: (Koellner & Woodin, 2010; Jackson et al., 2015)
Main article: Projective determinacy
The axiom of real determinacy ($\text{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 $\text{AD}$, and $\text{ZF+AD}_\mathbb{R}$ proves $\text{ZF+AD}$ consistent.
$\text{AD}_\mathbb{R}$ is equivalent (over $\text{ZF}$) to $\text{AD}$ plus the axiom of uniformization (which is false in $L(\mathbb{R})$). $\text{AD}_\mathbb{R}$ is also equivalent to determinacy for games of length $\omega^2$. In fact, $\text{AD}_\mathbb{R}$ is equivalent to the assertion that every game of bounded countable length is determined. It is however possible to show (in $\text{ZF}$) that there are non-determined games of length $\aleph_1$.
Solovay showed that $\text{ZF+AD}_\mathbb{R}+$”$\Theta$ has uncountable cofinality” (which follows from $\text{ZF+AD}_\mathbb{R}\text{+DC}$) proves $\text{ZF+AD}_\mathbb{R}$ consistent; it is therefore consistent with $\text{ZF+AD}_\mathbb{R}$ that $\Theta$ has cofinality $\omega$ and that $\text{DC}$ is false. (Larson, 2013)
Steel showed that under $\text{AD}_\mathbb{R}$, in a generic extension there is a proper class model of $\text{ZFC}$ in which there exists a cardinal $\delta$ of cofinality $\aleph_0$ which is a limit of Woodin cardinals and <$\delta$-strong cardinals. (Larson, 2013)
Under $\text{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$. $\text{AD}$ suffices for this result to hold in $L(\mathbb{R})$, but is not known to suffice for it to hold in $\text{V}$. (Larson, 2013)
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})\models\text{AD}^{+}+\text{AD}_\mathbb{R}+\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}\models\text{AD}^{+}+\text{AD}_\mathbb{R}$, one has $\Gamma\subset\mathcal{M}$. (see the ‘Read more’ section)
Main article: $\text{AD}^+$
The following theories are equiconsistent: (Kanamori, 2009; Trang & Wilson, 2016)
Where $\text{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$.
Woodin proved that the theory $\text{ZF+DC+AD+}$”$\omega_1$ is supercompact” is consistent relative to $\text{ZFC+}$ “there is a proper class of Woodin cardinals, each of which a limit of Woodin cardinals”.
Projective determinacy is a little weaker: it is equiconsistent with $\text{ZFC}$ plus, for all n, an axiom saying “there are n Woodin cardinals”. Since $\text{ZFC}$ can only use finitely many of its axioms, this axiom schema does not allow $\text{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: (Koellner & Woodin, 2010)
And so are $\text{Z}_3+$lightface $\Delta^1_2$-determinacy and $\text{MK+}$”$\text{Ord}$ is Woodin” where $\text{Z}_3$ is third-order arithmetic and $\text{MK}$ is Morse-Kelley set theory. It is also conjectured that $\text{Z}_2+\Delta^1_2$-determinacy and $\text{ZFC+}$”$\text{Ord}$ is Woodin” are equiconsistent, where $\text{Z}_2$ is second-order arithmetic and “$\text{Ord}$ is Woodin” is expressed as an axiom scheme.
Finally, Trang and Wilson proved that the following theories are equiconsistent: (Trang & Wilson, 2016)
As are the following theories:
“Is there a natural inner model of $\text{AD}_\mathbb{R}$?” [3]
“Limitations of determinacy hypotheses in ZFC” [4]
“Counterintuitive consequences of the Axiom of Determinacy?” [5]