Axiom of determinacy
From Exampleproblems
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 property of Baire.
AD implies the consistency of ZF. Hence it is not possible to prove in ZF that ZF is consistent with AD.
Contents |
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 ω-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):
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 (ADR)
- 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 3540440852.
- Template:Journal reference
- Moschovakis, Yiannis N. (1980). Descriptive Set Theory, North Holland. ISBN 0-444-70199-0.
- Template:Journal reference
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
