Axiom of determinacy

In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy.

Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model L(R) of a set theory, which accepts only a weak form of the axiom of choice (AC) but contains all real and all ordinal numbers. Some consequences of AD followed from theorems proved earlier by Stefan Banach and Stanisław Mazur, and Morton Davis. Mycielski and Stanisław Świerczkowski contributed another one: AD implies that all sets of real numbers are Lebesgue measurable. Later Donald A. Martin and others proved more important consequences, especially in descriptive set theory. In 1988, John R. Steel and W. Hugh Woodin concluded a long line of research. Assuming the existence of some uncountable cardinal numbers analogous to $\aleph _{0}$, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).

Types of game that are determined

The axiom of determinacy refers to games of the following specific form: Consider a subset A of the Baire space ω^ω of all infinite sequences of natural numbers. Two players, I and II, alternately pick natural numbers

n₀, n₁, n₂, n₃, ...

After infinitely many moves, a sequence $(n_{i})_{i\in \omega }$ is generated. Player I wins the game if and only if the sequence generated is an element of A. The axiom of determinacy is the statement that all such games are determined.

Not all games require the axiom of determinacy to prove them determined. If the set A is clopen, the game is essentially a finite game, and is therefore determined. Similarly, if A is a closed set, then the game is determined. It was shown in 1975 by Donald A. Martin that games whose winning set is a Borel set are determined. It follows from the existence of sufficiently large cardinals that all games with winning set a projective set are determined (see Projective determinacy), and that AD holds in L(R).

The axiom of determinacy implies that for every subspace X of the real numbers, the Banach–Mazur game BM(X) is determined (and therefore that every set of reals has the property of Baire).

Incompatibility of the axiom of determinacy with the axiom of choice

Under assumption of the axiom of choice, we create a counterexample to the axiom of determinacy. The set S1 of all first player strategies in an ω-game G has the same cardinality as the continuum. The same is true for the set S2 of all second player strategies. Let SG be the set of all possible sequences in G, and A be the subset of sequences of SG that make the first player win. With the axiom of choice we can well order the continuum, and we can do so in such a way that any proper initial portion has lower cardinality than the continuum. We use the obtained well ordered set J to index both S1 and S2, and construct A such that it will be a counterexample.

We start with empty sets A and B. Let α $\in$ J be the index of the strategies in S1 and S2. We need to consider all strategies S1 = {s1(α)} of the first player and all strategies S2 = {s2(α)} of the second player to make sure that for every strategy there is a strategy of the other player that wins against it. For every strategy of the player considered we will generate a sequence that gives the other player a win. Let t be the time whose axis has length ℵ₀ and which is used during each game sequence. We create the counterexample A by transfinite recursion on α:

1. Consider the strategy s1(α) of the first player.
2. Apply this strategy on an ω-game, generating (together with the first player's strategy s1(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to A. This is possible, because the number of choices for {b(2), b(4), b(6), ...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β $\in$ J | β $<$ α } of J.
3. Add this sequence to B (if it is not already in B), to indicate that s1(α) loses (on {b(2), b(4), b(6), ...}).
4. Consider the strategy s2(α) of the second player.
5. Apply this strategy on an ω-game, generating (together with the second player's strategy s2(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to B. This is possible, because the number of choices for {a(1), a(3), a(5),...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β $\in$ J | β $\leq$ α } of J.
6. Add this sequence to A (if it is not already in A), to indicate that s2(α) loses (on {a(1), a(3), a(5), ...}).
7. Process all possible strategies of S1 and S2 with transfinite induction on α. For all sequences that are not in A or B after that, decide arbitrarily whether they belong to A or to B. So B is the complement of A.

Once this has been done, prepare for an ω-game G. If you give me a strategy s1 of the first player, then there is an α $\in$ J such that s1 = s1(α), and we constructed A such that s1(α) fails (on certain choices {b(2), b(4), b(6), ...} of the second player). Hence s1 fails. Similarly, any other strategy of either player fails. Hence the axiom of determinacy and the axiom of choice are incompatible.

Infinitary logic and the axiom of determinacy

Many different versions of infinitary logic were proposed in the late 20th century. One reason that has been given for believing in the axiom of determinacy is that it can be written as follows (in a version of infinite logic):

$\forall G\subseteq Seq(S):$

$\forall a\in S:\exists a'\in S:\forall b\in S:\exists b'\in S:\forall c\in S:\exists c'\in S...:(a,a',b,b',c,c'...)\in G$ OR

$\exists a\in S:\forall a'\in S:\exists b\in S:\forall b'\in S:\exists c\in S:\forall c'\in S...:(a,a',b,b',c,c'...)\notin G$

