This question originates from the paper On the Axiom of Determinateness by Jan Mycielski, section 7. Given a set $X$ and an ordinal $\alpha$, the author defines a transfinite game of length $\alpha$ over $X$ to be given by a set $P\subset X^\alpha$: the game is played by two players, I and II, who take it in turns to select an element of $X$ (where Player I selects an element at each even ordinal and Player II selects an element at each odd ordinal) until they have built up a sequence $s\in X^\alpha$ of length $\alpha$. If $s\in P$, then the play is counted as a win for Player I; otherwise, it is a win for player II.

Denote by $\mathscr A_X^\alpha$ the statement that every transfinite game of length $\alpha$ over $X$ admits a winning strategy. So the Axiom of Determinacy is the statement $\mathscr A_\omega^\omega$, which is known to be independent of ZF.

By contrast, the author shows that the negation of $\mathscr A_2^{\omega_1}$ is a theorem of ZF, where $\omega_1$ is the first uncountable ordinal. I quote (sightly edited) the proof from the paper:

It is clear that $\mathscr A_2^{\omega_1}$ implies [the Axiom of Determinacy]. We also have $\mathscr A_2^{\omega_1}\rightarrow\mathscr A_{2^{\omega}}^{\omega_1}$, by the ordinal identity $\omega\cdot\omega_1=\omega_1$.1 Now we define a game $P\subset \left(2^{\omega}\right)^{\omega_1}$. According to [the Axiom of Determinacy], every sequence $s=(s_\beta)_{\beta<\omega_1}$ ($s_\beta\in 2^\omega$) has repetitions2; let $s_{a_0}$ be the first repeating term in $s$. Let $s\in P$ if and only if $a_0$ is odd. The situation of the two players in this game is essentially symmetric; i.e., the existence of a winning strategy for one of them would imply the same for the other, which is inconsistent, q.e.d.

Footnotes (mine)

1 Here, $2^\omega$ denotes the set of reals, rather than the countable ordinal with that name. Given a game $P$ of length $\omega_1$ over $2^\omega$, we may form a game over $2$ where each player in turn spends $\omega$-many moves constructing a real while we ignore the other player's moves. We then count the resulting sequence as a win for a particular player if the sequence of reals we have constructed is a win for that player in $P$. By the identity above, the new game still has length $\omega_1$, so $\scr A_{2}^\omega$ implies that it is determined and hence $P$ is determined.

2It is a theorem of ZF+AD that the cardinals $\aleph_1$ and $2^{\aleph_0}$ are incomparable.

To me, this game does not seem at all symmetric - Player I makes all moves after limit ordinals, whereas Player II always plays in response to some preceding play - and I am having some trouble working out how a strategy for Player II might translate into a strategy for Player I. Here's what I've tried:

  1. Player I makes a 'throwaway' move after each limit ordinal and somehow bijects the remaining reals with the reals that would have remained had she not made that move. The then applies that bijection to the Player II strategy, and continues.

    Problem: Even if we ignore for a second the issue of constructing this bijection, the move that Player I makes will have to depend on the moves that have been constructed already - a fixed move won't do, since Player II might have played that move already. It's difficult to see how to choose these moves without the Axiom of Choice. Clearly, we have to use the Player II strategy somehow, but it's not clear how to do so.

  2. After each limit ordinal, Player I pretends that player II made some move and then plays according to the Player II strategy. Once again, we need to biject the remaining moves with the remaining moves if that extra move had been played.

    This approach has exactly the same problems.

I'm not sure what else to try. I presume I'm missing something obvious, since Mycielski doesn't see the need to back up his claim.

It's quite a strange game, even ignoring its determinacy properties. It has three seemingly contradictory properties, which arise from the incomparability of $\alpha_1$ and $2^{\aleph_0}$ in ZF+AD:

  1. It is open in the sense that if one of the players loses then they must have made a losing move at some point - i.e., a move that guarantees that they will eventually lose, however the rest of the game is played out.

  2. At every position, it is possible for the current player to make a non-losing move. Indeed, let $s\colon\omega_1\to 2^{\omega}$ be a play in the game. $s$ cannot be surjective, since otherwise we could define an injection $j\colon 2^{\omega}\to\omega_1$ by $$ j(x) = \min\{\beta<\omega_1\;\colon\;s(\beta)=x\} $$ Therefore, there is some move $a$ that is never played. Then $a$ is a non-losing move at any position reached during the play $s$.

  3. One of the players must always lose.

  • $\begingroup$ Why not just email the author? $\endgroup$ – wrigley Nov 4 '16 at 15:12
  • $\begingroup$ @wrigley I hoped this might be a well known example in the field. But thanks for the suggestion - I've emailed him now. $\endgroup$ – John Gowers Nov 4 '16 at 15:28
  • 4
    $\begingroup$ Here is an alternative (folklore?) proof that $A^{\omega_1}_{2^\omega}$ is false. Consider the set $P$ of all sequences $(a_i,b_i:i<\omega_1)$ where exactly one $a_{i^*}$ is not $0$, and $b_{i^*}$ is not a code for the ordinal $i$. Player I wants to get into $P$. His only choice is to choose $i^*$, and clearly any such strategy can be defeated. But a strategy for player II would be a 1-1 function from $\omega_1$ into $2^\omega$. -- (This does not answer your question. Hence a comment, not an answer.) $\endgroup$ – Goldstern Nov 4 '16 at 16:34
  • 3
    $\begingroup$ My impression is that the proof given by @Goldstern in his comment is considered to be the standard proof of this result. Combining that with the original proof's difficulties as pointed out in the question, I'm inclined to think that maybe the original proof really can't be repaired and that's why the alternative proof has become standard. $\endgroup$ – Andreas Blass Nov 4 '16 at 17:01
  • 4
    $\begingroup$ Wait a minute. Can't player II win the game in the question just by always echoing player I's immediately preceding move except for reversing that move's first bit? This move of II doesn't repeat player I's immediately previous move,because of the reversed bit. If it repeated an earlier move $x$ (of either player) then player I's immediately previous move would also have been a repetition (of the move just before or just after $x$ depending on whether $x$ was II's or I's move). $\endgroup$ – Andreas Blass Nov 4 '16 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.