7
$\begingroup$

When considering (set-theoretic) games, we have three parameters we can adjust:

  1. Definability of the payoff set
  2. The set of legal moves
  3. The length of the game

When working in $\textsf{ZFC}$, what are our limitations on the above three parameters? When do we reach inconsistencies? Some more specific subquestions could be:

  • What is the least $\alpha$ such that open (or analytic) determinacy on $\omega$ of length $\alpha$ is inconsistent, if such an $\alpha$ exists?
  • Same question as above but instead consider analytic determinacy on $\alpha$ of length $\omega$.

I have found some partial results:

  • If we have no definability requirement then we can't even have determinacy of length $\omega$ games on $\omega$ (as this is just $\textsf{AD}$).
  • If we consider $\textsf{OD}$ games then (according to wiki) it's consistent relative to the sharp of a Woodin limit of Woodins that games on $\omega$ of length $\omega_1$ are determined, but it's inconsistent to consider length $\omega_1+\omega$ games. Is this relative to $\textsf{ZFC}$? (EDIT: Yes it is)
  • Caicedo mentions here that it's consistent that all $\textsf{OD}$ games on ordinals of length $\omega$ are determined - but again, is this relative to $\textsf{ZFC}$? I suppose not.

Also, here Noah Schweber asks the same question, but where we fix the length to be $\omega$, the legal moves to be $\mathbb R$ and then ask about the definability.


EDIT: I've written up an overview based on Juan's answer below and by taking a closer look at the complexity of the payoff sets in the non-determinacy proofs - this can be found here. Here are a few diagrams to illustrate. enter image description here enter image description here enter image description here

$\endgroup$
  • $\begingroup$ Regarding 3: In this answer Andreas Blass shows that determinacy on length $\omega_1$ games over $\omega$ is inconsistent with $\operatorname{ZF}$. $\endgroup$ – Stefan Mesken Jun 7 '17 at 16:46
  • 1
    $\begingroup$ @Stefan Thanks for the comment. Unfortunately I'm specifically interested in the $\mathsf{ZFC}$ context, where of course even determinacy of length $\omega$ games on $\omega$ is inconsistent. $\endgroup$ – Dan Saattrup Nielsen Jun 7 '17 at 21:08
  • $\begingroup$ Kechris-Solovay in "On the relative consistency strength of determinacy hypotheses" shows that if $V=L[x] $ for a real $x$, lightface $\Delta^1_2$ determinacy implies OD determinacy. $\endgroup$ – Yizheng Zhu Jun 8 '17 at 20:44
  • $\begingroup$ @YizhengZhu Ah yeah that's true, and if I recall correctly we also have that $\textsf{AD}^{L(\mathbb{R})}$ implies $\textsf{OD}(\mathbb{R})$, so that it's at least consistent (relative to a limit of Woodins with a measurable above) that we get determinacy of all $\textsf{OD}(\mathbb{R})$ games of length $\omega$ on $\omega$. $\endgroup$ – Dan Saattrup Nielsen Jun 9 '17 at 14:30
6
$\begingroup$

Here is a non-exhaustive list of limitations. I'm including some from ZF alone, for completeness.

  • As you mentioned, naturally there is a non-determined game of length $\omega$, in ZFC.

  • Without assuming choice, there is a non-determined game of length $\omega_1$.

  • Also without assuming choice, there is a non-determined game of length $\omega$ with moves in $\omega_1$ (this is due to Mycielski, I believe) and a non-determined game of length $\omega$ with moves in $\mathcal{P}(\mathbb{R})$.

  • Back to ZFC, there a definable non-determined game of length $\omega$ with moves in $\mathcal{P}(\mathbb{R})$.

  • One can consider long games on $\omega$ (or on $\mathbb{R}$, it becomes equivalent), but one needs to impose definability. Yes, all definable games of length $\omega$ can be determined, but you can get more - Woodin showed that if there is an iterable model of ZFC with a countable (in V) Woodin cardinal which is a limit of Woodin cardinals, then it is consistent that all ordinal-definable games of length $\omega_1$ are determined. Note that this is a proof of consistency. The assertion "all ordinal-definable games of length $\omega_1$ are determined" is not provable from large cardinals alone (this follows from a theorem of Larson).

  • As for (definable) games of length $\omega$ with moves in $\mathbb{R}$, they are subsumed by long games, so they can be determined (provably from large cardinals). Determinacy for, say, projective games follows from $\omega^3$-many Woodin cardinals (this is due to Neeman).

  • Beyond this, there is a definable game of length $\omega_1+\omega$ that is not determined.

Regarding your specific subquestions, it depends on how one defines analyticity for those games. If one naively defines it as in Baire space, then of course there is a non-determined "open" game of length $\omega+1$ (since there is a non-determined game of length $\omega$). If one means "analytic" as in "coded by an analytic set," then those games can be determined for every countable $\alpha$ by the above remarks (for long games, this is due to Neeman; for games on $\alpha$, one simply uses a bijection from $\omega$ to $\alpha$ to code the games).

$\endgroup$
  • $\begingroup$ Thanks for all these facts Juan! I think I've gotten close to having an overview of the situation now. In your penultimate bullet point, are you saying that it's consistent (modulo large cardinals) that we have OD determinacy of length $\omega$ games on $\mathbb R$? Is this because of Woodin's consistency result you mentioned, that a sharp of a Woodin limit of Woodins implies the consistency of OD games of length $\omega_1$ on $\omega$? $\endgroup$ – Dan Saattrup Nielsen Jun 19 '17 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.