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 , 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 n0, n1, n2, n3, ... After infinitely many moves, a sequence 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 present two separate constructions of counterexamples to the axiom of determinacy. It follows that the axiom of determinacy and the axiom of choice are incompatible.
Using well-ordering of the continuum
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 α 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 ℵ0 and which is used during each game sequence. We create the counterexample A by transfinite recursion on α: