Inmathematics, theaxiom of determinacy (abbreviated asAD) is a possibleaxiom forset theory introduced byJan Mycielski andHugo Steinhaus in 1962. It refers to certain two-persontopological games of lengthω. AD states that every game of acertain type isdetermined; that is, one of the two players has awinning strategy.
Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural modelL(R) of a set theory, which accepts only a weak form of theaxiom of choice (AC) but contains allreal and allordinal numbers. Some consequences of AD followed from theorems proved earlier byStefan Banach andStanisław Mazur, andMorton Davis.Mycielski andStanisław Świerczkowski contributed another one: AD implies that all sets ofreal numbers areLebesgue measurable. LaterDonald A. Martin and others proved more important consequences, especially indescriptive set theory. In 1988,John R. Steel andW. Hugh Woodin concluded a long line of research. Assuming the existence of someuncountable cardinal numbers analogous to ℵ0, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).
The axiom of determinacy refers to games of the following specific form:Consider a subsetA of theBaire space ωω of allinfinite sequences ofnatural numbers. Two players alternately pick natural numbers
That generates the sequence ⟨ni⟩i∈ω after infinitely many moves. The player who picks first wins the game if and only if the sequence generated is an element ofA. The axiom of determinacy is the statement that all such games are determined.
Not all games require the axiom of determinacy to prove them determined. If the setA isclopen, the game is essentially a finite game, and is therefore determined. Similarly, ifA is aclosed set, then the game is determined. By theBorel determinacy theorem, games whose winning set is aBorel set are determined. It follows from the existence of sufficientlylarge cardinals that AD holds inL(R) and that a game is determined if it has aprojective set as its winning set (seeProjective determinacy).
The axiom of determinacy implies that for every subspaceX of thereal numbers, theBanach–Mazur game BM(X) is determined, and consequently, that every set of reals has theproperty of Baire.
Under assumption of the axiom of choice, we present two separate constructions of counterexamples to the axiom of determinacy. It follows that the axiom of determinacy and the axiom of choice are incompatible.
The setS1 of all first player strategies in an ω-gameG has the samecardinality as thecontinuum. The same is true for the setS2 of all second player strategies. LetSG be the set of all possible sequences inG, andA be the subset of sequences ofSG that make the first player win. With the axiom of choice we canwell order the continuum, and we can do so in such a way that any proper initial portion has lower cardinality than the continuum. We use the obtained well ordered setJ to index bothS1 andS2, and constructA such that it will be a counterexample.
We start with empty setsA andB. Letα ∈ J be the index of the strategies inS1 andS2. We need to consider all strategiesS1 = {s1(α)}α∈J of the first player and all strategiesS2 = {s2(α)}α∈J 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 that gives the other player a win. Lett be the time whose axis has length ℵ0 and which is used during each game sequence. We create the counterexampleA bytransfinite recursion onα:
Once this has been done, prepare for an ω-gameG. For a given strategys1 of the first player, there is anα ∈ J such thats1 = s1(α), andA has been constructed such thats1(α) fails (on certain choices ⟨b2,b4,b6, ...⟩ of the second player). Hence,s1 fails. Similarly, any other strategy of either player also fails.
In this construction, the use of the axiom of choice is similar to the choice of socks as stated in thequote by Bertrand Russell.
In a ω-game, the two players are generating the sequence ⟨a1,b2,a3,b4, ...⟩, an element in ωω, where our convention is that 0 is not a natural number, hence neither player can choose it. Define the functionf: ωω → {0, 1}ω such thatf(r) is the unique sequence of length ω with values in {0, 1} whose first term equals 0, and whose sequence of runs (seerun-length encoding) equalsr. (Such anf can be shown to be injective. The image is the subset of {0, 1}ω of sequences that start with 0 and that are not eventually constant. Formally,f is theMinkowski question mark function, {0, 1}ω is theCantor space and ωω is theBaire space.)
Observe theequivalence relation on {0, 1}ω such that two sequences are equivalent if and only if they differ in a finite number of terms. This partitions the set into equivalence classes. LetT be the set of equivalence classes (such thatT has the cardinality of the continuum). Defineg: {0, 1}ω → T that takes a sequence to its equivalence class. Define the complement of any sequences in {0, 1}ω to be the sequence s1 that differs in each term. Define the functionh: T → T such that for any sequences in {0, 1}ω,h applied to the equivalence class ofs equals the equivalence class of the complement ofs (which is well-defined because ifs ands' are equivalent, then their complements are equivalent). One can show thath is aninvolution with no fixed points, and thus we have a partition ofT into size-2 subsets such that each subset is of the form {t, h(t)}. Using the axiom of choice, we can choose one element out of each subset. In other words, we are choosing "half" of the elements ofT, a subset that we denote byU (where U ⊆ T) such thatt ∈ U iffh(t) ∉ U.
Next, we define the subsetA ⊆ ωω in which1 wins:A is the set of allr such thatg(f(r)) ∈ U. We now claim that neither player has a winning strategy, using astrategy-stealing argument. Denote the current game state by a finite sequence of natural numbers (so that if the length of this sequence is even, then1 is next to play; otherwise2 is next to play).
Suppose thatq is a (deterministic) winning strategy for2. Player1 can construct a strategyp that beatsq as follows: Suppose that player2's response (according toq) to ⟨1⟩ isb1. Then1 specifies inp thata1 = 1 + b1. (Roughly,1 is now playing as2 in a second parallel game;1's winning set in the second game equals2's winning set in the original game, and this is a contradiction. Nevertheless, we continue more formally.)
Suppose that2's response (always according toq) to ⟨1 + b1⟩ isb2, and2's response to ⟨1,b1,b2⟩ isb3. In constructingp for1, we only aim to beatq, and therefore only have to handle the responseb2 to1's first move. Therefore setb3 as1's response to ⟨1 + b1,b2⟩. In general, for evenn, denote2's response to ⟨1 + b1, ..., bn−1⟩ bybn and2's response to ⟨1,b1, ...,bn⟩ bybn+1. Then we specify inp that1's response to ⟨1 + b1,b2, ...,bn⟩ isbn+1. Strategyq is presumed to be winning, and game-resultr in ωω given by ⟨1,b1, ...⟩ is one possible sequence allowed byq, sor must be winning for2 andg(f(r)) must not be inU. The game resultr' in ωω given by ⟨1 + b1,b2, ...⟩ is also a sequence allowed byq (specifically,q playing againstp), sog(f(r')) must not be inU. However,f(r) andf(r') differ in all but the first term (by the nature of run-length encoding and an offset of 1), sof(r) andf(r') are in complement equivalent classes, sog(f(r)),g(f(r')) cannot both be inU, contradicting the assumption thatq is a winning strategy.
Similarly, suppose thatp is a winning strategy for1; the argument is similar but now uses the fact that equivalence classes were defined by allowing an arbitrarily large finite number of terms to differ. Leta1 be1's first move. In general, for evenn, denote1's response to ⟨a1, 1⟩ (ifn = 2) or ⟨a1, 1,a2, ...,an−1⟩ byan and1's response to ⟨a1, 1 + a2, ...an⟩ byan+1. Then the game resultr given by ⟨a1, 1,a2,a3, ...⟩ is allowed byp so thatg(f(r)) must be inU; also the game resultr' given by ⟨a1, 1 + a2,a3, ...⟩ is also allowed byp so thatg(f(r')) must be inU. However,f(r) andf(r') differ in all but the firsta1 + 1 terms, so they are in complement equivalent classes, thereforeg(f(r)) andg(f(r')) cannot both be inU, contradicting thatp is a winning strategy.
The consistency of the axiom of determinacy is closely related to the question of the consistency oflarge cardinal axioms. By a theorem ofWoodin, the consistency ofZermelo–Fraenkel set theory without choice (ZF) together with the axiom of determinacy is equivalent to the consistency of Zermelo–Fraenkel set theory with choice (ZFC) together with the existence of infinitely manyWoodin cardinals. Since Woodin cardinals arestrongly inaccessible, if AD is consistent, then so are an infinity of inaccessible cardinals.
Moreover, if to the hypothesis of an infinite set of Woodin cardinals is added the existence of ameasurable cardinal larger than all of them, a very strong theory ofLebesgue measurable sets of reals emerges, as it is then provable that the axiom of determinacy is true inL(R), and therefore thatevery set of real numbers in L(R) is determined.
Yiannis Moschovakis introduced the ordinals δ1
n, which is the upper bound of the length ofΔ1
n-norms (injections of aΔ1
n set into the ordinals), whereΔ1
n is a level of theprojective hierarchy. Assuming AD, all δ1
n areinitial ordinals, and we haveδ1
2n+2 = (δ1
2n+1)+, and forn < ω, the2n-thSuslin cardinal is equal to δ1
2n−1.[1]
| Overview |  | |
|---|---|---|
| Axioms | ||
| Operations | ||
| ||
| Set types | ||
| Theories | ||
| ||
| Set theorists | ||