In mathematics, the axiom of determinacy (abbreviated as AD) is an axiom in set theory. It states the following:

The axiom of determinacy is inconsistent with the axiom of choice (AC); however, it has been shown that it implies that all sets of reals are Lebesgue measurable and have the Baire property.

The axiom of determinacy has not been proved consistent with ZF and cannot even be proved to be independent of ZF (assuming that ZF is consistent) without further axioms. It does not follow from ZF (since AC is independent of ZF). It is possible that the axiom of determinacy can be proved false without the use of the axiom of choice.

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 has been suggested that all games with winning set a projective set may be determined (see Projective determinacy).

Why the axiom of choice contradicts the axiom of determinacy

The set of all first player strategies in an ω-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.

1. Consider the current strategy. Consider which player this strategy is for.
2. 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)
3. This means there are possible outcomes of this strategy that have not yet been decided.
4. Pick an outcome of this strategy that has not yet been decided.
5. Pick this outcome to be against the player this strategy was for.
6. 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 infinite 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):

OR

Note: Seq(S) is the set of all ω-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.

See also

• Axiom of real determinacy (AD_R)
• AD⁺ , a variant of the axiom of determinacy formulated by Woodin
• Axiom of quasi-determinacy (ADQ)

External links

• Dmytro Taranovsky: A Case for the Axiom of Determinacy, posted on the Foundations of Mathematics mailing list

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 with violates the Axiom of Determinacy, BRICS-94-24, available online
• Thomas Jech, Set theory, third millennium edition (revised and expanded), Springer 2002, ISBN 3540440852