Let $A$ be a nonempty set, $T\subset A^\mathbb{N}$ a nonempty pruned tree and $X\subset [T]$. The game $G_{A}(T,X)$ is played as follows: Player I and Player II take turns playing $a_{0},a_{1},\dots$ so that $(a_{0},\dots,a_{n})\in T$ for each n. I wins iff $(a_{n})\in X$

Let $AD^*$ be the statement that all games are determined. That means that for any triple $(A,T,X)$, where $A$ is a nonempty set, $T$ a nonempty pruned tree on $A$ and $X\subset [T]$, the game $G_{A}(T,X)$ is determined. $AD$ is the statement that any game of the form $G_{\omega}(T,X)$ is determined. Obviously we have $AD^*\Rightarrow AD$.

Is $ZF+AD^*$ inconsistent?

My thought: Yes. $AD^*$ implies that all closed and all open games are determined, which is equivalent (in ZF) to the Axiom of Choice. But the Axiom of Choice gives us a undetermined game.

I nowhere found this result, so is it correct what I have done?


Yes, this is inconsistent, and your argument is a way of proving this.

In fact, $\mathsf{AD}^*$ is an overkill, and we can prove that there is an undetermined game with $A=\omega_1$. To see this, note that either there is an undetermined game on integers (and we are done), or else $\mathsf{AD}$ holds, so $\omega_1$ does not inject into $\mathbb R$. (The reason for this is that otherwise we can find an uncountable set of reals without the perfect set property, but this violates $\mathsf{AD}$.)

Now consider the game where player I starts by plays a countable ordinal $\alpha$. From that point on, we ignore player I's moves, and, bit by bit, playing natural numbers, II must play a sequence coding a well-ordering of $\omega$ in order type $\max(\omega,\alpha)$. Obviously, player I has no winning strategy here. If this game is determined, then player II has a winning strategy from which we can easily define an injection of $\omega_1$ into $\mathbb R$. This is a contradiction.

The argument is ancient, going back to Mycielski in 1964 (who also noticed your argument).

By the way, note that we did not exhibit a specific undetermined game, but rather a dichotomy: Either there is an undetermined game of this kind, or else, this other game is undetermined. In a sense, this is unavoidable, since it is consistent that all $\mathsf{OD}$ games on ordinals are determined. This is also an old observation, first noticed by Harrington and Kechris in 1980. It has been generalized in several significant ways by Woodin, Neeman, and others, by considering longer games (for instance, games of length $\omega_1$).

  • $\begingroup$ Hum: "an old observation, first noticed [...] in 1980". Sigh! $\endgroup$ – Daniel Fischer Aug 15 '14 at 16:37
  • $\begingroup$ I know! And set theory is a bit conservative here. In other fields, things are ancient once they are more than 20 years old. $\endgroup$ – Andrés E. Caicedo Aug 15 '14 at 16:40
  • 1
    $\begingroup$ (Seriously though, all I mean here is that the observation precedes the isolation of the concept of Woodinness.) $\endgroup$ – Andrés E. Caicedo Aug 15 '14 at 16:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.