Skip to main content

This question originates from the paper On the Axiom of DeterminatenessOn the Axiom of Determinateness by Jan MicielskiMycielski, 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.

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

This question originates from the paper On the Axiom of Determinateness by Jan Micielski, 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.

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

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.

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.

Source Link
John Gowers
  • 907
  • 4
  • 18

Why is this transfinite game not determined?

This question originates from the paper On the Axiom of Determinateness by Jan Micielski, 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.

  1. 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 Micielski 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.