Note: Seq(S) is the set of all $\omega$-sequences of S. The sentences here are infinitely long with a countably infinite list of quantifiers where the ellipses appear.

Large cardinals and the axiom of determinacy

The consistency of the axiom of determinacy is closely related to the question of the consistency of large cardinal axioms. By a theorem of Woodin, the consistency of Zermelo–Fraenkel set theory without choice (ZF) together with the axiom of determinacy is equivalent to the consistency of Zermelo–Fraenkel set theory with choice (ZFC) together with the existence of infinitely many Woodin cardinals. Since Woodin cardinals are strongly inaccessible, if AD is consistent, then so are an infinity of inaccessible cardinals.

Moreover, if to the hypothesis of an infinite set of Woodin cardinals is added the existence of a measurable cardinal larger than all of them, a very strong theory of Lebesgue measurable sets of reals emerges, as it is then provable that the axiom of determinacy is true in L(R), and therefore that every set of real numbers in L(R) is determined.

Projective ordinals

Moschovakis introduced the ordinals $\delta _{n}^{1}$, which is the upper bound of the length of ${\boldsymbol {\Delta }}_{n}^{1}$-norms (injections of a ${\boldsymbol {\Delta }}_{n}^{1}$ set into the ordinals), where Failed to parse (syntax error): {\displaystyle \boldsymbol_n^1} is a level of the projective hierarchy. Assuming AD, all $\delta _{n}^{1}$ are initial ordinals, and we have $\delta _{2n+2}^{1}=(\delta _{2n+1}^{1})^{+}$, and the $2n$th Suslin cardinals may be characterized in terms of $\delta _{2n-1}^{1}$.

See also

• Axiom of real determinacy (AD_R)
• Borel determinacy theorem
• Martin measure
• Topological game

References

• Mycielski, Jan; Steinhaus, Hugo (1962). "A mathematical axiom contradicting the axiom of choice". Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques. 10: 1–3. ISSN 0001-4117. MR 0140430.
• Mycielski, Jan; Świerczkowski, Stanisław (1964). "On the Lebesgue measurability and the axiom of determinateness". Fund. Math. 54: 67–71. doi:10.4064/fm-54-1-67-71.
• Woodin, W. Hugh (1988). "Supercompact cardinals, sets of reals, and weakly homogeneous trees". Proceedings of the National Academy of Sciences of the United States of America. 85 (18): 6587–6591. Bibcode:1988PNAS...85.6587W. doi:10.1073/pnas.85.18.6587. PMC 282022. PMID 16593979.
• Martin, Donald A.; Steel, John R. (Jan 1989). "A Proof of Projective Determinacy". Journal of the American Mathematical Society. 2 (1): 71–125. doi:10.2307/1990913. JSTOR 1990913.
• Jech, Thomas (2002). Set theory, third millennium edition (revised and expanded). Springer. ISBN 978-3-540-44085-7.
• Kanamori, Akihiro (2008). The Higher Infinite (2nd ed.). Springer Science & Business Media. ISBN 978-3-540-88866-6.
• Moschovakis, Yiannis N. (2009). Descriptive set theory (PDF) (2nd ed.). Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-4813-5. Archived from the original on 2014-11-12.{{cite book}}: CS1 maint: bot: original URL status unknown (link)

Further reading

• Philipp Rohde, On Extensions of the Axiom of Determinacy, Thesis, Department of Mathematics, University of Bonn, Germany, 2001
• Telgársky, R.J. Topological Games: On the 50th Anniversary of the Banach-Mazur Game, Rocky Mountain J. Math. 17 (1987), pp. 227–276. (3.19 MB)
• "Large Cardinals and Determinacy" at the Stanford Encyclopedia of Philosophy