Jump to content

Edit filter log

Details for log entry 37424741

14:19, 9 April 2024: DerSpezialist (talk | contribs) triggered filter 550, performing the action "edit" on Axiom of determinacy. Actions taken: Tag; Filter description: nowiki tags inserted into an article (examine | diff)

Changes made in edit

In [[mathematics]], the '''axiom of determinacy''' (abbreviated as '''AD''') is a possible [[axiom]] for [[set theory]] introduced by [[Jan Mycielski]] and [[Hugo Steinhaus]] in 1962. It refers to certain two-person [[topological game]]s of length [[ω (ordinal number)|ω]]. AD states that every game of a [[Axiom of determinacy#Types of game that are determined|certain type]] is [[determined game|determined]]; that is, one of the two players has a [[winning strategy]].
In [[mathematics]], the '''axiom of determinacy''' (abbreviated as '''AD''') is a possible [[axiom]] for [[set theory]] introduced by [[Jan Mycielski]] and [[Hugo Steinhaus]] in 1962. It refers to certain two-person [[topological game]]s of length [[ω (ordinal number)|ω]]. AD states that every game of a [[Axiom of determinacy#Types of game that are determined|certain type]] is [[determined game|determined]]; that is, one of the two players has a [[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 [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to <math>\alef_0</math>, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).
Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to [[Aleph-zero|&aleph;<sub>0</sub>]], they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).


==Types of game that are determined==
==Types of game that are determined==

The axiom of determinacy refers to games of the following specific form:
The axiom of determinacy refers to games of the following specific form:
Consider a subset ''A'' of the [[Baire space (set theory)|Baire space]] ''ω<sup>ω</sup>'' of all [[infinite sequence]]s of [[natural number]]s. Two players, '''I''' and '''II''', alternately pick natural numbers
Consider a subset ''A'' of the [[Baire space (set theory)|Baire space]] ω<sup>ω</sup> of all [[infinite sequence]]s of [[natural number]]s. Two players, '''1''' and '''2''', alternately pick natural numbers
:''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>, ...
:''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>,&nbsp;…
After infinitely many moves, a sequence <math>(n_i)_{i \in \omega}</math> 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.
That generates the sequence ⟨''n''<sub>''i''</sub>⟩<sub>''i''∈ω</sub> 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 [[Clopen set|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 cardinal]]s that all games with winning set a [[projective set]] are determined (see [[Projective determinacy]]), and that AD holds in [[L(R)]].


Not all games require the axiom of determinacy to prove them determined. If the set ''A'' is [[Clopen set|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 cardinal]]s that AD holds in [[L(R)]] and that a game is determined if it has a [[projective set]] as its winning set (see [[Projective determinacy]]).
The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|real numbers]], the [[Banach–Mazur game]] ''BM''(''X'') is determined (and therefore that every set of reals has the [[property of Baire]]).


The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|real numbers]], the [[Banach–Mazur game]] BM(''X'') is determined (and therefore that every set of reals has the [[property of Baire]]).
== Incompatibility of the axiom of determinacy with the axiom of choice ==


== 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.
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 well-ordering of the continuum ===
=== Using a well-ordering of the continuum ===
The set ''S''<sub>1</sub> of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set ''S''<sub>2</sub> of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and ''A'' be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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''<sub>1</sub> and ''S''<sub>2</sub>, and construct ''A'' such that it will be a counterexample.


