9
$\begingroup$

Let $T$ be a game tree and $T\in N\in M$, where $N,M$ are the two least admissibles containing $T$. Let $A$ be a boolean combination of two lightface open sets in $[T]$, or alternatively, a boolean combination of two open sets that happens to be a $\Delta_1$-definable class of $N$ and $M$. (There may be further work needed to say "the right thing" here: maybe the same $\Delta_1$ relation specifies different classes over $N$ and $M$, I'm not sure if this will affect things.)

Then apparently $M\vDash G(A;T)$ is determined, and furthermore this is minimal, i.e. in general $N$ will not see that $A$ is determined.

Since I heard this as an aside from my supervisor (who's currently away) I was wondering if there is a reference out there for this. I am aware that $\Sigma^0_1\wedge\Pi^0_1$-Determinacy is proved all the way back by Gale and Stewart from ZFC, so I'm specifically interested in the version with the weaker hypothesis.

$\endgroup$
7
  • $\begingroup$ For minimality, it would be enough to show that there is some (lightface) $\Sigma^0_1\wedge\Pi^0_1$-game on with no hyperarithmetic winning strategy, right? $\endgroup$ Commented Aug 22, 2013 at 18:08
  • $\begingroup$ Something seems wrong here, because $N$ and $M$ are only required to see the tree $T$, which might be just $\omega^{<\omega}$, not the essential information $A$ about the game. So it's not clear what is meant by $M\vDash G(A;T)$. $\endgroup$ Commented Aug 22, 2013 at 21:32
  • $\begingroup$ Actually I don't understand what a "game tree" is? Could someone explain please? Also what is meant by "admissibles"? Does this mean that M and N are admissible sets in the usual sense? Noah S: yes, the winning strategy will be $\Game (\Sigma^0_1 \wedge \Pi^0_1)$, which I think is $\Delta^1_1$ (positive hyperarithmetical inductive on $\omega$, if I'm not mistaken, correct me here). $\endgroup$ Commented Aug 22, 2013 at 22:19
  • $\begingroup$ @AndreasBlass - I could add that $A$ is a $\Delta_1$-definable class of $N$, but since it is arithmetical, is this not already the case? Carlo - The game tree is tree of positions obtainable in the game. Thus the game could be played with some other moves than just natural numbers. $\endgroup$ Commented Aug 22, 2013 at 23:41
  • $\begingroup$ Chris, I don't see where the question says $A$ is arithmetical. If $T=\omega^{<\omega}$ then $[T]$ is the Baire space of sequences of natural numbers. Let $B_n$ be the clopen set of those sequences that begin with $n$. Since the $B_n$'s are pairwise disjoint, we can form continuum many open sets by taking unions of some of them. So there are continuum many possibilities for the $A$ in the question; that's too many for them all to be arithmetical. $\endgroup$ Commented Aug 23, 2013 at 2:30

1 Answer 1

8
$\begingroup$

(As the absentee supervisor am I allowed to pitch in?) To my mind this is least confusing if we take $A$ to be $B\cap C$ the intersection of a lightface open with a lightface closed set in the full Baire space. Here then the `game tree' for our purposes can be defined to be the set of finite partial plays in $\omega^{<\omega}$ up to some finite round. (Martin for example defines game trees which may have finite maximal branches, but let us ignore that here, and we'll only allow trees where every node can be extended.) Then the tree $T = \omega^{<\omega }\in L_{\omega_1^{ck}}$. (Similar considerations hold for trees which are subspaces of other spaces $X^\omega$ for countable $X$, and 'double-admissible' sets containing $X$ as an element, which we shall ignore.)

(If the two sets are not lightface but are say open or closed in some real parameter $z$, then the tree may be in $L_{\omega_1^{ck}}$, but as Andreas points out the game (that is the payoff set $A$) may only be defined in $L_{\omega_1^{z ck}}[z]$. But let us continue to assume the param. $z=\emptyset$.)

Now a winning strategy for the (lightface) open game $B$ on this `game-tree' is definable over (but is not necessarily a member of) $L_{\omega_1^{ck}}$ (and similarly for the closed game with payoff $C$).

For $s \in \omega^{<\omega}$ let $N_s$ be the open neighbourhood of $s$: the set of all those $\omega$-sequences extending $s$. Suppose player I has no w.s for the game playing into $A$.

Let $z$ be : $$\{ s \mid s \mbox{ is a finite even length seq. with } N_s\subseteq B\wedge \mbox{ I has a w.s in the game with starting position } s \mbox{ and playing into } C \}$$

This is a $\Sigma^1_1$ set and thus $z\in L_{\omega_2^{ck}}$ (but not necessarily $ L_{\omega_1^{ck}}$). The set, $D$, of $\omega$-sequences extending elements of $z$ is thus an open set in the param. $z$. By the usual argument for $\Sigma^0_1(z)$-Det. either I or II has a w.s to play into, or out of, $D$; moreover this strategy can be taken to be either in (in the case of I winning), or $\Pi_1$-definable over (in case of II), the next admissible set containing $z$: here $L_{\omega_2^{ck}}$.

Now argue that I cannot have the w.strat. in this latter game (since we assumed I had no w.s. for $G_A$). Hence II has the w.s. here. Call it $\tau$.

Let $$y = \{ s \mid s \mbox{ is a finite even length seq. with } N_s\subseteq B\wedge s \notin z \} .$$

For each $s\in y$ let $\tau(y)$ be the $L$-least w.s for II witnessing that $s\notin z$ (using $\Sigma^0_1$-Det.) We may assume the function $ s \rightarrow \tau(s)$ with domain $y$ is $\Sigma_1(L_{\omega_2^{ck}})$ (an essential use of $\Sigma_1$-Rep. here.) Now define a strategy $\tau^*$ by setting $\tau^*(s) =\tau(s)$ if $N_s\not\subseteq B$ and $\tau^*(s\smallfrown r) = \tau(s)(r)$ where $N_s \subseteq B$ (and $s$ is the shortest init. set. of $s \smallfrown r$ for which the latter is true). Now argue that $\tau^*$ is a w.s. for II in $G_A$.

This shows that Det$(\Sigma^0_1 \cap \Pi^0_1)$ holds definably over (rather than strictly within) the second admissible set over the tree.)

Lastly we point out that strategies for such games cannot all be elements of $L_{\omega_2^{ck}}$ - or in other words of $HYP(\mathcal{O})$: the complete $\Game(\Sigma^0_1 \cap \Pi^0_1)$ set of integers will be $\Pi_1(L_{\omega_2^{ck}})$.

$\endgroup$
3
  • $\begingroup$ A totally unrelated question: how did you tex the game quantifier? (Detexify is not helping me.) $\endgroup$ Commented Aug 24, 2013 at 4:23
  • $\begingroup$ Thanks, Philip! But should I take it then that this is wholly "folklore" and not published? @NoahS - it's "\Game": $\Game$ $\endgroup$ Commented Aug 24, 2013 at 11:42
  • $\begingroup$ I always thought of it as folklore, and I don't know of an explicit first (or any) publication. But the equivalent statement of the determinacy of finite boolean combinations of open sets (so a boldface statement) is also equivalent to $\Pi^1_1$-CA (also a boldface statement) and this appears in Simpson's book, so there is some version of it there I think. In terms of $\beta$-models, the first such model of Det(Bool(Open)) is the minimal model of $\Pi^1_1$-CA, which is essentially the first $L_\alpha$ which is a limit of admissibles. $\endgroup$ Commented Aug 24, 2013 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .