Editing Axiom of determinacy (section)

=== 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'':&nbsp;ω<sup>ω</sup>&nbsp;→&nbsp;{0,&nbsp;1}<sup>ω</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>ω</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>ω</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>ω</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 ''g'':&nbsp;{0,&nbsp;1}<sup>ω</sup>&nbsp;→&nbsp;''T'' that takes a sequence to its equivalence class. Define the complement of any sequence ''s'' in {0,&nbsp;1}<sup>ω</sup> to be the sequence s<sub>1</sub> that differs in each term. Define the function ''h'':&nbsp;''T''&nbsp;→&nbsp;''T'' such that for any sequence ''s'' in {0,&nbsp;1}<sup>ω</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'' (where U&nbsp;⊆&nbsp;T) 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.