ⓘ Axiom of determinacy. In mathematics, the axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It ref ..


ⓘ Axiom of determinacy

In mathematics, the axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy.

They motivated AD by its interesting consequences, and suggested that AD could be true in the least natural model LR of a set theory, which accepts only a weak form of the axiom of choice AC but contains all real and all ordinal numbers. Some consequences of AD followed from theorems proved earlier by Stefan Banach and Stanislaw Mazur, and Morton Davis. Mycielski and Stanislaw Swierczkowski contributed another one: AD implies that all sets of real numbers are Lebesgue measurable. Later Donald A. Martin and others proved more important consequences, especially in descriptive set theory. In 1988, John R. Steel and W. Hugh Woodin concluded a long line of research. Assuming the existence of some uncountable cardinal numbers analogous to ℵ 0 {\displaystyle \aleph _{0}}, they proved the original conjecture of Mycielski and Steinhaus that AD is true in LR.


1. Types of game that are determined

The axiom of determinacy refers to games of the following specific form: Consider a subset A of the Baire space ω of all infinite sequences of natural numbers. Two players, I and II, alternately pick natural numbers

n 0, n 1, n 2, n 3.

After infinitely many moves, a sequence n i ∈ ω {\displaystyle n_{i}_{i\in \omega }} is generated. Player I wins the game if and only if the sequence generated is an element of A. 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 set A is clopen, the game is essentially a finite game, and is therefore determined. Similarly, if A is a closed set, then the game is determined. 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 sufficiently large cardinals that all games with winning set a projective set are determined see Projective determinacy, and that AD holds in LR.

The axiom of determinacy implies that for every subspace X of the real numbers, the Banach–Mazur game BM X is determined and therefore that every set of reals has the property of Baire.


2. Incompatibility of the axiom of determinacy with the axiom of choice

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 that 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 the cardinality of 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 {s1T} of the first player and all strategies {s2T} 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. Let t be the time whose axis has length ℵ 0 and which is used during each game sequence.

  • 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.
  • Go through the entire game, generating together with the first players strategy s1T) a sequence {a1, b2, a3, b4.,at, bt+1.}.
  • 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.
  • Decide that this sequence belongs to A, i.e. s2T lost.
  • Consider the strategy {s2T} of the second player.
  • Decide that this sequence does not belong to A, i.e. s1T lost.
  • Go through the next entire game, generating together with the second players strategy s2T) a sequence {c1, d2, c3, d4.,ct, dt+1.}, making sure that this sequence is different from {a1, b2, a3, b4.,at, bt+1.}.
  • Consider the current strategy {s1T} of the first player.

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 = Ts1. 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 and the axiom of choice are incompatible.


3. 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:

∀ G ⊆ S e q S: {\displaystyle \forall G\subseteq SeqS:}

∀ a ∈ S: ∃ a ′ ∈ S: ∀ b ∈ S: ∃ b ′ ∈ S: ∀ c ∈ S: ∃ c ′ ∈ S.: a, a ′, b, b ′, c, c ′. ∈ G {\displaystyle \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

∃ a ∈ S: ∀ a ′ ∈ S: ∃ b ∈ S: ∀ b ′ ∈ S: ∃ c ∈ S: ∀ c ′ ∈ S.: a, a ′, b, b ′, c, c ′. ∉ G {\displaystyle \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.\notin G}

Note: SeqS is the set of all ω {\displaystyle \omega } -sequences of S. The sentences here are infinitely long with a countably infinite list of quantifiers where the ellipses appear.

In an infinitary logic, this principle is therefore a natural generalization of the usual de Morgan rule for quantifiers that are true for finite formulas, such as ∀ a: ∃ b: ∀ c: ∃ d: R a, b, c, d {\displaystyle \forall a:\exists b:\forall c:\exists d:Ra,b,c,d} OR ∃ a: ∀ b: ∃ c: ∀ d: ¬ R a, b, c, d {\displaystyle \exists a:\forall b:\exists c:\forall d:\lnot Ra,b,c,d}.


4. 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–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 many Woodin cardinals. Since Woodin cardinals are strongly 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 a measurable cardinal larger than all of them, a very strong theory of Lebesgue measurable sets of reals emerges, as it is then provable that the axiom of determinacy is true in LR, and therefore that every set of real numbers in LR is determined.

  • projective determinacy is the special case of the axiom of determinacy applying only to projective sets. The axiom of projective determinacy abbreviated
  • Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning
  • In mathematics, the axiom of real determinacy abbreviated as ADR is an axiom in set theory. It states the following: Axiom - Consider infinite two - person
  • W. Hugh Woodin, to the axiom of determinacy The axiom which is to be understood in the context of ZF plus DCR the axiom of dependent choice for real
  • proof of the theorem in Zermelo Fraenkel set theory must make repeated use of the axiom of replacement. Later results showed that stronger determinacy theorems
  • determinacy Von Neumann Bernays Godel axioms Continuum hypothesis and its generalization Freiling s axiom of symmetry Axiom of determinacy Axiom of projective
  • University of North Texas. Much of his most notable work has involved the descriptive set - theoretic consequences of the axiom of determinacy In particular
  • is a filter on the set of Turing degrees of sets of natural numbers, named after Donald A. Martin. Under the axiom of determinacy it can be shown to be
  • Property of Baire Uniformization set theory Universally measurable set Determinacy AD Axiom of determinacy Axiom of projective determinacy Axiom of real
  • the axiom of determinacy The axiom of choice is avoided in some varieties of constructive mathematics, although there are varieties of constructive mathematics
  • relation can be uniformized in some transitive inner model of V in which the axiom of determinacy holds. Moschovakis, Yiannis N. 1980 Descriptive Set
  • L R does not satisfy the axiom of choice, but rather the axiom of determinacy However, L R will still satisfy the axiom of dependent choice, given only