Axiom of determinacy
Encyclopedia : A : AX : AXI : 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); 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.
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.
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 (ADR)
- AD+, a variant of the axiom of determinacy formulated by Woodin
- Axiom of quasi-determinacy (ADQ)
References
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.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.