| 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); 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.
- 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 deteminacy 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.
External links
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 (http://www.brics.dk/RS/94/24/BRICS-RS-94-24.ps.gz)
- Thomas Jech, Set theory, third millenium edition (revised and expanded), Springer 2002, ISBN 3540440852
|