We start with empty sets ''A'' and ''B''. Let ''&alpha;''&nbsp;∈&nbsp;''J'' be the index of the strategies in ''S''<sub>1</sub> and ''S''<sub>2</sub>. We need to consider all strategies ''S''<sub>1</sub>&nbsp;=&nbsp;{s<sub>1</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> of the first player and all strategies ''S''<sub>2</sub>&nbsp;=&nbsp;{s<sub>2</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample ''A'' by [[transfinite recursion]] on ''&alpha;'':
The set S1 of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set S2 of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and A be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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 S1 and S2, and construct A such that it will be a counterexample.


# Consider the strategy s<sub>1</sub>(''&alpha;'') of the first player.
We start with empty sets A and B. Let α <math>\in</math> J be the index of the strategies in S1 and S2. We need to consider all strategies S1 = {s1(α)} of the first player and all strategies S2 = {s2(α)} 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample A by [[transfinite recursion]] on α:
# Apply this strategy on an ω-game, generating (together with the first player's strategy s<sub>1</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…,a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''A''. This is possible, because the number of choices for ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;<&nbsp;''&alpha;''&nbsp;} of ''J.''
# Add this sequence to ''B'' to indicate that s<sub>1</sub>(''&alpha;'') loses (on ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩).
# Consider the strategy s<sub>2</sub>(''&alpha;'') of the second player.
# Apply this strategy on an ω-game, generating (together with the second player's strategy ''s''<sub>2</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…, a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''B.'' This is possible, because the number of choices for ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;≤&nbsp;''&alpha;''&nbsp;} of ''J.''
# Add this sequence to ''A'' to indicate that ''s''<sub>2</sub>(''&alpha;'') loses (on ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩).
# Process all possible strategies of ''S''<sub>1</sub> and ''S''<sub>2</sub> with [[transfinite induction]] on ''&alpha;.'' 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''<sub>1</sub> of the first player, there is an ''&alpha;''&nbsp;∈&nbsp;''J'' such that ''s''<sub>1</sub>&nbsp;=&nbsp;''s''<sub>1</sub>(''&alpha;''), and ''A'' has been constructed such that ''s''<sub>1</sub>(''&alpha;'') fails (on certain choices ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ of the second player). Hence, ''s''<sub>1</sub> fails. Similarly, any other strategy of either player also fails.
# Consider the strategy s1(α) of the first player.
#Apply this strategy on an ω-game, generating (together with the first player's strategy s1(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to A. This is possible, because the number of choices for {b(2), b(4), b(6), ...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math><</math> α } of J.
#Add this sequence to B (if it is not already in B), to indicate that s1(α) loses (on {b(2), b(4), b(6), ...}).
#Consider the strategy s2(α) of the second player.
#Apply this strategy on an ω-game, generating (together with the second player's strategy s2(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to B. This is possible, because the number of choices for {a(1), a(3), a(5),...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math>\le</math> α } of J.
#Add this sequence to A (if it is not already in A), to indicate that s2(α) loses (on {a(1), a(3), a(5), ...}).
#Process all possible strategies of S1 and S2 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 B is the complement of A.


=== Using a choice function ===
Once this has been done, prepare for an ω-game ''G''. For a given strategy s1 of the first player, there is an α <math>\in</math> J such that s1 = s1(α), and A has been constructed such that s1(α) fails (on certain choices {b(2), b(4), b(6), ...} 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 the quote by Bertrand Russell at [[Axiom of choice#Quotations]].


In a ω-game, the two players are generating the sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…⟩, an element in ω<sup>ω</sup>, where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function ''f''&#x202F;:&nbsp;&omega;<sup>&omega;</sup>&nbsp;→&nbsp;{0,&nbsp;1}<sup>&omega;</sup> 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 [[run-length encoding]]) equals ''r.'' (Such an ''f'' can be shown to be injective. The image is the subset of {0,&nbsp;1}<sup>&omega;</sup> of sequences that start with 0 and that are not eventually constant. Formally, ''f'' is the [[Minkowski question mark function]], {0,&nbsp;1}<sup>&omega;</sup> is the [[Cantor space]] and ω<sup>ω</sup> is the [[Baire space (set theory)|Baire space]].)
=== Using a choice function on a partition of the continuum into size-2 sets ===


Observe the [[equivalence relation]] on {0,&nbsp;1}<sup>&omega;</sup> 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,&nbsp;1}<sup>&omega;</sup>&nbsp;→&nbsp;''T'' that takes a sequence to its equivalence class. Define the complement of any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup> to be the sequence s<sub>1</sub> that differs in each term. Define the function ''h''&#x202F;:&nbsp;''T''&nbsp;→&nbsp;''T'' such that for any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup>, ''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_(mathematics)|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'',&nbsp;''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''&nbsp;∈&nbsp;''U'' iff ''h''(''t'')&nbsp;∉&nbsp;''U.''
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]].


Next, we define the subset ''A''&nbsp;⊆&nbsp;ω<sup>ω</sup> in which '''1''' wins: ''A'' is the set of all ''r'' such that ''g''(''f''(''r''))&nbsp;∈&nbsp;''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).
In a ω-game, the two players are generating the sequence <math>{a(1), b(2), a(3), b(4) ...}</math>, an element in ''ω<sup>ω</sup>'', where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function <math>f: \omega^\omega \rightarrow \{0, 1\}^\omega </math> such that f(r) is the unique sequence of length ω whose values are in {0, 1}, whose first term equals 0, and whose sequence of runs (see [[run-length encoding]]) equals r. (f can be shown to be injective. The image is the subset of <math> \{0, 1\}^\omega </math> of sequences that start with 0 and that are not eventually constant. Formally, f is the [[Minkowski question mark function]], <math> \{0, 1\}^\omega </math> is the [[Cantor space]] and ''ω<sup>ω</sup>'' is the [[Baire space (set theory)|Baire space]].)


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''<sub>1</sub>. Then '''1''' specifies in ''p'' that ''a''<sub>1</sub>&nbsp;=&nbsp;1&nbsp;+&nbsp;''b''<sub>1</sub>. (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.)
Observe the [[equivalence relation]] on <math>\{0, 1\}^\omega </math> 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, and let T be the set of equivalence classes (such that T has the cardinality of the continuum). Define <math>\{0, 1\}^\omega \rightarrow T</math> that takes a sequence to its equivalence class. Define the complement of any sequence s in <math>\{0, 1\}^\omega </math> to be the sequence s<sub>1</sub> that differs in each term. Define the function <math> h: T \rightarrow T </math> such that for any sequence s in <math>\{0, 1\}^\omega </math>, 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_(mathematics)|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 is in U iff h(t) is not in U.


Suppose that '''2'''{{`s}} response (always according to ''q'') to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub> is ''b''<sub>2</sub>, and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>, ''b''<sub>2</sub> is ''b''<sub>3</sub>. We construct ''p'' for '''1''', we only aim to beat ''q,'' and therefore only have to handle the response ''b''<sub>2</sub> to '''1'''{{`s}} first move. Therefore set '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub> is ''b''<sub>3</sub>. In general, for even ''n,'' denote '''2'''{{`s}} response to ⟨1&nbsp;+&nbsp;b<sub>1</sub>,&nbsp;…, b<sub>''n''−1</sub> by ''b''<sub>''n''</sub> and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>,&nbsp;…, ''b''<sub>''n''</sub> by ''b''<sub>''n''+1</sub>. Then '''1''' specify in ''p'' that '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…, ''b''<sub>''n''</sub> is ''b''<sub>''n''+1</sub>. Strategy ''q'' is presumed to be winning, and game-result ''r'' in ω<sup>ω</sup> given by ⟨1, ''b''<sub>1</sub>,&nbsp;…⟩ 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''<nowiki/>' in ω<sup>ω</sup> given by ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…⟩ is also a sequence allowed by ''q'' (specifically, ''q'' playing against ''p''), so ''g''(''f''(''r''<nowiki/>')) must not be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') 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''<nowiki/>') are in complement equivalent classes, so ''g''(''f''(''r'')), ''g''(''f''(''r''<nowiki/>')) cannot both be in ''U,'' contradicting the assumption that ''q'' is a winning strategy.
Next, we define the subset A of ''ω<sup>ω</sup>'' in which player 1 wins: A is the set of all r such that g(f(r)) is in 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 player 1 is next to play; otherwise player 2 is next to play).


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''<sub>1</sub> be '''1'''{{`s}} first move. In general, for even ''n,'' denote '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1⟩ (if ''n''&nbsp;=&nbsp;2) or ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>,&nbsp;…, ''a''<sub>n−1</sub> by ''a''<sub>''n''</sub> and '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>,&nbsp;… ''a''<sub>''n''</sub> by ''a''<sub>''n''+1</sub>. Then the game result ''r'' given by ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is allowed by ''p'' so that ''g''(''f''(''r'')) must be in ''U''; also the game result ''r''<nowiki/>' given by ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is also allowed by ''p'' so that ''g''(''f''(''r''<nowiki/>')) must be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') differ in all but the first ''a''<sub>1</sub>&nbsp;+&nbsp;1 terms, so they are in complement equivalent classes, therefore ''g''(''f''(''r'')) and ''g''(''f''(''r''<nowiki/>')) cannot both be in ''U,'' contradicting that ''p'' is a winning strategy.
Suppose that q is a (deterministic) winning strategy for player 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<sub>1</sub>. Then player 1 specifies in p that a(1) = 1 + b<sub>1</sub>. (Roughly, player 1 is now playing as the second player in a second parallel game; player 1's winning set in the second game equals player 2's winning set in the original game, and this is a contradiction. Nevertheless, we continue more formally).

Suppose that player 2's response (always according to q) to [1 + b<sub>1</sub>] is b<sub>2</sub>, and player 2's response to [1, b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. When player 1 is constructing p, they only aim to beat q, and therefore they only have to handle the response b<sub>2</sub> to their first move. Player 1 specifies that their response to [1 + b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. In general, for even n, denote player 2's response to [1 + b<sub>1</sub>, ..., b<sub>n-1</sub>] by b<sub>n</sub> and player 2s response to [1, b<sub>1</sub>, ..., b<sub>n</sub>] by b<sub>n + 1</sub>. Then player 1 specifies in p that their response to [1 + b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>] is b<sub>n + 1</sub>. Strategy q is presumed to be winning, and game-result r in ''ω<sup>ω</sup>'' given by [1, b<sub>1</sub>, ...] is one possible sequence allowed by q, so r must be winning for player 2 and g(f(r)) must not be in U. Game-result r' in ''ω<sup>ω</sup>'' given by [1 + b<sub>1</sub>, b<sub>2</sub>, ...] 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 player 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<sub>1</sub> be player 1's first move. In general, for even n, denote player 1's response to [a<sub>1</sub>, 1] (if n = 2) or [a<sub>1</sub>, 1, a<sub>2</sub>, ... a<sub>n-1</sub>] by a<sub>n</sub> and player 1's response to [a<sub>1</sub>, 1 + a<sub>2</sub>, ... a<sub>n</sub>] by a<sub>n + 1</sub>. Then game-result r given by [a<sub>1</sub>, 1, a<sub>2</sub>, a<sub>3</sub>, ...] is allowed by p so that g(f(r)) must be in U; also game-result r' given by [a<sub>1</sub>, 1 + a<sub>2</sub>, a<sub>3</sub>, ...] 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<sub>1</sub> + 1 terms, so they are in complement equivalent classes, so 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 ==
== 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 [[W. Hugh Woodin|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 cardinal]]s. Since Woodin cardinals are [[inaccessible cardinal|strongly inaccessible]], if AD is consistent, then so are an infinity of inaccessible cardinals.
The consistency of the axiom of determinacy is closely related to the question of the consistency of [[large cardinal]] axioms. By a theorem of [[W. Hugh Woodin|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 cardinal]]s. Since Woodin cardinals are [[inaccessible cardinal|strongly inaccessible]], if AD is consistent, then so are an infinity of inaccessible cardinals.




== Projective ordinals ==
== Projective ordinals ==
[[Yiannis Moschovakis]] introduced the ordinals &delta;{{su|b=''n''|p=1}}, which is the upper bound of the length of '''&Delta;'''{{su|b=''n''|p=1}}-norms (injections of a '''&Delta;'''{{su|b=''n''|p=1}} set into the ordinals), where '''&Delta;'''{{su|b=''n''|p=1}} is a level of the [[projective hierarchy]]. Assuming AD, all &delta;{{su|b=''n''|p=1}} are [[Initial ordinal|initial ordinals]], and we have {{nowrap|1=&delta;{{su|b=2''n''+2|p=1}} = (&delta;{{su|b=2''n''+1|p=1}})<sup>+</sup>}}, and for ''n''&nbsp;<&nbsp;&omega;, the {{nowrap|2''n''-th}} [[Suslin cardinal]] is equal to &delta;{{su|b=2''n''−1|p=1}}.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref>

[[Yiannis Moschovakis]] introduced the ordinals <math>\delta_n^1</math>, which is the upper bound of the length of <math>\boldsymbol\Delta_n^1</math>-norms (injections of a <math>\boldsymbol\Delta_n^1</math> set into the ordinals), where <math>\boldsymbol\Delta_n^1</math> is a level of the [[projective hierarchy]]. Assuming AD, all <math>\delta_n^1</math> are [[Initial ordinal|initial ordinals]], and we have <math>\delta_{2n+2}^1=(\delta_{2n+1}^1)^+</math>, and for <math>n<\omega</math> the <math>2n</math>th [[Suslin cardinal]] is equal to <math>\delta_{2n-1}^1</math>.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref>


== See also ==
== See also ==

* [[Axiom of real determinacy]] (AD<sub>R</sub>)
* [[Axiom of real determinacy]] (AD<sub>R</sub>)
* [[Borel determinacy theorem]]
* [[Borel determinacy theorem]]


== Further reading ==
== Further reading ==

* Philipp Rohde, ''On Extensions of the Axiom of Determinacy'', Thesis, Department of Mathematics, University of Bonn, Germany, 2001
* Philipp Rohde, ''On Extensions of the Axiom of Determinacy'', Thesis, Department of Mathematics, University of Bonn, Germany, 2001
* [[Rastislav J. Telgársky|Telgársky, R.J.]] [http://telgarska.com/1987-RMJM-Telgarsky-Topological-Games.pdf ''Topological Games: On the 50th Anniversary of the Banach-Mazur Game''], Rocky Mountain J. Math. '''17''' (1987), pp.&nbsp;227–276. (3.19 MB)
* [[Rastislav J. Telgársky|Telgársky, R.J.]] [http://telgarska.com/1987-RMJM-Telgarsky-Topological-Games.pdf ''Topological Games: On the 50th Anniversary of the Banach-Mazur Game''], Rocky Mountain J. Math. '''17''' (1987), pp.&nbsp;227–276. (3.19 MB)

Action parameters

VariableValue
Edit count of the user (user_editcount)
183
Name of the user account (user_name)
'DerSpezialist'
Age of the user account (user_age)
428344019
Groups (including implicit) the user is in (user_groups)
[ 0 => '*', 1 => 'user', 2 => 'autoconfirmed' ]
Rights that the user has (user_rights)
[ 0 => 'createaccount', 1 => 'read', 2 => 'edit', 3 => 'createtalk', 4 => 'writeapi', 5 => 'viewmyprivateinfo', 6 => 'editmyprivateinfo', 7 => 'editmyoptions', 8 => 'abusefilter-log-detail', 9 => 'urlshortener-create-url', 10 => 'centralauth-merge', 11 => 'abusefilter-view', 12 => 'abusefilter-log', 13 => 'vipsscaler-test', 14 => 'collectionsaveasuserpage', 15 => 'reupload-own', 16 => 'move-rootuserpages', 17 => 'createpage', 18 => 'minoredit', 19 => 'editmyusercss', 20 => 'editmyuserjson', 21 => 'editmyuserjs', 22 => 'sendemail', 23 => 'applychangetags', 24 => 'viewmywatchlist', 25 => 'editmywatchlist', 26 => 'spamblacklistlog', 27 => 'mwoauthmanagemygrants', 28 => 'reupload', 29 => 'upload', 30 => 'move', 31 => 'autoconfirmed', 32 => 'editsemiprotected', 33 => 'skipcaptcha', 34 => 'ipinfo', 35 => 'ipinfo-view-basic', 36 => 'transcode-reset', 37 => 'transcode-status', 38 => 'createpagemainns', 39 => 'movestable', 40 => 'autoreview' ]
Whether or not a user is editing through the mobile interface (user_mobile)
false
Whether the user is editing from mobile app (user_app)
false
Page ID (page_id)
1002300
Page namespace (page_namespace)
0
Page title without namespace (page_title)
'Axiom of determinacy'
Full page title (page_prefixedtitle)
'Axiom of determinacy'
Edit protection level of the page (page_restrictions_edit)
[]
Page age in seconds (page_age)
616967931
Action (action)
'edit'
Edit summary/reason (summary)
'Typography: Use HTML markup as <math> is unnecessary (no complicated formulas); also some other minor changes'
Old content model (old_content_model)
'wikitext'
New content model (new_content_model)
'wikitext'
Old page wikitext, before the edit (old_wikitext)
'{{Short description|Possible axiom for set theory}} In [[mathematics]], the '''axiom of determinacy''' (abbreviated as '''AD''') is a possible [[axiom]] for [[set theory]] introduced by [[Jan Mycielski]] and [[Hugo Steinhaus]] in 1962. It refers to certain two-person [[topological game]]s of length [[ω (ordinal number)|ω]]. AD states that every game of a [[Axiom of determinacy#Types of game that are determined|certain type]] is [[determined game|determined]]; that is, one of the two players has a [[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 [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to <math>\alef_0</math>, 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 [[Baire space (set theory)|Baire space]] ''ω<sup>ω</sup>'' of all [[infinite sequence]]s of [[natural number]]s. Two players, '''I''' and '''II''', alternately pick natural numbers :''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>, ... After infinitely many moves, a sequence <math>(n_i)_{i \in \omega}</math> 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 set|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 cardinal]]s that all games with winning set a [[projective set]] are determined (see [[Projective determinacy]]), and that AD holds in [[L(R)]]. The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|real numbers]], the [[Banach–Mazur game]] ''BM''(''X'') is determined (and therefore that every set of reals has the [[property of Baire]]). == Incompatibility of the axiom of determinacy 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 well-ordering of the continuum === The set S1 of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set S2 of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and A be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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 S1 and S2, and construct A such that it will be a counterexample. We start with empty sets A and B. Let α <math>\in</math> J be the index of the strategies in S1 and S2. We need to consider all strategies S1 = {s1(α)} of the first player and all strategies S2 = {s2(α)} 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample A by [[transfinite recursion]] on α: # Consider the strategy s1(α) of the first player. #Apply this strategy on an ω-game, generating (together with the first player's strategy s1(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to A. This is possible, because the number of choices for {b(2), b(4), b(6), ...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math><</math> α } of J. #Add this sequence to B (if it is not already in B), to indicate that s1(α) loses (on {b(2), b(4), b(6), ...}). #Consider the strategy s2(α) of the second player. #Apply this strategy on an ω-game, generating (together with the second player's strategy s2(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to B. This is possible, because the number of choices for {a(1), a(3), a(5),...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math>\le</math> α } of J. #Add this sequence to A (if it is not already in A), to indicate that s2(α) loses (on {a(1), a(3), a(5), ...}). #Process all possible strategies of S1 and S2 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 B is the complement of A. Once this has been done, prepare for an ω-game ''G''. For a given strategy s1 of the first player, there is an α <math>\in</math> J such that s1 = s1(α), and A has been constructed such that s1(α) fails (on certain choices {b(2), b(4), b(6), ...} of the second player). Hence, s1 fails. Similarly, any other strategy of either player also fails. === Using a choice function on a partition of the continuum into size-2 sets === 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 <math>{a(1), b(2), a(3), b(4) ...}</math>, an element in ''ω<sup>ω</sup>'', where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function <math>f: \omega^\omega \rightarrow \{0, 1\}^\omega </math> such that f(r) is the unique sequence of length ω whose values are in {0, 1}, whose first term equals 0, and whose sequence of runs (see [[run-length encoding]]) equals r. (f can be shown to be injective. The image is the subset of <math> \{0, 1\}^\omega </math> of sequences that start with 0 and that are not eventually constant. Formally, f is the [[Minkowski question mark function]], <math> \{0, 1\}^\omega </math> is the [[Cantor space]] and ''ω<sup>ω</sup>'' is the [[Baire space (set theory)|Baire space]].) Observe the [[equivalence relation]] on <math>\{0, 1\}^\omega </math> 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, and let T be the set of equivalence classes (such that T has the cardinality of the continuum). Define <math>\{0, 1\}^\omega \rightarrow T</math> that takes a sequence to its equivalence class. Define the complement of any sequence s in <math>\{0, 1\}^\omega </math> to be the sequence s<sub>1</sub> that differs in each term. Define the function <math> h: T \rightarrow T </math> such that for any sequence s in <math>\{0, 1\}^\omega </math>, 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_(mathematics)|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 is in U iff h(t) is not in U. Next, we define the subset A of ''ω<sup>ω</sup>'' in which player 1 wins: A is the set of all r such that g(f(r)) is in 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 player 1 is next to play; otherwise player 2 is next to play). Suppose that q is a (deterministic) winning strategy for player 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<sub>1</sub>. Then player 1 specifies in p that a(1) = 1 + b<sub>1</sub>. (Roughly, player 1 is now playing as the second player in a second parallel game; player 1's winning set in the second game equals player 2's winning set in the original game, and this is a contradiction. Nevertheless, we continue more formally). Suppose that player 2's response (always according to q) to [1 + b<sub>1</sub>] is b<sub>2</sub>, and player 2's response to [1, b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. When player 1 is constructing p, they only aim to beat q, and therefore they only have to handle the response b<sub>2</sub> to their first move. Player 1 specifies that their response to [1 + b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. In general, for even n, denote player 2's response to [1 + b<sub>1</sub>, ..., b<sub>n-1</sub>] by b<sub>n</sub> and player 2s response to [1, b<sub>1</sub>, ..., b<sub>n</sub>] by b<sub>n + 1</sub>. Then player 1 specifies in p that their response to [1 + b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>] is b<sub>n + 1</sub>. Strategy q is presumed to be winning, and game-result r in ''ω<sup>ω</sup>'' given by [1, b<sub>1</sub>, ...] is one possible sequence allowed by q, so r must be winning for player 2 and g(f(r)) must not be in U. Game-result r' in ''ω<sup>ω</sup>'' given by [1 + b<sub>1</sub>, b<sub>2</sub>, ...] 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 player 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<sub>1</sub> be player 1's first move. In general, for even n, denote player 1's response to [a<sub>1</sub>, 1] (if n = 2) or [a<sub>1</sub>, 1, a<sub>2</sub>, ... a<sub>n-1</sub>] by a<sub>n</sub> and player 1's response to [a<sub>1</sub>, 1 + a<sub>2</sub>, ... a<sub>n</sub>] by a<sub>n + 1</sub>. Then game-result r given by [a<sub>1</sub>, 1, a<sub>2</sub>, a<sub>3</sub>, ...] is allowed by p so that g(f(r)) must be in U; also game-result r' given by [a<sub>1</sub>, 1 + a<sub>2</sub>, a<sub>3</sub>, ...] 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<sub>1</sub> + 1 terms, so they are in complement equivalent classes, so 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 [[W. Hugh Woodin|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 cardinal]]s. Since Woodin cardinals are [[inaccessible cardinal|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 [[L(R)]], and therefore that ''every'' set of real numbers in L(R) is determined. == Projective ordinals == [[Yiannis Moschovakis]] introduced the ordinals <math>\delta_n^1</math>, which is the upper bound of the length of <math>\boldsymbol\Delta_n^1</math>-norms (injections of a <math>\boldsymbol\Delta_n^1</math> set into the ordinals), where <math>\boldsymbol\Delta_n^1</math> is a level of the [[projective hierarchy]]. Assuming AD, all <math>\delta_n^1</math> are [[Initial ordinal|initial ordinals]], and we have <math>\delta_{2n+2}^1=(\delta_{2n+1}^1)^+</math>, and for <math>n<\omega</math> the <math>2n</math>th [[Suslin cardinal]] is equal to <math>\delta_{2n-1}^1</math>.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref> == See also == * [[Axiom of real determinacy]] (AD<sub>R</sub>) * [[Borel determinacy theorem]] * [[Martin measure]] * [[Topological game]] ==References== {{refbegin}} * {{Cite journal | last1=Mycielski | first1=Jan | author1-link = Jan Mycielski | last2=Steinhaus | first2=Hugo | author2-link = Hugo Steinhaus | title=A mathematical axiom contradicting the axiom of choice | mr=0140430 | year=1962 | journal=Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques | issn=0001-4117 | volume=10 | pages=1–3 }} * {{cite journal|last1=Mycielski | first1=Jan | author1-link = Jan Mycielski | last2=Świerczkowski | first2=Stanisław | author2-link = Stanisław Świerczkowski|title=On the Lebesgue measurability and the axiom of determinateness|journal=Fund. Math.|volume=54| year=1964|pages=67–71| doi=10.4064/fm-54-1-67-71 |doi-access=free}} * {{cite journal|author=Woodin, W. Hugh | author-link = W. Hugh Woodin |journal=[[Proceedings of the National Academy of Sciences of the United States of America]]|year=1988|title=Supercompact cardinals, sets of reals, and weakly homogeneous trees|volume=85|issue=18|pages=6587–6591|doi=10.1073/pnas.85.18.6587|pmid=16593979|pmc=282022| bibcode = 1988PNAS...85.6587W | doi-access = free }} * {{cite journal|last1=Martin |first1=Donald A. |author1-link=Donald A. Martin |first2=John R. |last2=Steel |author2-link=John R. Steel |date=Jan 1989|title=A Proof of Projective Determinacy |journal=[[Journal of the American Mathematical Society]] |volume=2 |issue=1 |pages=71–125 |doi=10.2307/1990913 |jstor=1990913 |doi-access=free }} * {{cite book|last=Jech | first = Thomas | author-link = Thomas Jech | title=Set theory, third millennium edition (revised and expanded)|publisher=Springer|year=2002|isbn=978-3-540-44085-7}} * {{cite book|last=Kanamori | first = Akihiro|author-link=Akihiro Kanamori|title=The Higher Infinite|title-link=The Higher Infinite|edition=2nd|year=2008|publisher=Springer Science & Business Media|isbn=978-3-540-88866-6}} * {{cite book|last1=Moschovakis |first1=Yiannis N. |author-link1=Yiannis N. Moschovakis |title=Descriptive set theory |date=2009 |publisher=American Mathematical Society |location=Providence, R.I. |isbn=978-0-8218-4813-5 |edition=2nd |url=https://www.math.ucla.edu/~ynm/lectures/dst2009/dst2009.pdf |url-status=live|archive-url=https://web.archive.org/web/20141112111558/http://www.math.ucla.edu/~ynm/lectures/dst2009/dst2009.pdf |archive-date=2014-11-12 }} {{refend}} ===Inline citations=== {{Reflist}} == Further reading == * Philipp Rohde, ''On Extensions of the Axiom of Determinacy'', Thesis, Department of Mathematics, University of Bonn, Germany, 2001 * [[Rastislav J. Telgársky|Telgársky, R.J.]] [http://telgarska.com/1987-RMJM-Telgarsky-Topological-Games.pdf ''Topological Games: On the 50th Anniversary of the Banach-Mazur Game''], Rocky Mountain J. Math. '''17''' (1987), pp.&nbsp;227–276. (3.19 MB) * [http://plato.stanford.edu/entries/large-cardinals-determinacy/ "Large Cardinals and Determinacy"] at the [[Stanford Encyclopedia of Philosophy]] {{Set theory}} [[Category:Axioms of set theory]] [[Category:Determinacy]] [[Category:Large cardinals]]'
New page wikitext, after the edit (new_wikitext)
'{{Short description|Possible axiom for set theory}} In [[mathematics]], the '''axiom of determinacy''' (abbreviated as '''AD''') is a possible [[axiom]] for [[set theory]] introduced by [[Jan Mycielski]] and [[Hugo Steinhaus]] in 1962. It refers to certain two-person [[topological game]]s of length [[ω (ordinal number)|ω]]. AD states that every game of a [[Axiom of determinacy#Types of game that are determined|certain type]] is [[determined game|determined]]; that is, one of the two players has a [[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 [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to [[Aleph-zero|&aleph;<sub>0</sub>]], 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 [[Baire space (set theory)|Baire space]] ω<sup>ω</sup> of all [[infinite sequence]]s of [[natural number]]s. Two players, '''1''' and '''2''', alternately pick natural numbers :''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>,&nbsp;… That generates the sequence ⟨''n''<sub>''i''</sub>⟩<sub>''i''∈ω</sub> 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 [[Clopen set|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 cardinal]]s that AD holds in [[L(R)]] and that a game is determined if it has a [[projective set]] as its winning set (see [[Projective determinacy]]). The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|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''<sub>1</sub> of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set ''S''<sub>2</sub> of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and ''A'' be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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''<sub>1</sub> and ''S''<sub>2</sub>, and construct ''A'' such that it will be a counterexample. We start with empty sets ''A'' and ''B''. Let ''&alpha;''&nbsp;∈&nbsp;''J'' be the index of the strategies in ''S''<sub>1</sub> and ''S''<sub>2</sub>. We need to consider all strategies ''S''<sub>1</sub>&nbsp;=&nbsp;{s<sub>1</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> of the first player and all strategies ''S''<sub>2</sub>&nbsp;=&nbsp;{s<sub>2</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample ''A'' by [[transfinite recursion]] on ''&alpha;'': # Consider the strategy s<sub>1</sub>(''&alpha;'') of the first player. # Apply this strategy on an ω-game, generating (together with the first player's strategy s<sub>1</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…,a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''A''. This is possible, because the number of choices for ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;<&nbsp;''&alpha;''&nbsp;} of ''J.'' # Add this sequence to ''B'' to indicate that s<sub>1</sub>(''&alpha;'') loses (on ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩). # Consider the strategy s<sub>2</sub>(''&alpha;'') of the second player. # Apply this strategy on an ω-game, generating (together with the second player's strategy ''s''<sub>2</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…, a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''B.'' This is possible, because the number of choices for ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;≤&nbsp;''&alpha;''&nbsp;} of ''J.'' # Add this sequence to ''A'' to indicate that ''s''<sub>2</sub>(''&alpha;'') loses (on ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩). # Process all possible strategies of ''S''<sub>1</sub> and ''S''<sub>2</sub> with [[transfinite induction]] on ''&alpha;.'' 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''<sub>1</sub> of the first player, there is an ''&alpha;''&nbsp;∈&nbsp;''J'' such that ''s''<sub>1</sub>&nbsp;=&nbsp;''s''<sub>1</sub>(''&alpha;''), and ''A'' has been constructed such that ''s''<sub>1</sub>(''&alpha;'') fails (on certain choices ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ of the second player). Hence, ''s''<sub>1</sub> 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''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…⟩, an element in ω<sup>ω</sup>, where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function ''f''&#x202F;:&nbsp;&omega;<sup>&omega;</sup>&nbsp;→&nbsp;{0,&nbsp;1}<sup>&omega;</sup> 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 [[run-length encoding]]) equals ''r.'' (Such an ''f'' can be shown to be injective. The image is the subset of {0,&nbsp;1}<sup>&omega;</sup> of sequences that start with 0 and that are not eventually constant. Formally, ''f'' is the [[Minkowski question mark function]], {0,&nbsp;1}<sup>&omega;</sup> is the [[Cantor space]] and ω<sup>ω</sup> is the [[Baire space (set theory)|Baire space]].) Observe the [[equivalence relation]] on {0,&nbsp;1}<sup>&omega;</sup> 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,&nbsp;1}<sup>&omega;</sup>&nbsp;→&nbsp;''T'' that takes a sequence to its equivalence class. Define the complement of any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup> to be the sequence s<sub>1</sub> that differs in each term. Define the function ''h''&#x202F;:&nbsp;''T''&nbsp;→&nbsp;''T'' such that for any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup>, ''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_(mathematics)|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'',&nbsp;''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''&nbsp;∈&nbsp;''U'' iff ''h''(''t'')&nbsp;∉&nbsp;''U.'' Next, we define the subset ''A''&nbsp;⊆&nbsp;ω<sup>ω</sup> in which '''1''' wins: ''A'' is the set of all ''r'' such that ''g''(''f''(''r''))&nbsp;∈&nbsp;''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''<sub>1</sub>. Then '''1''' specifies in ''p'' that ''a''<sub>1</sub>&nbsp;=&nbsp;1&nbsp;+&nbsp;''b''<sub>1</sub>. (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&nbsp;+&nbsp;''b''<sub>1</sub>⟩ is ''b''<sub>2</sub>, and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>, ''b''<sub>2</sub>⟩ is ''b''<sub>3</sub>. We construct ''p'' for '''1''', we only aim to beat ''q,'' and therefore only have to handle the response ''b''<sub>2</sub> to '''1'''{{`s}} first move. Therefore set '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>⟩ is ''b''<sub>3</sub>. In general, for even ''n,'' denote '''2'''{{`s}} response to ⟨1&nbsp;+&nbsp;b<sub>1</sub>,&nbsp;…, b<sub>''n''−1</sub>⟩ by ''b''<sub>''n''</sub> and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>,&nbsp;…, ''b''<sub>''n''</sub>⟩ by ''b''<sub>''n''+1</sub>. Then '''1''' specify in ''p'' that '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…, ''b''<sub>''n''</sub>⟩ is ''b''<sub>''n''+1</sub>. Strategy ''q'' is presumed to be winning, and game-result ''r'' in ω<sup>ω</sup> given by ⟨1, ''b''<sub>1</sub>,&nbsp;…⟩ 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''<nowiki/>' in ω<sup>ω</sup> given by ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…⟩ is also a sequence allowed by ''q'' (specifically, ''q'' playing against ''p''), so ''g''(''f''(''r''<nowiki/>')) must not be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') 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''<nowiki/>') are in complement equivalent classes, so ''g''(''f''(''r'')), ''g''(''f''(''r''<nowiki/>')) 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''<sub>1</sub> be '''1'''{{`s}} first move. In general, for even ''n,'' denote '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1⟩ (if ''n''&nbsp;=&nbsp;2) or ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>,&nbsp;…, ''a''<sub>n−1</sub>⟩ by ''a''<sub>''n''</sub> and '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>,&nbsp;… ''a''<sub>''n''</sub>⟩ by ''a''<sub>''n''+1</sub>. Then the game result ''r'' given by ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is allowed by ''p'' so that ''g''(''f''(''r'')) must be in ''U''; also the game result ''r''<nowiki/>' given by ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is also allowed by ''p'' so that ''g''(''f''(''r''<nowiki/>')) must be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') differ in all but the first ''a''<sub>1</sub>&nbsp;+&nbsp;1 terms, so they are in complement equivalent classes, therefore ''g''(''f''(''r'')) and ''g''(''f''(''r''<nowiki/>')) 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 [[W. Hugh Woodin|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 cardinal]]s. Since Woodin cardinals are [[inaccessible cardinal|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 [[L(R)]], and therefore that ''every'' set of real numbers in L(R) is determined. == Projective ordinals == [[Yiannis Moschovakis]] introduced the ordinals &delta;{{su|b=''n''|p=1}}, which is the upper bound of the length of '''&Delta;'''{{su|b=''n''|p=1}}-norms (injections of a '''&Delta;'''{{su|b=''n''|p=1}} set into the ordinals), where '''&Delta;'''{{su|b=''n''|p=1}} is a level of the [[projective hierarchy]]. Assuming AD, all &delta;{{su|b=''n''|p=1}} are [[Initial ordinal|initial ordinals]], and we have {{nowrap|1=&delta;{{su|b=2''n''+2|p=1}} = (&delta;{{su|b=2''n''+1|p=1}})<sup>+</sup>}}, and for ''n''&nbsp;<&nbsp;&omega;, the {{nowrap|2''n''-th}} [[Suslin cardinal]] is equal to &delta;{{su|b=2''n''−1|p=1}}.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref> == See also == * [[Axiom of real determinacy]] (AD<sub>R</sub>) * [[Borel determinacy theorem]] * [[Martin measure]] * [[Topological game]] ==References== {{refbegin}} * {{Cite journal | last1=Mycielski | first1=Jan | author1-link = Jan Mycielski | last2=Steinhaus | first2=Hugo | author2-link = Hugo Steinhaus | title=A mathematical axiom contradicting the axiom of choice | mr=0140430 | year=1962 | journal=Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques | issn=0001-4117 | volume=10 | pages=1–3 }} * {{cite journal|last1=Mycielski | first1=Jan | author1-link = Jan Mycielski | last2=Świerczkowski | first2=Stanisław | author2-link = Stanisław Świerczkowski|title=On the Lebesgue measurability and the axiom of determinateness|journal=Fund. Math.|volume=54| year=1964|pages=67–71| doi=10.4064/fm-54-1-67-71 |doi-access=free}} * {{cite journal|author=Woodin, W. Hugh | author-link = W. Hugh Woodin |journal=[[Proceedings of the National Academy of Sciences of the United States of America]]|year=1988|title=Supercompact cardinals, sets of reals, and weakly homogeneous trees|volume=85|issue=18|pages=6587–6591|doi=10.1073/pnas.85.18.6587|pmid=16593979|pmc=282022| bibcode = 1988PNAS...85.6587W | doi-access = free }} * {{cite journal|last1=Martin |first1=Donald A. |author1-link=Donald A. Martin |first2=John R. |last2=Steel |author2-link=John R. Steel |date=Jan 1989|title=A Proof of Projective Determinacy |journal=[[Journal of the American Mathematical Society]] |volume=2 |issue=1 |pages=71–125 |doi=10.2307/1990913 |jstor=1990913 |doi-access=free }} * {{cite book|last=Jech | first = Thomas | author-link = Thomas Jech | title=Set theory, third millennium edition (revised and expanded)|publisher=Springer|year=2002|isbn=978-3-540-44085-7}} * {{cite book|last=Kanamori | first = Akihiro|author-link=Akihiro Kanamori|title=The Higher Infinite|title-link=The Higher Infinite|edition=2nd|year=2008|publisher=Springer Science & Business Media|isbn=978-3-540-88866-6}} * {{cite book|last1=Moschovakis |first1=Yiannis N. |author-link1=Yiannis N. Moschovakis |title=Descriptive set theory |date=2009 |publisher=American Mathematical Society |location=Providence, R.I. |isbn=978-0-8218-4813-5 |edition=2nd |url=https://www.math.ucla.edu/~ynm/lectures/dst2009/dst2009.pdf |url-status=live|archive-url=https://web.archive.org/web/20141112111558/http://www.math.ucla.edu/~ynm/lectures/dst2009/dst2009.pdf |archive-date=2014-11-12 }} {{refend}} ===Inline citations=== {{Reflist}} == Further reading == * Philipp Rohde, ''On Extensions of the Axiom of Determinacy'', Thesis, Department of Mathematics, University of Bonn, Germany, 2001 * [[Rastislav J. Telgársky|Telgársky, R.J.]] [http://telgarska.com/1987-RMJM-Telgarsky-Topological-Games.pdf ''Topological Games: On the 50th Anniversary of the Banach-Mazur Game''], Rocky Mountain J. Math. '''17''' (1987), pp.&nbsp;227–276. (3.19 MB) * [http://plato.stanford.edu/entries/large-cardinals-determinacy/ "Large Cardinals and Determinacy"] at the [[Stanford Encyclopedia of Philosophy]] {{Set theory}} [[Category:Axioms of set theory]] [[Category:Determinacy]] [[Category:Large cardinals]]'
Unified diff of changes made by edit (edit_diff)
'@@ -2,55 +2,50 @@ In [[mathematics]], the '''axiom of determinacy''' (abbreviated as '''AD''') is a possible [[axiom]] for [[set theory]] introduced by [[Jan Mycielski]] and [[Hugo Steinhaus]] in 1962. It refers to certain two-person [[topological game]]s of length [[ω (ordinal number)|ω]]. AD states that every game of a [[Axiom of determinacy#Types of game that are determined|certain type]] is [[determined game|determined]]; that is, one of the two players has a [[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 [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to <math>\alef_0</math>, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R). +Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to [[Aleph-zero|&aleph;<sub>0</sub>]], 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 [[Baire space (set theory)|Baire space]] ''ω<sup>ω</sup>'' of all [[infinite sequence]]s of [[natural number]]s. Two players, '''I''' and '''II''', alternately pick natural numbers -:''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>, ... -After infinitely many moves, a sequence <math>(n_i)_{i \in \omega}</math> 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 set|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 cardinal]]s that all games with winning set a [[projective set]] are determined (see [[Projective determinacy]]), and that AD holds in [[L(R)]]. +Consider a subset ''A'' of the [[Baire space (set theory)|Baire space]] ω<sup>ω</sup> of all [[infinite sequence]]s of [[natural number]]s. Two players, '''1''' and '''2''', alternately pick natural numbers +:''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>,&nbsp;… +That generates the sequence ⟨''n''<sub>''i''</sub>⟩<sub>''i''∈ω</sub> 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. -The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|real numbers]], the [[Banach–Mazur game]] ''BM''(''X'') is determined (and therefore that every set of reals has the [[property of Baire]]). +Not all games require the axiom of determinacy to prove them determined. If the set ''A'' is [[Clopen set|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 cardinal]]s that AD holds in [[L(R)]] and that a game is determined if it has a [[projective set]] as its winning set (see [[Projective determinacy]]). -== Incompatibility of the axiom of determinacy with the axiom of choice == +The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|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 well-ordering of the continuum === - -The set S1 of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set S2 of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and A be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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 S1 and S2, and construct A such that it will be a counterexample. - -We start with empty sets A and B. Let α <math>\in</math> J be the index of the strategies in S1 and S2. We need to consider all strategies S1 = {s1(α)} of the first player and all strategies S2 = {s2(α)} 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample A by [[transfinite recursion]] on α: +=== Using a well-ordering of the continuum === +The set ''S''<sub>1</sub> of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set ''S''<sub>2</sub> of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and ''A'' be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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''<sub>1</sub> and ''S''<sub>2</sub>, and construct ''A'' such that it will be a counterexample. -# Consider the strategy s1(α) of the first player. -#Apply this strategy on an ω-game, generating (together with the first player's strategy s1(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to A. This is possible, because the number of choices for {b(2), b(4), b(6), ...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math><</math> α } of J. -#Add this sequence to B (if it is not already in B), to indicate that s1(α) loses (on {b(2), b(4), b(6), ...}). -#Consider the strategy s2(α) of the second player. -#Apply this strategy on an ω-game, generating (together with the second player's strategy s2(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to B. This is possible, because the number of choices for {a(1), a(3), a(5),...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math>\le</math> α } of J. -#Add this sequence to A (if it is not already in A), to indicate that s2(α) loses (on {a(1), a(3), a(5), ...}). -#Process all possible strategies of S1 and S2 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 B is the complement of A. +We start with empty sets ''A'' and ''B''. Let ''&alpha;''&nbsp;∈&nbsp;''J'' be the index of the strategies in ''S''<sub>1</sub> and ''S''<sub>2</sub>. We need to consider all strategies ''S''<sub>1</sub>&nbsp;=&nbsp;{s<sub>1</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> of the first player and all strategies ''S''<sub>2</sub>&nbsp;=&nbsp;{s<sub>2</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample ''A'' by [[transfinite recursion]] on ''&alpha;'': -Once this has been done, prepare for an ω-game ''G''. For a given strategy s1 of the first player, there is an α <math>\in</math> J such that s1 = s1(α), and A has been constructed such that s1(α) fails (on certain choices {b(2), b(4), b(6), ...} of the second player). Hence, s1 fails. Similarly, any other strategy of either player also fails. +# Consider the strategy s<sub>1</sub>(''&alpha;'') of the first player. +# Apply this strategy on an ω-game, generating (together with the first player's strategy s<sub>1</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…,a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''A''. This is possible, because the number of choices for ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;<&nbsp;''&alpha;''&nbsp;} of ''J.'' +# Add this sequence to ''B'' to indicate that s<sub>1</sub>(''&alpha;'') loses (on ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩). +# Consider the strategy s<sub>2</sub>(''&alpha;'') of the second player. +# Apply this strategy on an ω-game, generating (together with the second player's strategy ''s''<sub>2</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…, a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''B.'' This is possible, because the number of choices for ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;≤&nbsp;''&alpha;''&nbsp;} of ''J.'' +# Add this sequence to ''A'' to indicate that ''s''<sub>2</sub>(''&alpha;'') loses (on ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩). +# Process all possible strategies of ''S''<sub>1</sub> and ''S''<sub>2</sub> with [[transfinite induction]] on ''&alpha;.'' 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.'' -=== Using a choice function on a partition of the continuum into size-2 sets === +Once this has been done, prepare for an ω-game ''G''. For a given strategy ''s''<sub>1</sub> of the first player, there is an ''&alpha;''&nbsp;∈&nbsp;''J'' such that ''s''<sub>1</sub>&nbsp;=&nbsp;''s''<sub>1</sub>(''&alpha;''), and ''A'' has been constructed such that ''s''<sub>1</sub>(''&alpha;'') fails (on certain choices ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ of the second player). Hence, ''s''<sub>1</sub> 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 the quote by Bertrand Russell at [[Axiom_of_choice#Quotations]]. +=== 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 <math>{a(1), b(2), a(3), b(4) ...}</math>, an element in ''ω<sup>ω</sup>'', where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function <math>f: \omega^\omega \rightarrow \{0, 1\}^\omega </math> such that f(r) is the unique sequence of length ω whose values are in {0, 1}, whose first term equals 0, and whose sequence of runs (see [[run-length encoding]]) equals r. (f can be shown to be injective. The image is the subset of <math> \{0, 1\}^\omega </math> of sequences that start with 0 and that are not eventually constant. Formally, f is the [[Minkowski question mark function]], <math> \{0, 1\}^\omega </math> is the [[Cantor space]] and ''ω<sup>ω</sup>'' is the [[Baire space (set theory)|Baire space]].) +In a ω-game, the two players are generating the sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…⟩, an element in ω<sup>ω</sup>, where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function ''f''&#x202F;:&nbsp;&omega;<sup>&omega;</sup>&nbsp;→&nbsp;{0,&nbsp;1}<sup>&omega;</sup> 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 [[run-length encoding]]) equals ''r.'' (Such an ''f'' can be shown to be injective. The image is the subset of {0,&nbsp;1}<sup>&omega;</sup> of sequences that start with 0 and that are not eventually constant. Formally, ''f'' is the [[Minkowski question mark function]], {0,&nbsp;1}<sup>&omega;</sup> is the [[Cantor space]] and ω<sup>ω</sup> is the [[Baire space (set theory)|Baire space]].) -Observe the [[equivalence relation]] on <math>\{0, 1\}^\omega </math> 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, and let T be the set of equivalence classes (such that T has the cardinality of the continuum). Define <math>\{0, 1\}^\omega \rightarrow T</math> that takes a sequence to its equivalence class. Define the complement of any sequence s in <math>\{0, 1\}^\omega </math> to be the sequence s<sub>1</sub> that differs in each term. Define the function <math> h: T \rightarrow T </math> such that for any sequence s in <math>\{0, 1\}^\omega </math>, 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_(mathematics)|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 is in U iff h(t) is not in U. +Observe the [[equivalence relation]] on {0,&nbsp;1}<sup>&omega;</sup> 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,&nbsp;1}<sup>&omega;</sup>&nbsp;→&nbsp;''T'' that takes a sequence to its equivalence class. Define the complement of any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup> to be the sequence s<sub>1</sub> that differs in each term. Define the function ''h''&#x202F;:&nbsp;''T''&nbsp;→&nbsp;''T'' such that for any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup>, ''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_(mathematics)|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'',&nbsp;''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''&nbsp;∈&nbsp;''U'' iff ''h''(''t'')&nbsp;∉&nbsp;''U.'' -Next, we define the subset A of ''ω<sup>ω</sup>'' in which player 1 wins: A is the set of all r such that g(f(r)) is in 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 player 1 is next to play; otherwise player 2 is next to play). +Next, we define the subset ''A''&nbsp;⊆&nbsp;ω<sup>ω</sup> in which '''1''' wins: ''A'' is the set of all ''r'' such that ''g''(''f''(''r''))&nbsp;∈&nbsp;''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 player 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<sub>1</sub>. Then player 1 specifies in p that a(1) = 1 + b<sub>1</sub>. (Roughly, player 1 is now playing as the second player in a second parallel game; player 1's winning set in the second game equals player 2's winning set in the original game, and this is a contradiction. Nevertheless, we continue more formally). +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''<sub>1</sub>. Then '''1''' specifies in ''p'' that ''a''<sub>1</sub>&nbsp;=&nbsp;1&nbsp;+&nbsp;''b''<sub>1</sub>. (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 player 2's response (always according to q) to [1 + b<sub>1</sub>] is b<sub>2</sub>, and player 2's response to [1, b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. When player 1 is constructing p, they only aim to beat q, and therefore they only have to handle the response b<sub>2</sub> to their first move. Player 1 specifies that their response to [1 + b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. In general, for even n, denote player 2's response to [1 + b<sub>1</sub>, ..., b<sub>n-1</sub>] by b<sub>n</sub> and player 2s response to [1, b<sub>1</sub>, ..., b<sub>n</sub>] by b<sub>n + 1</sub>. Then player 1 specifies in p that their response to [1 + b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>] is b<sub>n + 1</sub>. Strategy q is presumed to be winning, and game-result r in ''ω<sup>ω</sup>'' given by [1, b<sub>1</sub>, ...] is one possible sequence allowed by q, so r must be winning for player 2 and g(f(r)) must not be in U. Game-result r' in ''ω<sup>ω</sup>'' given by [1 + b<sub>1</sub>, b<sub>2</sub>, ...] 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. +Suppose that '''2'''{{`s}} response (always according to ''q'') to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>⟩ is ''b''<sub>2</sub>, and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>, ''b''<sub>2</sub>⟩ is ''b''<sub>3</sub>. We construct ''p'' for '''1''', we only aim to beat ''q,'' and therefore only have to handle the response ''b''<sub>2</sub> to '''1'''{{`s}} first move. Therefore set '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>⟩ is ''b''<sub>3</sub>. In general, for even ''n,'' denote '''2'''{{`s}} response to ⟨1&nbsp;+&nbsp;b<sub>1</sub>,&nbsp;…, b<sub>''n''−1</sub>⟩ by ''b''<sub>''n''</sub> and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>,&nbsp;…, ''b''<sub>''n''</sub>⟩ by ''b''<sub>''n''+1</sub>. Then '''1''' specify in ''p'' that '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…, ''b''<sub>''n''</sub>⟩ is ''b''<sub>''n''+1</sub>. Strategy ''q'' is presumed to be winning, and game-result ''r'' in ω<sup>ω</sup> given by ⟨1, ''b''<sub>1</sub>,&nbsp;…⟩ 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''<nowiki/>' in ω<sup>ω</sup> given by ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…⟩ is also a sequence allowed by ''q'' (specifically, ''q'' playing against ''p''), so ''g''(''f''(''r''<nowiki/>')) must not be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') 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''<nowiki/>') are in complement equivalent classes, so ''g''(''f''(''r'')), ''g''(''f''(''r''<nowiki/>')) cannot both be in ''U,'' contradicting the assumption that ''q'' is a winning strategy. -Similarly, suppose that p is a winning strategy for player 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<sub>1</sub> be player 1's first move. In general, for even n, denote player 1's response to [a<sub>1</sub>, 1] (if n = 2) or [a<sub>1</sub>, 1, a<sub>2</sub>, ... a<sub>n-1</sub>] by a<sub>n</sub> and player 1's response to [a<sub>1</sub>, 1 + a<sub>2</sub>, ... a<sub>n</sub>] by a<sub>n + 1</sub>. Then game-result r given by [a<sub>1</sub>, 1, a<sub>2</sub>, a<sub>3</sub>, ...] is allowed by p so that g(f(r)) must be in U; also game-result r' given by [a<sub>1</sub>, 1 + a<sub>2</sub>, a<sub>3</sub>, ...] 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<sub>1</sub> + 1 terms, so they are in complement equivalent classes, so g(f(r)) and g(f(r')) cannot both be in U, contradicting that p 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''<sub>1</sub> be '''1'''{{`s}} first move. In general, for even ''n,'' denote '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1⟩ (if ''n''&nbsp;=&nbsp;2) or ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>,&nbsp;…, ''a''<sub>n−1</sub>⟩ by ''a''<sub>''n''</sub> and '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>,&nbsp;… ''a''<sub>''n''</sub>⟩ by ''a''<sub>''n''+1</sub>. Then the game result ''r'' given by ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is allowed by ''p'' so that ''g''(''f''(''r'')) must be in ''U''; also the game result ''r''<nowiki/>' given by ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is also allowed by ''p'' so that ''g''(''f''(''r''<nowiki/>')) must be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') differ in all but the first ''a''<sub>1</sub>&nbsp;+&nbsp;1 terms, so they are in complement equivalent classes, therefore ''g''(''f''(''r'')) and ''g''(''f''(''r''<nowiki/>')) 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 [[W. Hugh Woodin|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 cardinal]]s. Since Woodin cardinals are [[inaccessible cardinal|strongly inaccessible]], if AD is consistent, then so are an infinity of inaccessible cardinals. @@ -58,9 +53,7 @@ == Projective ordinals == - -[[Yiannis Moschovakis]] introduced the ordinals <math>\delta_n^1</math>, which is the upper bound of the length of <math>\boldsymbol\Delta_n^1</math>-norms (injections of a <math>\boldsymbol\Delta_n^1</math> set into the ordinals), where <math>\boldsymbol\Delta_n^1</math> is a level of the [[projective hierarchy]]. Assuming AD, all <math>\delta_n^1</math> are [[Initial ordinal|initial ordinals]], and we have <math>\delta_{2n+2}^1=(\delta_{2n+1}^1)^+</math>, and for <math>n<\omega</math> the <math>2n</math>th [[Suslin cardinal]] is equal to <math>\delta_{2n-1}^1</math>.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref> +[[Yiannis Moschovakis]] introduced the ordinals &delta;{{su|b=''n''|p=1}}, which is the upper bound of the length of '''&Delta;'''{{su|b=''n''|p=1}}-norms (injections of a '''&Delta;'''{{su|b=''n''|p=1}} set into the ordinals), where '''&Delta;'''{{su|b=''n''|p=1}} is a level of the [[projective hierarchy]]. Assuming AD, all &delta;{{su|b=''n''|p=1}} are [[Initial ordinal|initial ordinals]], and we have {{nowrap|1=&delta;{{su|b=2''n''+2|p=1}} = (&delta;{{su|b=2''n''+1|p=1}})<sup>+</sup>}}, and for ''n''&nbsp;<&nbsp;&omega;, the {{nowrap|2''n''-th}} [[Suslin cardinal]] is equal to &delta;{{su|b=2''n''−1|p=1}}.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref> == See also == - * [[Axiom of real determinacy]] (AD<sub>R</sub>) * [[Borel determinacy theorem]] @@ -84,5 +77,4 @@ == Further reading == - * Philipp Rohde, ''On Extensions of the Axiom of Determinacy'', Thesis, Department of Mathematics, University of Bonn, Germany, 2001 * [[Rastislav J. Telgársky|Telgársky, R.J.]] [http://telgarska.com/1987-RMJM-Telgarsky-Topological-Games.pdf ''Topological Games: On the 50th Anniversary of the Banach-Mazur Game''], Rocky Mountain J. Math. '''17''' (1987), pp.&nbsp;227–276. (3.19 MB) '
New page size (new_size)
19169
Old page size (old_size)
17026
Size change in edit (edit_delta)
2143
Lines added in edit (added_lines)
[ 0 => 'Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to [[Aleph-zero|&aleph;<sub>0</sub>]], they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).', 1 => 'Consider a subset ''A'' of the [[Baire space (set theory)|Baire space]] ω<sup>ω</sup> of all [[infinite sequence]]s of [[natural number]]s. Two players, '''1''' and '''2''', alternately pick natural numbers', 2 => ':''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>,&nbsp;…', 3 => 'That generates the sequence ⟨''n''<sub>''i''</sub>⟩<sub>''i''∈ω</sub> 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.', 4 => 'Not all games require the axiom of determinacy to prove them determined. If the set ''A'' is [[Clopen set|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 cardinal]]s that AD holds in [[L(R)]] and that a game is determined if it has a [[projective set]] as its winning set (see [[Projective determinacy]]).', 5 => 'The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|real numbers]], the [[Banach–Mazur game]] BM(''X'') is determined (and therefore that every set of reals has the [[property of Baire]]).', 6 => '== Incompatibility with the axiom of choice ==', 7 => '=== Using a well-ordering of the continuum ===', 8 => 'The set ''S''<sub>1</sub> of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set ''S''<sub>2</sub> of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and ''A'' be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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''<sub>1</sub> and ''S''<sub>2</sub>, and construct ''A'' such that it will be a counterexample.', 9 => 'We start with empty sets ''A'' and ''B''. Let ''&alpha;''&nbsp;∈&nbsp;''J'' be the index of the strategies in ''S''<sub>1</sub> and ''S''<sub>2</sub>. We need to consider all strategies ''S''<sub>1</sub>&nbsp;=&nbsp;{s<sub>1</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> of the first player and all strategies ''S''<sub>2</sub>&nbsp;=&nbsp;{s<sub>2</sub>(''&alpha;'')}<sub>''&alpha;''∈''J''</sub> 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample ''A'' by [[transfinite recursion]] on ''&alpha;'':', 10 => '# Consider the strategy s<sub>1</sub>(''&alpha;'') of the first player.', 11 => '# Apply this strategy on an ω-game, generating (together with the first player's strategy s<sub>1</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…,a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''A''. This is possible, because the number of choices for ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;<&nbsp;''&alpha;''&nbsp;} of ''J.''', 12 => '# Add this sequence to ''B'' to indicate that s<sub>1</sub>(''&alpha;'') loses (on ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩). ', 13 => '# Consider the strategy s<sub>2</sub>(''&alpha;'') of the second player.', 14 => '# Apply this strategy on an ω-game, generating (together with the second player's strategy ''s''<sub>2</sub>(''&alpha;'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…, a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>,&nbsp;…⟩, which does not belong to ''B.'' This is possible, because the number of choices for ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion {&nbsp;''&beta;''&nbsp;∈&nbsp;''J''&nbsp;| ''&beta;''&nbsp;≤&nbsp;''&alpha;''&nbsp;} of ''J.''', 15 => '# Add this sequence to ''A'' to indicate that ''s''<sub>2</sub>(''&alpha;'') loses (on ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>,&nbsp;…⟩).', 16 => '# Process all possible strategies of ''S''<sub>1</sub> and ''S''<sub>2</sub> with [[transfinite induction]] on ''&alpha;.'' 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.''', 17 => 'Once this has been done, prepare for an ω-game ''G''. For a given strategy ''s''<sub>1</sub> of the first player, there is an ''&alpha;''&nbsp;∈&nbsp;''J'' such that ''s''<sub>1</sub>&nbsp;=&nbsp;''s''<sub>1</sub>(''&alpha;''), and ''A'' has been constructed such that ''s''<sub>1</sub>(''&alpha;'') fails (on certain choices ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>,&nbsp;…⟩ of the second player). Hence, ''s''<sub>1</sub> fails. Similarly, any other strategy of either player also fails.', 18 => '=== Using a choice function ===', 19 => '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]].', 20 => 'In a ω-game, the two players are generating the sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>,&nbsp;…⟩, an element in ω<sup>ω</sup>, where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function ''f''&#x202F;:&nbsp;&omega;<sup>&omega;</sup>&nbsp;→&nbsp;{0,&nbsp;1}<sup>&omega;</sup> 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 [[run-length encoding]]) equals ''r.'' (Such an ''f'' can be shown to be injective. The image is the subset of {0,&nbsp;1}<sup>&omega;</sup> of sequences that start with 0 and that are not eventually constant. Formally, ''f'' is the [[Minkowski question mark function]], {0,&nbsp;1}<sup>&omega;</sup> is the [[Cantor space]] and ω<sup>ω</sup> is the [[Baire space (set theory)|Baire space]].) ', 21 => 'Observe the [[equivalence relation]] on {0,&nbsp;1}<sup>&omega;</sup> 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,&nbsp;1}<sup>&omega;</sup>&nbsp;→&nbsp;''T'' that takes a sequence to its equivalence class. Define the complement of any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup> to be the sequence s<sub>1</sub> that differs in each term. Define the function ''h''&#x202F;:&nbsp;''T''&nbsp;→&nbsp;''T'' such that for any sequence ''s'' in {0,&nbsp;1}<sup>&omega;</sup>, ''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_(mathematics)|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'',&nbsp;''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''&nbsp;∈&nbsp;''U'' iff ''h''(''t'')&nbsp;∉&nbsp;''U.''', 22 => 'Next, we define the subset ''A''&nbsp;⊆&nbsp;ω<sup>ω</sup> in which '''1''' wins: ''A'' is the set of all ''r'' such that ''g''(''f''(''r''))&nbsp;∈&nbsp;''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).', 23 => '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''<sub>1</sub>. Then '''1''' specifies in ''p'' that ''a''<sub>1</sub>&nbsp;=&nbsp;1&nbsp;+&nbsp;''b''<sub>1</sub>. (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.)', 24 => 'Suppose that '''2'''{{`s}} response (always according to ''q'') to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>⟩ is ''b''<sub>2</sub>, and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>, ''b''<sub>2</sub>⟩ is ''b''<sub>3</sub>. We construct ''p'' for '''1''', we only aim to beat ''q,'' and therefore only have to handle the response ''b''<sub>2</sub> to '''1'''{{`s}} first move. Therefore set '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>⟩ is ''b''<sub>3</sub>. In general, for even ''n,'' denote '''2'''{{`s}} response to ⟨1&nbsp;+&nbsp;b<sub>1</sub>,&nbsp;…, b<sub>''n''−1</sub>⟩ by ''b''<sub>''n''</sub> and '''2'''{{`s}} response to ⟨1, ''b''<sub>1</sub>,&nbsp;…, ''b''<sub>''n''</sub>⟩ by ''b''<sub>''n''+1</sub>. Then '''1''' specify in ''p'' that '''1'''{{`s}} response to ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…, ''b''<sub>''n''</sub>⟩ is ''b''<sub>''n''+1</sub>. Strategy ''q'' is presumed to be winning, and game-result ''r'' in ω<sup>ω</sup> given by ⟨1, ''b''<sub>1</sub>,&nbsp;…⟩ 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''<nowiki/>' in ω<sup>ω</sup> given by ⟨1&nbsp;+&nbsp;''b''<sub>1</sub>, ''b''<sub>2</sub>,&nbsp;…⟩ is also a sequence allowed by ''q'' (specifically, ''q'' playing against ''p''), so ''g''(''f''(''r''<nowiki/>')) must not be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') 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''<nowiki/>') are in complement equivalent classes, so ''g''(''f''(''r'')), ''g''(''f''(''r''<nowiki/>')) cannot both be in ''U,'' contradicting the assumption that ''q'' is a winning strategy.', 25 => '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''<sub>1</sub> be '''1'''{{`s}} first move. In general, for even ''n,'' denote '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1⟩ (if ''n''&nbsp;=&nbsp;2) or ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>,&nbsp;…, ''a''<sub>n−1</sub>⟩ by ''a''<sub>''n''</sub> and '''1'''{{`s}} response to ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>,&nbsp;… ''a''<sub>''n''</sub>⟩ by ''a''<sub>''n''+1</sub>. Then the game result ''r'' given by ⟨''a''<sub>1</sub>, 1, ''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is allowed by ''p'' so that ''g''(''f''(''r'')) must be in ''U''; also the game result ''r''<nowiki/>' given by ⟨''a''<sub>1</sub>, 1&nbsp;+&nbsp;''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;…⟩ is also allowed by ''p'' so that ''g''(''f''(''r''<nowiki/>')) must be in ''U.'' However, ''f''(''r'') and ''f''(''r''<nowiki/>') differ in all but the first ''a''<sub>1</sub>&nbsp;+&nbsp;1 terms, so they are in complement equivalent classes, therefore ''g''(''f''(''r'')) and ''g''(''f''(''r''<nowiki/>')) cannot both be in ''U,'' contradicting that ''p'' is a winning strategy.', 26 => '[[Yiannis Moschovakis]] introduced the ordinals &delta;{{su|b=''n''|p=1}}, which is the upper bound of the length of '''&Delta;'''{{su|b=''n''|p=1}}-norms (injections of a '''&Delta;'''{{su|b=''n''|p=1}} set into the ordinals), where '''&Delta;'''{{su|b=''n''|p=1}} is a level of the [[projective hierarchy]]. Assuming AD, all &delta;{{su|b=''n''|p=1}} are [[Initial ordinal|initial ordinals]], and we have {{nowrap|1=&delta;{{su|b=2''n''+2|p=1}} = (&delta;{{su|b=2''n''+1|p=1}})<sup>+</sup>}}, and for ''n''&nbsp;<&nbsp;&omega;, the {{nowrap|2''n''-th}} [[Suslin cardinal]] is equal to &delta;{{su|b=2''n''−1|p=1}}.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref>' ]
Lines removed in edit (removed_lines)
[ 0 => 'Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model [[L(R)]] of a set theory, which accepts only a weak form of the [[axiom of choice]] (AC) but contains all [[real number|real]] and all [[ordinal number]]s. Some consequences of AD followed from theorems proved earlier by [[Stefan Banach]] and [[Stanisław Mazur]], and [[Morton Davis]]. [[Mycielski]] and [[Stanisław Świerczkowski]] contributed another one: AD implies that all sets of [[real number]]s 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 number]]s analogous to <math>\alef_0</math>, they proved the original conjecture of Mycielski and Steinhaus that AD is true in L(R).', 1 => '', 2 => 'Consider a subset ''A'' of the [[Baire space (set theory)|Baire space]] ''ω<sup>ω</sup>'' of all [[infinite sequence]]s of [[natural number]]s. Two players, '''I''' and '''II''', alternately pick natural numbers', 3 => ':''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>, ...', 4 => 'After infinitely many moves, a sequence <math>(n_i)_{i \in \omega}</math> 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.', 5 => '', 6 => 'Not all games require the axiom of determinacy to prove them determined. If the set ''A'' is [[Clopen set|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 cardinal]]s that all games with winning set a [[projective set]] are determined (see [[Projective determinacy]]), and that AD holds in [[L(R)]].', 7 => 'The axiom of determinacy implies that for every subspace ''X'' of the [[Real line#As a topological space|real numbers]], the [[Banach–Mazur game]] ''BM''(''X'') is determined (and therefore that every set of reals has the [[property of Baire]]).', 8 => '== Incompatibility of the axiom of determinacy with the axiom of choice ==', 9 => '=== Using well-ordering of the continuum ===', 10 => '', 11 => 'The set S1 of all first player strategies in an ω-game ''G'' has the same [[cardinality]] as the [[cardinality of the continuum|continuum]]. The same is true for the set S2 of all second player strategies. Let ''SG'' be the set of all possible sequences in ''G'', and A be the subset of sequences of ''SG'' that make the first player win. With the axiom of choice we can [[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 S1 and S2, and construct A such that it will be a counterexample.', 12 => '', 13 => 'We start with empty sets A and B. Let α <math>\in</math> J be the index of the strategies in S1 and S2. We need to consider all strategies S1 = {s1(α)} of the first player and all strategies S2 = {s2(α)} 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 ℵ<sub>0</sub> and which is used during each game sequence. We create the counterexample A by [[transfinite recursion]] on α:', 14 => '# Consider the strategy s1(α) of the first player.', 15 => '#Apply this strategy on an ω-game, generating (together with the first player's strategy s1(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to A. This is possible, because the number of choices for {b(2), b(4), b(6), ...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math><</math> α } of J.', 16 => '#Add this sequence to B (if it is not already in B), to indicate that s1(α) loses (on {b(2), b(4), b(6), ...}). ', 17 => '#Consider the strategy s2(α) of the second player.', 18 => '#Apply this strategy on an ω-game, generating (together with the second player's strategy s2(α)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}, which does not belong to B. This is possible, because the number of choices for {a(1), a(3), a(5),...} has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { β <math>\in</math> J | β <math>\le</math> α } of J.', 19 => '#Add this sequence to A (if it is not already in A), to indicate that s2(α) loses (on {a(1), a(3), a(5), ...}).', 20 => '#Process all possible strategies of S1 and S2 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 B is the complement of A.', 21 => 'Once this has been done, prepare for an ω-game ''G''. For a given strategy s1 of the first player, there is an α <math>\in</math> J such that s1 = s1(α), and A has been constructed such that s1(α) fails (on certain choices {b(2), b(4), b(6), ...} of the second player). Hence, s1 fails. Similarly, any other strategy of either player also fails.', 22 => '=== Using a choice function on a partition of the continuum into size-2 sets ===', 23 => '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]].', 24 => 'In a ω-game, the two players are generating the sequence <math>{a(1), b(2), a(3), b(4) ...}</math>, an element in ''ω<sup>ω</sup>'', where our convention is that 0 is not a natural number, hence neither player can choose it. Define the function <math>f: \omega^\omega \rightarrow \{0, 1\}^\omega </math> such that f(r) is the unique sequence of length ω whose values are in {0, 1}, whose first term equals 0, and whose sequence of runs (see [[run-length encoding]]) equals r. (f can be shown to be injective. The image is the subset of <math> \{0, 1\}^\omega </math> of sequences that start with 0 and that are not eventually constant. Formally, f is the [[Minkowski question mark function]], <math> \{0, 1\}^\omega </math> is the [[Cantor space]] and ''ω<sup>ω</sup>'' is the [[Baire space (set theory)|Baire space]].) ', 25 => 'Observe the [[equivalence relation]] on <math>\{0, 1\}^\omega </math> 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, and let T be the set of equivalence classes (such that T has the cardinality of the continuum). Define <math>\{0, 1\}^\omega \rightarrow T</math> that takes a sequence to its equivalence class. Define the complement of any sequence s in <math>\{0, 1\}^\omega </math> to be the sequence s<sub>1</sub> that differs in each term. Define the function <math> h: T \rightarrow T </math> such that for any sequence s in <math>\{0, 1\}^\omega </math>, 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_(mathematics)|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 is in U iff h(t) is not in U.', 26 => 'Next, we define the subset A of ''ω<sup>ω</sup>'' in which player 1 wins: A is the set of all r such that g(f(r)) is in 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 player 1 is next to play; otherwise player 2 is next to play).', 27 => 'Suppose that q is a (deterministic) winning strategy for player 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<sub>1</sub>. Then player 1 specifies in p that a(1) = 1 + b<sub>1</sub>. (Roughly, player 1 is now playing as the second player in a second parallel game; player 1's winning set in the second game equals player 2's winning set in the original game, and this is a contradiction. Nevertheless, we continue more formally).', 28 => 'Suppose that player 2's response (always according to q) to [1 + b<sub>1</sub>] is b<sub>2</sub>, and player 2's response to [1, b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. When player 1 is constructing p, they only aim to beat q, and therefore they only have to handle the response b<sub>2</sub> to their first move. Player 1 specifies that their response to [1 + b<sub>1</sub>, b<sub>2</sub>] is b<sub>3</sub>. In general, for even n, denote player 2's response to [1 + b<sub>1</sub>, ..., b<sub>n-1</sub>] by b<sub>n</sub> and player 2s response to [1, b<sub>1</sub>, ..., b<sub>n</sub>] by b<sub>n + 1</sub>. Then player 1 specifies in p that their response to [1 + b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>] is b<sub>n + 1</sub>. Strategy q is presumed to be winning, and game-result r in ''ω<sup>ω</sup>'' given by [1, b<sub>1</sub>, ...] is one possible sequence allowed by q, so r must be winning for player 2 and g(f(r)) must not be in U. Game-result r' in ''ω<sup>ω</sup>'' given by [1 + b<sub>1</sub>, b<sub>2</sub>, ...] 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.', 29 => 'Similarly, suppose that p is a winning strategy for player 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<sub>1</sub> be player 1's first move. In general, for even n, denote player 1's response to [a<sub>1</sub>, 1] (if n = 2) or [a<sub>1</sub>, 1, a<sub>2</sub>, ... a<sub>n-1</sub>] by a<sub>n</sub> and player 1's response to [a<sub>1</sub>, 1 + a<sub>2</sub>, ... a<sub>n</sub>] by a<sub>n + 1</sub>. Then game-result r given by [a<sub>1</sub>, 1, a<sub>2</sub>, a<sub>3</sub>, ...] is allowed by p so that g(f(r)) must be in U; also game-result r' given by [a<sub>1</sub>, 1 + a<sub>2</sub>, a<sub>3</sub>, ...] 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<sub>1</sub> + 1 terms, so they are in complement equivalent classes, so g(f(r)) and g(f(r')) cannot both be in U, contradicting that p is a winning strategy.', 30 => '', 31 => '', 32 => '[[Yiannis Moschovakis]] introduced the ordinals <math>\delta_n^1</math>, which is the upper bound of the length of <math>\boldsymbol\Delta_n^1</math>-norms (injections of a <math>\boldsymbol\Delta_n^1</math> set into the ordinals), where <math>\boldsymbol\Delta_n^1</math> is a level of the [[projective hierarchy]]. Assuming AD, all <math>\delta_n^1</math> are [[Initial ordinal|initial ordinals]], and we have <math>\delta_{2n+2}^1=(\delta_{2n+1}^1)^+</math>, and for <math>n<\omega</math> the <math>2n</math>th [[Suslin cardinal]] is equal to <math>\delta_{2n-1}^1</math>.<ref>V. G. Kanovei, [http://lab6.iitp.ru/en/pub/en_jms_1988_k.pdf 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.</ref>', 33 => '', 34 => '' ]
Whether or not the change was made through a Tor exit node (tor_exit_node)
false
Unix timestamp of change (timestamp)
'1712672317'