I'd like to close a gap left open in an old question of mine; I've tweaked the terminology to be a bit nicer.

For a (boldface) pointclass $\Gamma$ and a payoff set $G\subseteq\omega^\omega$, say that $G$ is $\Gamma$-narrow iff there is some equivalence relation $E\in\Gamma$ such that $E$ has $\le\omega_1$-many classes and $G$ is $E$-invariant. Gabe Goldberg showed that, provably in $\mathsf{ZFC+\neg CH}$, there is a $(\Sigma^1_1\wedge\Pi^1_1)\vee(\Sigma^1_1\wedge\Pi^1_1)$-narrow set whose associated Gale-Stewart game is undetermined.

My question is whether this bound can be improved. For example, is there $\mathsf{ZFC+\neg CH}$-provably a $\Pi^1_1\vee\Sigma^1_1$-narrow undetermined game? What about $\Sigma^1_1\wedge\Pi^1_1$?

Briefly, the motivation for this is that when $\mathsf{CH}$ fails, an assumption of $\Gamma$-narrowness prevents an easy construction of an undetermined game via diagonalization against strategies since there are more strategies than there are basic facts needed to determine the whole payoff set. Producing $\mathsf{ZFC+\neg CH}$ examples of $\Gamma$-narrow undetermined games, especially for "tame" $\Gamma$s, seems to require meaningfully more effort than straight diagonalization. For this reason I'd also be interested in the situation of "$\le\omega_1$" is replaced with "$<2^{\aleph_0}$," although I am primarily interested in the precise version above.


1 Answer 1


Solovay's coded club game is $\Pi^1_1\vee\Sigma^1_1$-narrow. So $\mathsf{ZFC}$ proves the existence of a $\Pi^1_1\vee\Sigma^1_1$-narrow undetermined game. I don't know about $\Pi^1_1\wedge\Sigma^1_1.$

It's just optimizing the analysis in the other answer you linked to, Undetermined games of "overdetermined" type. I'll use the variant where the sequences aren't required to be increasing; see Hachtman and Palumbo's notes "Notes on determinancy" http://homepages.math.uic.edu/~shac/determinacy/determinacy2015.pdf Definition 14.6.

To streamline the analysis I will change the indexing to treat both players at once, so a point in Baire space $z$ corresponds to a single sequence $((z))_0,((z))_1,\dots$ instead of the usual two sequences $((x_n)_{n\in\omega},(y_n)_{n\in\omega}).$ The conversion is given by $((z))_{2n}=(x)_n$ and $((z))_{2n+1}=(y)_n.$ I'll regard the $((z))_n$ as binary relations on $\omega\times\omega,$ so they can be called isomorphic if they are isomorphic as binary relations. $|.|$ means order-type.

Define partial equivalence relations $S,P$ on Baire space by:

  • $z S z'$ iff: for some $n,$ both $((z))_n$ and $((z'))_n$ fail to be well-founded total orders, and $((z))_m$ is isomorphic to $((z'))_m$ for all $m<n.$
  • $z P z'$ iff: $((z))_n$ and $((z'))_n$ are well-founded total orders for all $n,$ and $\sup_n(|((z))_n|+1)=\sup_n(|((z'))_n|+1).$

The domains of $S$ and $P$ partition Baire space. So $S\cup P$ is a total equivalence relation. The winner of the coded club game with play $z$ is a function of the equivalence class of $z$ (and the stationary co-stationary set $A\subseteq \omega_1$ that defines the club game).

$S$ has $|\sum\omega_1^n|=\aleph_1$ equivalence classes. $P$ has $|\omega_1\setminus (\omega+1)|=\aleph_1$ equivalence classes.

$S$ is $\Sigma^1_1.$ A witness consists of infinite decreasing sequences in $((z))_n$ and $((z'))_{n}$ and isomorphisms $((z))_m\cong((z'))_m$ for $m<n.$ It's ok for the witness not to use the minimal possible $n,$ because larger $n$ give a stronger equivalence.

$P$ is $\Pi^1_1.$ A antiwitness consists of an infinite decreasing sequence in some $((z))_n$ or $((z'))_n,$ or a sequence of non-surjective embeddings $f_n:((z))_n\to ((z'))_{m}$ for some fixed $m,$ or a sequence of non-surjective embeddings $f_n:((z'))_n\to ((z))_{m}$ for some fixed $m.$

  • $\begingroup$ Terribly sorry for the late response, I just noticed this! I'm still interested in the $\Pi^1_1\wedge\Sigma^1_1$ situation, so I'm going to wait a bit before accepting, but this is good to know. (And I've taken the liberty of a small typographical edit.) $\endgroup$ Jul 27, 2021 at 21:09

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.