1 Introduction
To each
$A\subset \mathbb {N}^{\mathbb {N}}$
corresponds a two-player, perfect-information game
$G_A$
in which Players I and II alternate turns playing infinitely many natural numbers
$x(i)$
, eventually producing a sequence
$x\in \mathbb {N}^{\mathbb {N}}$
. Player I wins if and only if
$x\in A$
. (For background in descriptive set theory and infinite games, we refer the reader to Moschovakis [Reference Moschovakis18].) These games were introduced by Gale and Stewart, who proved:
Theorem 1 (Gale-Stewart [Reference Gale, Stewart, Kuhn and Tucker10]).
Suppose A is
$\Sigma ^0_1$
. Then one of the players has a winning strategy for
$G_A$
.
A natural question is: How complicated must the winning strategies for open games be? That is: What is the smallest complexity class in which one is guaranteed to find a winning strategy for each open game? The answer to this question is well-known and we call it the strong Gale–Stewart theorem. Its earliest appearance that we know of is in Moschovakis [Reference Moschovakis17], though the theorem as stated here seems to have been part of the folklore at the time. The second half of the theorem is due to Blass [Reference Blass7].
Theorem 2 (Strong Gale–Stewart theorem).
Suppose A is
$\Sigma ^0_1$
. Then one of the players has a winning strategy for
$G_A$
recursive in
$\mathcal {O}$
. Moreover, this is optimal: there is a
$\Sigma ^0_1$
game for which no player has a
$\Delta ^1_1$
winning strategy.
If it is Player I who has a winning strategy, one can always find a strategy which is
$\Delta ^1_1$
, but Player II might need to look beyond
$\Delta ^1_1$
to find one.
Analogs of the Strong Gale Stewart Theorem for games with payoff in classes other than the
$\Sigma ^0_1$
have been studied at length in the past. We give a few examples. Versions of the theorem for
$\Sigma ^0_3$
sets and
$\Sigma ^0_4$
sets have been obtained by Welch [Reference Welch24] and Hachtman [Reference Hachtman12]. Building on work of Friedman [Reference Friedman9], Martin established a similar result for
$\Delta ^1_1$
games. For
$\Pi ^1_1$
games, Martin [Reference Martin15] showed that the strategies can always be taken to be recursive in
$0^\sharp $
, and Friedman [Reference Friedman8] showed that this is best possible, in the sense that some of these games have no winning strategy in L (see also Harrington [Reference Harrington13]). For projective games, Woodin showed that the strategies can be found in a model of the form
$M_n^\sharp (x)$
and that this is optimal (see Müller–Schindler–Woodin [Reference Müller, Schindler and Woodin19]). Similar results can be obtained for games on other sets. Martin’s argument for
$\Pi ^1_1$
shows that
$\boldsymbol \Pi ^1_1$
games with moves in
$\mathbb {R}$
always have a winning strategy which is continuously reducible to
$\mathbb {R}^\sharp $
, while Martin–Steel [Reference Martin, Steel, Kechris, Löwe and Steel16] show that this is best possible, in the sense that some of these games do not have winning strategies in
$L(\mathbb {R})$
. An analogous result for projective games with moves in
$\mathbb {R}$
follows from the results in [Reference Aguilera and Müller4]. General facts surrounding Strong Gale–Stewart theorems follow from the periodicity theorems of Moschovakis (see [Reference Moschovakis18]).
Oddly, less is known about
$\Sigma ^0_2$
. It is the intent of this article to change this state of affairs, and answer as thoroughly as we can:
Question 3. What is the analog of the Strong Gale–Stewart theorem for
$\Sigma ^0_2$
?
The study of
$\Sigma ^0_2$
began with:
Theorem 4 (Wolfe [Reference Wolfe25]).
Suppose A is
$\Sigma ^0_2$
. Then one of the players has a winning strategy for
$G_A$
.
Solovay (unpublished, but see Kechris [Reference Kechris, Kechris, Löwe and Steel14] or Moschovakis [Reference Moschovakis18]) obtained partial results about exactly where winning strategies for such games appear. Specifically, he identified the smallest class which is guaranteed to contain winning strategies for
$\Sigma ^0_2$
games that are determined in favor of Player I. What is left to do is to find where winning strategies for Player II appear.
Let us describe Solovay’s theorem. Consider a monotone operator
$$\begin{align*}\phi:\mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N}), \mathrm{where} \; A \subseteq B \rightarrow \phi(A) \subseteq \phi(B).\end{align*}$$
We can iterate
$\phi $
transfinitely to obtain an inductive definition as follows:
$$ \begin{align*} W^0 &= \varnothing\\ W^{<\alpha} &= \bigcup_{\beta<\alpha} W^\beta\\ W^\alpha &= \phi(W^{<\alpha})\\ W^\infty &= \bigcup_{\beta} W^\beta. \end{align*} $$
Due to matters of cardinality, there is a countable ordinal
$\kappa $
such that
$\phi ^{\kappa } = \phi ^{\kappa +1}$
, and the least such
$\kappa $
is called the closure ordinal of
$\phi $
and denoted by
$|\phi |$
. Solovay proved that if Player I has a winning strategy in a
$\Sigma ^0_2$
game, then she has one which is given by a
$\Sigma ^1_1$
inductive definition. In fact, Solovay proved the stronger result that
$\Game \Sigma ^0_2 = \Sigma ^1_1$
-IND. Let
$$\begin{align*}\sigma = \sup\{|\phi|: \phi \in \Sigma^1_1\}.\end{align*}$$
(More generally,
$\sigma ^m_n$
is
$\sup \{|\phi |: \phi \in \Sigma ^m_n\},$
so that
$\sigma $
is really an abbreviation for
$\sigma ^1_1$
.)
A relation on a subset of an ordinal
$\alpha $
is
$\alpha $
-r.e. if it is
$\Sigma _1$
-definable over
$L_\alpha $
. Define
$$\begin{align*}\delta_\alpha = \sup\{\gamma: \text{ there is an } \alpha\text{-r.e. wellorder of length } \gamma\}.\end{align*}$$
Thus,
$\delta _\alpha $
is one kind of analog of the Church–Kleene ordinal
$\omega _1^{CK}$
at the level of
$L_\alpha $
. Much of the focus throughout this article will be on
$\delta _{\sigma }$
, therefore we abbreviate
$\delta _\sigma $
as
$\delta $
. According to a theorem of Gostanian [Reference Gostanian11],
$\delta $
is inadmissible, unlike the case for
$\omega $
and
$\omega _1^{CK}$
. (In fact, it can be shown that
$\sigma $
is the least ordinal for which the notions of “supremum of all recursive well-orderings” and “next admissible ordinal” do not coincide.) By the inadmissibility of
$\delta $
, there are sets of integers which are
$\Delta _1$
-definable over
$L_\delta $
but not elements of
$L_{\delta }$
, which fact enables the following theorem.
Theorem 5. Suppose A is
$\Sigma ^0_2$
. Then one of the players has a winning strategy for
$G_A$
which is
$\Delta _1$
-definable over
$L_{\delta }$
.
We do not know if the bound given by Theorem 5 is optimal, as discussed in the questions at the end. What we do know is that if we strengthen the conclusion of Theorem 5 slightly, then the bound obtained is optimal. The strengthening we need involves the difference between having a winning strategy and knowing that you have a winning strategy. By way of illustration, consider the simpler setting of
$\Sigma ^0_1$
games. As usual, we think of a
$\Sigma ^0_1$
game as being given by pruning the full tree
$\mathbb {N}^{< \mathbb {N}}$
to a subtree T, and it is the goal of Player I to reach a leaf. Now consider an example in which T is well-founded. Absolutely any strategy for Player I would be winning! But the only way we can see to know that, is to have a function providing the ordinal ranks of the nodes of T. Similarly, in our setting of
$\Sigma ^0_2$
, strategies for Player II will be witnessed as winning by providing certain ordinal ranks for nodes in trees. Our intention is then to show that, while you may get lucky and have a winning strategy appear in L way before stage
$\delta $
, in order to get a witness which guarantees that your strategy is winning, you do have to go all the way to
$\delta $
.
This brings up a fundamental problem. It will be easy enough to show that the ordinal ranks we choose to assign to the trees we define will be cofinal in
$\delta $
. But how do we know that somebody more clever won’t be able to find a different, perhaps better, way to witness that a strategy is winning? One that doesn’t have to go all the way through
$\delta $
? By way of addressing this objection, we will define what seems to be the most general notion possible of witnessing that a strategy is winning. We state Definition 6 in its lightface form, noting that it relativizes to Borel games the natural way. Below, a definition for a
$\Delta ^1_1$
set A is a formula
$\psi \in \Sigma ^0_\alpha $
for some
$\alpha <\omega _1^{CK}$
such that
$$\begin{align*}\forall x\, \big( x\in A\leftrightarrow \psi(x,y)\big).\end{align*}$$
Definition 6. Consider a game
$G_A$
induced by some
$\Delta ^1_1$
set
$A \subseteq \mathbb {N}^{\mathbb {N}}$
, as given by a
$\Sigma ^0_\alpha $
definition
$\psi $
(for some
$\alpha <\omega _1^{CK}$
). A witnessed winning strategy for
$G_A$
is a triple
$(\tau , \phi , p)$
such that:
-
•
$\phi (x,y)$
is a
$\Delta _0$
formula in the language of set theory, with the free variables x and y, such that for all
$\bar \tau $
and all admissible sets M containing
$\bar \tau $
, we have
$M\models \exists x\, \phi (x,\bar \tau )$
if and only if (in V)
$\tau $
is a winning strategy for the game defined by
$\psi $
; -
•
$\exists x\, \phi (x,\tau )$
holds in every admissible set containing
$\tau $
; and -
•
$\phi (p, \tau )$
.
Why are there any witnessed winning strategies at all? For any Borel game A, it is straightforward that the assertion of
$\tau $
being a winning strategy is
$\Pi ^1_1$
: “for every real s, the outcome
$\tau * s$
of Player I using
$\tau $
against the input s is in A, or for every s the outcome of Player II using
$\tau $
against s is not in A”. Moreover, this assertion is uniform in the definition of A. By a result of Barwise, Gandy, and Moschovakis [Reference Barwise, Gandy and Moschovakis6], there is a uniform translation of
$\Pi ^1_1$
formulas
$\chi $
into
$\Sigma _1$
formulas
$\chi ^*$
so that for all
$x\in \mathbb {R}$
, we have
$(\mathbb {N}, x) \models \chi (x)$
if and only if
$L_{\omega _1^x}\models \chi ^*(x)$
, where
$\omega _1^x$
denotes the least x-admissible ordinal. Hence there is at least one
$\phi $
which is suitable for use as an entry in a witnessed winning strategy. Then every winning strategy
$\tau $
(for
$G_A$
given by
$\psi $
) will have some p witnessing
$\exists x\,\phi (x,\tau )$
.
Proofs of determinacy usually produce both a winning strategy and a witness for it, simultaneously, with the two having roughly the same complexity. Indeed, the distinction between winning strategies and witnessed winning strategies is not usually made, because witnesses can always be obtained easily (e.g., in a
$\Delta ^1_1$
way) from winning strategies; however, it appears to be a subtlety arising when considering the complexity of strategies for
$\Sigma ^0_2$
games, since the ordinal
$\delta $
is inadmissible.
Theorem 7. Suppose A is
$\Sigma ^0_2$
. Then, one of the players has a witnessed winning strategy
$(\tau , \phi , p)$
for
$G_A$
in which
$\tau $
and p are
$\Delta _1$
-definable over
$L_{\delta }$
.
Moreover, this is optimal: for each
$\bar \delta <\delta $
there is a
$\Sigma ^0_2$
game for which no player has a witnessed winning strategy definable over
$L_{\bar \delta }$
.
2 Proof of Theorem 5
We begin by recalling some facts. A set M is called admissible if
$(M,\in )\models {\mathsf {KP}}$
. (For thorough background on admissibility, we refer the reader to Barwise [Reference Barwise5].) An ordinal
$\alpha $
is admissible if
$L_\alpha $
is admissible. For an ordinal
$\alpha $
, we denote by
$$\begin{align*}\alpha^+\end{align*}$$
the smallest admissible ordinal greater than
$\alpha $
. If
$\alpha $
is an admissible limit of admissibles, we say that
$\alpha $
is recursively inaccessible. Let
$\theta (x)$
be a formula in the language of second-order set theory. We say that
$\alpha $
reflects
$\theta $
if
$$ \begin{align*} \forall \beta<\alpha\, \Big(L_\alpha\models \theta(\beta) \to \exists \bar\alpha<\alpha\, \big(\beta<\bar\alpha \wedge L_{\bar\alpha}\models\theta(\beta)\big)\Big). \end{align*} $$
(To be clear, since
$\theta $
is second-order, its class quantifiers range over all possible subsets of the model over which the formula is being interpreted.) We say that
$\alpha $
is
$\Sigma ^1_1$
-reflecting if it is admissible and it reflects every
$\Sigma ^1_1$
formula. If so,
$\alpha $
is recursively inaccessible. A classical theorem of Barwise, Gandy, and Moschovakis [Reference Barwise, Gandy and Moschovakis6] asserts that
$\Sigma ^1_1$
sentences can be uniformly translated into
$\Pi _1$
sentences about the next admissible set. By a theorem of Aczel and Richter [Reference Aczel, Richter, Fenstad and Hinman1],
$\sigma $
is the least
$\Sigma ^1_1$
-reflecting ordinal. Note also that it is the least ordinal which reflects
$\Sigma ^1_1$
formulas without parameters.
$\sigma $
has many more different characterizations and we refer the reader to [Reference Aguilera and Lubarsky3, Section 4] for a compilation of them.
2.1
$\Sigma ^0_2$
games
The first step to proving the theorem is to recall the proof of
$\Sigma ^0_2$
-determinacy. The proof is essentially Wolfe’s, but presented as in Solovay’s argument, which clarifies several considerations of complexity. We will need to pay extra attention to how certain objects are defined, since ultimately our complexity bound will depend on a reflection argument.
Let A be a
$\Sigma ^0_2$
set of reals. A can be assumed to be of the form
$$\begin{align*}x\in A \leftrightarrow \exists n\,\forall m\, R(n,m,x \upharpoonright 2m)\end{align*}$$
for some recursive relation R. For conceptual ease, we may assume that, for each n, R is closed downwards: if
$R(n,m,x \upharpoonright 2m)$
and
$k < m$
then
$R(n,k,x \upharpoonright 2k)$
.
In the proof, we consider a family of auxiliary games
$G(X,s)$
. In
$G(X,s)$
, Players I and II take turns playing natural numbers to produce a sequence x, after which Player I wins if and only if
where 
is the length of s and
$s^\frown x\upharpoonright 2m$
denotes the first
$2m$
elements of the concatenation of s and x.
We consider the operator
$X\mapsto \phi (X)$
given by
Claim 8.
$\phi $
is a positive
$\Sigma ^1_1$
operator.
Proof. It is positive, since
$G(X,s)$
is a
$\Pi ^0_1$
game and X appears only positively in its definition.
$\phi $
is an operator in
$\Game \Pi ^0_1$
, where
$\Game $
denotes the game quantifier. By a theorem of Svenonius (see Barwise [Reference Barwise5, Chapter VI]),
$\Game \Pi ^0_1$
is equal to
$\Sigma ^1_1$
.
We consider the inductive definition given by
$\phi $
and denote the stages by
$W^\alpha $
as in the introduction.
Claim 9. Suppose
$s\in W^\infty $
. Then, Player I has a winning strategy for
$G_A$
from s.
Proof. Let
$\xi _0$
be such that
$s \in W^{\xi _0}$
and let
$\sigma _0$
be the strategy witnessing this. Playing according to
$\sigma _0$
guarantees that one of the following holds:
-
1. after infinitely many turns, we have a play x with the following property: for some
, we have
$R(n,m,s^\frown x \upharpoonright 2m)$
for all m; or -
2. after finitely many turns, we have a play
$s_1$
such that
$s^\frown s_1 \in W^{\xi _1}$
for some
$\xi _1 < \xi _0$
.
, we have 
In the first case, Player I wins the game. In the second case, we obtain a strategy
$\sigma _1$
for the game
$G(W^{\xi _1}, s^\frown s_1)$
. Since there cannot be an infinite descending sequence of ordinals, repeating this procedure eventually leads to an infinite run of the game won by Player I.
Claim 10. Suppose s is of even length and
$s\not \in W^\infty $
. Then Player II has a winning strategy for
$G_A$
from s.
Proof. Since
$W^\infty $
is a fixed point of
$\phi $
,
$W^\infty $
is the set of all positions s such that Player I has a winning strategy in
$G(W^{\infty }, s)$
. This is a
$\Pi ^0_1$
game and thus determined for each s, so Player II has a winning strategy in it if Player I does not.
In particular, since we have chosen an s not in
$W^\infty $
, there is a strategy
$\sigma _s$
for Player II. If Player II follows this strategy for infinitely many rounds, it produces a sequence x such that
This means if Player II follows the strategy, for each 
there is a finite number
$m_n$
witnessing that II has won the nth game, in that
$\lnot R(n,m_n, s^\frown x \upharpoonright 2m_n)$
, while also
$s^\frown x \upharpoonright 2m_n \not \in W^\infty $
. There are only finitely many such n to consider, and so after finitely many steps we will have produced a sequence
$s_1$
(of length say
$2m$
) witnessing that II has won the nth game for all 
:
Moreover, we can assume that
$s_1$
is not the empty sequence: even if the empty sequence would suffice for the first clause of II’s winning condition, we can take the result of one step of each player in the game, still staying out of
$W^\infty $
.
Now we repeat the construction. Since
$s^\frown s_1 \not \in W^\infty $
strictly extends s, Player II has a winning strategy in
$G(W^\infty , s^\frown s_1)$
, which applies to strictly more ns. Thus we obtain a new strategy
$\sigma _{s_1}$
which Player II can now follow to obtain a new position
$s_2$
such that the conditions above hold with
$s^\frown s_1 ^\frown s_2$
in place of
$s^\frown s_1$
and
$s^\frown s_1$
in place of s. Repeating this infinitely often results in a play x such that
$$\begin{align*}\forall n \, \exists m_n\, \lnot R(n,m_n,s^\frown x\upharpoonright 2m_n),\end{align*}$$
which is the winning condition for Player II in
$G_A$
.
2.2 Partial strategies
Solovay’s argument relied on the fact that, according to Claims 9 and 10, if Player I has a winning strategy for
$G_A$
, then she has one which is computable from
$W^\infty $
and indeed from some
$W^{\xi }$
with
$\xi <|\phi |\leq \sigma $
. As observed by Welch [Reference Welch23], the argument also shows that the strategies for Player II lie within the next admissible set after
$L_{\sigma }$
. It is easy to see though that
$\sigma ^+$
is not the least upper bound for the existence of strategies: the collection of games that Player I wins is definable over
$L_\sigma $
, so the collection of games that Player II wins is a set in
$L_{\sigma ^+}$
; since the function that takes such a game and returns the least winning strategy for II is
$\Sigma _1$
-definable, its range has to be bounded beneath the next admissible set.
In order to optimize this upper bound, we appeal to the uniformity with which each of the strategies for the auxiliary games can be computed, in the instances where those games are won by Player II. We will show:
Lemma 11. Let
$\sigma _s$
denote the L-least strategy for Player II in
$G(W^\infty , s)$
. Then,
-
(1) for each
$s\not \in W^\infty $
, if
$\sigma _s$
exists, then it belongs to
$L_\delta $
, -
(2) the predicate
$s\not \in W^\infty \wedge x = \sigma _s$
is
$\Delta _1$
over
$L_\delta $
.
Granted the lemma, Theorem 5 follows: Player II chooses her moves for the game A following the procedure of Claim 10. Such strategies always appear in
$L_\delta $
and determining whether an element of
$L_\delta $
is the strategy is
$\Delta _1$
, so the procedure is
$\Delta _1$
over
$L_\delta $
. The proof of the lemma appears on p. 8.
Remark 12. In general, if A is a countable admissible set, then the
$\Game \Sigma ^0_1$
-definable relations over A are those that are
$\Sigma _1$
-definable over the next admissible set (see Barwise–Gandy–Moschovakis [Reference Barwise, Gandy and Moschovakis6]). A consequence of this is that winning strategies for games which are recursive relative to
$W^\infty $
appear arbitrarily close to the next admissible. It is perhaps surprising that a bound such as the one given by Lemma 11 is possible.
We need to analyze how strategies for
$G(W^\infty ,s)$
are constructed. These are
$\Pi ^0_1$
games with respect to the parameter
$W^\infty $
; from the perspective of Player II, these are
$\Sigma ^0_1$
games with respect to
$W^\infty $
. Thus, we consider
$\boldsymbol \Sigma ^0_1$
games now.
2.3
$\Sigma ^0_1$
games
Let us briefly recall how strategies for
$\boldsymbol \Sigma ^0_1$
games are constructed. Consider a
$\boldsymbol \Sigma ^0_1$
set B, say
$$ \begin{align} x \in B \leftrightarrow \exists n\, S(x\upharpoonright n, X) \end{align} $$
for some recursive relation S and some parameter
$X\subset \mathbb {N}$
. We define an operator
$Y\mapsto \psi (Y)$
by
Letting
$V^\alpha $
denote the
$\alpha $
th stage of this inductive definition, we have:
Claim 13. Player I has a winning strategy for
$G_B$
from the position s if and only if
$s \in V^\infty $
, in which case
$s \in V^\alpha $
for some
$\alpha < \omega _1^{X}$
and such a strategy is definable over
$L_\alpha [X]$
.
Proof. By induction, similarly to the corresponding claims for
$\Sigma ^0_2$
games. Since
$\psi $
is a positive X-arithmetical operator, its closure ordinal is at most
$\omega _1^X$
, which implies the second part of the claim.
Given a set X and a
$\Sigma ^0_1(X)$
game G, let us say that an ordinal
$\alpha $
is good for G if
$\alpha $
is the least ordinal such that the empty sequence
$\langle \rangle $
is seen to belong to the set of winning positions for Player I in the game G after
$\alpha $
steps of the inductive definition. Using the notation above, this is the least
$\alpha $
such that
$\langle \rangle \in V^\alpha $
. Thus, we have:
Claim 14. The following are equivalent:
-
(1) Player I has a winning strategy for G;
-
(2) there is some
$\alpha <\omega _1^{X}$
which is good for G; -
(3) for every admissible set M containing X there is some
$\alpha \in M$
such that
$M \models $
“
$\alpha $
is good for G.”
If so, then Player I has a winning strategy for G in any admissible set containing X.
Proof. By Claim 13, Player I has a winning strategy for G if and only if there is some
$\alpha <\omega _1^{X}$
which is good for G, in which case she has a strategy in
$L_{\alpha }[X]$
. The result follows from the fact that every admissible set containing X contains every element of
$L_{\omega _1^X}[X]$
.
2.4 Bounding strategies for
$G(W^\infty , s)$
Claim 15. Suppose s has even length and
$s\not \in W^\infty $
. For each
$\gamma $
, Player II has a winning strategy for
$G(W^{<\gamma }, s)$
.
Proof. Otherwise, Player I has a winning strategy for
$G(W^{<\gamma }, s)$
and hence
$s \in W^\gamma \subset W^\infty $
.
Claim 16.
$W^{<\gamma }$
is
$\Sigma _1$
-definable over
$L_{\omega _\gamma ^{CK}}$
, uniformly.
Proof. This is proved by induction, using the fact that
$\phi $
is
$\Sigma ^1_1$
, and so
$W^{\alpha }$
is
$\Pi _1$
-definable over
$L_{\omega _1^{W^{<\alpha }}}[W^{<\alpha }]$
, uniformly.
Claim 17. Suppose s has even length and
$s\not \in W^\infty $
. Then, for each
$\gamma $
, there is an ordinal
$\alpha $
which is good for the complement of
$G(W^{<\gamma }, s)$
and moreover
$\alpha $
belongs to any admissible set containing
$W^{<\gamma }$
.
(Of course, we expect II to win
$G(W^{<\gamma }, s)$
, and the role of II in
$G(W^{<\gamma }, s)$
is the same as the role of I in the complement of
$G(W^{<\gamma }, s)$
.)
Let us define a function f by
$$ \begin{align*} f(\gamma,s) = \begin{cases} \text{least } \alpha \text{ which is good for } G(W^{<\gamma}, s)\text{, if } \gamma = \omega_{\gamma}^{CK}\\ 0 \text{ otherwise.} \end{cases} \end{align*} $$
Claim 18. Suppose s has even length and
$s\not \in W^\infty $
. Then the function
$$\begin{align*}\gamma\mapsto f(\gamma,s)\end{align*}$$
is total and uniformly
$\Sigma _1$
-definable over all admissible sets.
The following claim is the crucial step in the proof.
Claim 19. Suppose s has even length and
$s\not \in W^\infty $
. Then,
$f(\sigma ,s)<\delta $
.
Proof. Suppose otherwise that
$\delta \leq f(\sigma ,s)$
. Let
$\theta $
be the second-order sentence in the language of set theory which over
$L_{\sigma }$
asserts the existence of a model
$(M, \in ^M)$
of
${\mathsf {KP}}$
satisfying
$V = L$
and such that
-
(1) M end-extends
$L_{\sigma +1}$
, -
(2)
$M \models $
“
$\delta \leq f(\sigma )$
.”
This is a
$\Sigma ^1_1$
sentence and by hypothesis we have
$L_\sigma \models \theta $
. By
$\Sigma ^1_1$
-reflection, there is some
$\bar \sigma <\sigma $
such that
$L_{\bar \sigma }\models \theta $
. Hence, there is a model
$\bar M$
of
${\mathsf {KP}}$
satisfying
$V = L$
and such that
-
(1)
$\bar M$
end-extends
$L_{\bar \sigma + 1}$
, -
(2)
$\bar M \models $
“
$\delta _{\bar \sigma }^{\bar M}\leq f(\bar \sigma )$
.”
By Ville’s lemma (see Barwise [Reference Barwise5]), any model of
${\mathsf {KP}}$
which end-extends
$L_{\bar \sigma +1}$
must end-extend
$L_{\bar \sigma ^+}$
. By a theorem of Gostanian [Reference Gostanian11], if
$\alpha <\sigma $
, then
$\delta _\alpha = \alpha ^+,$
and thus
$$\begin{align*}\delta_{\bar\sigma} = \bar\sigma^+.\end{align*}$$
By Claim 18,
$f(\bar \sigma ) < \bar \sigma ^+$
and so it belongs to the wellfounded part of
$\bar M$
. However, this means that
$\delta _{\bar \sigma }^{\bar M}$
belongs to the wellfounded part of
$\bar M$
and thus
$$\begin{align*}\delta_{\bar\sigma}^{\bar M} \leq f(\bar\sigma) < \bar\sigma^+,\end{align*}$$
which is impossible, since
$\bar M$
contains
$L_{\bar \sigma +1}$
and thus it contains all true
$\bar \sigma $
-recursive wellorderings of
$\bar \sigma $
.
We can now prove Lemma 11. By Claim 19,
$f(\sigma ,s) < \delta $
for each s of even length with
$s\not \in W^\infty $
. Since for each s of even length there is at most one ordinal which is good for the complement of
$G(W^{\infty }, s)$
, and whether such an ordinal exists depends only on whether
$s \in W^\infty $
, we obtain both clauses of Lemma 11. This completes the proof of the lemma and thus of the upper bound.
We mention that the key fact of
$\sigma $
we used was that
$\delta $
, albeit inadmissible, satisfies certain closure properties. Claim 19, together with Van de Wiele’s theorem [Reference van de Wiele and Stern22] (see also Sacks [Reference Sacks20]) shows, by the argument of Claim 19, that if
$\rho $
is a
$\Sigma ^1_1$
-reflecting ordinal and f is a total set-recursive function on the ordinals, then
$$\begin{align*}f(\rho) < \delta_\rho.\end{align*}$$
3 Proof of Theorem 7
We have seen that, for any
$\Sigma ^0_2$
game, if Player I has a winning strategy then there is one in
$L_{\sigma }$
, else Player II has one
$\Delta _1$
definable over
$L_\delta $
. Solovay showed that
$\sigma $
is the optimal bound for strategies for Player I. Since
$\sigma $
is recursively inaccessible, these strategies can be assumed to be witnessed. Similarly, the strategies for Player II we constructed are witnessed:
Lemma 20. The strategies
$\tau $
for Player II constructed in Section 2 can be extended to witnessed winning strategies
$(\tau , \phi , p)$
, where p is definable over
$L_\delta $
.
Proof. To have a witnessed winning strategy, we need among other things a formula
$\phi (x,y)$
which correctly tells us whether y is a winning strategy. We gave an example of such a
$\phi $
right after Definition 6. But that
$\phi $
will not be adequate here, because we have little control over where the witnesses for this
$\phi $
show up. On general principles we know that witnesses appear by the next admissible ordinal
$\sigma ^+$
, but we want them earlier, namely definable over
$L_\delta $
. That is, we need to choose
$\phi $
so that the constructions from Section 2 which we used to define
$\tau $
suffice as a witness p for the witnessed winning strategy.
Let’s briefly review what these constructions are. In a
$\Sigma ^0_2$
game, Player II is in the position of playing (as Player I) an
$\omega $
-sequence
$G_A^n$
of open games, where
$G_A^n$
is the complement of
$\forall m \; R(n, m, x\upharpoonright 2m)$
. (Recall that R is what is used to define A.) We addressed that by considering the games
$G(W^\infty , s)$
, which are based on the
$\Pi ^0_1$
set
That covers
$G_A^n$
for each 
. The argument that a node s was winning for II in
$G(W^\infty , s)$
went by assigning ordinal ranks
$f(\sigma , s)$
to s and certain of its extensions. Moreover, we showed that each
$f(\sigma , s)$
is less than
$\delta $
, and the inductive definition of f was simple, so that the calculation of
$f(\sigma , s)$
is given by a construction in
$L_\delta $
. We want to take this construction to be a witness that
$\tau $
starting from s is winning in
$G(W^\infty , s)$
. Furthermore, we want to take as a witness that
$\tau $
is winning the set of all such constructions for all
$s \not \in W^\infty $
.
Therefore, we take
$\exists x\,\phi (x,y)$
as a formalization of the following: there is a transitive set
$L_{\bar \delta }$
which is a standard model of “
$V = L$
”, and which has as a member a standard model
$L_{\bar \sigma }$
of
${\mathsf {KP}}$
, and also has a
$\Sigma ^1_1$
-inductive construction
$\{W^\alpha \}_\alpha $
of winning nodes for Player I indexed by the ordinals of
$L_{\bar \sigma }$
, and for each
$s \not \in W^\infty := W^{<\bar \sigma }$
there is an ordinal ranking function in
$L_{\bar \delta }$
witnessing that s is a win for II in
$G(W^\infty , s)$
, and y is the induced strategy.
To complete the proof, let us show that the bound
$\delta $
is optimal, i.e., that there is a
$\Sigma ^0_2$
game with no witnessed winning strategy in
$L_\delta $
. This is an immediate consequence of Solovay’s bound together with the following observation.
Lemma 21. Suppose that
$(\tau , \phi , p) \in L_\delta $
is a witnessed winning strategy for a
$\Sigma ^0_2$
game defined by
$\psi $
. Then, there is a witnessed winning strategy
$(\bar \tau , \phi , \bar p)$
for the same game in
$L_{\sigma }$
.
Proof. By [Reference Aguilera2, Proposition 15], we have
$L_\sigma \prec _{\Sigma _1} L_\delta $
, so if
$(\tau , \phi , p) \in L_\delta $
were as in the statement of the lemma, we would have
$L_\sigma \models \exists x\, \exists y\, \phi (x,y)$
. Letting
$\bar \tau , \bar p \in L_\sigma $
be so that
$L_\sigma \models \phi (\bar p,\bar \tau )$
, then
$(\bar \tau , \phi , \bar p)$
are as desired.
This completes the proof of Theorem 7. Let us finish with the observation that the restriction to witnessed winning strategies is crucial for Lemma 21.
Proposition 22 (Tanaka [Reference Tanaka21]).
There is a
$\Sigma ^0_2$
game for which Player II has a winning strategy in
$L_{\sigma +1}$
but not one in
$L_{\sigma }$
.
Tanaka’s example is essentially that Player II must play something that looks like a complete
$\Sigma ^1_1$
inductive set. We have chosen to give an example which is similar but not identical; namely, Player II must play a model of “
$V = L_\sigma $
”. Tanaka’s priority notwithstanding, we are doing this for the following reasons. To help keep this paper self-contained, we would want to give the details of the construction. If we’re going to give the details anyway, we may as well give a variant of the game, in case having this alternative in the literature turns out to be useful some day. Finally, we find it more intuitive, more natural, to think in terms of building models of initial segments of L; it also generalizes more readily to other settings, like other complexity classes.
Proof. Consider the game in which, to be brief, II must play a (term) model (
$\omega $
-standard) of
$"V = L_\sigma ,"$
and I’s goal is to show that it is not the correct model.
The requirements on Player II: II must ultimately produce a term model M of
$"V = L$
, KP, and
$\sigma $
does not exist,” and the full
$\Sigma _1$
theory of M (which we take to include the true
$\Pi _1$
statements too). The rules can enforce that M be
$\omega $
-standard by, say, forcing that
$\omega ^M$
consist of the evens in their natural order. The particular syntax that II has to use to name sets does not matter, so we will describe only how the (transfinite) ordinals are to be named. If an ordinal
$\alpha $
is neither admissible nor a limit of admissibles, then let
$\beta $
be the supremum of the admissibles less than
$\alpha $
. Notice that by assumption
$\beta < \alpha < \beta ^+$
. In this case,
$\alpha $
is the order-type of a
$\beta $
-recursive ordering. (As a reminder, this is not true for all ordinals
$\alpha $
: namely, the supremum of the admissibles less than
$\delta $
is
$\sigma $
, but there is no
$\sigma $
-recursive ordering of type
$\delta $
. The point here is that
$\delta $
and
$\sigma $
form the least such counter-example, so there can be no such example in a structure purported to model
$V = L_\sigma $
.) Then the definition of this ordering, along with
$\beta $
, serves as a name for
$\alpha $
. The other case is that
$\alpha $
is either admissible or a limit of admissibles. Since II is to build a model in which
$\alpha < \sigma $
,
$\alpha $
is not
$\Sigma ^1_1$
reflecting. Then the
$\Sigma ^1_1$
assertion which does not reflect can be taken as the name of
$\alpha $
.
The other requirement of II is that I is allowed to ask a question of II during I’s play of the game, a question of the form “is this particular sentence true in M,” and II must answer that question promptly. We cannot allow that I win the game by constantly asking II questions, so that II never gets to build their model, so II may interleave steps in building the model with steps answering I’s questions. For instance, we could require II to build M at the even steps and to answer I’s questions, in the order in which they were posed, at the odd. Furthermore, M must be consistent with their answers to I’s questions. That is, II’s answers can be taken to be part of the diagram of M.
The requirements on Player I: It is I’s task to show, if possible, that II’s model is not the right one. It will be clear that II can win this game by telling the truth, playing the
$\Sigma _1$
theory of the true
$L_\sigma $
. This strategy for II is
$\Delta _2$
definable over
$L_\sigma $
. The role of I is to keep II honest, so that this is effectively II’s best strategy, thereby preventing a winning strategy from showing up before
$\sigma $
.
To describe the rules for Player I, let’s think through how they can strategize. They can assume that M will be a model of “
$V = L$
” regardless of what they do (because, if not, I wins automatically). For sure M depends on what I does, but I can still examine what the options are for what M will ultimately be. What I does depends very much on the ordinal standard part of M, osp M. Note that M could be either standard or non-standard; if the former, then osp M is just the ordinal height of M.
Case I: osp
$M> \sigma $
: Since osp M is an admissible ordinal, M would contain all of
$L_{\sigma ^+}$
, and therefore not model “
$\sigma $
does not exist”, leading I to win the game automatically.
Case II: osp
$M = \sigma $
: If M is standard, i.e.,
$M = L_\sigma $
, then II wins and there is nothing I can do. As it turns out, there will be ways for II to win by playing non-standard models with osp
$\sigma $
, as we will see later. Although this is not the intent of the game, this actually will not bother us, because II still needs access to
$L_\sigma $
to play such a strategy.
Case III: osp
$M < \sigma $
: By way of notation, let osp M be
$\alpha $
. Then I can demonstrate that M is not
$L_\sigma $
by playing
$L_{\alpha ^+}$
, noting that
$L_\alpha $
is an initial segment of M but not a member of M, and witnessing that
$\alpha < \sigma $
by producing a
$\Sigma ^1_1$
statement
$\psi $
which is true of
$L_\alpha $
, as witnessed definably over
$L_{\alpha ^+}$
, yet does not reflect. Player I is to build a model using the same naming conventions as Player II. To build a model of “
$V = L_{\alpha ^+}$
for some
$\alpha $
” is straightforward, as is witnessing
$\alpha < \sigma $
by checking that
$\psi $
works as described. To show that
$L_\alpha $
is an initial segment of M, every time I makes a
$\Delta _0$
statement about
$L_\alpha $
they are to ask II whether that statement is true of M. Showing that
$L_\alpha $
is not a member of M breaks up into several cases.
Subcase a):
$\psi $
does not name an ordinal in M. I can demonstrate that this is so by asking II whether
$\psi $
names an ordinal in M and receiving the answer “no”. Note that this includes the case when M is standard, i.e., for
$M = L_\alpha $
.
Subcase b):
$\psi $
does name an ordinal in M, and
$\alpha $
is not recursively inaccessible. The challenge here is that there is a least non-standard admissible ordinal, and that ordinal could be named by
$\psi $
. That makes M look a lot like the standard universe. But in this case,
$\alpha = \beta ^+$
for some
$\beta $
which is either admissible or a limit of admissibles. Then some
$\beta $
-recursive ordering will represent a non-standard ordinal. Player I could win by witnessing that M is non-standard by listing an infinite descending sequence through this ordering.
Subcase c):
$\psi $
does name an ordinal in M, and
$\alpha $
is recursively inaccessible. Then there will be no least non-standard admissible ordinal. (If
$\gamma $
were the least non-standard admissible ordinal, then the supremum of the admissible ordinals less than
$\gamma $
would define
$\alpha $
in M.) Let
$\beta $
be the M-ordinal named by
$\psi $
, which must be non-standard. Then let
$\chi $
be a
$\Sigma ^1_1$
statement naming a non-standard admissible ordinal less than
$\beta $
. In the real universe V,
$\chi $
does not name any ordinal less than
$\alpha $
. Hence I can witness that
$L_\alpha $
is not in M by noting that in I’s model
$\psi $
names
$\alpha $
and
$\chi $
names nothing less than
$\alpha $
, and that in M
$\psi $
names
$\beta $
and
$\chi $
names an ordinal less than
$\beta $
.
By way of enabling I to do this kind of witnessing regarding M, the rules for I are as follows. Identify
$\omega $
with
$\omega \times \omega $
. On I’s nth turn, where
$n = \langle i,j \rangle $
, I makes the jth move on the ith slice of
$\omega $
. At the beginning of a slice, I must announce either that they are building an infinite descending sequence through a linear order given by a
$\Delta _1$
definition
$\psi $
over an ordinal
$\beta $
, or they are building a model of
$V = L_{\alpha ^+}$
in which some
$\Sigma ^1_1$
formula
$\psi $
names
$\alpha $
. In the former case, on the 2jth move of the slice (
$j> 0$
), I must play an ordinal
$\beta _j < \beta $
, and on the (2
$j\#Z$
+1)th move I must ask II whether
$\beta _j <_\psi \beta _{j-1}$
. In the latter case, on the even moves I must build their model according to some fixed scheme, like on the 2jth move I must decide on the statement (with parameters) coded by j, so that I cannot indefinitely postpone a decision, and on the odd moves I must ask II whether the last
$\Delta _0$
statement I made about
$L_\alpha $
is true in M.
The complexity of the game: Player I wins if there is a slice on which one of two things happens. One possibility is that I has announced that this slice is an infinite descending sequence, and there is a step by which II has stated that
$\beta $
as named by I is indeed an ordinal and the
$\beta $
-recursive ordering named by
$\psi $
also gives an ordinal, and every time I has asked II whether
$\beta _j <_\psi \beta _{j-1}$
II has said yes. The other possibility is that I has announced they are building a model of
$V = L_{\alpha ^+}$
, where
$\psi $
names
$\alpha $
, and there is a step by which II has said
$\psi $
does not name an ordinal, or II has said some
$\chi $
names an ordinal less than
$\psi $
’s and I has said there is no ordinal less than
$\psi $
’s named by
$\chi $
, and every time I has asked II whether an assertion is true of M, II has answered yes. It is easy to see these winnings conditions are
$\Sigma ^0_2$
.
How Player II can win: If I wins a play of the game the first way, then I has built an infinite descending sequence through II’s ordinals, witnessing that M is ill-founded. If I wins a play the second way, then I has determined an initial segment
$L_\alpha $
of M such that
$\alpha $
itself is not in M; if
$\alpha $
is a standard ordinal then I’s model witnesses that
$\alpha < \sigma $
, and if
$\alpha $
is non-standard then, since
$L_\alpha $
is an initial segment of M, M is non-standard. It follows directly that II can prevent I from winning by playing the true
$L_\sigma $
; in other words, this is a winning strategy for II, and easily seen to be
$\Delta _2$
definable over
$L_\sigma $
. (It also follows easily that the only way II can win is by playing a model with ordinal standard part
$\sigma $
. We describe below why there are winning strategies for II which play non-standard models.)
All we have left to show is that II has no winning strategy in
$L_\sigma $
. Suppose II plays with a strategy
$\tau \in L_\sigma $
. It will suffice to show how I can win.
Let
$\gamma < \sigma $
be the supremum of the admissible ordinals which are at most the L-rank of
$\tau $
. Note that
$\gamma $
is either admissible or a limit of admissibles, and that
$\tau \in L_{\gamma ^+}$
. If in response to player I doing nothing,
$\tau $
would do anything other than play the
$\Sigma _1$
theory of a model of
$V = L + KP$
then I can win by doing nothing. So we can now assume that
$\tau $
plays such a model N when I does nothing. (Note that N is fixed, as opposed to M, which could depend on I’s moves.) For reasons of complexity,
$N \in L_{\gamma ^+}$
. Hence osp
$N \leq \gamma $
. Let
$\phi $
name osp N. As described above, either
$\phi $
does not name any ordinal in N, or there is a
$\chi $
which names an ordinal smaller than the ordinal named by
$\phi $
in N (even though in the real world
$\chi $
does not name any ordinal smaller than osp N). Each of those possibilities is in the
$\Sigma _1$
theory II is playing, so II must assert one at some point. When they do so, this then constrains any model II ultimately builds to have ordinal standard part at most osp N, even if
$M \not = N$
.
At this point, Player I can win, as follows. For each admissible or limit thereof
$\beta <$
osp N, and each
$\beta $
-recursive ill-founded linear order
$\psi $
, I lists an infinite descending sequence through
$\psi $
on one of the slices of
$\omega $
(on the even moves, to be precise, and on the odd moves asks II whether each entry on the sequence is correct). Also, for each admissible or limit thereof
$\beta \leq \gamma $
, and name
$\psi $
of
$\beta $
, and optionally each
$\Sigma ^1_1(L_\beta )$
statement
$\chi $
which names nothing in
$L_{\beta }$
, on some slice of
$\omega $
I acts as though
$\beta $
is the ordinal standard part of M, as follows. On the even moves, I plays
$L_{\beta ^+}$
, and asserts that, in M, either
$\psi $
names nothing or
$\chi $
names an ordinal smaller than
$\psi $
’s. On the odd moves, I checks out that
$L_\beta $
is indeed an initial segment of M by asking II all possible
$\Delta _0$
questions about it. Since II is constrained to play a model with ordinal standard part at most osp N, one of I’s attempts (i.e., one of the slices of
$\omega $
) must succeed.
We mentioned that Player II has a winning strategy which plays a non-standard model. That can be seen as follows. Consider a variant of this game in which II must play a model of
$V = L_{\sigma ^+}$
. II has a winning strategy: tell the truth. Hence II has a winning strategy definable over
$L_\delta $
. But this strategy cannot tell the truth! (Lest reals of L-rank greater than
$\delta $
end up definable over
$L_\delta $
.) Therefore the restriction of this strategy to play only the
$\Sigma _1$
theory of (its version of)
$L_\sigma $
is a winning strategy for the original game. This sets the stage for several questions. For instance, for the game of Proposition 22, “play the true
$L_\sigma $
” is a winning strategy for Player II. Is that the L-least winning strategy? The strategy of playing the true
$L_\sigma $
is
$\Delta _2$
; is there a winning strategy of less definitional complexity? Perhaps there are Barwise-style model-theoretic methods which need only a
$\Pi _1$
consistency check to succeed.
Note that, the way this game was set up, II has a sure win by playing any model of the theory with ordinal standard part
$\sigma $
. This includes playing a fixed such model, of which some are definable over
$L_\sigma $
. Consider in contrast the variant of the game in which we give Player I an additional tool, namely to win by listing any infinite descending sequence through II’s ordinals. Then II could not guarantee a win by playing any fixed model. One could then ask the same questions as above about this variant. Moreover, it’s not even obvious whether there are any winning strategies in all of
$L_\delta $
other than playing the true
$L_\sigma $
. Are there any other winning conditions we could reasonably give to Player I?
The example above is of a game with least winning strategy definable over, but not in,
$L_\sigma $
, even though on general principles any witness that it’s winning is at best definable over
$L_\delta $
, so we have:
Question 23. Does every
$\Sigma ^0_2$
game have a winning strategy in
$L_\delta $
?
One of the authors conjectures the answer goes is “yes,” and the other that it is “no.” A more general question is: for which
$\alpha $
is it the case that a winning strategy for a
$\Sigma ^0_2$
game is first definable over
$L_\alpha $
?
Funding
The first author was partially supported by FWO grant 3E017319 and FWF grant P36837.
