Axiom of Determinacy - The Axiom of Choice and The Axiom of Determinacy Are Incompatible

The Axiom of Choice and The Axiom of Determinacy Are Incompatible

The set S1 of all first player strategies in an ω-game G has the same cardinality as the continuum. The same is true of the set S2 of all second player strategies. We note that the cardinality of the set SG of all sequences possible in G is also the continuum. Let A be the subset of SG of all sequences which make the first player win. With the axiom of choice we can well order the continuum; furthermore, we can do so in such a way that any proper initial portion does not have the cardinality of the continuum. We create a counterexample by transfinite induction on the set of strategies under this well ordering:

We start with the set A undefined. Let T be the "time" whose axis has length continuum. We need to consider all strategies {s1(T)} of the first player and all strategies {s2(T)} 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 which gives the other player a win. Let t be the time whose axis has length ℵ₀ and which is used during each game sequence.

1. Consider the current strategy {s1(T)} of the first player.
2. Go through the entire game, generating (together with the first player's strategy s1(T)) a sequence {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}.
3. Decide that this sequence does not belong to A, i.e. s1(T) lost.
4. Consider the strategy {s2(T)} of the second player.
5. Go through the next entire game, generating (together with the second player's strategy s2(T)) a sequence {c(1), d(2), c(3), d(4),...,c(t), d(t+1),...}, making sure that this sequence is different from {a(1), b(2), a(3), b(4),...,a(t), b(t+1),...}.
6. Decide that this sequence belongs to A, i.e. s2(T) lost.
7. Keep repeating with further strategies if there are any, making sure that sequences already considered do not become generated again. (We start from the set of all sequences and each time we generate a sequence and refute a strategy we project the generated sequence onto first player moves and onto second player moves, and we take away the two resulting sequences from our set of sequences.)
8. For all sequences that did not come up in the above consideration arbitrarily decide whether they belong to A, or to the complement of A.

Once this has been done we have a game G. If you give me a strategy s1 then we considered that strategy at some time T = T(s1). At time T, we decided an outcome of s1 that would be a loss of s1. Hence this strategy fails. But this is true for an arbitrary strategy; hence the axiom of determinacy and the axiom of choice are incompatible.