Axiom of determinacy

In

winning strategy

.

Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model

ℵ₀

, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).

Types of game that are determined

The axiom of determinacy refers to games of the following specific form: Consider a subset A of the

infinite sequences of natural numbers

. Two players, 1 and 2, alternately pick natural numbers

n₀, n₁, n₂, n₃, ...

That generates the sequence ⟨n_i⟩_i∈ω after infinitely many moves. Player 1 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

Projective determinacy

).

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

).

Incompatibility with the axiom of choice

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.

Using a well-ordering of the continuum

The set S₁ of all first player strategies in an ω-game G has the same

well 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 set J to index both S₁ and S₂, and construct A such that it will be a counterexample.

We start with empty sets A and B. Let α ∈ J be the index of the strategies in S₁ and S₂. We need to consider all strategies S₁ = {s₁(α)}_α∈J of the first player and all strategies S₂ = {s₂(α)}_α∈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. Let t be the time whose axis has length ℵ₀ and which is used during each game sequence. We create the counterexample A by

transfinite recursion

on α:

Consider the strategy s₁(α) of the first player.

Apply this strategy on an ω-game, generating (together with the first player's strategy s₁(α)) a sequence ⟨a₁, b₂, a₃, b₄, ...,a_t, b_t+1, ...⟩, which does not belong to A. This is possible, because the number of choices for ⟨b₂, b₄, b₆, ...⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β ∈ J | β < α } of J.

Add this sequence to B to indicate that s₁(α) loses (on ⟨b₂, b₄, b₆, ...⟩).

Consider the strategy s₂(α) of the second player.

Apply this strategy on an ω-game, generating (together with the second player's strategy s₂(α)) a sequence ⟨a₁, b₂, a₃, b₄, ..., a_t, b_t+1, ...⟩, which does not belong to B. This is possible, because the number of choices for ⟨a₁, a₃, a₅, ...⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β ∈ J | β ≤ α } of J.

Add this sequence to A to indicate that s₂(α) loses (on ⟨a₁, a₃, a₅, ...⟩).

Process all possible strategies of S₁ and S₂ with transfinite induction on α. For all sequences that are not in A or B after that, decide arbitrarily whether they belong to A or to B, so that B is the complement of A.

Once this has been done, prepare for an ω-game G. For a given strategy s₁ of the first player, there is an α ∈ J such that s₁ = s₁(α), and A has been constructed such that s₁(α) fails (on certain choices ⟨b₂, b₄, b₆, ...⟩ of the second player). Hence, s₁ fails. Similarly, any other strategy of either player also fails.

Using a choice function

In this construction, the use of the axiom of choice is similar to the choice of socks as stated in the quote by Bertrand Russell at Axiom of choice#Quotations.

In a ω-game, the two players are generating the sequence ⟨a₁, b₂, a₃, b₄, ...⟩, an element in ω^ω, where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function f: ω^ω → {0, 1}^ω such that f(r) is the unique sequence of length ω with values are in {0, 1} whose first term equals 0, and whose sequence of runs (see

Minkowski question mark function, {0, 1}^ω is the Cantor space and ω^ω is the Baire space

.)

Observe the equivalence 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. Let T be the set of equivalence classes (such that T has the cardinality of the continuum). Define {0, 1}^ω → T that takes a sequence to its equivalence class. Define the complement of any sequence s in {0, 1}^ω to be the sequence s₁ that differs in each term. Define the function h: T → T such that for any sequence s in {0, 1}^ω, h applied to the equivalence class of s equals the equivalence class of the complement of s (which is well-defined because if s and s' are equivalent, then their complements are equivalent). One can show that h is an involution with no fixed points, and thus we have a partition of T 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 of T, a subset that we denote by U, such that t ∈ U iff h(t) ∉ U.

Next, we define the subset A ⊆ ω^ω in which 1 wins: A is the set of all r such that g(f(r)) ∈ U. We now claim that neither player has a winning strategy, using a strategy-stealing argument. Denote the current game state by a finite sequence of natural numbers (so that if the length of this sequence is even, then 1 is next to play; otherwise 2 is next to play).

Suppose that q is a (deterministic) winning strategy for 2. Player 1 can construct a strategy p that beats q as follows: Suppose that player 2's response (according to q) to ⟨1⟩ is b₁. Then 1 specifies in p that a₁ = 1 + b₁. (Roughly, 1 is now playing as 2 in a second parallel game; 1's winning set in the second game equals 2's winning set in the original game, and this is a contradiction. Nevertheless, we continue more formally.)

Suppose that 2's response (always according to q) to ⟨1 + b₁⟩ is b₂, and 2's response to ⟨1, b₁, b₂⟩ is b₃. We construct p for 1, we only aim to beat q, and therefore only have to handle the response b₂ to 1's first move. Therefore set 1's response to ⟨1 + b₁, b₂⟩ is b₃. In general, for even n, denote 2's response to ⟨1 + b₁, ..., b_n−1⟩ by b_n and 2's response to ⟨1, b₁, ..., b_n⟩ by b_n+1. Then 1 specify in p that 1's response to ⟨1 + b₁, b₂, ..., b_n⟩ is b_n+1. Strategy q is presumed to be winning, and game-result r in ω^ω given by ⟨1, b₁, ...⟩ is one possible sequence allowed by q, so r must be winning for 2 and g(f(r)) must not be in U. The game result r' in ω^ω given by ⟨1 + b₁, b₂, ...⟩ is also a sequence allowed by q (specifically, q playing against p), so g(f(r')) must not be in U. However, f(r) and f(r') differ in all but the first term (by the nature of run-length encoding and an offset of 1), so f(r) and f(r') are in complement equivalent classes, so g(f(r)), g(f(r')) cannot both be in U, contradicting the assumption that q is a winning strategy.

Similarly, suppose that p is a winning strategy for 1; 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. Let a₁ be 1's first move. In general, for even n, denote 1's response to ⟨a₁, 1⟩ (if n = 2) or ⟨a₁, 1, a₂, ..., a_n−1⟩ by a_n and 1's response to ⟨a₁, 1 + a₂, ... a_n⟩ by a_n+1. Then the game result r given by ⟨a₁, 1, a₂, a₃, ...⟩ is allowed by p so that g(f(r)) must be in U; also the game result r' given by ⟨a₁, 1 + a₂, a₃, ...⟩ is also allowed by p so that g(f(r')) must be in U. However, f(r) and f(r') differ in all but the first a₁ + 1 terms, so they are in complement equivalent classes, therefore g(f(r)) and g(f(r')) cannot both be in U, contradicting that p is a winning strategy.

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

Lebesgue measurable sets of reals emerges, as it is then provable that the axiom of determinacy is true in L(R)

, and therefore that every set of real numbers in L(R) is determined.

Projective ordinals

initial ordinals, and we have δ¹
_2n+2 = (δ¹
_2n+1)⁺, and for n < ω, the 2n-th Suslin cardinal is equal to δ¹
_2n−1.^[1]

References

MR 0140430
.

doi:10.4064/fm-54-1-67-71
.

PMID 16593979
.

JSTOR 1990913
.

ISBN 978-3-540-44085-7
.

ISBN 978-3-540-88866-6
.

ISBN 978-0-8218-4813-5. Archived
(PDF) from the original on 2014-11-12.

Inline citations

^ V. G. Kanovei, The axiom of determinacy and the modern development of descriptive set theory, UDC 510.225; 510.223, Plenum Publishing Corporation (1988) p.270,282. Accessed 20 January 2023.

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo