Axiom of determinacy

From Wikipedia, the free encyclopedia

You have new messages (last change).

In mathematics, the axiom of determinacy (abbreviated as AD) is an axiom in set theory. It was introduced by Polish mathematicians: Mycielski and Steinhaus. 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.

Contents

[edit] 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).

[edit] Why the axiom of choice contradicts the axiom of determinacy

The set S1 of all first player strategies in an ω-game G has the same cardinality as the continuum. The same is true of the set S2 of all second player strategies. We note that the cardinality of the set SG of all sequences possible in G is also the continuum. Let A be the subset of SG of all sequences which make the first player win. 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 the set A undefined. Let T be the "time" whose axis has length continuum. We need to consider all strategies {s1(T)} of the first player and all strategies {s2(T)} of the second player to make sure that for every strategy there is a strategy of the other player that wins against it. For every strategy of the player considered we will generate a sequence which gives the other player a win. Let t be the time whose axis has length \aleph_0 and which is used during each game sequence.


  1. Consider the current strategy {s1(T)} of the first player.
  2. Go through the entire game, generating (together with the first player's strategy s1(T)) a sequence {a(1),b(2),a(3),b(4),...,a(t),b(t+1),...}.
  3. Decide that this sequence does not belong to A, i.e. s1(T) lost.
  4. Consider the strategy {s2(T)} of the second player.
  5. Go through the next entire game, generating (together with the second player's strategy s2(T)) a sequence {c(1),d(2),c(3),d(4),...,c(t),d(t+1),...}, making sure that this sequence is different from {a(1),b(2),a(3),b(4),...,a(t),b(t+1),...}.
  6. Decide that this sequence belongs to A, i.e. s2(T) lost.
  7. Keep repeating with further strategies if there are any, making sure that sequences already considered do not become generated again.(We start from the set of all sequences and each time we generate a sequence and refute a strategy we project the generated sequence onto first player moves and onto second player moves, and we take away the two resulting sequences from our set of sequences.)
  8. For all sequences that did not come up in the above consideration arbitrarily decide whether they belong to A, or to the complement of A.

Once this has been done we have a game G. If you give me a strategy s1 then we considered that strategy at some time T = T(s1). At time T, we decided an outcome of s1 that would be a loss of s1. Hence this strategy fails. But this is true for an arbitrary strategy; hence the axiom of determinacy is false.

[edit] 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 GOR

\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 ω-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.

[edit] 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.

[edit] See also

[edit] 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.

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../a/x/i/Axiom_of_determinacy.html"
In other languages