Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Axiom of determinacy
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
=== 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 ''α'' ∈ ''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> = {s<sub>1</sub>(''α'')}<sub>''α''∈''J''</sub> of the first player and all strategies ''S''<sub>2</sub> = {s<sub>2</sub>(''α'')}<sub>''α''∈''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 ''α'': # Consider the strategy s<sub>1</sub>(''α'') of the first player. # Apply this strategy on an ω-game, generating (together with the first player's strategy s<sub>1</sub>(''α'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>, ...,a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>, ...⟩, 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>, ...⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { ''β'' ∈ ''J'' | ''β'' < ''α'' } of ''J.'' # Add this sequence to ''B'' to indicate that s<sub>1</sub>(''α'') loses (on ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>, ...⟩). # Consider the strategy s<sub>2</sub>(''α'') of the second player. # Apply this strategy on an ω-game, generating (together with the second player's strategy ''s''<sub>2</sub>(''α'')) a sequence ⟨''a''<sub>1</sub>, ''b''<sub>2</sub>, ''a''<sub>3</sub>, ''b''<sub>4</sub>, ..., a<sub>''t''</sub>, ''b''<sub>''t''+1</sub>, ...⟩, 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>, ...⟩ has the same cardinality as the continuum, which is larger than the cardinality of the proper initial portion { ''β'' ∈ ''J'' | ''β'' ≤ ''α'' } of ''J.'' # Add this sequence to ''A'' to indicate that ''s''<sub>2</sub>(''α'') loses (on ⟨''a''<sub>1</sub>, ''a''<sub>3</sub>, ''a''<sub>5</sub>, ...⟩). # Process all possible strategies of ''S''<sub>1</sub> and ''S''<sub>2</sub> with [[transfinite induction]] on ''α.'' For all sequences that are not in ''A'' or ''B'' after that, decide arbitrarily whether they belong to ''A'' or to ''B,'' so that ''B'' is the complement of ''A.'' Once this has been done, prepare for an ω-game ''G''. For a given strategy ''s''<sub>1</sub> of the first player, there is an ''α'' ∈ ''J'' such that ''s''<sub>1</sub> = ''s''<sub>1</sub>(''α''), and ''A'' has been constructed such that ''s''<sub>1</sub>(''α'') fails (on certain choices ⟨''b''<sub>2</sub>, ''b''<sub>4</sub>, ''b''<sub>6</sub>, ...⟩ of the second player). Hence, ''s''<sub>1</sub> fails. Similarly, any other strategy of either player also fails.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)