Axiom of determinacy In mathematics , the axiom of determinacy ( abbreviated as AD ) is an axiom in set theory . It states the following : Consider infinite two-person games with perfect information . Then , every game of length ω where both players choose integers is determined , i.e. , one of the two players has a winning strategy . The axiom of determinacy is inconsistent with the axiom of choice ( AC ) ; indeed , it has been shown that it implies that all sets of reals are Lebesgue measurable and have the property of Baire . AD implies the consistency of ZF. Hence it is not possible to prove in ZF that ZF is consistent with AD . Types of game that are determined Not all games require the axiom of determinacy to prove them determined . Games whose winning sets are closed are determined . These correspond to many naturally defined infinite games . 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 sufficient large cardinals that all games with winning set a projective set are determined ( see Projective determinacy ) , and that AD holds in L ( R ) . Why the axiom of choice contradicts the axiom of determinacy The set of all first player strategies in an \omega -game G has the same cardinality as the continuum . The same is true of second player strategies . We note that the cardinality of all outcomes possible in G is also the continuum . With the axiom of choice we can well order the continuum ; furthermore , we can do so in such a way that any proper initial portion does not have cardinality the continuum . We create a counterexample by transfinite induction on the set of strategies under this well ordering : We start with no outcomes of the game decided . Consider the current strategy . Consider which player this strategy is for . The set of possible outcomes of this strategy which we have already decided on has cardinality less than the continuum. ( By choice of well ordering and the fact that we only decide on one outcome per strategy ) This means there are possible outcomes of this strategy that have not yet been decided . Pick an outcome of this strategy that has not yet been decided . Pick this outcome to be against the player this strategy was for . Repeat with the next strategy if there is one otherwise fill in any undefined outcomes in any way you see fit . Once this has been done we have a game G . If you give me a strategy S then we considered that strategy at some time t = t ( S ) . At time t , we decided an outcome of S that would be a win for the other player . Hence the other player need only fill in her moves correctly and she will win . Hence this strategy fails . But this is true for an arbitrary strategy ; hence the axiom of determinacy is false . Infinite 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 \in\ 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' ... ) \not\in 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 . If logic were generalised to allow infinite statements of the sort given above then the above statement could be interpreted as being of the form S OR not S and hence trivially true . However , many mathematicians do not agree with generalising logic in this way . 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-Frankel set theory without choice ( ZF ) together with the axiom of determinacy is equivalent to the consistency of Zermelo-Frankel 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 inacessible 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 every bounded set of real numbers in L ( R ) is measureable . Also , if the extremely strong rank-into-rank axiom I0 is posulated , it follows that the axiom of determinacy is true of L ( R ) , and hence that the suspicion that L ( R ) is a canonical inner model for AD within ZFC set theory is correct . Thus , assuming I0 is not contradictory , a coherent and powerful theory of AD and of measurable sets emerges . See also Axiom of real determinacy ( AD R ) AD + , a variant of the axiom of determinacy formulated by Woodin Axiom of quasi-determinacy ( ADQ ) References Jech , Thomas ( 2002 ) . Set theory , third millennium edition ( revised and expanded ) . Springer . ISBN 3-540-44085-2 . Kanamori , Akihiro ( 2000 ) . The Higher Infinite , second edition . Springer . ISBN 3-540-00384-3 . Martin , Donald A. and John R. Steel ( Jan. , 1989 ) . `` A Proof of Projective Determinacy '' . Journal of the American Mathematical Society 2 ( 1 ) : 71-125 . Moschovakis , Yiannis N. ( 1980 ) . Descriptive Set Theory . North Holland . ISBN 0-444-70199-0 . 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 . Further reading Philipp Rohde , On Extensions of the Axiom of Determinacy , Thesis , Department of Mathematics , University of Bonn , Germany , 2001 Søren Riis , A Fractal which violates the Axiom of Determinacy , BRICS-94-24 , available online Telgársky , R.J. Topological Games : On the 50th Anniversary of the Banach-Mazur Game , Rocky Mountain J. Math. 17 ( 1987 ) , pp. 227-276 . Categories : Axioms of set theory | Determinacy | Large cardinals In other languages : Polski Jech , Thomas Set theory , third millennium edition ( revised and expanded ) Springer 2002 ISBN 3-540-44085-2 Kanamori , Akihiro The Higher Infinite , second edition Springer 2000 ISBN 3-540-00384-3 Martin , Donald A. and John R. Steel Jan. , 1989 A Proof of Projective Determinacy Journal of the American Mathematical Society 2 1 71-125 Moschovakis , Yiannis N. Descriptive Set Theory North Holland 1980 ISBN 0-444-70199-0 Woodin , W. Hugh Proceedings of the National Academy of Sciences of the United States of America 1988 Supercompact cardinals , sets of reals , and weakly homogeneous trees 85 18 6587-6591 