This is motivated by a previous question of mine, but I think it is ultimately more interesting (and hopefully easier to answer in the positive). In that question, a class of games (on $\omega$, of length $\omega$) is considered where the payoff set for such a game is determined by $\omega_1$-many, rather than the usual $2^\omega$-many, yes/no facts. Call such a class of games overdetermined; I'm interested in whether there are, provably in ZFC+$\neg$CH, undetermined overdetermined games (heh).

Formally, say that a game with payoff set $A$ is $\Gamma$-overdetermined (for $\Gamma$ a pointclass) if $A$ is $E$-invariant for some equivalence relation $E\in\Gamma$ with $\omega_1$-many classes. Obviously this is a silly notion in full generality: take $E=\{(a, b): a\in A\iff b\in A\}$. Things become interesting, however, when we restrict attention to reasonably-definable $E$. For example, every copy/diagonalize game on ordinals (see the question linked above) is overdetermined with respect to a (fixed) $(\Sigma^1_1\vee\Pi^1_1)$-relation: changing notation slightly, a play $\pi$ yields a sequence of linear orderings $L_i^\pi$ $(i\in\omega)$, and two plays $\pi,\chi$ are guaranteed to be won by the same player if $L_i^\pi\approx L_i^\chi$ for each $i\in\omega$, where $A\approx B$ for linear orders $A, B$ if $A$ and $B$ are isomorphic or each is ill-founded. And this equivalence relation has only $\omega_1$-many classes.

My question is:

Working in ZFC + $\neg$CH, can we prove the existence of an undetermined game which is overdetermined by some "tame" pointclass (e.g. projective, or even better $\Sigma^1_1\vee\Pi^1_1$)?

I strongly suspect that the answer is "yes," even for $\Sigma^1_1\vee\Pi^1_1$, but I don't immediately see how to prove it. Note that I'm allowing the game itself to be as horrible as desired, as long as it respects some nice equivalence relation with few classes (incidentally, I'd also be happy to replace "$\omega_1$" with "$<2^\omega$") - the point is to restrict the usefulness of choice in terms of building an undetermined game by ensuring that any naive construction via transfinite recursion has to "end too early" to be guaranteed to work.

Beyond this question, I'm interested in any literature on games of arbitrary complexity but which respect some "tame" equivalence relation with few classes; I haven't managed to find any on my own.


1 Answer 1


The club game is overdetermined by a projective equivalence relation, so stationary co-stationary subsets of $\omega_1$ will give the counterexamples to overdeterminacy that you're looking for. The equivalence relation is actually $\Delta^1_2$, and if you're careful you can probably show it's low in the difference hierarchy on $\Pi^1_1$.

Recall that in the club game, two players alternate playing natural numbers $x(n)$ and $y(n)$. Thus Player I produces $x\in \mathbb R$ and Player II produces $y\in \mathbb R$. The outcome of the game depends on the reals $(x)_n$ and $(y)_n$ given by the canonical homeomorphism $\mathbb R\to \mathbb R^\omega$. Consider the sequence $(x)_0,(y)_0,(x)_1,(y)_1,\dots$. If some element of this sequence does not code a wellorder of $\omega$, we assign the play the value $\infty_\text{I}$ if Player $\text{I}$ is responsible for the first failure and $\infty_\text{II}$ otherwise. Let $|\cdot|$ be the rank function $\text{WO}\to \omega_1$. Assuming each $(x)_n,(y)_n$ codes a wellorder, if the sequence $|(x)_0|,|(y)_0|,|(x)_1|,|(y)_1|,\dots$ is not strictly increasing, we assign the play the value $\infty_\text{I}$ if Player $\text{I}$ is responsible for the first failure and $\infty_\text{II}$ otherwise. Otherwise all the rules have been followed, and we assign the play the value $\sup_{n<\omega} |(x)_n|,|(y)_n|$. Two plays are deemed equivalent if they have the same value. The equivalence relation is $\Delta^1_2$ since it is correctly computed by any transitive model of $\text{ZFC}^-$ that contains the play.

Given a subset $S\subseteq \omega_1$, let $A_S\subseteq \mathbb R$ be the collection of plays whose value is either $\infty_{\text{II}}$ or else lies in $S$. If Player $\text{I}$ wins $G(A_S)$ then $S$ contains a club, and if Player $\text{II}$ wins $G(A_S)$ then $\omega_1\setminus S$ contains a club. The argument is on pages 1972-1973 of the Handbook of Set Theory, Koellner-Woodin Theorem 2.12. Thus if $S$ is stationary co-stationary, $A_S$ is not determined.

  • $\begingroup$ Nice! How low is it in the difference hierarchy? I can't quite get it as low as $\Sigma^1_1\wedge\Pi^1_1$, which would be nice ... $\endgroup$ Nov 12, 2017 at 23:15
  • $\begingroup$ @NoahSchweber You can also find this game of Solovay presented in Chapter II of Kleinberg's book or Sherwood's notes on Determinacy. It seems to me you can write the equivalence relation as formula of the form $(\Sigma_1^1 \wedge \Pi_1^1) \vee (\Sigma_1^1 \wedge \Pi_1^1)$. Besides the $\omega_1$-many classes, you need two additional classes corresponding to who loses first. Quickly looking at your copy game, it seems that after you account for all the ways that player I and II can lose, it seems like your equivalence relation need more than one disjunctions of $(\Sigma_1^1 \wedge \Pi_1^1)$. $\endgroup$
    – William
    Nov 13, 2017 at 6:45
  • $\begingroup$ @William Yes, that was the bound I got. I'm curious if it can be gotten lower. $\endgroup$ Nov 13, 2017 at 22:37
  • $\begingroup$ I'm going to hold of on accepting, to see if the bound can be improved, but this is great so I've awarded the bounty. $\endgroup$ Nov 13, 2017 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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