The metamathematics of separated determinacy

Introduction for non-logicians

One of the major themes in Mathematical Logic is the distinction between a mathematical statement being true, and it being provable. One is typically interested in both, and the latter naturally implies the former. In order to clarify what a theorem is, it is necessary to specify a set of rules for what constitutes a proof. For our purposes, we can think of these rules simply as a collection of axioms, called a theory. Thus, different theories lead to different notions of what a proof is, and hence of what a theorem is. Examples of theories are Zermelo-Fraenkel set theory with the Axiom of Choice (\({ \mathsf{ZFC}}\)) or Peano Arithmetic (\(\mathsf{PA}\)).

In Reverse Mathematics, one is typically interested in considering specific mathematical theorems \(\phi \) and understanding precisely which axioms are necessary to prove \(\phi \). Given a proof from the right axioms, one often finds the theorem to be equivalent to these. For example, the Bolzano-Weierstraß theorem and the infinite Ramsey theorem on ℕ are both equivalent to the axiomatic system of Arithmetical Comprehension (\({ \mathsf{ACA_{0}}}\)), which carries the same proof-theoretic strength as \(\mathsf{PA}\). Thus we see unexpectedly that common theorems from combinatorics and analysis share the same strength as the principle of mathematical induction. These strict and formal logical equivalences do not always match up with our natural intuitions on theorems being “equivalent,” as the examples above show; in the opposite direction, we have that e.g., Brouwer’s fixed-point theorem is not logically equivalent to Sperner’s lemma (see Simpson [78]) even though one might informally expect it to be, and Caristi’s fixed-point theorem is not equivalent to Ekeland’s variational principle (see Fernández-Duque, Shafer and Yokoyama [25]; Fernández-Duque, Shafer, Townser, and Yokoyama [26]).

An early observation due to Friedman [30] is that a great deal of theorems from everyday mathematics are equivalent to one of five axiomatic systems, denoted by \({\mathsf{RCA_{0}}}\) (essentially computational mathematics), \(\mathsf{WKL}_{0}\) (König’s tree lemma for binary trees), \({\mathsf{ACA_{0}}}\), \({\mathsf{ATR_{0}}}\) (transfinite recursion for number-theoretic operators), or \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\) (comprehension for sets definable by universal second-order formulas). It is commonly said that \({\mathsf{ACA_{0}}}\) is powerful enough to prove all theorems required to obtain an undergraduate degree in Mathematics, while \({\mathsf{ATR_{0}}}\) can obtain a degree with relatively good grades, and \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\) is powerful enough to obtain a Master’s degree and possibly a PhD. Beyond \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\) come \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\), \(\boldsymbol {\Pi}^{1}_{3}{-}{\mathsf{CA_{0}}}\), and so on. The union \(\bigcup _{n\in \mathbb{N}}\boldsymbol {\Pi}^{1}_{n}{-}{ \mathsf{CA_{0}}}\) is Hilbert’s Second-Order Arithmetic and is denoted \(Z_{2}\) or \(\boldsymbol {\Pi}^{1}_{\infty}{-}{\mathsf{CA_{0}}}\).

While the so-called “Big Five” systems of Reverse Mathematics suffice to analyze most theorems, we as mathematicians do not usually content ourselves with “most” and tend to be drawn to the exceptional cases, of which many are known nowadays. Notable instances of these exceptions are combinatorial Ramsey-theoretical principles (see e.g., Chong, Slaman, and Yang [20] and subsequent work by Patey and Yokoyama [75] and by Monin and Patey [62], as well as Fiori-Carones, Shafer, and Soldà [27]) and game-theoretic assertions. Reverse Mathematics nowadays is well developed and has at its disposal a long catalog of theories \(T\) which can be used to gauge the strength of theorems \(\phi \). These generally come in one of several flavors. The main kind of theories one considers are obtained via comprehension axioms, asserting that various sets exist. A second kind of theory one considers is given by axioms asserting that the real numbers (or some other set) is closed under a certain kind of computability-theoretic operator. We shall say nothing more about this for now, except that for the range of theories of most relevance to Reverse Mathematics, such axioms can often easily be seen to be equivalent to axioms of the first kind.

A third kind of theory is given by determinacy principles asserting that infinite games of various kinds are determined, in the sense that optimal strategies exist. Determinacy principles have a strange dual nature in that they can be thought of both as theorems and as axioms simultaneously. Several people (including the author) believe that these three strands of theories cover the same range of axiomatic strength, in the sense that none is bounded by any of the others.

Determinacy principles can all be described uniformly in terms of the structure \((\mathcal{P}(\mathbb{R}),\leq _{W})\), where \(\leq _{W}\) is the pre-order of continuous reducibility. Recent work by Day, Greenberg, Harrison-Trainor, and Turetsky [21, 22] shows that this description can be implemented in the context of Reverse Mathematics. In his list of “Open Questions in Reverse Mathematics,” Montalbán [63] posed the problem of a systematic study of determinacy principles and the comprehension axioms to which they correspond. The purpose of this work is to take on such a systematic study, considering every possible determinacy principle up to a certain level of strength and matching it with a theory of one of the other two kinds, thus effectively carrying out a reverse mathematics of these determinacy principles.

The bulk of our work is done by proving a series of three “Separation Reduction” theorems, which can be regarded as a “functional” type of reverse-mathematical analysis: instead of proving an equivalence between a mathematical theorem \(\phi \) and an axiom \(A\), we prove a result of the form “Suppose that \(\phi \) has been shown to be equivalent to \(A\). Then, \(f(\phi )\) is equivalent to \(g(A)\).” These results can be regarded as “higher-type” versions of reverse-mathematical analysis. By instantiating \(\phi \) in various ways (e.g., substituting a trivial statement like \(0 = 0\) for \(\phi \)) we recover many of the reverse-mathematical analyses of determinacy from the literature. The name of the “Separation Reduction” theorems is explained by the fact that they “reduce” the study of a principle of determinacy for separated sets to a simpler determinacy axiom. Although the theorems are stated and proved from the perspective of the weak theory \({\mathsf{RCA_{0}}}\), we shall find applications for these in the context of \({\mathsf{ZFC}}\), leading to strengthenings of classical results from descriptive set theory. We shall see that the hierarchy of determinacy principles is highly non-strictly-monotone (this is called the determinacy transfer phenomenon) and discontinuous in strength. Thus, in the figure below, the picture obtained is closer to that on the right-hand side than that on the left-hand side.

The systems \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\) of \(\boldsymbol {\Pi}^{1}_{n}\)-Comprehension and \(Z_{2} = \boldsymbol {\Pi}^{1}_{\infty}{-}{\mathsf{CA_{0}}}\) of Hilbert’s Second-Order Arithmetic are among the most important theories in Reverse Mathematics. It has long been known by work of Tanaka [81], Heinatsch and Möllerfeld [38], and Montalbán and Shore [66] that \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\), \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\), and \(\boldsymbol {\Pi}^{1}_{\infty}{-}{\mathsf{CA_{0}}}\) are equiconsistent with (i.e., have the same logical strength as) collections (schemata) of determinacy principles. Because of this, the author – and possibly others – had conjectured that all the systems \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\) are also equiconsistent with some schema of determinacy principles. We shall disprove this conjecture for \(2 < n < \infty \).

We now discuss the context of this work in more detail before turning to a summary of the results obtained. The remainder of this introduction, while aimed at audiences with a logical background, should be accessible to a general readership.

1.1 Overview and background

The purpose of this work is to address –for the first time in a systematic and exhaustive manner – three families of problems concerning infinite games with payoff in classes \(\boldsymbol {\Gamma}\subset \mathcal{P}(\mathbb{R})\) of low Borel complexity:

1. (1)

   What is the logical strength of \(\boldsymbol {\Gamma}\)-Determinacy?

2. (2)

   What is the optimal Turing degree of winning strategies for games in \(\boldsymbol {\Gamma}\), at least for one of the players?

3. (3)

   How can one describe the pointclass \(\Game \boldsymbol {\Gamma}\subset \mathcal{P}(\mathbb{R})\)?

The first question is of concern to Reverse Mathematics; the second, to Recursion Theory; and the third, to Descriptive Set Theory. Nonetheless, an answer to any one of these three questions must necessarily include an answer to the other two, at least partially. Let us explain why this is the case after introducing the relevant terminology.

Let \(A \subset \mathbb{N}^{\mathbb{N}}\) be a set of infinite sequences of natural numbers (henceforth called reals and identified with elements of ℝ). The Gale-Stewart game \(G(A)\) on \(A\) is played as follows [31]: Players I and II alternate infinitely many turns playing numbers \(x_{i}\), eventually producing a sequence \(x \in \mathbb{N}^{\mathbb{N}}\) (see Fig. 1). Player I wins if and only if \(x \in A\); otherwise, Player II wins. The game \(G(A)\) is said to be determined if one of the players has a winning strategy, where the notions of a winning strategy for Player I and for Player II are defined the natural way, as functions from finite tuples of integers to integers.

The celebrated Borel Determinacy Theorem of Martin [56] asserts that \(G(A)\) is determined whenever \(A\) is a Borel set. Four years before Martin’s theorem was proved, Friedman [29] had shown that Borel Determinacy cannot be proved without making crucial use of all the axioms of \({\mathsf{ZF}}\). More precisely, Borel Determinacy is not provable in Zermelo set theory with the Axiom of Choice, \(\mathsf{ZC}\), nor in \({\mathsf{ZFC}}^{-}\), \({\mathsf{ZFC}}\) without the Powerset axiom. By Martin’s theorem, it is provable in \({\mathsf{ZFC}}\). Sets of complexity higher than Borel can also be proved to be determined, but this requires going beyond the axioms of \({\mathsf{ZFC}}\) and making use of large infinite sets, e.g., by Harrington [37]. In particular, if one assumes the existence of large cardinals, one can prove that all projective sets are determined (see Martin-Steel [59]) and even obtain the consistency of the assertion that all sets are determined (see Woodin [88]), though this requires forfeiting the Axiom of Choice. Such determinacy assertions have useful consequences on the structure of the real line; we refer the reader to Kanamori [41] or Larson [50] for an overview of the area. Recently, Borel determinacy has found applications in Borel combinatorics (see Marks [54]) and the study of continuous randomness (see Reimann-Slaman [76]).

Friedman’s and Martin’s work showed that the dependence of determinacy principles on the axioms is gradual, in the sense that stronger axioms are needed for \(\boldsymbol {\Gamma}{-}\)Determinacy as \(\boldsymbol {\Gamma}\) increases in complexity along the Borel hierarchy. This can be made precise in the sense of Reverse Mathematics (see Friedman [30] for an introduction to Reverse Mathematics). In particular, Martin (unpublished) showed that \(\boldsymbol {\Sigma}^{0}_{4}{-}\) (i.e., \(F_{\sigma \delta \sigma \delta}{-}\))Determinacy is not provable in Hilbert’s Second-Order Arithmetic \((Z_{2})\). More precisely, over a sufficiently weak axiomatic system, such as Recursive Comprehension \(({\mathsf{RCA_{0}}})\), one can prove the equivalence between determinacy principle and set-existence axioms of various kinds. Thus, one not only determines which axioms are sufficient for proofs of determinacy, but also which are necessary.

These proofs usually proceed by first presenting a proof of determinacy from the optimal hypotheses, which generally assert that certain complicated sets of integers exist, and follow by exhibiting a specific game any winning strategy \(\sigma \) for which must have high enough Turing degree that the existence of the complicated sets follows from that of \(\sigma \). It is this way that the solutions to the reverse-mathematical and recursion-theoretic questions are intertwined. In general, these solutions relativize to arbitrary real parameters and thus also lead to descriptive-set-theoretic considerations, such as structural consequences or alternative descriptions of various pointclasses.

Results of this kind are ubiquitous in the literature. An example of this is Steel’s theorem [79] that determinacy for \(\boldsymbol {\Sigma}^{0}_{1}\) (i.e., open) games is equivalent to Arithmetical Transfinite Recursion \(({\mathsf{ATR_{0}}})\). Before that, it was commonly known (perhaps due to Moschovakis) that \(\Sigma ^{0}_{1}\) games had winning strategies recursive in Kleene’s \(\mathcal{O}\), and Blass [16] had observed that this is optimal, in the sense that they generally do not have \(\Delta ^{1}_{1}\) strategies. There is another way in which this complexity result is optimal, and this is given by Svenonious’ theorem that

Equation (1.1) is true not only when regarding \(\Sigma ^{1}_{1}\) as classes of subsets of ℕ but also when regarding them as pointclasses on ℝ or any Polish space. Here, \(\Game \) is the game-quantifier; for more on this, see Definition 56 in §5.1. \(\boldsymbol {\Sigma}^{1}_{1}\) is the class of analytic sets, the projections of Borel sets from the plane into the real line. One of the consequences of working with \(\mathbb{N}^{\mathbb{N}}\) instead of (the literal) ℝ is that analytic sets can all be obtained as projections of closed sets. Svenonious’ theorem asserts that this fact remains unchanged if we replace the usual projection operator by a one that is significantly more restrictive. A third equivalence is given by the Barwise-Gandy-Moschovakis theorem [15], which asserts that \(\Sigma ^{1}_{1}\) subsets of ℕ are precisely those which are \(\Pi _{1}\)-definable over the admissible set \(L_{\omega _{1}^{ck}}\). As a consequence, we have

This equation extends as well to a description of the pointclass \(\Game \Sigma ^{0}_{1}\): a set \(A\subset \mathbb{R}\) is \(\Game \Sigma ^{0}_{1}\) if and only if there exists a \(\Sigma _{1}\)-formula \(\phi \) such that

This type of equivalence has analogs for other complexity classes. Solovay (unpublished) showed that \(\Sigma ^{0}_{2}\) games won by Player I have winning strategies in \(L_{\sigma ^{1}_{1}}\), where \(\sigma ^{1}_{1}\) is the least \(\Sigma ^{1}_{1}\)-reflecting ordinal, and \(L_{\alpha}\) denotes the \(\alpha \)th level of Gödel’s constructible hierarchy. The author and Lubarsky have shown (unpublished) that \(\Sigma ^{0}_{2}\) games won by Player II have winning strategies \(\Delta _{1}\)-definable over \(L_{\delta _{\sigma ^{1}_{1}}}\), where \(\delta _{\sigma ^{1}_{1}}\) is the supremum of order-types of wellorderings of \(\sigma ^{1}_{1}\) which are \(\Sigma _{1}\)-definable over \(L_{\sigma ^{1}_{1}}\) (note that this ordinal is inadmissible; see Gostanian [32]). Thus, \(\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy is equivalent to the existence of arbitrarily large \(\Sigma ^{1}_{1}\)-reflecting ordinals. Tanaka [82] has shown that \(\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy is equivalent to \(\boldsymbol {\Sigma}^{1}_{1}{-}{\mathsf{MI}}\), the principle of \(\boldsymbol {\Sigma}^{1}_{1}{-}\)monotone induction, and Solovay’s proof yields the analog of (1.2) for \(\Sigma ^{0}_{2}\):

Note, however, that Solovay’s theorem does not yield the only answer to the equation, since e.g.,

also holds true. Equation (1.4) also extends to a description of the pointclass \(\Game \Sigma ^{0}_{2}\) similar to (1.3): a set \(A\subset \mathbb{R}\) is \(\Game \Sigma ^{0}_{2}\) if and only if there is a \(\Sigma _{1}\)-formula \(\phi \) such that:

where \(\sigma ^{1}_{1}(x)\) denotes the least ordinal which is \(\Sigma ^{1}_{1}\)-reflecting in the \(L[x]\)-hierarchy.

Welch [84, 85] has explored the analogs of (1.2) and (1.4) for \(\Sigma ^{0}_{3}\) and identified the range of ordinals \(\beta \) such that

These ordinals \(\beta \) can be described in terms of a certain reflection structure in illfounded models called a \(\Sigma _{2}\)-nesting, and Welch’s proof shows that \(\boldsymbol {\Sigma}^{0}_{3}\)-Determinacy is equivalent to the existence of arbitrarily large ordinals which admit \(\Sigma _{2}\)-nestings. Hachtman [36] has given an alternative characterization of \(\boldsymbol {\Sigma}^{0}_{3}\)-Determinacy in terms of the existence of \(\beta \)-models of \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\). Once more, these results extend to descriptions of the pointclass \(\Game \Sigma ^{0}_{3}\) in the same spirit as (1.3) and (1.5).

Motivated by (1.2), (1.4), and (1.6), we feel compelled to pursue a general study of determinacy axioms in Second-Order Arithmetic, identifying the subsystems of \(Z_{2}\) needed for proofs of determinacy, the optimal Turing degrees of winning strategies, and the subsets of Polish spaces definable in terms of the game quantifier. Whether such a study could be carried out was posed as a question by Montalbán [63].

Towards a more precise statement of our goal, let us recall some aspects of the Wadge theory of relative complexity of subsets of ℝ. Given sets of reals \(A\) and \(B\), we write \(A \leq _{W} B\) if there is a continuous function \(f:\mathbb{R}\to \mathbb{R}\) such that \(f[A]\subset B\) (where \(f[A]\) denotes the image of \(A\) under \(f\)). Such an \(f\) is a continuous reduction of \(A\) into \(B\). Wadge [83] showed that the relation \(\leq _{W}\) is a wellfounded semi-linear order on \(\mathcal{P}(\mathbb{R})\) when restricted to Borel sets. This means that all antichains in \(\leq _{W}\) have cardinality at most 2. In fact, identifying sets in \(\mathcal{P}(\mathbb{R})\) with their equivalence classes induced by \(\leq _{W}\), nontrivial antichains in \(\leq _{W}\) must consist of a set \(A\) and its complement \(\bar{A}\).

Since \(\leq _{W}\) is wellfounded, it yields a useful hierarchy of complexity for Borel sets by stratifying them into Wadge classes, subsets of \(\mathcal{P}(\mathbb{R})\) closed under continuous preimages. Classification theorems of Louveau [51] and of Louveau and Saint-Raymond [52] yield concrete and complete descriptions of what these classes look like. Recent work of Day, Greenberg, Harrison-Trainor, and Turetsky [21, 22] shows that Wadge, Louveau, and Saint-Raymond’s work on the structure of \(\leq _{W}\) can be carried out within a weak subsystem of \(Z_{2}\), and in particular that the semi-linear ordering principle for Borel sets is provable in \({\mathsf{ATR_{0}}}+ \boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{IND}}\). One of the main ideas behind the work of [21, 22] is that some of the classical methods used in the study of Borel sets can be replaced by Montalbán’s “true stage” machinery (see [64, 65]), thus leading to the study of Wadge classes via iterated priority arguments and therefore to proofs of the results of [52] from weak hypotheses. The relevance of this work for our purposes is that it makes sense to consider determinacy principles for all the Borel Wadge classes from the perspective of Reverse Mathematics.

Beyond Borel sets, the order \(\leq _{W}\) is also semilinear and wellfounded if one assumes enough determinacy and Dependent Choice. Indeed, under \({\mathsf{DC}}_{\mathbb{R}}\) and category assumptions, Martin showed that \(\leq _{W}\) is wellfounded if it is semilinear. The need for \({\mathsf{DC}}_{\mathbb{R}}\) stems from the various possible definitions of “wellfoundedness” in \({\mathsf{ZF}}\), but this distinction disappears when working in theories in the language of Second-Order Arithmetic. Since all Borel sets have the Baire property, it follows from this and the result of [21] quoted above that \(\leq _{W}\) is wellfounded when restricted to Borel sets, provably in relatively weak theories such as \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\).

Thus, our question: given a Wadge class \(\boldsymbol {\Gamma}\), we ask: what is the reverse-mathematical strength of \(\boldsymbol {\Gamma}\)-Determinacy? In this work, we develop the machinery to answer this question for a large collection of such \(\boldsymbol {\Gamma}\) and, over the weak theory \({\mathsf{RCA_{0}}}\), give an explicit answer for all \(\boldsymbol {\Gamma}\) with Wadge rank

These are precisely the Wadge classes for which determinacy is weaker than \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \Pi ^{1}_{4}{-}{ \mathsf{CA_{0}}}\) in terms of consistency strength.^{Footnote 1} In answering this question, we will inevitably also obtain answers to the other two questions phrased at the beginning, as well as analogs of equations (1.2), (1.3), (1.2), (1.5), and (1.6).

Before discussing the contents of this work, let us recall some further history and relevant literature. Systems of determinacy between \(\boldsymbol {\Sigma}^{0}_{1}\) and \(\boldsymbol {\Sigma}^{0}_{2}\) have been studied by Tanaka [81]. These systems are defined in terms of the Hausdorff difference hierarchy \(\alpha{-}\boldsymbol {\Sigma}^{0}_{1}\). Wadge’s work shows that the Hausdorff classes are the only non-selfdual Wadge classes below \(\boldsymbol {\Sigma}^{0}_{2}\). Nemoto, MedSalem, and Tanaka [73] study games in this region but with moves restricted to \(\{0,1\}\), and their connections with games on integers. Nemoto [72] studies weaker games also with moves restricted to \(\{0,1\}\). MedSalem and Tanaka [60, 61] have studied the strength of determinacy for sets at levels of the difference hierarchy over \(\boldsymbol {\Sigma}^{0}_{2}\). Work by Kołodziejczyk and Michalewski [47] and by Yokoyama and Pacheco [74] sheds light on the limit levels of this difference hierarchy. The difference hierarchy was introduced by Kuratowski [49] in order to generalize Hausdorff’s theorem. Heinatsch and Möllerfeld [38] studied the finite levels of the difference hierarchy and its connections with \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\). Montalbán and Shore [66, 67] study the difference hierarchy over \(\boldsymbol {\Sigma}^{0}_{3}\) and give bounds on its strength. The author and Welch [11] have subsequently refined these results towards very narrow bounds on the strength of \(n{-}\boldsymbol {\Sigma}^{0}_{3}{-}\)Determinacy. The work of [11] suggests that for all the Wadge classes \(\boldsymbol {\Gamma}\) such that \(\boldsymbol {\Gamma}{-}\)Determinacy is provable in \(Z_{2}\) and which are not considered here, \(\boldsymbol {\Gamma}{-}\)Determinacy is not equivalent to any “natural” subsystem of \(Z_{2}\) (not phrased in terms of other determinacy principles).

1.2 Summary of results

The main contribution of this work is given in the form of three Separation Reduction Theorems. These results allow us to transform a reverse-mathematical analysis of \(\boldsymbol {\Gamma}\)-Determinacy into one of \(\boldsymbol {\Gamma}'\)-Determinacy, where \(\boldsymbol {\Gamma}'\) is strictly larger than \(\boldsymbol {\Gamma}\). Each of these theorems is aimed at a different type of classes \(\boldsymbol {\Gamma}'\), and combining them in the right order results in the complete study of Wadge classes below \(\omega _{1}^{\omega _{1}\cdot \omega _{1}}\). The name of these theorems comes from the fact that they are typically applied to Wadge classes \(\boldsymbol {\Gamma}\) described in terms of separation of one kind or another.

In order to describe the classes we study, we rely on the classification theorems of Louveau [51] and of Louveau and Saint-Raymond [52], which in turn build on the work of Wadge [83]. The key tool to describing Wadge classes is the notion of separation. Hausdorff introduced his hierarchy of differences of closed sets \(\alpha{-}\boldsymbol {\Pi}^{0}_{1}\) in order to characterize the class \(\boldsymbol {\Delta}^{0}_{2}\) of sets which are both \(F_{\sigma}\) and \(G_{\delta}\).^{Footnote 2} This characterization is exhaustive, in the sense that every non-selfdual Wadge class below \(\boldsymbol {\Delta}^{0}_{2}\) is of the form \(\alpha{-}\boldsymbol {\Pi}^{0}_{1}\) for some \(0\leq \alpha <\omega _{1}\). Generalizing Hausdorff’s work, Kuratowski proved that for all countable ordinals \(\xi \), we have

However, this classification is no longer exhaustive, in the sense that there are uncountably many Wadge classes between \(1{-}\boldsymbol {\Pi}^{0}_{\xi}\) (\(=\boldsymbol {\Pi}^{0}_{\xi}\)) and \(2{-}\boldsymbol {\Pi}^{0}_{\xi}\) (\(= \boldsymbol {\Pi}^{0}_{\xi} \setminus \boldsymbol {\Pi}^{0}_{\xi }= \boldsymbol {\Pi}^{0}_{\xi} \wedge \boldsymbol {\Sigma}^{0}_{\xi}\)) in general. This is where the notion of separation comes in: the idea is that the two \(\boldsymbol {\Pi}^{0}_{\xi}\) sets \(A_{0}\), \(A_{1}\) might be too close together, making it very hard to determine whether a real \(x\) belongs to their difference \(A = A_{0}\setminus A_{1}\). If we assume that \(A_{0}\) and \(A_{1}\) are separated by some simpler set (e.g., an open set), then the difference will have strictly lower complexity. Similar principles can be applied to describe infinite unions or infinite differences of sets separated by simpler sets, and Louveau [51] has shown that these separated combinations of sets exhaust all Borel Wadge classes.

Unlike earlier work on the Reverse Mathematics of systems of Borel Determinacy, our results are phrased in as general terms as possible, and most of our results apply to Wadge classes of arbitrary complexity. Thus, we obtain new theorems about weak theories, such as \({\mathsf{RCA_{0}}}\), which lead to new facts about the strength of determinacy principles in the contexts of \(Z_{2}\) or of \({\mathsf{ZFC}}\) or extensions thereof.

1.2.1 The separation reduction theorems

Behind each of the three Separation Reduction Theorems is a new conceptual contribution. The first one deals with the notion of Strategic Replacement. This is a very slight strengthening of determinacy which asserts that countable sequences of games can be mapped to winning strategies for them. Over theories such as \({\mathsf{KP}}\) one can prove that \(\boldsymbol {\Gamma}\)-Determinacy implies \(\boldsymbol {\Gamma}\)-Strategic Replacement, but this fact is not provable in \({\mathsf{RCA_{0}}}\) or even in \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\). It turns out that in many ways this strengthening of determinacy is much easier to manipulate. The First Separation Reduction Theorem (Theorem 40 in §4.1) is a Strategic Replacement Transfer theorem of the form

where \(\boldsymbol {\Gamma}^{*}\) is a larger class than \(\boldsymbol {\Gamma}\). This theorem is powerful in the sense that it can be applied to large classes, such as \(\boldsymbol {\Gamma}=\) all projective sets, but also to small classes such as \(\boldsymbol {\Gamma}= \boldsymbol {\Sigma}^{0}_{2}\). Iterative applications of the First Separation Reduction Theorem show the following interesting fact: even though there are \(\omega _{1}^{\omega _{1}}\)-many Wadge classes below \(\boldsymbol {\Delta}^{0}_{3}\), the only nontrivial classes from the point of (boldface) determinacy are \(\boldsymbol {\Sigma}^{0}_{1}\) and those of the form \(\alpha{-}\boldsymbol {\Sigma}^{0}_{2}\), at least when analyzing them relative to theories which extend \({\mathsf{KP}}\).

The Second Separation Reduction Theorem (Theorem 69 in §5.1) deals with game-quantified monotone-induction, i.e., principles of monotone induction for operators of complexity \(\Game \boldsymbol {\Gamma}\), as well as the related notion of \(\Game \boldsymbol {\Gamma}\)-Comprehension. While one application of \(\Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}\) is generally weak, inductive applications of it are enough to yield determinacy principles. The Second Separation Reduction Theorem reverses, in the sense that the determinacy principles it yields in turn imply the existence of inductive fixpoints for the corresponding monotone operators.

The Third Separation Reduction Theorem is different from the other two in, while its first part applies generally to Wadge classes \(\boldsymbol {\Gamma}\), its hypothesis depends on the definability of elements of \(\boldsymbol {\Gamma}\). Moreover, its second part applies only to the Wadge classes of interest to us for the applications we have in mind. Part I of the Third Separation Reduction Theorem (Theorem 91 in §6) yields determinacy for some class \(\boldsymbol {\Gamma}^{*}\) from the hypothesis that there exist \(\beta \)-models of \(\boldsymbol {\Gamma}\)-Determinacy satisfying enough monotone induction, for a certain \(\boldsymbol {\Gamma}\prec \boldsymbol {\Gamma}^{*}\). Part II (Theorem 94 in §6) in turn provides these models for certain Wadge classes, namely, for the separation hierarchy over \(\boldsymbol {\Sigma}^{0}_{3}\). These models, called \(\alpha \)-suitable models are defined in terms of certain iterated illfounded extensions called \(\Sigma _{2}\)-nestings. We shall see that the existence of \(\alpha \)-suitable models is equivalent to determinacy principles stronger than \(\boldsymbol {\Sigma}^{0}_{3}\)-Determinacy.

1.2.2 Reverse mathematics of determinacy

As mentioned earlier, our main application of the three Separation Reduction Theorems is a complete analysis of the systems of determinacy for Wadge classes \(\boldsymbol {\Gamma}\) of rank smaller than \(\omega _{1}^{\omega _{1}\cdot \omega _{1}}\). These are precisely the determinacy principles weaker than \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \Pi ^{1}_{4}{-}{ \mathsf{CA_{0}}}\) (here and throughout, a “determinacy principle” is an assertion of \(\boldsymbol {\Gamma}\)-Determinacy for some Wadge class \(\boldsymbol {\Gamma}\)). For each Wadge class \(\boldsymbol {\Gamma}\) of rank \(o(\boldsymbol {\Gamma}) < \omega _{1}^{\omega _{1}\cdot \omega _{1}}\) with an effective description and such that “\(\boldsymbol {\Gamma}\) is a Wadge class” is provable in, say, \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \Pi ^{1}_{4}{-}{ \mathsf{CA_{0}}}\), we exhibit a combination of reflection, induction, and comprehension axioms equivalent to \(\boldsymbol {\Gamma}\)-Determinacy. Our methods can be combined with those of [11] to provide upper bounds for all other Wadge classes \(\boldsymbol {\Gamma}\) such that \(\boldsymbol {\Gamma}{-}\)Determinacy is provable in \(Z_{2}\), i.e., those \(\boldsymbol {\Gamma}\) with \(o(\boldsymbol {\Gamma}) < \omega _{1}^{\omega _{1}^{\omega}}\), and the bounds obtained are likely optimal (see §6.5 for more on this). However, new methods are required for the lower bounds of some of these classes.

1.2.3 Transferable and weakly transferable Wadge classes

A Wadge class \(\boldsymbol {\Gamma}\) with an effective description is transferable (respectively, weakly transferable) if \(\boldsymbol {\Gamma}\)-Determinacy is equivalent to \(\boldsymbol {\Gamma}'\)-Determinacy for some fixed \(\boldsymbol {\Gamma}' \prec \boldsymbol {\Gamma}\) in every transitive model of \({\mathsf{KP}}\) (respectively, of \({\mathsf{KP}}\vee {\mathsf{KPl}}\)). The way our exhaustive analysis of determinacy principle is carried out is as follows: we exhibit a collection of Wadge classes. We show that if a Wadge class is not transferable, then it must belong to one of five different types of Wadge classes (see the statement of Theorem 150 in §7.1 for the list), and we carry out direct reverse-mathematical analyses for the classes of each of those five types. Finally, the proofs of transferability can be internalized to \({\mathsf{KP}}\) (in the sense that the equivalences also hold in arbitrary models of \({\mathsf{KP}}\), provided that they agree with the fact that the description of \(\boldsymbol {\Gamma}\) is indeed a description of a Wadge class), thus completing the reverse-mathematical analysis of determinacy principles over \({\mathsf{KP}}\). In particular, we shall see that the only Wadge degrees below \(\boldsymbol {\Delta}^{0}_{3}\) which are non-transferable are \(\boldsymbol {\Delta}^{0}_{1}\) and \(\alpha{-}\boldsymbol {\Sigma}^{0}_{2}\). The proof of this fact proceeds by showing that for each countable \(\alpha \), \({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2}{-}\)Determinacy implies \(\Delta (\alpha{-}\boldsymbol {\Sigma}^{0}_{2}){-}\)Determinacy, and then appealing to the fact that there is no Wadge class between \(\Delta (\alpha{-}\boldsymbol {\Sigma}^{0}_{2})\) and \(\alpha{-}\boldsymbol {\Sigma}^{0}_{2}\) (by Borel Wadge determinacy). This implication is proved by transfinite induction along the Wadge hierarchy in the interval

This is an aspect of the proof which we find amusing, since we do not know of any other example of a theorem proved by transfinite induction along \(\leq _{W}\).

Over \({\mathsf{RCA_{0}}}\), the situation is similar, but slightly more involved, the main cause of this being that \({\mathsf{RCA_{0}}}\) is not strong enough to prove the equivalence between \(\boldsymbol {\Gamma}\)-Determinacy and \(\boldsymbol {\Gamma}\)-Strategic Replacement in general. Here, we must analyze sixteen different types of Wadge classes in order to exhaust all cases (see the statement of Theorem 164 in §7.2 for the list).

The comprehension axioms corresponding to determinacy principles are generally those asserting the closure of ℝ under some type of “jump” operator. In general, \(\boldsymbol {\Gamma}^{*}\)-Determinacy will be equivalent to the closure of ℝ under some iterations of operators

where \(\mathcal{O}_{\vec{\Gamma}}^{x}\) is a generalized kind of hyperjump computing fixpoints of inductive definitions of unions of operators of complexity in the sequence of complexity classes \(\vec{\Gamma}\). These hyperjumps are introduced in Definition 168 and Definition 172 in §7.2.2. According to these definitions, we have

uniformly (where \(\equiv _{1}\) indicates one-one reducibility), so in this sense the operators we introduce generalize the usual hyperjump. Although we do not dwell on these operators and instead simply introduce them briefly in order to characterize the determinacy principles they correspond to, we suspect there is much more to say about them and the corresponding notions of reducibility. In particular, they can easily be used to define “plus” versions of well-studied theories, such as \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) and \((\boldsymbol {\Sigma}^{1}_{1}{-}{\mathsf{MI}})^{+}\) (incidentally, these theories are equivalent to determinacy principles).

These generalized hyperjump operators only come into play when working over the base theory \({\mathsf{RCA_{0}}}\). For readers which are content with working over \({\mathsf{KP}}\), the situation can be simplified greatly, mainly due to the fact that closure under jump operators implies closure under transfinite iterations of these, at least for the kind of operators considered in this work.

1.2.4 Discontinuities and non-strict-monotonicity in the hierarchy of determinacy principles

The hierarchy of comprehension principles enjoys a very “gradual” increase, in the sense that from any given comprehension principle one can easily define one which is “slightly stronger.” The hierarchy of determinacy principles behaves very differently, due to two phenomena: the first one is that of transfer, first noticed directly by Kechris and Woodin [45] in the setting of strong axioms. This is the phenomenon whereby \(\boldsymbol {\Gamma}\)-Determinacy implies \(\boldsymbol {\Gamma}'\)-Determinacy, for some strictly larger \(\boldsymbol {\Gamma}'\). In [45], the phenomenon was observed for Wadge classes with strong enough closure properties. However, as we shall see, the phenomenon happens at every stage of the Wadge hierarchy. Indeed, we shall see that there is no single Wadge degree \(\boldsymbol {\Gamma}\) such that \(\boldsymbol {\Gamma}\)-Determinacy is not equivalent to any other \(\boldsymbol {\Gamma}'\)-Determinacy (once more, we restrict to classes \(\boldsymbol {\Gamma}\) which have an effective description and such that “\(\boldsymbol {\Gamma}\) is a Wadge class” is provable in some suitable theory). This phenomenon is naturally at the core of the notion of “transferability” mentioned earlier.

The second one is discontinuities. Rather than increasing gradually in consistency strength, determinacy principles tend to concentrate on a few comprehension principles and then suddenly grow dramatically. The most striking instance of this is that of \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\). By Tanaka [81], \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\) is equivalent to a determinacy principle, namely: \((\boldsymbol {\Sigma}^{0}_{1}\wedge \boldsymbol {\Pi}^{0}_{1})\)-Determinacy. Although (by simple issues of logical complexity) \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\) is not equivalent to any determinacy principle, work of Heinatsch and Möllerfeld [38] shows that it is are equiconsistent with a schema of determinacy principles. Work of Montalbán and Shore [66] similarly shows that \(Z_{2}\) is equiconsistent with a schema of determinacy principles.

Our work on separated determinacy initially arose from the question of whether \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\) is in general equiconsistent with a schema of determinacy principles. This, surprisingly, turns out not to be the case. Indeed, every single determinacy principle is either much weaker or much stronger than \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\) when \(2 < n\) (see Theorem 122 in §6.5.2 for the case \(n= 3\) and Theorem 146 in §6.5.2 for the general case). Another example of such a discontinuity is the well-known case of \({\mathsf{ZFC}}\): Borel determinacy is, in terms of consistency strength, much weaker than \({\mathsf{ZFC}}\); while the next determinacy principle, \(\boldsymbol {\Pi}^{1}_{1}{-}\)Determinacy, is much stronger. The situation here is not as extreme, however, since \(\boldsymbol {\Pi}^{1}_{1}{-}\)Determinacy is needed in order to show that there are no Wadge classes between \(\boldsymbol {\Delta}^{1}_{1}\) and \(\boldsymbol {\Sigma}^{1}_{1}\) in the first place.

1.2.5 Applications beyond second-order arithmetic

Our separation reduction theorems are phrased in as general terms as possible and their scope is not restricted to the study of subsystems of Second-Order Arithmetic. Indeed, we expect them to be of use in future work on the reverse mathematics of subsystems of transfinite-order arithmetic and of extensions of \({\mathsf{ZFC}}\) by large cardinal axioms.

Even beyond this, they can be applied to the context of \({\mathsf{ZFC}}\). We shall prove a result which we call the Generalized Borel Determinacy Theorem (see Theorem 175 in §8). According to it, if \(\boldsymbol {\Gamma}\) is any Wadge class, then

The definition of the class on the right-hand side is given in Definition 9 in §3.2; it is essentially a separated union of \(\boldsymbol {\Gamma}\) sets by \(\boldsymbol {\Sigma}^{0}_{2}\) sets with a Borel set added to it. This construction is introduced in order to unify what would otherwise be several arguments in the course of this work and figures in the statements of the separation reduction theorems. In particular, we have

so the usual statement of Borel determinacy is a particular case of Generalized Borel Determinacy. However, Martin’s theorem is not subsumed by ours, since the proof of Generalized Borel Determinacy makes use of usual Borel Determinacy (as well as of ideas in its proof).

Although equation (1.7) might seem strange, it is optimal. For instance, it is no longer true if \(\boldsymbol {\Sigma}^{0}_{2}\) is replaced even by \(\boldsymbol {\Pi}^{0}_{2}\). Thus, the operation which given a sequence of sets in \(\boldsymbol {\Gamma}\) maps it to its union separated by disjoint \(F_{\sigma}\) sets and adds a disjoint Borel set somehow captures the limits of \({\mathsf{ZFC}}\) as far as propagating winning strategies along the Wadge hierarchy. The Separation Reduction Theorems capture a similar limiting behavior for subsystems of \(Z_{2}\).

The Generalized Borel Determinacy Theorem can be combined with other known results and used to conclude optimal strengthenings of the well-known determinacy transfer theorems of Martin-Harrington [37, 55], Kechris-Woodin [45], and Neeman [71]; namely:

(see Corollary 176 in §8). This implication is best possible.

A remarkable aspect of (1.7) is that there are absolutely no hypotheses on the Wadge class \(\boldsymbol {\Gamma}\). In order to do away with these, we prove a curious general fact about Wadge reducibility: every Wadge class \(\boldsymbol {\Gamma}\) not below \(\Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\) is closed under unions with open sets and intersections with closed sets (see Theorem 20 in §3.3; Wadge classes with this property we call “treeable”). This fact was proved earlier by Andretta, Hjorth, and Neeman [13] in the theory \({\mathsf{ZF}}+ {\mathsf{AD}}+ {\mathsf{DC}}_{\mathbb{R}}\). However, as we shall see, it is in fact also provable in \({\mathsf{ZFC}}\) and, in fact, in Third-Order Arithmetic with Dependent Choices (incidentally, this theory is sufficient to prove a local version of the Generalized Borel Determinacy theorem; see Theorem 186 in §8). It is perhaps surprising that such a general fact about Wadge classes can be consistent with the Axiom of Choice, let alone provable. We also observe that this Treeability Theorem is provable in \(Z_{2}\) if one restricts to projective sets, and in \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) if one restricts to Borel sets; this latter fact is a crucial ingredient of our reverse-mathematical analysis of determinacy in Second-Order Arithmetic.

Brief outline

We begin in §2 with preliminaries. This includes a review of Wadge theory, including among other things a summary of Louveau’s theory of descriptions for Borel Wadge classes. In §3 we introduce three definitions which, albeit technical, will appear and re-appear throughout the article. The first is that of a definable Wadge class, which will allow us to uniformly treat all Wadge classes of interest over both \({\mathsf{ZFC}}\) and \({\mathsf{RCA_{0}}}\). The second is that of a layered union of sets, which will simplify notation and arguments in the future. We also prove that this construction subsumes many of the more familiar and/or natural ones. These two definitions are more technical than they are deep and in fact, when the time comes, we shall point out parts of §3 which one might wish to skip when reading the article for the first time. The third definition is that of a treeable Wadge class. We also prove what we call the Treeability Theorem (Theorem 20 in §3.3).

Afterwards, §4, §5, and §6 deal with the statement and proof of each of one of the three separation reduction theorems, arguably the main results of the article. After each theorem has been proved, a short discussion takes place which mentions various corollaries and applications in the context of sufficiently weak subsystems of \(Z_{2}\), as well as in the context of \({\mathsf{ZFC}}\). Towards the end of §6 (see §6.5) we mention how the first part of the Third Separation Reduction Theorem can be extended to obtain information about determinacy principles in the region of \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\), by supplementing the techniques developed here with joint work with Welch [11].

In §7 we carry out our exhaustive analysis of determinacy principles below \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \Pi ^{1}_{4}{-}{ \mathsf{CA_{0}}}\). By this point most of the work has been done in the corollaries following the Separation Reduction Theorems, so most of the work remaining is the proofs of transferability. In §8 on we state and prove the Generalized Borel Determinacy Theorem. We also mention consequences and rule out its possible strengthenings.

Finally, in §9 we present our concluding remarks, returning to our initial triple family of problems and their status. We finish with a list of questions left open.

Basic Notions. We shall recall some preliminaries and fix notation. We assume some basic familiarity with notions from general logic, including provability and consistency, computability, constructibility, and the definitions and consequences of various theories. We refer the reader to Simpson [78] for background in subsystems of Second-Order Arithmetic, to Barwise [14] for admissible set theory, or Jensen [40] for constructibility, to Jech [39] or Kanamori [41] for infinite games, to Moschovakis [69] for descriptive set theory, and to Moschovakis [68] for inductive definability. Other than some general background in these areas, our work is self-contained.

Notation. We will often work informally and argue in ways that can be easily formalized in some suitable mathematical theory, without explicitly indicating the intended formalizations and leaving them to the reader instead. In doing so, we will often move back and forth between the languages of Set Theory and Second-Order Arithmetic, identifying theories in one language with theories in the other for convenience. For instance, we may abuse notation by writing e.g.,

to mean “\((\mathbb{N}, \mathbb{R}\cap L_{\alpha}) \models \boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\),” and so on. We will write \(\alpha <\omega _{1}\) to denote that \(\alpha \) is a countable ordinal (even when working in theories which do not prove the existence of \(\omega _{1}\)).

We write \(A \subset B\) to mean that \(A\) is a subset of \(B\) and write \(\bar{A}\) for the complement of \(A\) (often relative to ℝ). Incidentally, we use ℝ to refer to the Baire space \(\mathbb{N}^{\mathbb{N}}\) of all countable sequences of natural numbers and call the elements of ℝ “reals.” This is justified by the fact that the Baire space is homeomorphic to the set of irrational numbers, though we caution the reader that this set has slightly different topological properties from those of the real line. Thus, it will be important to keep in mind that ℝ denotes the Baire space. Sometimes we will also identify ℝ with the powerset of the natural numbers, particularly when referring to models of theories (in which context we will only refer to ℝ as a set and not as a topological space). These abuses of notation in theory should lead to no confusion.

For finite sequences \(p\), \(q\), we write \(p\sqsubset q\) to mean that \(p\) is a (possibly improper) initial segment of \(q\). We similarly write \(p\sqsubset x\), when \(x\) is an infinite sequence.

We use the notation \(\Sigma ^{0}_{n}\) and \(\Sigma ^{1}_{n}\) to refer to the Kleene classes as is customary. The boldface versions of these, \(\boldsymbol {\Sigma}^{0}_{n}\), \(\boldsymbol {\Sigma}^{1}_{n}\), denote the corresponding classes obtained by allowing real parameters. This distinction is applied to the names of axioms as well (e.g., “\(\Pi ^{1}_{1}{-}{ \mathsf{CA_{0}}}\)” versus “\(\boldsymbol {\Pi}^{1}_{1}{-}{ \mathsf{CA_{0}}}\)”).

Given a set of reals \(A\), we denote by \(G(A)\) the Gale-Stewart game with payoff \(A\). We use the notion of a game tree, due to Martin. A game tree is a tree \(T\) of finite sequences with no terminal nodes. The game \(G(A,T)\) is defined just like \(G(A)\), except that if a player moves outside of \(T\), she loses immediately. A quasi-strategy for Player I is a game tree \(T\) which does not restrict Player II’s moves, and a quasi-strategy for Player II is a game tree \(T\) which does not restrict Player I’s moves. A strategy is a single-valued quasi-strategy. As they are trees, we may write \(p \in \sigma \) to mean that the position \(p\) is consistent with the strategy \(\sigma \). The set of branches through a tree \(T\) is denoted by \([T]\), so \([\sigma ]\) is the set of moves consistent with the strategy \(\sigma \). We often use the expression “\(U\subset T\) is a quasi-strategy” to mean that \(U\) is a quasi-strategy in the sense of the game tree \(T\).

Closed sets of reals are precisely those of the form \([T]\) for some tree \(T\). Given an open set \(A\) and a tree \(T\) such that \(x \in A \leftrightarrow x\notin [T]\), and given a finite sequence \(p\), we may abuse notation by writing

to mean \(p \notin T\), i.e., \(p \in A\) means that no real extending \(p\) belongs to \(\bar{A}\). Dually, given a closed set \(A\), we may abuse notation by writing \(p \in A\) to mean that \(p \in T\), i.e., that some real extending \(p\) belongs to \(A\).

Base theory. Officially, and unless otherwise indicated, all of our work is carried out over the weak theory of Recursive Comprehension (\({\mathsf{RCA_{0}}}\)) whose axioms comprise Robinson’s \(\mathsf{Q}\) together with the \(\boldsymbol {\Sigma}^{0}_{1}\)-Induction schema and the axiom of \(\boldsymbol {\Delta}^{0}_{1}\)-Comprehension. That being said, we will be working with the reverse mathematics of determinacy, and determinacy for the class \(\boldsymbol {\Sigma}^{0}_{1}\wedge \boldsymbol {\Pi}^{0}_{1}\) already implies \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\), so we may almost always assume for all practical purposes that we work over \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\) and thus (by our abuse of notation) that we work over \({\mathsf{KPl}}_{0}\), the extension of \(\mathsf{ATR}_{0}^{set}\) asserting that every set belongs to an admissible set. By matters of absoluteness, we can mostly behave as though we were working over \({\mathsf{KPl}}_{0} + V = L\). Some results are easier to prove over \({\mathsf{KP}}\) than over \({\mathsf{RCA_{0}}}\) and sometimes this is done separately for readers who are not interested in weakening the base theory as much as possible. As before, when working in \({\mathsf{KP}}\) we may almost always behave as though we were working in \({\mathsf{KPi}}= {\mathsf{KP}}+ \boldsymbol {\Pi}^{1}_{1}{-}{ \mathsf{CA_{0}}}\) for our purposes. In this article, \({\mathsf{KP}}\) includes the Axiom of Infinity and the full schema of Foundation. \(Z_{n}\) is \(n\)th-Order Arithmetic and is identified with the theory \({\mathsf{KP}}\) + Collection + “\(\mathcal{P}^{n-2}(\mathbb{N})\) exists.”

Review of Wadge Theory. A reduction from a set \(A\subset \mathbb{R}\) to a set \(B\subset \mathbb{R}\) is a continuous function \(f:\mathbb{R}\to \mathbb{R}\) such that

If there is such a reduction, we write \(A\leq _{W} B\). The relation \(\leq _{W}\) is clearly reflexive and transitive. Equivalence classes given by \(\leq _{W}\) are called Wadge degrees. A Wadge class is a subset of \(\mathcal{P}(\mathbb{R})\) closed downwards under \(\leq _{W}\). Wadge classes (or degrees) closed under negations are called selfdual. The dual of a class \(\boldsymbol {\Gamma}\) is denoted by \(\breve{\boldsymbol {\Gamma}}\) and we write

Thus, \(\boldsymbol {\Gamma}\) is selfdual if and only if \(\boldsymbol {\Gamma}= \Delta (\boldsymbol {\Gamma})\). We use the notation

to mean \(\boldsymbol {\Gamma}\subset \Delta (\boldsymbol {\Gamma}')\). (This is standard notation in Spector theory, but we often find it useful in contexts such as this.) Sometimes, and especially for typographical reasons when a Wadge class has a long name, it is customary to write \(\boldsymbol {\Gamma}^{\breve{}}\) for the dual of \(\boldsymbol {\Gamma}\). For instance, we may write

(this class will be defined below in this section).

A Wadge class \(\boldsymbol {\Gamma}\) generated by a degree \(d\) is called parametrized. We may abuse notation and identify a parametrized Wadge class with the corresponding degree. An example of a selfdual Wadge degree is \(\boldsymbol {\Delta}^{0}_{1}\); an example of a selfdual Wadge class which is not parametrized is \(\boldsymbol {\Delta}^{0}_{2}\); an example of a non-selfdual Wadge degree is \(\boldsymbol {\Sigma}^{0}_{2}\). Under our terminology, the set-theoretic union \(\boldsymbol {\Sigma}^{0}_{2}\cup \boldsymbol {\Pi}^{0}_{2}\) (i.e., the collection of sets which are either \(\boldsymbol {\Sigma}^{0}_{2}\) or \(\boldsymbol {\Pi}^{0}_{2}\); not to be confused with the class \(\boldsymbol {\Sigma}^{0}_{2} \vee \boldsymbol {\Pi}^{0}_{2}\) of sets which are unions of a \(\boldsymbol {\Sigma}^{0}_{2}\) set and a \(\boldsymbol {\Pi}^{0}_{2}\) set) is also a Wadge class, but is not parametrized. The Wadge game \(G_{W}(A, B)\) is defined as follows: during turn \(k\), Player I plays a digit \(x_{k}\). Player II then either plays a digit \(y_{k}\), or passes. At the end of the game, Player I has produced a real \(x\). If Player II has not produced a real (i.e., has passed all but finitely many of his turns), then he loses. Otherwise, Player II wins if and only if

Wadge’s lemma [83] says that (i) If Player II has a winning strategy in \(G_{W}(A,B)\), then \(A\leq _{W} B\); and (ii) if Player I has a winning strategy in \(G_{W}(A,B)\), then \(B \leq _{W} \bar{A}\). It follows that if the Axiom of Determinacy holds, then the relation \(\leq _{W}\) is a semi-linear ordering, in the sense that for all \(A\), \(B\) we have

This means that \(\leq _{W}\) is a linear pre-ordering if one identifies complementary sets and in any case there are no antichains in \(\leq _{W}\) of size greater than 2. When restricting to Borel sets, the lemma becomes provable in weak subsystems of \(Z_{2}\) (in particular, it follows from \(\boldsymbol {\Sigma}^{0}_{1}\wedge \boldsymbol {\Pi}^{0}_{1}{-}\)Determinacy), by recent work of Day, Greenberg, Harrison-Trainor, and Turetsky [21].

By a result of Martin, it follows from determinacy that the Wadge hierarchy is wellordered. Under the full Axiom of Determinacy, the length of \(\leq _{W}\) is \(\Theta \) (the supremum of order-types of pre-wellorderings of ℝ). Since we will be working mostly (but not exclusively) with sets of low Wadge rank, we can explicitly compute the rank of Wadge classes of interest, using the results of Wadge [83]. If \(\boldsymbol {\Gamma}\) is a Wadge degree in the wellfounded part of \(\leq _{W}\), we denote by

its rank in the Wadge hierarchy. For Wadge classes \(\boldsymbol {\Gamma}\) which are not generated by a degree, we also define \(o(\boldsymbol {\Gamma})\) to be supremum of Wadge ranks of degrees of sets in \(\boldsymbol {\Gamma}\).

We shall now recall some operations on Wadge classes due to Hausdorff, Kuratowski [49], Wadge [83], Myers, and Louveau [51]. These will be crucial for our analysis of determinacy, since they can be used to fully describe an initial segment of the Wadge hierarchy which covers all classes of interest to us here.

Definition 1

We define various operations on Wadge classes \(\boldsymbol {\Gamma}\), \(\boldsymbol {\Gamma}'\), \(\boldsymbol {\Gamma}''\).

1. (1)

   Let \(\xi <\omega _{1}\) and for each \(\eta <\xi \), let \(A_{\eta}\) be a set in \(\boldsymbol {\Gamma}\). We define the difference \(A\) of the sets \(A_{\eta}\) by

   $$ A = \textstyle\begin{cases} \bigcup _{\eta < \xi , \text{ $\eta $ odd}}A_{\eta }\setminus \bigcup _{ \eta '< \eta}A_{\eta '}, &\text{ for $\xi $ even,} \\ \bigcup _{\eta < \xi , \text{ $\eta $ even}}A_{\eta }\setminus \bigcup _{ \eta '< \eta}A_{\eta '}, &\text{ for $\xi $ odd.} \end{cases} $$

   We denote by \(\xi{-}\boldsymbol {\Gamma}\) the collection of all differences of ⊂-increasing \(\xi \)-sequences of sets in \(\boldsymbol {\Gamma}\).

2. (2)

   Let \(A_{0}\), \(A_{1}\), and \(C\) be sets. The union of \(A_{0}\) and \(A_{1}\) separated by \(C\) is defined by

   $$ S(A_{0},A_{1},C) = (A_{0} \cap C) \cup (A_{1} \cap \bar{C}). $$

   The class \(S(\boldsymbol {\Gamma}',\boldsymbol {\Gamma})\) consists of all sets of the form \(S(A_{0},A_{1},C)\) with \(A_{0} \in \boldsymbol {\Gamma}\), \(A_{1} \in \breve{\boldsymbol {\Gamma}}\), and \(C \in \boldsymbol {\Gamma}'\).

3. (3)

   Let \(A_{0}\), \(A_{1}\) be sets and \(C_{0}\), \(C_{1}\) be disjoint sets. The union of \(A_{0}\) and \(A_{1}\) two-sided–separated by \(C_{0}\), \(C_{1}\) is defined by

   $$ B(A_{0},A_{1},C_{0}, C_{1}) = (A_{0} \cap C_{0}) \cup (A_{1} \cap C_{1}). $$

   The class \(B(\boldsymbol {\Gamma}',\boldsymbol {\Gamma})\) consists of all sets of the form \(B(A_{0},A_{1},C_{0},C_{1})\) with \(A_{0} \in \boldsymbol {\Gamma}\), \(A_{1} \in \breve{\boldsymbol {\Gamma}}\), and \(C_{0},C_{1} \in \boldsymbol {\Gamma}'\) (and disjoint).

   Suppose \(A_{0}\), \(A_{1}\), \(C_{0}\), \(C_{1}\) are as above and let \(D\) be a set. We also define

   $$ B(A_{0},A_{1},C_{0}, C_{1}, D) = (A_{0} \cap C_{0}) \cup (A_{1} \cap C_{1}) \cup (D\setminus (C_{0} \cup C_{1})) $$

   and let \(B(\boldsymbol {\Gamma}',\boldsymbol {\Gamma}, \boldsymbol {\Gamma}'')\) be the class of all sets of the form \(B(A_{0},A_{1},C_{0}, C_{1}, D)\) with \(A_{0} \in \boldsymbol {\Gamma}\), \(A_{1} \in \breve{\boldsymbol {\Gamma}}\), \(C_{0},C_{1} \in \boldsymbol {\Gamma}'\) (disjoint), and \(D \in \boldsymbol {\Gamma}''\).

4. (4)

   Let \(C_{l} \in \boldsymbol {\Gamma}'\) be disjoint sets and \(A_{l}\in \boldsymbol {\Gamma}\) be sets, for \(l\in \mathbb{N}\). The separated union of the family \(\{A_{l}:l\in \mathbb{N}\}\) by the family \(\{C_{l}:l\in \mathbb{N}\}\) is given by

   $$ A = \bigcup _{l\in \mathbb{N}}(A_{l} \cap C_{l}). $$

   The set \(C = \bigcup _{l\in \mathbb{N}} C_{l}\) is called the envelope of \(A\) and denoted \(\text{Env}(A)\). The class \(\mathsf{SU}(\boldsymbol {\Gamma}',\boldsymbol {\Gamma})\) consists of all sets \(A\) as above.

5. (5)

   Let \(\xi <\omega _{1}\) and for each \(\eta <\xi \), let \(A_{\eta }\in \boldsymbol {\Gamma}\) and \(C_{\eta }\in \boldsymbol {\Gamma}'\) be such that for all \(\eta \) we have \(A_{\eta}\subset C_{\eta}\subset A_{\eta +1}\) and the sequences \(\{A_{\eta}:\eta <\xi \}\) and \(\{C_{\eta}:\eta <\xi \}\) are increasing. We define the separated difference of \(\{A_{\eta}:\eta <\xi \}\) by \(\{C_{\eta}:\eta <\xi \}\) to be the set

   $$ A = \mathsf{SD}\big(\{A_{\eta}:\eta < \xi \}, \{C_{\eta}:\eta < \xi \} \big) = \bigcup _{\eta < \xi} \Big( A_{\eta }\setminus \bigcup _{\eta '< \eta} C_{\eta '}\Big). $$

   We denote by \(\mathsf{SD}_{\xi}(\boldsymbol {\Gamma}', \boldsymbol {\Gamma})\) the collection of all such sets \(A\). If moreover \(B \in \boldsymbol {\Gamma}''\) is some other set, we define

   $$ \mathsf{SD}\big(\{A_{\eta}:\eta < \xi \}, \{C_{\eta}:\eta < \xi \}, B \big) = \bigcup _{\eta < \xi} \Big(A_{\eta }\setminus \bigcup _{\eta '< \eta} C_{\eta '}\Big) \cup \Big( B\setminus \bigcup _{\eta < \xi} C_{ \eta}\Big) $$

   and let \(\mathsf{SD}_{\xi}(\boldsymbol {\Gamma}', \boldsymbol {\Gamma}, \boldsymbol {\Gamma}'')\) be the corresponding class. We write simply \(\mathsf{SD}_{\xi}(\boldsymbol {\Gamma}', \boldsymbol {\Gamma})\) when \(\boldsymbol {\Gamma}'' = \{\varnothing \}\).

We might also consider degenerate differences and separated differences by writing we put

and

In particular, we notice that \(S(0{-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}) = \breve{\boldsymbol {\Gamma}}\).

Remark 2

We make use of Louveau’s definition of the difference hierarchy. It will mostly be applied to the case \(\boldsymbol {\Gamma}= \boldsymbol {\Sigma}^{0}_{\alpha}\). Note that this definition is different from the one used by Hausdorff and Kuratowski, which is more suitable for differences built over \(\boldsymbol {\Pi}^{0}_{\alpha}\) sets. We will always denote the classes in the difference hierarchy for Borel sets by \(\alpha{-}\boldsymbol {\Sigma}^{0}_{\xi}\) rather than by \(\alpha{-}\boldsymbol {\Pi}^{0}_{\xi}\) to indicate this fact.

Warning: Our definition of \(S(\boldsymbol {\Gamma}', \boldsymbol {\Gamma})\) is dual from that of Louveau. This will not play a role below, since \(\boldsymbol {\Gamma}\)-Determinacy is always equivalent to \({\breve{\boldsymbol {\Gamma}}}\)-Determinacy, but we find it more convenient to use the current definition.

We will use various facts about these operations and the classes they produce, but rather than listing these facts here, we will instead cite them when appropriate. Appendix B records some closure properties of Wadge classes constructed according to the separation operators. The reader might wish to verify that

and

A Wadge class \(\boldsymbol {\Gamma}\) has the reduction property if whenever \(A, B \in \boldsymbol {\Gamma}\), one can find sets \(A' \subset A\), \(B'\subset B\) such that \(A'\) and \(B'\) are disjoint and \(A' \cup B' = A \cup B\). An example of a class with the reduction property is \(\boldsymbol {\Sigma}^{0}_{1}\) (recall that we work with the Baire space and not with the literal ℝ). A Wadge class \(\boldsymbol {\Gamma}\) has the separation property if for all disjoint \(A, B \in \boldsymbol {\Gamma}\) we can find a set \(C \in \Delta (\boldsymbol {\Gamma})\) separating \(A\) from \(B\). An example of a class with the separation property is \(\boldsymbol {\Pi}^{0}_{1}\). More generally, work of Van Wesep [87] and Steel [80] shows that, under determinacy, precisely one of \(\boldsymbol {\Gamma}\) or \(\boldsymbol {\Gamma}'\) has the separation property, and precisely one has the reduction property, when \(\boldsymbol {\Gamma}\) is non-selfdual. Recent work of Greenberg and Turetsky [33] yields effective versions of this result.

A Wadge class \(\boldsymbol {\Gamma}\) is said to be closed under \(\boldsymbol {\Gamma}'\)-separated unions if

General conditions for this to hold when \(\boldsymbol {\Gamma}\) and \(\boldsymbol {\Gamma}'\) are Borel are laid out in Lemma 1.4 of Louveau [51] (see also Lemma 215 in Appendix B).

Effective Wadge Classes. Often, we will find it convenient to work with the effective (or lightface) versions of various Wadge classes. While our results are mostly phrased in terms of boldface classes, the proofs will often require dealing with their lightface counterparts. This is an instance of the usefulness of the effective descriptive set theory for the study of its classical aspects. All definitions effectivize the natural way: classes such as \(\Sigma ^{0}_{\alpha}\) or \(\mathsf{SU}(\Sigma ^{0}_{\alpha},\Sigma ^{0}_{\gamma})\) are defined as one would expect: by demanding that all operations involved be recursive (in particular this requires that \(\alpha \) and \(\gamma \) be recursive ordinals). An effective Wadge class is thus a collection of subsets of ℝ closed under continuous preimages by a recursive function. Given an effective Wadge class \(\Gamma \), we denote by \(\Gamma (x)\) the result of relativizing it to the real parameter \(x\in \mathbb{R}\) and we denote by \(\boldsymbol {\Gamma}\) the associated boldface class. Thus, while expressions such as “\(\Sigma ^{0}_{\omega _{1}^{ck}}\)” are undefined, one can speak of \(\Sigma ^{0}_{\omega _{1}^{ck}}(\mathcal{O})\). Such classes will play important roles in our arguments below.

3.1 Definable Wadge classes

We will attempt to deal with Wadge classes in as much generality as possible. This is problematic for several reasons. First, there are various explicit descriptions of the Borel Wadge classes, due to Wadge [83], Louveau [51] and Louveau and Saint-Raymond [52]. These descriptions do not extend beyond the Borel sets. Carroy, Medini and Müller [17] have given a description of Wadge classes which extends beyond the Borel sets, but it appears not to be suitable for our purposes. We mostly work with the Louveau descriptions, since we find it to be the most explicit and because they behave well within the various inductive arguments that will arise later on. Nonetheless, the separation reduction theorems in their full generality must be stated in terms of a slight variant of the Louveau–Saint-Raymond descriptions, using the notion of a layered union, which will be introduced soon.

Another problem is that general Wadge classes need not be closed under reasonable operations. Already levels of the difference hierarchy need not be closed under Boolean operations. Even worse, once one goes past the Borel classes, the Wadge hierarchy need not have a nice structure. For instance, the statement that every set in \(\boldsymbol {\Sigma}^{1}_{1}\) but not in \(\boldsymbol {\Delta}^{1}_{1}\) is \(\boldsymbol {\Sigma}^{1}_{1}\)-complete is equivalent to \(\boldsymbol {\Pi}^{1}_{1}\)-Determinacy. Finally, we run into the problem of expressibility. When working over subsystems of \({\mathsf{ZFC}}\), the mere fact that the definitions of Wadge classes might be complicated becomes an issue. The complexity of the sets themselves could potentially also cause difficulties, though this is of lesser concern.

These problems lead us to the notion of a definable Wadge class. These will be our main subject of study here. Although our treatment will be informal, we first give a precise definition. We do remark that the definition we give could probably be replaced by any other reasonable definition and the rest of the article would still make sense. The following definition makes sense in the context of \({\mathsf{RCA_{0}}}\) and of \({\mathsf{ZFC}}\):

Definition 3

Assume \({\mathsf{RCA_{0}}}\). A definable pre-Wadge class consists of a sequence of formulas \(\vec{\phi}= \{\phi _{l}(\cdot ,\cdot ,\cdot ,\cdot ): l\in \mathbb{N} \}\) (in the language of set theory or second-order arithmetic) such that \(\vec{\phi}\) forms a set, together with a (set or real) parameter \(p\). Let \(\vec{\phi}\) and \(p\) be as above. For each \(n,l\in \mathbb{N}\) and each \(y\in \mathbb{R}\), we obtain a collection of reals

(Note that \(A_{\vec{\phi},l,n,y}\) need not form a set.) Let \(\boldsymbol {\Gamma}\) be the class of all \(A_{\vec{\phi},l,n,y}\) as \(l\), \(n\) range over ℕ and \(y\) ranges over elements of ℝ which are sets and such that \(\vec{\phi}\leq _{T} y\) in some uniform way (e.g., we may restrict to \(y\) of the form \(\vec{\phi}\oplus y_{0}\), where ⊕ denotes the Turing join). We say that \(\boldsymbol {\Gamma}\) is a definable Wadge class if \(\boldsymbol {\Gamma}\) is uniformly and effectively closed under continuous preimages, in the sense that for all continuous \(f:\mathbb{R}\to \mathbb{R}\), the set \(f^{-1}(A_{\vec{\phi},l,n,y})\) is of the form \(A_{\vec{\phi},l^{*},n,y\oplus f}\), \(l^{*}\) depends only on \(f\) and \(l\), and the functions

exist for each continuous \(f\).

Example 4

Assume \({\mathsf{ZFC}}\). Then, every Wadge class is a definable Wadge class, since it can be defined using itself as a parameter.

Example 5

Assume \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\). Then, every Borel Wadge class is a definable Wadge class, since by Louveau [51] all Borel Wadge classes have descriptions in terms of the operators in Definition 1 and by Day, Greenberg, Harrison-Trainor, and Turetsky [21] this fact is provable in \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\). Here, the parameters are sequences of ordinal numbers.

Example 6

Assume \({\mathsf{RCA_{0}}}\). Then, every class of the form \(\boldsymbol {\Sigma}^{1}_{n}\) is definable, since the sequence of all \(\Sigma ^{1}_{n}\) formulas is recursive. Moreover, the result of applying any of the operations from Definition 1 to \(\boldsymbol {\Sigma}^{1}_{n}\) results in a definable Wadge class.

Given a definable Wadge class \(\boldsymbol {\Gamma}\) with a definition \((\vec{\phi}, p)\) as above and a real \(y\) such that \((\vec{\phi}, p)\leq _{T} y\), we let \(\Gamma (y)\) be the collection of all sets \(A_{\vec{\phi},l,n,y}\) as \(l\), \(n\) range over ℕ. This is the \(y\)-lightface section of \(\boldsymbol {\Gamma}\). We write \(\Gamma = \Gamma (x)\) where \(x\) is a code for the pair \((\vec{\phi},p)\) as in Definition 3. In most cases of interest we will have \(\vec{\phi}\) recursive and write \(\Gamma = \Gamma (0) = \Gamma (x)\) (for \(x\) as above). An exception would be “\(\Sigma ^{0}_{\omega _{1}^{ck}}\),” as mentioned earlier.

Remark 7

We should point out that there is a distinction between a Wadge class being effective and it having an effective description. In general, the reader should keep in mind the distinction between a Wadge class \(\boldsymbol {\Gamma}\) containing complicated sets (i.e., some sets in \(\boldsymbol {\Gamma}\) have complicated definitions), and \(\boldsymbol {\Gamma}\) having a complicated definition itself. For example, \(\boldsymbol {\Sigma}^{0}_{2}\) is a non-effective Wadge class consisting of relatively simple sets. \(\boldsymbol {\Sigma}^{1}_{17}\) is a non-effective Wadge class consisting of relatively more complicated sets, but it is still effectively describable, since it is the collection of sets definable by \(\Sigma ^{1}_{17}\) formulas with parameters. On the other hand, \(\Sigma ^{0}_{\omega _{1}^{ck}}(\mathcal{O})\) is an effective (lightface) Wadge class although it does not have a recursive definition.

Our intention below is to work within (models of) \({\mathsf{RCA_{0}}}\) and prove results about definable Wadge classes, internally. Models of \({\mathsf{RCA_{0}}}\) could in principle believe mistakenly that some pair \((\vec{\phi}, p)\) is a definable Wadge class when in reality it is not, and they could also contain definable Wadge classes \((\vec{\phi}, p)\) and mistakenly believe that they do not form a definable Wadge class.

Remark 8

One can only do Reverse Mathematics for explicit sentences written down in the language of arithmetic or set theory. Expressions such as “\(\omega{-}\Sigma ^{0}_{2}\)-Determinacy” need to be formalized and thus depend on how \(\omega \) is represented as a recursive ordering of ℕ. As mentioned in the introduction, we have mostly elected to sweep these issues under the rug. The concerned reader should do the sensible thing and assume throughout that whenever any explicit ordinal is referred to, it is done so via a recursive representation which is provably wellfounded in some suitable theory. We shall not be concerned with theories such as “\(|{\mathsf{ZFC}}|_{\Pi ^{1}_{1}}{-}\boldsymbol {\Sigma}^{0}_{1}{-}\)Determinacy.”

Notation. We will use the expression “let \(\{A_{l}:l\in \mathbb{N}\}\) be a sequence of sets in \(\boldsymbol {\Gamma}\)” to mean that the sequence of definitions for the sets \(A_{l}\) forms a set itself.

3.2 Layered unions and representation lemmata

We introduce a technical operation on Wadge classes which will be convenient for stating and proving results on Wadge classes over weak theories.

Definition 9

Let \(\{A_{l}: l\in \mathbb{N}\}\) and \(\{C_{l} : l\in \mathbb{N}\}\) be sequences of sets and \(B\) be a set. We define the layered union of \(\{A_{l}: l\in \mathbb{N}\}\) by \(\{C_{l} : l\in \mathbb{N}\}\) relative to \(B\) to be the set

and write

provided that

We denote by

the class of all layered unions as above (with \(W \cap C_{l} = A_{l} \cap C_{l}\)). We simply write \(\mathsf{LU}(\boldsymbol {\Gamma}',\boldsymbol {\Gamma})\) when \(\boldsymbol {\Gamma}'' = \{\varnothing \}\).

Layered unions are a form of separated difference where the sets \(A_{l}\) are required to converge to a fixed set \(A\) in a way that at each stage \(l\), larger and larger parts (given by the sets \(C_{l}\)) of \(A\) become fixed. We will often be interested in the case where \(\boldsymbol {\Gamma}\) is not a Wadge degree, or in cases in which \(A\) does not belong to \(\boldsymbol {\Gamma}\).

There is a reason why layered unions have not been considered explicitly in the past (as far as we can tell), and this is that these sets can be expressed in terms of the operators previously defined. Conversely, many of the operations defined in the previous section can be restated in terms of layered unions. We will find it convenient to work with these sets directly, and in order to do this we must briefly explain these restatements.

Suggestion. The remainder of this section is rather technical and is not needed for the statement or proofs of the Separation Reduction Theorems. First-time readers might now wish to consider skipping ahead to §4 (perhaps briefly stopping at the definition of treeability in §3.3 and/or the entirety of §3.3 on the way) and returning here later when these lemmata are needed.

Clearly every representation of a set \(W\) as a set in the class \(\mathsf{SU}(\boldsymbol {\Gamma}',\boldsymbol {\Gamma})\) is a representation of \(W\) as a set in \(\mathsf{LU}(\boldsymbol {\Gamma}',\boldsymbol {\Gamma})\). The following lemma says that layered unions are essentially the same as separated unions (modulo the additional set \(B\)).

Lemma 10

Let \(\boldsymbol {\Gamma}\) and \(\boldsymbol {\Gamma}''\) be Wadge classes and let \(\xi <\omega _{1}\). Suppose

is a set in \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{\xi},\boldsymbol {\Gamma}, \boldsymbol {\Gamma}'')\). Then, there is a representation of \(W\) of the form (3.1) in which the sets \(C_{l}\) are pairwise disjoint.

Proof

Let \(W\) be represented above in terms of the sets \(A_{l}\), \(C_{l}\), and \(B\), where \(l\in \mathbb{N}\) and each \(C_{l}\) belongs to \(\boldsymbol {\Sigma}^{0}_{\xi}\). For each \(l\), write

where \(C_{l,k} \in \boldsymbol {\Pi}^{0}_{<\xi}\). Put

where \(\langle \cdot , \cdot \rangle \) denotes the pairing function on natural numbers. Then, \(\{C^{*}_{l} : l\in \mathbb{N}\}\) is a family of pairwise disjoint \(\boldsymbol {\Sigma}^{0}_{\xi}\) sets whose union is \(\bigcup _{l\in \mathbb{N}} C_{l}\). As can be verified directly, the fact that \(W \cap C_{l} = A_{l} \cap C_{l}\) for each \(l\in \mathbb{N}\) implies that

as well, and this is a representation of \(W\) as a layered union. Specifically, suppose \(x \in W \cap C_{l}\) for some \(l\). Let \(\langle l,k\rangle \) be least such that \(x \in C_{l,k}\). By the definition of layered union, we have \(x \in A_{l}\). Moreover, by the definition of \(C^{*}_{l}\), we have \(x \in C^{*}_{l}\), so \(x \in A_{l} \cap C^{*}_{l}\), as desired. □

Similarly to Lemma 10, it is easy to see that

if \(\boldsymbol {\Gamma}'\) is closed under binary unions, in which case indeed every representation (3.1) of a set \(W\) in the class on the left-hand side is also a representation of \(W\) as a set in the class on the right-hand side. The converse is not true, since separated-difference representations might not satisfy the condition \(W \cap C_{l} = A_{l} \cap C_{l}\).

3.2.1 Representation lemmata for separated unions

In this section, we prove two results whereby one-sided separated unions of sets can be represented as layered unions or as particular cases of the layered-union construction. This will allow us to apply the general results of the following sections to classes of the form \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{\xi}, \boldsymbol {\Gamma})\). All proofs for results in this section can be found in Appendix A.

Lemma 11

Suppose that \(\boldsymbol {\Gamma}\) is closed under unions and intersections with \(\boldsymbol {\Sigma}^{0}_{\xi}\) and \(\boldsymbol {\Pi}^{0}_{\xi}\). Then, the sets in \(S((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{\xi},\boldsymbol {\Gamma})\) are all of the form

where \(W_{0} \in S(\alpha{-}\boldsymbol {\Sigma}^{0}_{\xi}, \boldsymbol {\Gamma})^{\breve{}}\), \(W_{1} \in \breve{\boldsymbol {\Gamma}}\), and \(D\in \boldsymbol {\Sigma}^{0}_{\xi}\).

Moreover, if \(\boldsymbol {\Gamma}\) is closed under binary intersections, then the converse holds (i.e., the sets in \(S((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{\xi},\boldsymbol {\Gamma})\) are precisely those of the form (3.3)).

Lemma 12 below is a slightly more elaborate version of Lemma 11.

Lemma 12

Suppose that \(\boldsymbol {\Gamma}\) is a Borel Wadge class closed under unions and intersections with \(\boldsymbol {\Sigma}^{0}_{\xi}\) and \(\boldsymbol {\Pi}^{0}_{\xi}\), under binary intersections, and under \(\boldsymbol {\Sigma}^{0}_{\xi}\)-separated unions. Then, we have

Lemma 13

Let \(\xi \) be a countable ordinal and \(\lambda \) be a countable limit ordinal. Then,

If, moreover, \(\boldsymbol {\Gamma}\) is closed under intersections (with itself), unions with \(\boldsymbol {\Sigma}^{0}_{\xi}\) and \(\boldsymbol {\Pi}^{0}_{\xi}\), and \(\boldsymbol {\Sigma}^{0}_{\xi}\)-separated unions, then the converse inclusion holds. In particular, this holds of \(\boldsymbol {\Gamma}= \boldsymbol {\Sigma}^{0}_{\xi + 1 + \xi '}\) for any countable \(\xi '\).

3.2.2 Representation lemmata for two-sided separated unions

Proofs for results in this section can be found in Appendix A.

Lemma 14

Let \(\lambda \) be a limit ordinal, \(\xi \) be a countable ordinal, and \(\boldsymbol {\Gamma}\) be a Wadge class. Then,

Moreover, if \(\boldsymbol {\Gamma}\) is closed under \(\boldsymbol {\Sigma}^{0}_{\xi}\)-separated unions and unions and intersections with \(\boldsymbol {\Sigma}^{0}_{\xi}\) sets, then the converse implication holds as well.

We also mention the following variant of Lemma 14

Lemma 15

Let \(\lambda \) be a limit ordinal, \(\xi \) be a countable ordinal, and \(\boldsymbol {\Gamma}\) be a Wadge class. Then,

Moreover, if \(\boldsymbol {\Gamma}\) is closed under \(\boldsymbol {\Sigma}^{0}_{\xi}\)-separated unions and unions and intersections with \(\boldsymbol {\Sigma}^{0}_{\xi}\) sets, then the converse implication holds as well.

Lemma 16

Let \(\lambda \) be a limit ordinal and \(\alpha \) and \(\xi \) be countable ordinals, and let \(\boldsymbol {\Gamma}\) be a Wadge class. Then,

Moreover, if \(\boldsymbol {\Gamma}\) is closed under \(\boldsymbol {\Sigma}^{0}_{\xi}\)-separated unions and unions and intersections with \(\boldsymbol {\Sigma}^{0}_{\xi}\) sets, then the converse implication holds as well.

We conclude this section by mentioning without proof the following analog of the preceding results for the difference hierarchy.

Lemma 17

Let \(\lambda \) be a countable limit ordinal and \(\xi \) be a countable ordinal, and let \(\boldsymbol {\Gamma}\) be a Wadge class. Then,

3.3 The treeability theorem

Definition 18

A definable Wadge class \(\boldsymbol {\Gamma}\) is treeable if it is closed under unions with open sets and intersections with closed sets.

The name “treeable” comes from the following consequence of the definition: if \(\boldsymbol {\Gamma}\) is treeable, \(A\in \boldsymbol {\Gamma}\), and \(T\) is a game tree, then \(G(A,T)\) is a Gale-Stewart game with payoff in \(\boldsymbol {\Gamma}\). Thus we have:

Lemma 19

Suppose \(\boldsymbol {\Gamma}\) is treeable and all games of the form \(G(A)\) are determined. Then, all games of the form \(G(A,T)\) are determined.

Proof

Immediate. □

Over weak theories, it seems difficult to prove that Wadge classes are treeable, so we will have to mention treeability as a hypothesis for many of our theorems, though this hypothesis can be ignored in all cases of interest.

Examples of Wadge classes that are not treeable are \(n{-}\boldsymbol {\Sigma}^{0}_{1}\) and its dual, for \(n\in \mathbb{N}\). The following result, which we call the Treeability theorem, says that these are essentially the only ones in \({\mathsf{ZFC}}\) and, indeed, in \(Z_{3}\) (Third-Order Arithmetic).

Theorem 20

Assume \(Z_{3} + {\mathsf{DC}}_{\mathbb{R}}\). Suppose that \(A\subset \mathbb{R}\) and \(A \notin \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\). Then, \(A \cup C \leq _{W} A\) for any open set \(C\).

Corollary 21

Assume \(Z_{3} + {\mathsf{DC}}_{\mathbb{R}}\). Let \(\boldsymbol {\Gamma}\) be a definable Wadge class. Then, one of the following holds:

1. (1)

   \(\boldsymbol {\Gamma}\prec \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\), or

2. (2)

   \(\boldsymbol {\Gamma}\) is treeable.

Proof

If \(\boldsymbol {\Gamma}\nprec \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\), then Theorem 20 implies that \(\boldsymbol {\Gamma}\) is closed under unions with open sets. Moreover, \(\breve{\boldsymbol {\Gamma}} \nprec \Delta (\omega{-} \boldsymbol {\Sigma}^{0}_{1})\), because any reduction from a set in \(\breve{\boldsymbol {\Gamma}}\) to a set in \(\Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\) is also a reduction from its complement to a set in \(\Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\). Thus \(\breve{\boldsymbol {\Gamma}}\) is closed under unions with open sets and so \(\boldsymbol {\Gamma}\) is closed under intersections with closed sets. □

The following result illustrates one of the reasons why we focus on determinacy hypotheses for Wadge classes rather than focus on the complexity of individual sets. The slogan is: useful determinacy principles assert not that complicated sets are determined, but rather that non-determined sets are complicated.

Corollary 22

Assume \(Z_{3} + {\mathsf{DC}}_{\mathbb{R}}\). Then the collection of determined sets is cofinal in the Wadge hierarchy.

Proof

Given a real \(x\), let \(x'\) be given by \(x'(n) = x(n+1)\). Let \(A \subset \mathbb{R}\). If \(A \in \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\), then \(A\) is determined, by \(Z_{3}\). Otherwise, let \(A'' = \{1^{\frown }x: x\in A\}\). It is easy to verify directly that \(A \equiv _{W} A''\). Consider the set \(A'\) defined as follows: \(x\in A'\) if and only if either \(x(0) = 0\) or else \(x(1) = 1\) and \(x' \in A\). Then, \(A'\) is the union of \(A''\) with the basic open set given by \(\langle 0\rangle \) and thus also \(A' \leq _{W} A\) by Theorem 20. The converse reduction \(A\leq _{W} A'\) is easy to verify. Clearly \(A'\) is determined in favor of Player I, who could begin the game by playing 0. Since \(A\) was arbitrary, the corollary follows. □

Theorem 20 is stated and proved in Andretta, Hjorth, and Neeman [13, Lemma 6(a)] under \({\mathsf{AD}} + {\mathsf{DC}}_{\mathbb{R}}\). The idea for their proof is the following: by \({\mathsf{AD}}+ {\mathsf{DC}}_{\mathbb{R}}\), Wadge’s lemma shows that the Wadge hierarchy is wellfounded all through \(\mathcal{P}(\mathbb{R})\). Let \(\alpha \) be the Wadge rank of \(A\). Then, the Wadge rank of \(A \cup C\) is \(1 + \alpha \). Therefore, if \(\alpha \) is infinite, it follows that \(A \cup C\) and \(A\) have the same Wadge rank, and Wadge’s lemma yields the conclusion. It might seem rather surprising that the theorem is also provable in \({\mathsf{ZFC}}\) with this much generality, let alone \(Z_{3}\). What we will do is construct an explicit continuous reduction of \(A\cup C\) to \(A\).

Let \(A\in \mathbb{R}\). For a finite sequence \(p \in \mathbb{N}^{<\mathbb{N}}\), we put \(A_{p} = \{x\in A: p\sqsubset x\}\). (This notation is only for §3.3.) We define the Wadge trees \(T^{\alpha}(A)\) by:

Below, we will make use of a result of Louveau [51, Lemma 1.4] (which in this particular case follows trivially) whereby

Lemma 23

For each \(\alpha \leq \omega \), \(T^{\alpha}(A)\) is a nonempty tree with no terminal nodes.

Proof

Suppose towards a contradiction that \(p \in T^{\alpha}(A)\) is a terminal node. Then, for each \(n\), we have \(A_{p^{\frown }n} \in \Delta (\alpha{-}\boldsymbol {\Sigma}^{0}_{1})\). Let \(k = \text{\textsc{lth}}(p)\). Thus, for every \(x\), we have

Since the sets \(A_{p^{\frown }n}\) belong to \(\alpha{-}\boldsymbol {\Sigma}^{0}_{1}\), \(A_{p}\) is easily seen to belong to \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\alpha{-}\boldsymbol {\Sigma}^{0}_{1})\) (the separating sets are the cones given by each \(p^{\frown }n\)). Similarly, we have

Since the sets \(A_{p^{\frown }n}\) belong to \((\alpha{-}\boldsymbol {\Sigma}^{0}_{1})^{\breve{}}\), \(\bar{A}_{p}\) is easily seen to belong to \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1}, \alpha{-}\boldsymbol {\Sigma}^{0}_{1})\). Thus, we have a contradiction by (3.4). □

Lemma 24

Suppose \(0\leq m < \alpha \leq \omega \). For each \(p \in T^{\alpha}(A)\), there exist \(x_{0}, x_{1} \in \mathbb{R}\) such that

1. (1)

   \(p \sqsubset x_{0}\) and \(p\sqsubset x_{1}\);

2. (2)

   \(x_{0} \in A\) and \(x_{1} \notin A\);

3. (3)

   \(x_{0}, x_{1} \in [T^{m}(A)]\).

Proof

Suppose towards a contradiction that no such \(x_{0}\), \(x_{1}\) exist. Thus, we have either \([T^{m}(A_{p})] \subset A_{p}\), or else \([T^{m}(A_{p})] \cap A_{p} = \varnothing\). Suppose without loss of generality that the first case occurs. By definition, for every extension \(q\) of \(p\) outside \(T^{m}(A)\), we have \(A_{q} \in \Delta (m{-}\boldsymbol {\Sigma}^{0}_{1})\). But then, we have

where \(O(q)\) denotes the basic open set generated by \(q\). This shows that

contradicting the fact that \(A_{p} \notin \Delta (\alpha{-}\boldsymbol {\Sigma}^{0}_{1})\). □

3.3.1 Proof of the treeability Theorem 20

We now continue to the proof of the theorem. Suppose that \(A\) and \(C\) are as in the statement of the theorem. We prove that \(A\cup C \leq _{W} A\) by explicitly exhibiting a winning strategy \(\sigma \) for Player II in the Wadge game \(G_{W}(A\cup C, A)\).

We describe a typical game according to \(\sigma \), first considering the case in which Player I plays within the closed set \(\bar{C}\); the other case will be covered afterwards.

Thus, for now, we suppose that Player I plays moves for the game \(G_{W}(A\cup C, A)\), yielding a position \(p \in \bar{C}\). As Player II, we copy Player I’s moves as long as \(p \in T^{\omega}(A)\).

Claim 25

If Player I plays \(x \in \bar{C} \cap [T^{\omega}(A)]\), then Player II wins.

Proof

By the part of the strategy just described, if Player I plays \(x \in \bar{C} \cap [T^{\omega}(A)]\), then Player II copies Player I’s moves, so that, since \(x \notin C\), we have

so Player II wins. □

Suppose that at some point in the game a position \(p \in \bar{C}\) is played by Player I such that \(p \in \bar{C}\setminus T^{\omega}(A)\). By definition, this means that \(A_{p} \in \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\). By Louveau [51, Lemma 1.23], we have

where the rightmost class denotes the Wadge class of unions of \({<}\omega{-}\boldsymbol {\Sigma}^{0}_{1}\) sets partitioned by \(\boldsymbol {\Sigma}^{0}_{1}\) sets, i.e., those sets of the form

where \(B_{l} \in {<}\omega{-}\boldsymbol {\Sigma}^{0}_{1}\) and the sets \(D_{l} \in \boldsymbol {\Sigma}^{0}_{1}\) form a partition of the Baire space. Let \(B\) be represented as in (3.5).

After such a position \(p\) is reached, let \(p^{II}\) be Player II’s current position, so \(p^{II} \in T^{\omega}(A)\). As Player II, we wait until Player I reaches a position in \(D_{l}\) for some \(l\in \mathbb{N}\) and pass in all our turns until then. Such a position must be reached after finitely many moves, because the sets \(D_{l}\) form an open partition of the Baire space. Let \(n\) be least such that \(B_{l} \in n{-}\boldsymbol {\Sigma}^{0}_{1}\). Denote the position reached by \(p^{I}\) and suppose for definiteness that \(n\) is even and nonzero. Thus, we have \(p^{I} \in D_{l}\). The idea is that from now on, we can observe Player I’s moves and continuously predict whether they will belong to \(A\) since for reals \(x\) extending \(p^{I}\) we have

(modifying the representation accordingly if \(n\) is odd). In a way, we have simplified the Wadge game \(G_{W}(A\cup C, A)\) to one where the set on the left-hand side has complexity \(n{-}\boldsymbol {\Sigma}^{0}_{1}\). For the argument below, we put \(B_{-1} := \varnothing \).

Back to the Wadge game \(G_{W}(A\cup C, A)\). By Lemma 24, there is some real \(x_{n}\) extending \(p^{II}\) such that

[In the case where \(n\) is odd, we instead find some \(x_{n}\) such that \(x \in A\) and \(x \in [T^{n}(A)]\).] We continue describing the construction of \(\sigma \) by induction on \(n\).

Still assuming that Player I plays positions within \(\bar{C}\), we have Player II play precisely the digits of \(x_{n}\) as long as Player I plays positions within the closed set \(\bar{B}_{l,n-1}\) (\(B_{l,n-1}\) is the largest set in the \(n{-}\boldsymbol {\Sigma}^{0}_{1}\) representation of \(B_{l}\) given above).

Claim 26

If Player I plays some \(x\) in \(\bar{C}\cap \bar{B}_{l,n-1}\), then Player II wins.

Proof

This follows from the part of the strategy just described. For such an \(x\), we have:

The second inequality in the displayed equation follows from the fact that \(x\) extends \(p^{I}\) and

In this run of the game, Player II plays \(x_{n} \notin A\), so Player II wins. □

Suppose now that at some point during the game Player I plays a position in \(B_{l, n-1}\). Let \(k \leq n-1\) be least such that the position belongs to the open set \(B_{l, k}\) and denote the position by \(q^{I}\). Denote by \(q^{II}\) the position reached by Player II immediately before Player I plays \(q^{I}\). We have now in essence simplified the Wadge game \(G_{W}(A\cup C, A)\) to one where the set on the left-hand side has complexity \(k{-}\boldsymbol {\Sigma}^{0}_{1}\). Use Lemma 24 to find some \(x_{k}\) extending \(q^{II}\) such that

if \(k\) is even, or

if \(k\) is odd. The key point is that this is possible because \(q^{II} \in T^{n}(A)\), since \(q^{II}\) is an initial segment of \(x_{n} \in [T^{n}(A)]\), so the hypothesis of Lemma 24 is satisfied. Moreover, since \(q^{I} \in B_{l, k}\), every extension \(y\) of \(q^{I}\) in \(\bar{C}\) satisfies

(for even \(k\), and mutatis mutandis for odd \(k\)). Hence, we can prove the analog of Claim 26 and, inductively on \(k\), the strategy just described guarantees a win for Player II, provided that Player I plays within \(\bar{C}\), so we now need to consider the case in which she does not.

The success of the construction hinges on the fact that even in the case \(n = 0\), Player II only ever plays moves in \(T^{0}(A)\). Hence, if at any point during the game Player I moves into the open set \(C\), Player II is at a position \(r \in T^{0}(A)\). By the definition of \(T^{0}(A)\), there is some extension \(x_{0}\) of \(r\) such that \(x_{0} \in A\). From this point on, Player II can simply play \(x_{0}\). Since Player I has moved into \(C\) and \(C\) is open, Player I’s play is guaranteed to remain inside \(A\cup C\), and Player II’s play is guaranteed to be \(x_{0}\), which belongs to \(A\), so the play is won by Player II. This completes the description of \(\sigma \). Along its description we have verified that it is indeed a winning strategy for Player II.

Finally, notice that the strategy \(\sigma \) was obtained directly from the trees \(T^{\alpha}(A)\) whose existence is provable in \(Z_{3}\) (for any \(A\subset \mathbb{R}\)). This completes the proof of the theorem.

3.3.2 Effective forms of the treeability theorem

We will need an effective form of Theorem 20 below, to apply in situations in which we do not have access to \(Z_{3}\). In order to do this, it seems necessary to impose restrictions on the complexity of \(A\).

Definition 27

\((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) is the principle that \(L_{\omega_{\omega}^{x}}[x]\) exists for all \(x\in \mathbb{R}\).

Theorem 28

Suppose that \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) holds. Let \(A\subset \mathbb{R}\) be a \(\boldsymbol {\Delta}^{1}_{1}\) set such that \(A \leq _{W} B\) for no \(B\in \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\). Then, \(A \cup C \leq _{W} A\) for any open set \(C\).

Proof

The idea is to carry out the proof of Theorem 20 while taking measures to ensure that the complexity of the strategy \(\sigma \) constructed is not too high. In order to do this, we will need to prove the lightface form of the theorem. By relativizing, let us suppose that \(A \in \Delta ^{1}_{1}\). We define the following effective forms of the trees \(T^{\alpha}(A)\) for \(0\leq \alpha \leq \omega \):

Lemma 29

\(T^{\alpha}(A)\) exists for all \(\alpha \leq \omega \).

Proof

It follows from the definition that \(T^{m}(A)\) is first-order definable over \(L_{\omega _{m+1}^{ck}}\). \(T^{\omega}(A)\) is first-order definable over \(L_{\omega _{\omega +1}^{ck}}\). Hence, existence follows from \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\). □

We now need the analogs of Lemma 23 and Lemma 24.

Lemma 30

For each \(\alpha \leq \omega \), \(T^{\alpha}(A)\) is a nonempty tree with no terminal nodes.

Proof

This follows the proof of Lemma 23. Suppose towards a contradiction that \(p \in T^{\alpha}(A)\) is a terminal node and thus \(A_{p^{\frown }n} \in \Delta (\alpha{-}\Sigma ^{0}_{1})(x_{n})\) for some \(x_{n} \in L_{\omega _{\alpha +1}^{ck}}\). The argument of Lemma 23 leads to a contradiction by showing that \(A_{p} \in \Delta (\alpha{-}\boldsymbol {\Sigma}^{0}_{1})\); the only step missing is to check that the complexity of the parameters does not grow too quickly and thus \(A_{p} \in \Delta (\alpha{-}\Sigma ^{0}_{1})(x)\) for some \(x \in L_{\omega _{\alpha +1}^{ck}}\). The sentence

is true for all \(n\) by hypothesis. Moreover, it says

By the Spector-Gandy theorem (see e.g., Moschovakis [69]) this is \(\Pi ^{1}_{1}\) in any real coding \(L_{\omega _{\alpha}^{ck}}\) and thus \(\Sigma _{1}\) over \(L_{\omega _{\alpha +1}^{ck}}\) by Barwise-Gandy-Moschovakis [15]. By the admissibility of \(\omega _{\alpha +1}^{ck}\), we can find a uniform bound \(\gamma < \omega _{\alpha +1}^{ck}\) such that \(L_{\gamma}\) contains some such \(x_{n}\) for all \(n\in \mathbb{N}\). Letting \(x\) code \(L_{\gamma}\), we then have \(A_{p} \in \Delta (\alpha{-}\Sigma ^{0}_{1})(x)\). □

Lemma 31

Suppose \(0\leq m < \alpha \leq \omega \). For each \(p \in T^{\alpha}(A)\), there exist \(x_{0}, x_{1} \in \mathbb{R}\) such that

1. (1)

   \(p \sqsubset x_{0}\) and \(p\sqsubset x_{1}\);

2. (2)

   \(x_{0} \in A\) and \(x_{1} \notin A\);

3. (3)

   \(x_{0}, x_{1} \in [T^{m}(A)]\).

Proof

This is proved by imitating the proof of Lemma 24. As before, the argument leads to a contradiction by showing that \(A_{p} \notin \Delta (\alpha{-}\Sigma ^{0}_{1})(x)\) for some \(x\in \mathbb{R}\). By examining the proof, we see that

where \(x\) is some real which computes \(T^{m}(A)\) and all parameters \(x_{q}\) occurring in the definition of each \(A_{q}\), for \(q \notin T^{m}(A)\). Since \(T^{m}(A)\) is first-order definable over \(L_{\omega _{m+1}^{ck}}\) and the parameters \(x_{q}\) all belong to \(L_{\omega _{m+1}^{ck}}\), we see that \(x \in L_{\omega _{m+2}^{ck}}\subset L_{\omega _{\alpha +1}^{ck}}\), contradicting the fact that \(p \in T^{\alpha}(A)\). □

The rest of the proof follows that of Theorem 20 without much difficulty. □

We also mention a version of the Treeability Theorem for \(\boldsymbol {\Delta}^{1}_{n}\) Wadge classes.

Definition 32

\((\boldsymbol {\Pi}^{1}_{n+1}{-}{\mathsf{CA_{0}}})^{+}\) is the principle that for each \(x\in \mathbb{R}\), there is a sequence \(\{X_{i}: i\leq \omega +1\}\) of sets such that \(X_{i} \prec _{\Sigma _{n}} H(\omega _{1})\) for all \(i\leq \omega +1\) and \(X_{i} \in X_{i+1}\) for all \(i\leq \omega \).

Theorem 33

Suppose that \((\boldsymbol {\Pi}^{1}_{n+1}{-}{\mathsf{CA_{0}}})^{+}\) holds. Let \(A\subset \mathbb{R}\) be a \(\boldsymbol {\Delta}^{1}_{n+1}\) set such that \(A \leq _{W} B\) for no \(B\in \Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\). Then, \(A \cup C \leq _{W} A\) for any open set \(C\).

Proof

This follows the proof of Theorem 28. The main difference worth noting is the definition of the trees, which is given by:

where \(\{X_{i}: i\leq \omega +1\}\) is the sequence witnessing \((\boldsymbol {\Pi}^{1}_{n+1}{-}{\mathsf{CA_{0}}})^{+}\) for \(x = \) the parameter used in the definition of \(A\). □

3.3.3 Effective treeability

According to the Treeability Theorem, every Wadge class not included in \(\Delta (\omega{-}\boldsymbol {\Sigma}^{0}_{1})\) is treeable, provably so in \(Z_{3}\). Theorem 28 yields the same conclusion over \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) for Borel classes. Unfortunately, the Wadge reductions constructed in both instances are not recursive (which is why \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) is needed in the first place. Hence, our arguments do not yield the lightface form of the conclusion of the treeability theorem. For our purposes, it will be necessary to consider a weak form of this lightface result.

Definition 34

A Wadge class \(\boldsymbol {\Gamma}\) is effectively treeable if for all \(x\in \mathbb{R}\) there is \(y\in \mathbb{R}\) such that

The point of effective treeability is that even supposing that \(\boldsymbol {\Gamma}\) is treeable, it could in principle happen – in cases in which we do not have access to choice principles – that the real parameters witnessing that sets in \(\Sigma ^{0}_{1} \vee \Gamma \) belong to \(\boldsymbol {\Gamma}\) cannot all be collected into one. Trivially, effective treeability for Borel sets follows from treeability using \(\boldsymbol {\Sigma}^{1}_{2}{-}{\mathsf{AC_{0}}}\), but the proof of Theorem 28 shows that this assumption can be avoided.

Corollary 35

Suppose that \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) holds. Then, every Borel Wadge class is effectively treeable.

Proof

Given \(x\in \mathbb{R}\) and a treeable Borel class \(\boldsymbol {\Gamma}\), the proof of Theorem 28 shows that

where \(y\) is a real coding \(L_{\omega _{\omega +2}^{x}}[x]\). Such a real exists by \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\). □

Corollary 36

Suppose that \(\boldsymbol {\Gamma}\) is effectively treeable and let \(x\in \mathbb{R}\). For each standard \(k\in \mathbb{N}\), there is \(y\in \mathbb{R}\) such that all sets obtained from sets in \(\Gamma (x)\) by applying \(k\) unions with sets in \(\Sigma ^{0}_{1}(x)\) and \(k\) intersections with sets in \(\Pi ^{0}_{1}(x)\) in any order belong to \(\Gamma (y)\).

Proof

Immediate by external induction. □

It seems one can weaken the hypothesis of \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) in the statement of Theorem 28 to \({\mathsf{ATR_{0}}}+ \boldsymbol {\Pi}^{1}_{1}{-}\mathsf{IND}\) by appealing to the proofs of the results of Day, Greenberg, Harrison-Trainor, and Turetsky [21], though we have not checked this carefully. Nonetheless, \((\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}})^{+}\) will be an adequate hypothesis for our purposes.

4.1 Strategic replacement

Our medium-term plan shall from now on be the statement and proof of three Separation Reduction Theorems. The idea behind these theorems is to reduce a determinacy principle for some Wadge class described in terms of separated unions or differences to a determinacy principle for a smaller Wadge class, possibly with the aid of a certain set-existence axiom. In the theory of infinite games, determinacy-transfer theorems of the form

are useful and common. The phenomenon of transfer was first explored by Kechris and Woodin [45] in their proof that the Axiom of Determinacy is equivalent to the existence of arbitrarily large cardinals satisfying the strong partition property (assuming \(V = L(\mathbb{R})\)). Other transfer theorems have been obtained by Kechris and Solovay [44] and by others. Our first Separation Reduction Theorem will be of this kind. However, it will be phrased in extremely effective terms and will in fact be provable in \({\mathsf{RCA_{0}}}\). This quickly leads to an obstacle which can be solved with the help of the notion of Strategic Replacement.

Definition 37

Let \(\boldsymbol {\Gamma}\) be a Wadge class. The principle of \(\boldsymbol {\Gamma}\)-Strategic Replacement (\(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\)) is the assertion that for all countable sequences \(\{A_{i} :i\in \mathbb{N}\}\) of sets in \(\boldsymbol {\Gamma}\) there is a countable sequence \(\{\sigma _{i}: i\in \mathbb{N}\}\) such that for each \(i\in \mathbb{N}\), \(\sigma _{i}\) is a winning strategy for the game \(G(A_{i})\) (for one of the players).

Strategic Replacement is a strong form of determinacy which combines the existence of winning strategy with a weak form of the Axiom of Replacement, since it demands that a countable collection of games can be won by strategies which can be collected into a countable set. When dealing with Borel sets, the existence of winning strategies is absolute to \(L\), so the use of Replacement amounts to an application of a fragment of the Axiom of Choice. Hence, we obtain:

Lemma 38

Suppose \(\boldsymbol {\Gamma}\) is a Borel Wadge class. Suppose moreover that \(\boldsymbol {\Gamma}\)-determinacy and \(\boldsymbol {\Sigma}^{1}_{2}{-}\mathsf{AC}\) hold. Then, \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) holds.

Proof

Immediate. □

Let us also point out the following simple fact:

Lemma 39

Suppose that \(\boldsymbol {\Gamma}\) is a Borel Wadge class. Suppose moreover that \({\mathsf{KP}}\) and \(\boldsymbol {\Gamma}\)-determinacy hold. Then, \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) holds.

Proof

Immediate from Lemma 38 (or directly from \({\mathsf{KP}}\)). □

Thus, the distinction between determinacy and strategic replacement is only relevant within the context of weak theories of arithmetic or of set theory. However, this distinction is important conceptually and it, as well as the interrelation between the two notions, will figure in the arguments below. The intuition is that the principle of \(\boldsymbol {\Gamma}\)-Strategic Replacement is much better behaved than that of \(\boldsymbol {\Gamma}\)-Determinacy for Wadge classes \(\boldsymbol {\Gamma}\) that to not have strong closure properties. The First Separation Reduction Theorem will be a strategic replacement transfer theorem of the form

which applies to a very broad collection of classes \(\boldsymbol {\Gamma}\). For many of these \(\boldsymbol {\Gamma}\), the corresponding determinacy transfer principle is not provable in \({\mathsf{RCA_{0}}}\). While it is provable in theories such as \({\mathsf{KP}}\) (by Lemma 39), the proof becomes clearer when phrased in terms of strategic replacement.

Theorem 40

Separation Reduction, I

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class.

1. (1)

   The following are equivalent:

   1. (a)

      \(\boldsymbol {\Gamma}\)-Strategic Replacement;

   2. (b)

      \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}, \breve{\boldsymbol {\Gamma}})\)-Strategic Replacement.

2. (2)

   If \(\boldsymbol {\Gamma}\) is closed under complements, then the following are equivalent:

   1. (a)

      \(\boldsymbol {\Gamma}\)-Strategic Replacement;

   2. (b)

      \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\)-Determinacy.

In addition to the first clause of the theorem on the transfer of strategic replacement, the second clause of the theorem phrases this principle in terms of determinacy for a slightly larger Wadge class. In practice, the theorem will often be applied to classes \(\boldsymbol {\Gamma}\) obtained as the union of smaller classes \(\boldsymbol {\Gamma}_{l}\) or of a class \(\boldsymbol {\Gamma}'\) and its dual \(\breve{\boldsymbol {\Gamma}}'\). Typically, this union will be non-trivial, \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma})\) will be a non-selfdual Wadge class of countable cofinality, and \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\) will also be a Wadge class (in fact – a degree!) and it will contain \(\boldsymbol {\Gamma}\) strictly. We shall see later that this equivalence is not vacuous, in that there are classes \(\boldsymbol {\Gamma}\) and models of \({\mathsf{RCA_{0}}}\) which satisfy \(\boldsymbol {\Gamma}\)-Determinacy but not \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\).

Let us turn to the proof of the theorem and then proceed to derive consequences from it (cf. §4.3).

4.2 Proof of the first separation reduction theorem

We begin with the proof of (1). Let \(\boldsymbol {\Gamma}\) be as in the statement of the theorem, so that \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) holds. The hypothesis requires that \(\boldsymbol {\Gamma}\) be closed under intersections with \(\boldsymbol {\Pi}^{0}_{1}\) sets and unions with \(\boldsymbol {\Sigma}^{0}_{1}\) sets. Observe that these assumptions hold of \(\breve{\boldsymbol {\Gamma}}\) as well, for if \(A\in \boldsymbol {\Gamma}\) and \(C \in \boldsymbol {\Pi}^{0}_{1}\), then

similarly, \(\breve{\boldsymbol {\Gamma}}\) is closed under unions with \(\boldsymbol {\Sigma}^{0}_{1}\) sets.

We first argue that all sets in \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}, \breve{\boldsymbol {\Gamma}})\) are determined. To do so, we assume without loss of generality (by relativizing to a Turing cone if necessary) that the lightface class \(\Gamma \) is defined – so that \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma})\) is also defined – and prove that all sets in \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma})\) are determined. The result then follows from relativizing.

Consider a set in \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma})\), say \(W\). Then, \(W\) has the form

where for each \(l\in \mathbb{N}\) we have \(A_{l} \in \Gamma \), \(C_{l} \in \Sigma ^{0}_{1}\), \(B \in \breve{\Gamma}\), and \(W\cap C_{l} = A_{l}\cap C_{l}\). We are assuming by relativization that, since \(W \in \Gamma \) and \(\Gamma \) is a lightface class, \(W\) has a recursive code \(c_{W}\).

Consider a fixed enumeration of all (countably many) sets in \(\Gamma \). Applying \(\Gamma{-}{\mathsf{SR}}\) to this enumeration, we obtain a set \(G^{*}\) collecting winning strategies for all such games. Observe that effectively from \(G^{*}\) we can recover the index set \(G\) of all games in \(\Gamma \) for which Player I has a winning strategy. We will use this index set – as well as the collection \(G^{*}\) – below.

Consider the game \(G(H)\) with the following rules: given a play \(x\) of the game,

1. (1)

   If \(x \notin C_{l}\) for any \(l\in \mathbb{N}\), then Player I wins if and only if \(x \in B\); otherwise Player II wins.

2. (2)

   If at some point in the game a play \(p\) is reached such that \(p \in C_{l}\) for some \(l\in \mathbb{N}\), then let \(l\) be least such. The game ends immediately at this point. Player I wins this run of \(G(H)\) if and only if she has a winning strategy for \(G((A_{l})_{p})\) (recall that this is defined exactly like the game \(G(A_{l})\), except that the starting position is \(p\)). Otherwise, Player II wins.

Let us compute the complexity of the winning set \(H\). The second clause in the definition of \(G(H)\) asks whether \(f_{l}(p)\) belongs to \(G\), where \(f_{l}\) is some fixed recursive function, and \(f_{l}\) can be obtained uniformly in \(l\) and \(c_{W}\). Thus, the second clause asks whether for some \(l \in \mathbb{N}\), some condition in \(\Delta ^{0}_{1}(G)\) holds. It follows that the second clause is a condition in \(\Sigma ^{0}_{1}(G)\).

The first clause asks whether

Since \(\breve{\boldsymbol {\Gamma}}\) is closed under intersection with \(\boldsymbol {\Pi}^{0}_{1}\) sets, this is a condition in \(\breve{\boldsymbol {\Gamma}}\). Hence, we have

(Note: it is not immediately clear whether \(H\) belongs to the lightface class \(\breve{\boldsymbol {\Gamma}}(G)\), but this is not necessary.) By hypothesis, we have \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), which yields \(\boldsymbol {\Gamma}\)-determinacy and thus \(\breve{\boldsymbol {\Gamma}}\)-determinacy, so \(H\) is determined.

Suppose that Player I has a winning strategy \(\sigma \) for \(G(H)\); we describe a winning strategy for \(W\). Play according to \(\sigma \) until a position \(p\) is reached such that \(p\in C_{l}\) for some \(l\in \mathbb{N}\), if ever. If this happens, let \(l\) be least such. At this point, the use of \(\sigma \) guarantees the existence of a winning strategy \(\sigma _{p}\) for \(G((A_{l})_{p})\); continue playing according to \(\sigma _{p}\), where \(\sigma _{p}\) is the strategy for \(G((A_{l})_{p})\) in \(G^{*}\).

Suppose \(x\) is a run of the game played according to \(\sigma \). If \(x\notin C_{l}\) for any \(l\), then by choice of \(\sigma \) we have \(x \in B\); thus \(x\in W\). If \(x\in C_{l}\) for some \(l\), then let \(p\) be the first position such that \(p \in C_{l}\) and let \(l\) be least such. Then \(x\) is played according to \(\sigma _{p}\) and thus \(x\in A_{l}\). This means that

In either case we have \(x \in W\). Note that in this case the winning strategy for \(W\) is recursive in \((G^{*},\sigma )\), uniformly in \(c_{W}\).

Suppose now that Player II has a winning strategy \(\tau \) for \(G(H)\); we describe a winning strategy for \(W\). Play according to \(\tau \) until a position \(p\) is reached such that \(p\in C_{l}\), if ever. At this point, the use of \(\tau \) guarantees the non-existence of a winning strategy for Player I for \(G((A_{l})_{p})\). By hypothesis, all sets in \(\Gamma \) are determined, so there is a winning strategy \(\tau _{p}\) for Player II for \(G((A_{l})_{p})\); continue playing according to \(\tau _{p}\), where \(\tau _{p}\) is the strategy for \(G((A_{l})_{p})\) in \(G^{*}\).

Suppose \(x\) is a run of the game played according to \(\tau \). If \(x\notin C_{l}\) for all \(l\), then by choice of \(\tau \) we have \(x \notin B\); thus

If \(x\in C_{l}\) for some least \(l\), then let \(p\) be the first position such that \(p \in C_{l}\) and let \(l\) be least such. Then \(x\) is played according to \(\tau _{p}\) and thus \(x\notin A_{l}\). Since

we have

Thus again \(\tau \) is as desired. As constructed, the strategy is recursive in \((G^{*},\sigma )\), uniformly in \(c_{W}\). This completes the proof that all sets in \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma})\) are determined.

To obtain \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma}){-}{\mathsf{SR}}\), let \(\vec{W} = \{W_{i}:i\in \mathbb{N}\}\) be a countable sequence of sets in \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma})\). From \(\vec{W}\) we can uniformly compute the sequence \(\vec{G}(H) = \{G(H_{i}):i\in \mathbb{N}\}\) of auxiliary games corresponding to each \(W_{i}\) as above. By Corollary 36, these games all belong to \(\breve{\Gamma}(y)\) for some \(y\). By hypothesis, we have \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), so we can uniformly compute a sequence \(\{\sigma _{i}:i\in \mathbb{N}\}\) of winning strategies for the games \(G(H_{i})\). (This is where the hypothesis of effective treeability – versus plain treeability – is used: the sequence of definitions of the auxiliary games is a set.) Uniformly for each \(i\), we can compute, from the oracle \((\vec{W}, \sigma _{i}, G^{*})\), a winning strategy \(\sigma ^{*}_{i}\) for \(W_{i}\) (for one of the players), as needed. This establishes \(\mathsf{LU}(\Sigma ^{0}_{1},\Gamma ,\breve{\Gamma}){-}{\mathsf{SR}}\). The boldface result follows from relativizing. This completes the proof of statement (1) of the theorem.

Let us now prove statement (2). Observe that one of the implications follows from (1), since

(trivially). Thus, according to clause (1) of the theorem, we have

Hence, it suffices to assume that \(\boldsymbol {\Gamma}\) is closed under complements and that all sets in \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\) are determined and prove that \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) holds.

Let \(\vec{W} = \{W_{i}:i\in \mathbb{N}\}\) be a countable family of sets in \(\boldsymbol {\Gamma}\). We consider an auxiliary game \(H\). In this game, Player II begins by choosing a number \(i\in \mathbb{N}\). In the remainder of the game, the players will play the game \(G(W_{i})\). Before doing so, Player I decides whether she will take on the role of Player I or of Player II in \(G(W_{i})\). The winner of the subgame \(G(W_{i})\) is the winner of \(H\). Thus, Player I wins a run \(x\) of the game if and only if letting \(i\in \mathbb{N}\) be Player II’s first move, one of the following holds:

1. (1)

   Player I’s first move (after Player II’s move) is 1 and \(x \upharpoonright [2,\infty ) \in W_{i}\), or

2. (2)

   Player I’s first move (after Player II’s move) is 2 and \(x \upharpoonright [2,\infty ) \notin W_{i}\).

Clearly, this is a union of sets in \(\boldsymbol {\Gamma}\) (namely, the sets \(W_{i}\) and their complements) separated by \(\Sigma ^{0}_{1}\) sets. Indeed, the separating sets depend only on the first two plays and are thus in \(\Delta ^{0}_{1}\). Player II’s winning condition is also in a union of sets in \(\boldsymbol {\Gamma}\) separated by \(\Delta ^{0}_{1}\) sets since, letting \(i\) be as above, Player II wins if one of the following holds:

1. (1)

   Player I’s first move (after Player II’s move) is 1 and \(x \upharpoonright [2,\infty ) \notin W_{i}\),

2. (2)

   Player I’s first move (after Player II’s move) is 2 and \(x \upharpoonright [2,\infty ) \in W_{i}\), or

3. (3)

   Player I’s first move is neither 1 nor 2.

Thus, the payoff set belongs to the class \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\) and hence the game is determined. Clearly, Player II cannot have a winning strategy for this game, for letting \(i\) be the first move given by the strategy, say \(\tau \), \(\tau \) would require that Player II be able to defeat Player I taking any role in the game \(W_{i}\), which is impossible. Thus, Player I has a winning strategy, \(\sigma \). Clearly, from \(\sigma \) one can compute a family of strategies for the games \(W_{i}\) (for one of the players), as required. This completes the proof of the First Separation Reduction Theorem.

4.2.1 Discussion

We observe that, in general, the principle of \(\boldsymbol {\Gamma}\)-Determinacy is not equivalent to \(\boldsymbol {\Gamma}\)-Strategic Replacement, as shown by the following lemma:

Lemma 41

There are Wadge classes \(\boldsymbol {\Gamma}\) for which

Proof

Let

Then, \(L_{\omega _{\omega}^{ck}}\) is a model of \(\boldsymbol {\Gamma}\)-Determinacy, but not of \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), since infinite sequences of strategies of \(\boldsymbol {\Gamma}\) games are in general only \(\Sigma _{1}\)-definable over \(L_{\omega _{\omega}^{ck}}\). This is because for each \(n\in \mathbb{N}\) there is an \((n+1){-}\boldsymbol {\Sigma}^{0}_{1}\) game any winning strategy for which computes the theory of \(L_{\omega _{n}^{ck}}\). The proof of this is a simple modification of the usual argument for \(2{-}\boldsymbol {\Sigma}^{0}_{1}\) (cf. e.g., Tanaka [81] for the argument; cf. also Theorem 167 in §7.2.1 for other general forms of this result). □

Although \(\boldsymbol {\Gamma}\)-Determinacy is in general not enough to guarantee \(\boldsymbol {\Gamma}\)-Strategic Replacement, it is almost enough. By Theorem 40, \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\) suffices. In the example above, \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\) is extremely close to \(\boldsymbol {\Gamma}\); indeed, there is no Wadge class \(\boldsymbol {\Gamma}'\) such that

This is a general phenomenon: when restricting to Borel sets, all Wadge degrees \(\boldsymbol {\Gamma}\) such that

are of the form \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}'))\) for some \(\boldsymbol {\Gamma}'\) (this is a consequence of Louveau [51, Lemma 1.23]).

4.3 Consequences of the first separation reduction theorem

We now apply the First Separation Reduction Theorem to obtain information about various Wadge classes and their associated determinacy hypotheses.

Corollary 42

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class. Then, for each countable ordinal \(\alpha \), the following are equivalent:

1. (1)

   \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}){-}{ \mathsf{SR}}\); and

2. (2)

   \(S((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}){-}{ \mathsf{SR}}\).

Proof

By Lemma 210 in Appendix B, \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma})\) is also effectively treeable. By Theorem 40 applied to \(\boldsymbol {\Gamma}= S(\alpha{-}\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\), we obtain \(\boldsymbol {\Gamma}^{*}{-}{\mathsf{SR}}\), where

By Lemma 11 all sets in \(S((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma})\) are in \(\boldsymbol {\Gamma}^{*}\), so the result follows. □

The following is the corresponding result for limit ordinals:

Corollary 43

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class. Then, for each limit ordinal \(\lambda \), the following are equivalent:

1. (1)

   \(S(\lambda{-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}){-}{ \mathsf{SR}}\); and

2. (2)

   \(S({<}\lambda{-}\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}){-}{ \mathsf{SR}}\),

where

Proof

First notice that \(S({<}\lambda{-}\boldsymbol {\Sigma}^{0}_{1})\) is effectively treeable by Lemma 210 in Appendix B. Thus, by Lemma 13 we have

Hence, the result follows from Theorem 40 applied to \(S({<}\lambda{-}\boldsymbol {\Sigma}^{0}_{1})\). □

Corollary 44

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class. Then, the following are equivalent:

1. (1)

   \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\); and

2. (2)

   \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}){-}{ \mathsf{SR}}\),

Proof

Since \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}) = \mathsf{LU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma})\), the result follows from an application of Theorem 40. □

The next two applications of Theorem 40 concern the hierarchy of differences separated by open sets.

Corollary 45

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class. Then, for each ordinal \(\alpha \neq 0\), the following are equivalent:

1. (1)

   \(\mathsf{SD}_{\alpha}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma}){-}{\mathsf{SR}}\); and

2. (2)

   \(\mathsf{SD}_{\alpha +1}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma}){-}{\mathsf{SR}}\).

Proof

If \(W \in \mathsf{SD}_{\alpha +1}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\), then \(W\) is of the form

where \(W' \in \mathsf{SD}_{\alpha}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\), \(C_{\alpha }\in \boldsymbol {\Sigma}^{0}_{1}\), \(A_{\alpha }\in \boldsymbol {\Gamma}\), and \(W' \subset C_{\alpha }\subset A_{\alpha}\). Thus,

Let \(\boldsymbol {\Lambda}\) be the set-theoretic union of \(\breve{\boldsymbol {\Gamma}}\) and \(\mathsf{SD}_{\alpha}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\). Then, \(\boldsymbol {\Lambda}\) is effectively treeable. Moreover, \(\boldsymbol {\Lambda}{-}{\mathsf{SR}}\) holds. By (4.2), we have

and hence the result follows from Theorem 40. □

Corollary 46

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class. Then, for each limit ordinal \(\lambda \), the following are equivalent:

1. (1)

   \(\mathsf{SD}_{{<}\lambda}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma}){-}{\mathsf{SR}}\); and

2. (2)

   \(\mathsf{SD}_{\lambda}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma}){-}{\mathsf{SR}}\);

where

Proof

If \(W \in \mathsf{SD}_{\lambda}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\), then \(W\) is of the form

where each \(A_{\eta}\) belongs to \(\boldsymbol {\Gamma}\) and each \(C_{\eta}\) belongs to \(\boldsymbol {\Sigma}^{0}_{1}\). Let \(\{\lambda _{l} : l\in \mathbb{N}\}\) be an infinite sequence converging to \(\lambda \) and put

so that

Clearly this representation of \(W\) shows that

so the result follows by an application of Theorem 40. □

The next application simply points out that, if one has access to enough transfinite induction, then one can propagate Strategic Replacement to a great extent:

Corollary 47

Suppose that \(\boldsymbol {\Pi}^{1}_{n+2}{-}{\mathsf{TI}}\) holds. Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable \(\boldsymbol {\Delta}^{1}_{n}\) Wadge class. Then, the following are equivalent for any countable ordinal \(\alpha \):

1. (1)

   \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\),

2. (2)

   \(\mathsf{SD}_{\alpha}(\boldsymbol {\Sigma}^{0}_{1},\mathsf{SU}( \boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})){-}{\mathsf{SR}}\), and

3. (3)

   \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma}){-}{ \mathsf{SR}}\).

Proof

Immediate from the previous corollaries by transfinite induction. The main fact to point out is that the statement \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) is \(\boldsymbol {\Pi}^{1}_{n+2}\) if \(\boldsymbol {\Gamma}\) is \(\boldsymbol {\Delta}^{1}_{n}\)-definable. □

Corollary 47 is optimal under its hypotheses, in the sense that \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\) and \(\mathsf{SD}_{\alpha}(\boldsymbol {\Sigma}^{0}_{1},\mathsf{SU}( \boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma}))\) cannot generally be replaced by any strictly larger Wadge classes. For instance, in the case \(\boldsymbol {\Gamma}= \boldsymbol {\Sigma}^{0}_{2}\), we have

so any more Strategic Replacement would yield \(2{-}\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy, which is strictly stronger than \(\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy (e.g., over \({\mathsf{KPi}}\)).

We want to emphasize that the results so far impose no upper bound on the complexity of \(\boldsymbol {\Gamma}\). This leads us to general determinacy-transfer theorems which yield new results in the context of \({\mathsf{ZFC}}\) and related theories.

Corollary 48

Suppose that \({\mathsf{KP}}\) holds and ℝ exists. Let \(\boldsymbol {\Sigma}^{1}_{<\omega}\) be the pointclass of all projective sets and \(\boldsymbol {\Sigma}^{1,*}_{<\omega}\) be as in Theorem 40. Then, the following are equivalent:

1. (1)

   \(\boldsymbol {\Sigma}^{1}_{<\omega}{-}\)Determinacy,

2. (2)

   \(S(\boldsymbol {\Delta}^{0}_{2},\boldsymbol {\Sigma}^{1}_{{<}\omega}){-}\)Determinacy.

Proof

Immediate from Corollary 47. □

We remark that in this case the class \(S(\boldsymbol {\Delta}^{0}_{2},\boldsymbol {\Sigma}^{1}_{{<}\omega})\) is strictly larger than the pointclass of all projective sets, since e.g., it (strictly) includes the class \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Sigma}^{1}_{< \omega})\), in which the unions may diagonalize over \(\boldsymbol {\Sigma}^{1}_{n+1}\)-complete sets.

The idea behind Corollary 48 can be applied more generally to any Wadge class such that

We do not state this as a theorem since a stronger abstract determinacy transfer theorem will follow from results in later sections. We do, however, mention the following application of the First Separation Reduction Theorem. It is a strengthening of the determinacy transfer theorem of Kechris-Woodin [45] and Neeman [71].

Corollary 49

Suppose that \(Z_{2}\) holds. Then,^{Footnote 3}

where

Proof

It is well known that \(\boldsymbol {\Sigma}^{1}_{n+1}\)-Determinacy implies \(\Game ^{n}({<}\omega ^{2}{-}\boldsymbol {\Pi}^{1}_{1})\)-Determinacy: this follows from theorems of Woodin (see Müller-Schindler-Woodin [70]) and of Neeman [71] by showing that \(\boldsymbol {\Sigma}^{1}_{n+1}\)-Determinacy implies the existence of the inner models \(M_{n}^{\sharp}(x)\) for all \(x\in \mathbb{R}\) and using these to prove determinacy (the result for \(n = 0\) is due to Martin [55] and Harrington [37]). This proof can be carried out within Second-Order Arithmetic (this requires the boldface determinacy hypothesis). Then, Theorem 40 yields \(\boldsymbol {\Gamma}\)-Determinacy, where

Finally, transfinite induction, using Corollary 47, yields the result. □

Later on, we will prove strengthenings of Corollary 49. However, we have included this corollary because we suspect that full \(Z_{2}\) is not necessary for the result as stated (though we have not verified this carefully), and that the conclusion of the corollary is optimal with a suitably chosen subsystem of \(Z_{2}\) as the base theory (possibly depending on \(n\)). More specifically, we conjecture the following:

Conjecture 50

Optimal Transfer, I

The implication

is provable and optimal over \({\mathsf{ACA_{0}}}\), where \(\boldsymbol {\Gamma}^{*}\) is as in Corollary 49. In particular:

Remark 51

The lightface form of Theorem 49 trivializes when \({\mathsf{ZFC}}\) holds and \(V = L(x)\), since Martin has shown that if \(V = L(x)\), then \(\Delta ^{1}_{2}\)-Determinacy implies \(\mathsf{OD}\)-Determinacy.

Although all results so far have been stated in their boldface forms, we observe that the proofs had a certain degree of effectiveness, and this can lead to lightface versions, though these have to be phrased carefully. We mention an example which gives a partial answer to a well-known open problem in the context of Second-Order Arithmetic.

We mentioned in the proof of Corollary 49 the implication

It is an open problem whether this fact is provable in \(Z_{2}\), though a theorem of Cheng-Schindler [19] shows that it is provable in \(Z_{4}\).

Remark 52

Notice that the open problem refers to the determinacy of lightface pointclasses. The boldface transfer principle is easily provable in \(Z_{2}\), since it implies the existence of sharps: since we have Borel determinacy, then it follows from Friedman [29] that each \(x\in \mathbb{R}\) belongs to a model of \({\mathsf{KP}}+ \mathsf{Z}\). Then, working in \(L[x]\) for some \(x\) coding all relevant strategies, we can carry out the Cheng-Schindler proof.

Cheng [18], Woodin, and possibly others, have observed that Martin’s unpublished proof that

can be carried out in Second-Order Arithmetic.

Using Strategic Replacement and the First Separation Reduction Theorem, we obtain a partial result towards this question:

Corollary 53

Suppose that \(\boldsymbol {\Sigma}^{1}_{3}{-}{\mathsf{AC_{0}}}+ \boldsymbol {\Pi}^{1}_{4}{-}{ \mathsf{TI}}\) holds. Let

Then, the following are equivalent:

1. (1)

   \(\Sigma ^{1}_{1}(L)\)-Determinacy, and

2. (2)

   \(S(\Delta ^{0}_{2},\Sigma ^{1}_{1}(L))\)-Determinacy.

Proof

This proof makes use of the game-quantifier \(\Game \) (see Definition 56 in §5.1 below). We suppose that \(\Sigma ^{1}_{1}(L){-}\)Determinacy holds. Using \(\boldsymbol {\Pi}^{1}_{4}{-}{\mathsf{TI}}\), we prove by simultaneous induction on \(\alpha \) that

1. (1)

   \(S(\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1}(L))\)-Determinacy holds.

2. (2)

   The complete \(\Game S(\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1}(x))\) real belongs to \(L\) for each \(x\in \mathbb{R}\cap L\).

By \(\boldsymbol {\Sigma}^{1}_{3}{-}{\mathsf{AC_{0}}}\), we have

so, in order to obtain the first item, we show

This would be immediate from Corollary 42 and Corollary 43 if we were dealing with boldface pointclasses.

Let \(x\in \mathbb{R}\cap L\). Let us inspect the application of the First Separation Reduction Theorem needed to prove Corollary 42 and Corollary 43 for a set \(W\) in the pointclass \(S(\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1})(x)\). Here, an auxiliary game \(H\) is defined with the property that

1. (1)

   If Player I has a winning strategy for \(G(H)\), then Player I has a winning strategy for \(G(W)\),

2. (2)

   If Player II has a winning strategy for \(G(H)\), then Player II has a winning strategy for \(G(W)\).

The proof of these two implications requires

which we have.

The complexity of the set \(H\) is

where \(G\) is the complete \(\Game S({<}\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1}(x))\) set (see equation (4.1) in §4.2). By the induction hypothesis on \(\alpha \) and \(\boldsymbol {\Sigma}^{1}_{3}{-}\mathsf{AC}\), we have \(G \in L\), so \(H\) is in \(S({<}\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1}(L))^{\breve{}}\) and is thus determined. Thus, our first inductive claim follows.

For the second one, we simply observe that (by the argument just given and the fact that the definition of the auxiliary game \(G(H)\) is uniform in the definition of \(W\)) the complete \(\Game S(\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1})(x)\) real is many-one reducible to the complete \(\Game S({<}\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1})(x')\) real, for some \(x'\) in \(L\). □

Remark 54

Corollary 53 says that \(L\) can compute membership in sets in \(\Game S(\alpha{-}\Sigma ^{0}_{1}, \Sigma ^{1}_{1})\). However, the winning strategies for these games will generally not belong to \(L\) (except when \(\alpha = 0\) and the \(\Pi ^{1}_{1}\) player wins). \(\Sigma ^{1}_{1}\)-Determinacy implies that \(V \neq L\) over \({\mathsf{ZFC}}\) and presumably this is the case as well under the hypotheses of Corollary 53. Martin [57] has shown that if \(0^{\sharp}\) exists, then the reals in \(L\) are precisely those in \(\Game ({<}\omega ^{2}{-}\Pi ^{1}_{1})\).

Remark 55

For the proof of Corollary 53, one can replace the class \(\Sigma ^{1}_{1}(L)\) by smaller classes, such as \(\Sigma ^{1}_{1}(\Delta ^{1,L}_{3})\), where

We will obtain stronger abstract determinacy transfer theorems as consequences of the Second Separation Reduction Theorem below.

5.1 The game quantifier and set-existence axioms

The purpose of this section is to state and prove the Second Separation Reduction Theorem. Like the first one, this deals with the transfer of strategic replacement to a larger Wadge class. As we mentioned during the discussion following Corollary 47 in §4.3, one cannot expect to obtain for free any more strategic replacement transfer than that given by Theorem 40. The theorem in this section will require a payment in the form of set-existence axioms. The precise set existence axioms we will need assert the convergence of certain monotone operators on the powerset of the integers. The complexity of this operator depends on the Wadge class one wants to apply the Separation Reduction Theorem to and is defined in terms of the game quantifier:

Definition 56

Suppose that \(\boldsymbol {\Gamma}\) is a Wadge class. A set \(A\) is in \(\Game \boldsymbol {\Gamma}\) if there is \(B\in \boldsymbol {\Gamma}\) such that

where

If so, we write \(A = \Game B\).

The definition above applies to sets \(A\) in any space \(X\) such as ℕ, ℝ, etc., in which case the set \(B\) belongs to \(X \times \mathbb{R}\).

Definition 57

Suppose \(\boldsymbol {\Gamma}\) is a Wadge class. The principle of \(\Game \boldsymbol {\Gamma}\)-Comprehension (\(\Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}\)) asserts that every \(\Game \boldsymbol {\Gamma}\)-definable subset of ℕ exists. The lightface form of this principle is defined the natural way.

The game quantifier is a kind of generalized projection which is more restrictive than the usual existential quantifier on reals. However, its definition immediately bounds its expressive capability, and indeed we have the following:

Lemma 58

Suppose that \(\boldsymbol {\Gamma}\subset \boldsymbol {\Pi}^{1}_{1}\) and \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\vdash \) “\(\boldsymbol {\Gamma}\) is a Wadge class.” Then, \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\vdash \Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}\).

Proof

If \(\boldsymbol {\Gamma}\subset \boldsymbol {\Pi}^{1}_{1}{-}{ \mathsf{CA_{0}}}\), then every set of the form \(\Game A\) with \(A \in \boldsymbol {\Gamma}\) belongs to \(\boldsymbol {\Pi}^{1}_{2}\), so the lemma follows. □

Recall that a definable Wadge class \(\boldsymbol {\Gamma}\) is parametrized if there is a universal \(\boldsymbol {\Gamma}\) set in \(\Gamma \), and that in this case we also say that \(\Gamma \) is parametrized.

Lemma 59

Suppose \(\boldsymbol {\Gamma}\) is parametrized. Then, \(\Game \boldsymbol {\Gamma}\) is parametrized.

Proof

Immediate. □

We introduce a new principle. It is a weak form of strategic replacement which does not imply determinacy. It asserts that countably many winning strategies for Player I can be collected, provided they exist.

Definition 60

Let \(\boldsymbol {\Gamma}\) be a Wadge class. The principle of weak \(\Gamma \)-Strategic Replacement (weak \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\)) is the assertion that whenever \(\{W_{i} : i\in \mathbb{N}\}\) is a countable sequence of sets in \(\boldsymbol {\Gamma}\) such that Player I has a winning strategy for \(G(W_{i})\) for each \(i\in \mathbb{N}\) or Player II has a winning strategy for \(G(W_{i})\) for each \(i\in \mathbb{N}\), then there is a set \(\{\sigma _{i}:i\in \mathbb{N}\}\) such that for each \(i\in \mathbb{N}\), \(\sigma _{i}\) is a winning strategy for \(G(W_{i})\).

Remark 61

There is a slight analogy to be drawn with the usual choice principles. Weak Strategic Replacement is a countable-choice-like principle, in that it allows choosing countable sequences of strategies for a player, provided they all exist. (Strong) Strategic Replacement, on the other hand, is similar to Strong Dependent Choice, in that it allows choosing strategies for Player I if they exist, but returns a strategy for Player II otherwise. Like Strong \(\boldsymbol {\Gamma}{-}{\mathsf{DC}}\), \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) can simultaneously be regarded as a choice principle and as a set-existence principle.

The relation between this and other principles is laid out in the following lemma.

Lemma 62

Let \(\boldsymbol {\Gamma}\) be a Wadge class. Then,

1. (1)

   \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\leftrightarrow \boldsymbol {\Gamma}\)-Determinacy + weak \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}+ \Game \boldsymbol {\Gamma}{-}{ \mathsf{CA_{0}}}\).

2. (2)

   \(\Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}+ \Delta (\mathsf{SU}( \boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\)-Determinacy \(\to \boldsymbol {\Gamma}{-}{\mathsf{SR}}\).

3. (3)

   Therefore, if \(\boldsymbol {\Gamma}\) is a non-selfdual Borel Wadge class, or if \(\boldsymbol {\Gamma}\) is a definable, effectively treeable Wadge class closed under complements, then we have

   $$\begin{aligned} \textit{$\boldsymbol {\Gamma}{-}{\mathsf{SR}}\leftrightarrow \Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}+ \boldsymbol {\Gamma}$-Determinacy.} \end{aligned}$$

Proof

For (1), clearly \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) implies weak \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) and \(\boldsymbol {\Gamma}\)-Determinacy. Let us show that it also implies \(\Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}\). Suppose that \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) holds and let \(B \in \boldsymbol {\Gamma}\). We want to prove the existence of the set

Using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), let \(\{\sigma _{i}:i\in \mathbb{N}\}\) be a set such that \(\sigma _{i}\) is a winning strategy for \(G(B_{i})\) for each \(i\) (for one of the players). Then, we can simply form the set of all indices \(i\) such that \(\sigma _{i}\) is a strategy for Player I, using \({\mathsf{RCA_{0}}}\).

For the right-to-left implication, let \(\{W_{i}:i\in \mathbb{N}\}\) be a sequence of sets in \(\boldsymbol {\Gamma}\). Using \(\Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}\), let \(I\) be the set of all indices \(i\) such that Player I has a winning strategy for \(W_{i}\). Using weak \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), we can first form a set of strategies \(T = \{\sigma _{i} : i\in I\}\). Now, Player II has a winning strategy for \(\hat{W}_{i}\) whenever \(i\notin I\), by \(\boldsymbol {\Gamma}\)-Determinacy. Again using weak \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), we can form a set of strategies \(S = \{\sigma _{i} : i\notin I\}\) for each \(\{W_{i}: i\notin I\}\) (for Player II). Putting \(S\) and \(T\) together, the result follows. This proves (1).

For (2), it suffices to prove weak \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), by (1). Let \(\{W_{i}:i\in \mathbb{N}\}\) be a sequence of sets in \(\boldsymbol {\Gamma}\) such that Player I has a winning strategy for \(W_{i}\) for each \(i\in \mathbb{N}\). Consider the following game: Player II begins by playing \(i\in \mathbb{N}\), after which the game continues with the players playing \(W_{i}\). The winning set is clearly seen to belong to the class

Moreover, clearly Player II does not have a winning strategy, so by \(\Delta (\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1},\boldsymbol {\Gamma}))\)-Determinacy, Player I does. Let \(\sigma \) be such a strategy. Then, \(\sigma \) applied to each number \(i\) yields a winning strategy for \(W_{i}\), so the necessary set is recursive in \(\sigma \). If \(\{W_{i}:i\in \mathbb{N}\}\) is a sequence of sets in \(\boldsymbol {\Gamma}\) such that Player II has a winning strategy for \(W_{i}\) for each \(i\in \mathbb{N}\), a similar auxiliary game yields the desired sequence of strategies. This proves (2).

Claim (3) is immediate from (2) and Theorem 40 since for non-selfdual Borel Wadge classes \(\boldsymbol {\Gamma}\) we always have either \(\boldsymbol {\Gamma}= \mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1}, \boldsymbol {\Gamma})\) or \(\breve{\boldsymbol {\Gamma}} = \mathsf{SU}(\boldsymbol {\Sigma}^{0}_{1}, \breve{\boldsymbol {\Gamma}})\) by Louveau [51, Lemma 1.4] (and determinacy for a Wadge class implies determinacy for its dual). □

We shall now introduce a principle of monotone induction which will be crucial for the Second Separation Reduction Theorem. We first recall the relevant definitions. An operator

is monotone if \(\Phi (X) \subset \Phi (Y)\) whenever \(X\subset Y\). Such operators can be iterated transfinitely in a simple way by putting

An inductive fixpoint of \(\Phi \) is a set of the form \(\Phi ^{\alpha}\) such that \(\Phi ^{\alpha }= \Phi ^{<\alpha}\) and \(\alpha \) is least with this property. For such an \(\alpha \), we write \(\Phi ^{\infty }:= \Phi ^{\alpha}\). \(\Phi ^{\infty}\) gives rise to a prewellordering \(\leq _{\Phi}\) given by

This prewellordering is often called the stage comparison relation on \(\Phi \). In order to make things easier when working over \({\mathsf{RCA_{0}}}\), one may define the “inductive fixpoint” of \(\Phi \) to be the prewellordering \(\leq _{\Phi}\) itself. Hence, the sentence “\(\Phi \) has an inductive fixpoint” means that such a \(\leq _{\Phi}\) exists. Thus, we say:

Definition 63

Assume \({\mathsf{RCA_{0}}}\). Let \(\Phi : \mathcal{P}(\mathbb{N})\to \mathcal{P}(\mathbb{N})\) be a monotone operator. We say that \(\Phi \) has an inductive fixpoint if there is a prewellordering \((W,\leq _{\Phi})\) of ℕ such that

1. (1)

   for all \(a,b \in W\), we have

   $$ a\leq _{\Phi} b \leftrightarrow b\in \Phi (W_{< a}), $$
2. (2)

   \(\Phi (W) \subset W\).

If so, we write \(\Phi ^{\alpha }:= W_{a}\) whenever \(a \in W\) and \(\alpha = |a|_{\leq _{\Phi}}\), and we write \(\Phi ^{\infty }= W\), so that (5.1) holds.

Definition 64

Let \(\boldsymbol {\Gamma}\) be a Wadge class. The principle of \(\boldsymbol {\Gamma}\)-Monotone Induction (\(\boldsymbol {\Gamma}{-}{\mathsf{MI}}\)) asserts that every monotone operator

with graph in \(\boldsymbol {\Gamma}\) has an inductive fixpoint \(\Phi ^{\infty}\).

Definition 65

Suppose that \(\boldsymbol {\Gamma}_{l}\) is a Wadge class for each \(l\in \mathbb{N}\).

1. (1)

   If \(\{\Phi _{l}:l\in \mathbb{N}\}\) is a sequence of operators, we define the operator \(\Phi = \bigcup _{l\in \mathbb{N}}\Phi _{l}\) by

   $$ \Phi (X) = \bigcup _{l\in \mathbb{N}}\Phi _{l}(X) $$

   for all \(X\in \mathbb{R}\).

2. (2)

   The principle of

   $$ \Big(\bigcup _{l\in \mathbb{N}}\boldsymbol {\Gamma}_{l}\Big){-}{ \mathsf{MI}} $$

   is the assertion that whenever \(\{\Phi _{l}: l\in \mathbb{N}\}\) is a sequence of operators in the union \(\bigcup _{l\in \mathbb{N}}\boldsymbol {\Gamma}_{l}\) (i.e., such that each \(\Phi _{l}\) belongs to \(\boldsymbol {\Gamma}_{l'}\) for some \(l'\)), then \(\Phi = \bigcup _{l\in \mathbb{N}}\Phi _{l}\) has an inductive fixpoint.

Remark 66

The notation \((\bigcup _{l\in \mathbb{N}}\boldsymbol {\Gamma}_{l}){-}{\mathsf{MI}}\) might be ambiguous, since in principle it could also denote the principle of monotone induction for operators in the class \(\bigcup _{l\in \mathbb{N}}\boldsymbol {\Gamma}_{l}\), i.e., the principle

However, \((\bigcup _{l\in \mathbb{N}}\boldsymbol {\Gamma}_{l}){-}{\mathsf{MI}}\) will always denote the principle defined in Definition 65 and, in any case, this should be clear from the context.

Lemma 67

Suppose that \(\{\Phi _{l}: l\in \mathbb{N}\}\) is a sequence of operators and that \(\Phi _{l}\) is monotone for each \(l\). Then,

is monotone.

Proof

Immediate. □

The next simple lemma asserts that principles of game-monotone induction imply the corresponding comprehension axioms.

Lemma 68

Let \(\boldsymbol {\Gamma}\) be a Wadge class. Then, \(\Game \boldsymbol {\Gamma}{-}{\mathsf{MI}}\) implies \(\Game \boldsymbol {\Gamma}{-}{\mathsf{CA_{0}}}\).

Proof

Let \(B \in \boldsymbol {\Gamma}\). If \(\Game B = \varnothing \), then there is nothing to prove. Otherwise, let \(n\in \Game B\). Consider the constant operator \(\Phi \in \Game \boldsymbol {\Gamma}\) given by

for all \(X\). By \(\Game \boldsymbol {\Gamma}{-}{\mathsf{MI}}\), \(\Phi \) has an inductive fixpoint. Since \(n \in \Game B\), it follows that \(\Phi ^{\infty }\neq \varnothing \) and thus \(\Phi ^{\infty }= \Game B\), since it is constant. Thus, \(\Game B\) exists. □

We are finally ready to state and prove the Second Separation Reduction Theorem.

Theorem 69

Separation Reduction, II

Let

be a union of definable, effectively treeable Wadge classes \(\boldsymbol {\Gamma}_{l}\) such that and \(\boldsymbol {\Gamma}_{2l+1} = \breve{\boldsymbol {\Gamma}}_{2l}\) for each \(l\in \mathbb{N}\). Then the following are equivalent:

1. (1)

   \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy,

2. (2)

   \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Strategic Replacement, and

3. (3)

   \(\boldsymbol {\Gamma}\)-Strategic Replacement and \((\bigcup _{l\in \mathbb{N}}\Game \boldsymbol {\Gamma}_{l})\)-\({ \mathsf{MI}}\),

where \((\bigcup _{l\in \mathbb{N}}\Game \boldsymbol {\Gamma}_{l})\)-\({ \mathsf{MI}}\) is as in Definition 65.

5.2 Proof of the second separation reduction theorem

By Lemma 10, we have

so it will suffice to consider separated unions. The plan of the proof is the following. There are two main steps: We will begin by showing that (3) implies (1). In fact, we will show that

The second main step is proving that (1) implies (3). Let us explain how to derive the rest of the theorem from these two claims.

First observe that

since a set in the class on the right-hand side can easily be rearranged into a \(\boldsymbol {\Sigma}^{0}_{2}\)-separated union of \(\boldsymbol {\Gamma}\) sets (using that \(\boldsymbol {\Sigma}^{0}_{2}\) is closed under intersection with \(\boldsymbol {\Sigma}^{0}_{1}\)). Hence, trivially we have

Implication (5.2) and the fact that (1) implies (3) yield

and putting together (5.3) and (5.4) with Lemma 62 yields

i.e., (2). The converse is trivial and hence we have the equivalence between (1) and (2), and the equivalence between (1) and (3) follows from (5.2) and the fact that (1) implies (3).

Therefore, as promised, it suffices to prove claim (5.2) and the fact that (1) implies (3).

5.2.1 Proof that (3) implies (1)

We let \(\boldsymbol {\Gamma}\) be as in the statement and suppose that \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) and \(\bigcup _{l\in \mathbb{N}}\Game \boldsymbol {\Gamma}_{l}\)-\({ \mathsf{MI}}\) hold.

Consider a set in \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\), say

with \(C_{i} \in \boldsymbol {\Sigma}^{0}_{2}\) for each \(i\in \mathbb{N}\) and the family \(\{C_{i}: i\in \mathbb{N}\}\) pairwise disjoint, and so that \(A_{i} \in \Gamma _{l(i)}\) for some \(l(i)\in \mathbb{N}\), for each \(i\in \mathbb{N}\). We will point out when we use the fact that the sets \(C_{i}\) are disjoint.

For each \(i\in \mathbb{N}\), find closed sets \(C_{i,n}\) such that

For each \(i\in \mathbb{N}\), each \(n\in \mathbb{N}\), and each \(X\subset \mathbb{N}\), we consider a game \(G(W_{i,n}(X))\) with winning set given by

We define an operator \(\Phi _{i,n}\) by

Finally, we define the operator

Lemma 70

\(\Phi \) is a monotone operator and

Proof

This is clear from the definition. Since each \(\boldsymbol {\Gamma}_{l}\) is closed under intersection with \(\boldsymbol {\Pi}^{0}_{1}\) sets and unions with \(\boldsymbol {\Sigma}^{0}_{1}\) sets, the set \(W_{i,n}(X)\) is in \(\boldsymbol {\Gamma}_{l(i)}\), and thus the relation \(p \in \Phi _{i,n}(X)\) is in \(\Game \boldsymbol {\Gamma}_{l(i)}\) so that

as desired. Moreover, clearly each \(\Phi _{i,n}\) is monotone and hence so too is \(\Phi \).

To clarify, for each \(\Phi _{i,n}\), the set \(A_{i}\) belongs to \(\Gamma _{l(i)}\) (lightface, by relativization). By effective treeability, \(W_{i,n}\) – viewed as a relation on \(\mathbb{R}\times \mathbb{R}\) – belongs to \(\Gamma _{l(i)}(y)\) for some real parameter \(y\), and so \(\Phi _{i,n}\) belongs to \(\Game \Gamma _{l(i)}(y)\) (the parameter \(y\) is fixed and does not depend on the input of the operator, nor on \(i\) nor \(n\)). □

Lemma 71

Suppose \(p \in \Phi ^{\infty}\). Then, Player I has a winning strategy for \(W\) from \(p\).

Proof

We construct a winning strategy \(\sigma \) by induction on \(\alpha = \alpha ^{p} = \) least ordinal such that \(p \in \Phi ^{\alpha}\). By the definition of \(p\), there exist \(i, n = i^{p}\), \(n^{p} \in \mathbb{N}\) such that Player I has a winning strategy for \(W_{i,n}(\Phi ^{<\alpha})\). Choose such a strategy \(\sigma ^{\alpha}_{i,n}\) using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) (this uses the effective treeability of \(\boldsymbol {\Gamma}\) once more). For all \(x\), we have

Play according to \(\sigma ^{\alpha}_{i,n}\) until a position \(q\) is reached with \(q \in \Phi ^{\alpha ^{q}}\) and \(\alpha ^{q} < \alpha \), if ever. If so, then continue the game according to the strategy for \(W_{i^{q},n^{q}}(\Phi ^{<\alpha ^{q}})\) given by \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\).

Let \(\sigma \) be the strategy thus described. Since only countably many auxiliary games appear in the description of \(\sigma \), and these are given uniformly in \(q \in \mathbb{N}^{<\mathbb{N}}\) using \(\Phi ^{\infty}\) and the definition of \(W\), \(\sigma \) exists, by \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\).

Let \(x \in [\sigma ]\). Since there cannot be an infinite descending sequence of ordinals, there must be some \(k\in \mathbb{N}\) such that all extensions of \(x\upharpoonright k\) in \(x\) are played according to some fixed \(\sigma ^{\alpha ^{*}}_{i^{*},n^{*}}\). According to (5.5), we have

Therefore,

as desired. □

Lemma 72

Suppose \(p\notin \Phi ^{\infty}\). Then, Player II has a winning strategy for \(W\) from \(p\).

Proof

Suppose \(p\notin \Phi ^{\infty}\). We describe a winning strategy \(\sigma \) for Player II. Since \(p\notin \Phi ^{\infty }= \Phi (\Phi ^{\infty})\), it follows that for all pairs \((i,n)\in \mathbb{N} \times \mathbb{N}\), Player I does not have a winning strategy for \(W_{i,n}(\Phi ^{\infty})\) from \(p\).

The payoff of \(W_{i,n}(\Phi ^{\infty})\) belongs to \(\boldsymbol {\Gamma}\), by effective treeability, and thus the game is determined.

Choose any such pair, say \((i,n)\). Let \(\sigma _{i,n}\) be a winning strategy for Player II for the game \(W_{i,n}(\Phi ^{\infty})\) from \(p\), chosen using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\). Thus, for all plays \(x\) consistent with \(\sigma _{i,n}\), we have

Consider the auxiliary game given by

Note that this game belongs to

and thus belongs to \((\Sigma ^{0}_{1} \vee \Pi ^{0}_{1})(\Phi ^{\infty})\), so it is determined.

Case I: Player II has a winning strategy for \(H_{i,n}\). Choose one, using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\). Playing according to this strategy guarantees producing a real \(y\) such that all initial segments of \(y\) belong to \(\bar{\Phi}^{\infty}\) and some initial segment of \(y\) belongs to \(\bar{C}_{i,n}\). Play until such a position \(q\) is reached and proceed to the section marked Both cases below.

Case II: Player I has a winning strategy for \(H_{i,n}\). Define the canonical non-losing quasi-strategy \(Q\) for \(H_{i,n}\) as follows: a node \(q\) belongs to \(Q\) if and only if either \(q\) has an initial segment (possibly non-strict) in \(\Phi ^{\infty}\), or if \(q \in C_{i,n}\). Note that \(Q\) is recursive in \(\Phi ^{\infty}\) (uniformly for all \(i\) and \(n\) which fall under the case hypothesis).

Now, consider a further auxiliary game \(G(W_{i,n}(\Phi ^{\infty}), Q)\). This is the game \(W_{i,n}(\Phi ^{\infty})\) restricted to the game-tree \(Q\). Since this is a quasi-strategy for Player I, only Player I’s moves are restricted. Hence, any winning strategy for this game for Player I would be a winning strategy for Player I in \(W_{i,n}(\Phi ^{\infty})\) and thus no such strategy can exist. The payoff of \(G(W_{i,n}(\Phi ^{\infty}), Q)\) is the intersection of \(W_{i,n}(\Phi ^{\infty})\) with a closed set and hence belongs to \(\Gamma (\Phi ^{\infty},y)\) for some fixed \(y\) which does not depend on \(i\) nor on \(n\), by effective treeability. It follows that \(G(W_{i,n}(\Phi ^{\infty}), Q)\) is determined and that Player II has a winning strategy for it. Choose such a strategy \(\sigma ^{G}_{i,n}\), using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\).

Back to defining our desired strategy \(\sigma \) for \(W\), we have Player II play according to \(\sigma ^{G}_{i,n}\) as long as Player I plays according to \(Q\). If at any point Player I plays a move \(q\) that is inconsistent with \(Q\), then, by definition, we have \(q\in \Phi ^{\infty}\) and \(q\in \bar{C}_{i,n}\). Proceed to the section marked Both cases below.

Claim 73

Suppose that \(y\in [Q] \cap [\sigma ^{G}_{i,n}]\) is an infinite play. Then, \(y \notin W\).

Proof

Since \(y\in [\sigma ^{G}_{i,n}]\), we have

by the definition of \(W_{i,n}(\Phi ^{\infty})\). Since \(y \in [Q]\), (5.6) implies that

Again by \(y\in [\sigma ^{G}_{i,n}]\), we have

Hence, it follows from (5.7) that \(y \in \bar{A}_{i}\). But then, again by (5.7), we have

as desired. Here, we use that the sets \(C_{i}\) are pairwise disjoint (but \(W\cap C_{i} = A_{i} \cap C_{i}\) suffices). □

Both cases. We have reached a position \(q\) such that \(q \in \bar{\Phi}^{\infty}\) and \(q \in \bar{C}_{i,n}\). Since \(q \in \bar{\Phi}^{\infty}\), we can choose a different pair \((i',n')\) and repeat the procedure above for the game \(W_{i',n'}(\Phi ^{\infty})\). Choose the pair \((i',n')\) so that this is the next element after \((i,n)\) according to some fixed enumeration of \(\mathbb{N}\times \mathbb{N}\) in order-type \(\omega \).

The construction described above required making use of winning strategies for various games in \(\boldsymbol {\Gamma}\), including the auxiliary games. Note, however, that the descriptions of these games were all given uniformly in \((i,n)\) from \(\Phi ^{\infty}\), the code for \(W\), and the parameter given by effective treeability, so we can indeed choose all the necessary auxiliary strategies using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\). This completes the description of the strategy \(\sigma \).

Now, let \(x \in [\sigma ]\). We need to show that \(x \notin W\). There are two possibilities, either \(x\) was obtained from \(\sigma \) through a play in which all the pairs \((i,n)\) were considered, or else \(x\) was obtained from \(\sigma \) through a play in which only finitely many such pairs were considered. In the latter case, we have \(x\notin W\) by Claim 73. In the former case, the construction in both cases produces a partial play \(p_{i,n}\) such that \(p_{i,n} \notin C_{i,n}\). Since this is a closed set, it follows that we have

as desired. This completes the proof of the lemma. □

This completes the proof that all sets in \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\) are determined if \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) and \(\bigcup _{l\in \mathbb{N}}\Game \boldsymbol {\Gamma}_{l}{-}{ \mathsf{MI}}\) hold.

5.2.2 Proof of (5.2)

In order to obtain (5.2), it suffices to prove that \(\Game \mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}){-}{ \mathsf{CA_{0}}}\) follows from (3). Let \(W\in \mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\) be a set in \(\mathbb{N}\times \mathbb{R}\). Then, \(W_{i}\) is also a set in \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\) for each \(i\in \mathbb{N}\) (this follows from the fact that \(\boldsymbol {\Sigma}^{0}_{2}\) sets are closed under continuous preimages). To each \(W_{i}\) we can associate an operator \(\Phi _{i}\) as above, and the definition of \(\Phi _{i}\) is given uniformly in \(i\) from the definition of \(W\). Each operator \(\Phi _{i}\) is given as an infinite union of operators in \(\Game \boldsymbol {\Gamma}_{l}\) (for possibly varying \(l\)), and indeed in \(\Game \Gamma _{l}(y)\) for some fixed \(y\) (obtained via effective treeability).

Consider the “amalgamated” operator

given by

where \(X_{i} = \{n: (i,n) \in X\}\). Thus, \(\Phi \) simply carries out all inductive definitions \(\Phi _{i}\) in parallel. From the fixpoint \(\Phi ^{\infty}\) one can recover the desired set in \(\Game \mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\), since

where we are using 0 to code the empty sequence and the second implication follows from Lemma 71 and Lemma 72. This completes the proof of (5.2).

5.2.3 Proof that (1) implies (3)

This is the only part of the proof where we use that \(\boldsymbol {\Gamma}_{2l+1} = \breve{\boldsymbol {\Gamma}}_{2l}\), since we will need that \(\boldsymbol {\Gamma}\) is closed under complements.

To prove the implication, assume that \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy holds. This trivially implies

and thus \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) by the First Separation Reduction Theorem and the fact that \(\boldsymbol {\Gamma}\) is closed under complements by hypothesis.

It remains to prove that every monotone operator in \(\bigcup _{l\in \mathbb{N}} \Game \boldsymbol {\Gamma}_{l}\) has an inductive fixpoint. We will also use the fact that \(\boldsymbol {\Gamma}\) is closed under complements here.

Fix a sequence \(\{\Phi _{l}: l\in \mathbb{N}\}\) of (definitions of) monotone operators each belonging to \(\Game \boldsymbol {\Gamma}_{l^{*}}\) for some \(l^{*}\), and let

Relativizing to a parameter, we will consider the lightface classes \(\Gamma _{l}\) and assume that the enumeration of \(\{\Phi _{l}: l\in \mathbb{N}\}\) given is recursive. Recall that by our assumptions on the definability of \(\boldsymbol {\Gamma}\), it is decidable (relative to a parameter) whether a definition of an operator is a definition of an operator in some \(\Gamma _{l^{*}}\), so the function mapping each \(l\) to the least \(l^{*}\) such that \(\Phi _{l} \in \Gamma _{l^{*}}\) exists and will also assumed to be recursive (by relativizing). We need to show that \(\Phi \) has an inductive fixpoint. We will show that there is a prewellordering \(W^{*} \subset \mathbb{N}\times \mathbb{N}\) such that for each \(a \in {\text{dom}}(W^{*})\), we have

and moreover \(\Phi (\text{field}(W^{*})) \subset \text{field}(W^{*})\).

We will consider a specific game with the properties that Player I cannot have a winning strategy and that any winning strategy \(\tau \) for Player II is such that a set \(W^{*}\) as above is computable from the hyperjump of \(\tau \). Since (1) trivially implies \(\boldsymbol {\Sigma}^{0}_{1}\wedge \boldsymbol {\Pi}^{0}_{1}{-}\)Determinacy and thus \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\), we have access to hyperjumps.

The game we consider draws some inspiration from by the one in Tanaka [82], though there are some very crucial differences. The main difference is that we incorporate a mechanism for the players to pass on to an auxiliary game which is \(\Gamma \) relative to the play. The second main difference is one which is not necessary for the result, but which greatly simplifies the proof: we shall make the game symmetric (Tanaka’s payoff condition is not symmetric for the two players, and this leads to Player II having “nonstandard” winning strategies). This will raise the complexity of the payoff set, which instead of belonging to \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\) will belong to

However, according to the First Separation Reduction Theorem (see Corollary 42), we have

so we have access to this stronger hypothesis.

Definition of the game. In the game, Player I begins by presenting Player II with a pair \((b^{*},m^{*})\). Player II has to decide whether she believes that \((b^{*},m^{*})\) belongs to the prewellordering \(W^{*}\) as above and respond “yes” or “no.” The game continues with the players taking on different roles. If Player II responds “yes,” then Player II is called “Pro” and Player I is called “Con” for the remainder of the game. If Player II responds “no,” then the roles are reversed.

In the remainder of the game, Pro attempts to argue that \((b^{*},m^{*})\) indeed belongs to the pre-wellordering given by \(\Phi \). This is done by Pro constructing a pre-ordering \(V\) which she claims is an initial segment of \(W^{*}\) and such that \((b^{*},m^{*})\) belongs to \(V\). Con’s role is to look for problems with Pro’s construction and point them out. Con will have two types of tools to do this, called positive challenges and negative challenges. Let us describe these.

Construction of \(V\) and strategies. During each turn of the game, Pro considers a pair \((b,m)\) (in the order given by some enumeration of all pairs in \(\mathbb{N}\times \mathbb{N}\) in order-type ℕ, fixed in advance) and decides whether \((b,m)\) belongs to the pre-order \(V\) being constructed. Then, Pro asserts either “\((b,m) \in V\)” or “\((b,m) \notin V\).” Pro must moreover justify her positive choices as follows. Recall that the interpretation of Pro accepting a pair \((b,m)\) is the claim that \((b,m) \in W^{*}\), so that

Thus, if she claims \((b,m) \in W\), then she must also play a number \(l\in \mathbb{N}\), indicating the “promise” that

Recall that (5.8) is a formula in \(\Game \Gamma _{l^{*}}(V_{< m})\) for some \(l\in \mathbb{N}\), and the assignment \(l\mapsto l^{*}\) is recursive by assumption. The formula (5.8) should further be justified with a strategy \(\tau _{b,m,l}\) for the \(\Gamma _{l}(V_{< m})\) game in question (this strategy is for Player I of that game). This strategy is played slowly: for the rest of the game, Pro must add one new digit to it each turn, in addition to all other moves required. Thus, as the game progresses, Pro’s turns become longer and longer (not that this has any effect).

Similarly, Pro rejecting a pair \((b,m)\) should be interpreted as a claim that

Rejected pairs should be defended with an infinite sequence of strategies \(\{\tau _{b,m,l}: l\in \mathbb{N}\}\) for the corresponding games in \(\Gamma _{l^{*}}(V_{< m})\) (for Player II in these games). These strategies are similarly played slowly for the remainder of the game.

Positive challenges. At any point during the game, Con may put forth a positive challenge if he believes that one of Pro’s claim that (5.8) holds is incorrect. [Mnemonic: positive challenges challenge positive claims; negative challenges challenge negated claims.] If so, then Con must play a strategy for the \(\Gamma _{l^{*}}(V_{< m})\) game given by (5.8) (for Player II in this game). This is again done slowly, with one move played each turn for the remainder of the game. At the end of the game, Con will have produced a strategy \(\sigma _{b,m,l}\) and Pro will also have played a strategy \(\tau _{b,m,l}\). Let \(x_{b,m,l}\) be the real produced from facing off the strategies \(\sigma _{b,m,l}\) and \(\tau _{b,m,l}\) against each other. If \(x_{b,m,l}\) is a win for Player II (of the auxiliary game), we say that Con’s challenge is successful. Otherwise, we say that the challenge is failed. Notice that a challenge being successful is a condition in \(\breve{\Gamma}_{l^{*}}(V_{< m})\) (and thus in \(\breve{\Gamma}_{l^{*}}\) relative to the play) and a challenge failing is a condition in \(\Gamma _{l^{*}}\) relative to the play. [Though a successful challenge being beneficial to a player in the main game will depend on whether that player is taking on the role of Pro and Con; this will come up later when we define the winning set for the main game. The reader should not devote much energy to distinguishing between \(\Gamma _{l}\) and \(\breve{\Gamma}_{l}\), since both classes are included in \(\Gamma \).]

Negative challenges. At any point during the game, Con may put forth a negative challenge if he believes that one of Pro’s assertions that (5.9) is incorrect. If so, then Con must play a natural number \(l\) for which he believes (5.8) holds, together with a strategy \(\sigma _{b,m,l}\) for the \(\Gamma _{l^{*}}(V_{< m})\) game corresponding to this \(l\) (for Player I in this game). As in the previous case, let \(x_{b,m,l}\) be the real resulting from facing off the strategies \(\sigma _{b,m,l}\) and \(\tau _{b,m,l}\) against each other. If \(x_{b,m,l}\) is a win for Player I (of the auxiliary game), we say that the challenge is successful, and otherwise we say that it is failed. As before, a challenge being successful is a condition in \(\breve{\Gamma}_{l^{*}}(V_{< m})\) (and thus in \(\breve{\Gamma}_{l^{*}}\) relative to the play) and a challenge failing is a condition in \(\Gamma _{l^{*}}\) relative to the play.

Rules of the game. The rules of the game are as follows.

1. (1)

   Pro must play a pre-order \(V\) with \((b^{*},m^{*}) \in V\).

2. (2)

   Con can challenge a move \((b,m) \in V\) or \((b,m) \notin V\) previously made by Pro at any time, as long as the following conditions are satisfied:

   1. (a)

      it has already been established by Pro that \((m, m^{*}) \in V\), and

   2. (b)

      if \((b', m')\) is a previous move challenged by Con, then Con can only (positively) challenge \((b,m) \in V\) if Pro has already established that \(m \leq _{V} m'\) and, similarly, Con can only (negatively) challenge \((b,m) \notin V\) if Pro has already established that \(m \leq _{V} m'\).

3. (3)

   Suppose the previous rules are satisfied.

   1. (a)

      If Con makes no challenge, then Pro wins.

   2. (b)

      If Con makes infinitely many challenges, then Pro wins.

   3. (c)

      If Con makes a positive, but finite, number of challenges, then Con wins if and only if the last challenge placed is successful.

Lemma 74

The payoff set of game just described is in \(\Delta (B(\boldsymbol {\Sigma}^{0}_{1},\mathsf{SU}( \boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})))\).

Proof

Rules (1) and (2) are closed for Pro and Con respectively. If these conditions are satisfied, then Pro wins the game if and only if either no challenge is made (this is a \(\Pi ^{0}_{1}\) condition), or else if there exists a last challenge, say to a move \((b, m)\) and a number \(l\in \mathbb{N}\) and the corresponding auxiliary subgame is won by Pro in whichever role she is assuming. This condition is either in \(\Gamma _{l^{*}}(V_{< m})\) or in \(\breve{\Gamma}_{l^{*}}(V_{< m})\), and \(V_{< m}\) is easily computable from the play. Thus, this winning set for Pro is a union of sets in \(\boldsymbol {\Gamma}_{l^{*}}\) and \(\breve{\boldsymbol {\Gamma}}_{l^{*}} = \boldsymbol {\Gamma}_{l^{*}+1}\) separated by disjoint \(\Sigma ^{0}_{2}\) sets. The \(\Sigma ^{0}_{2}\) sets assert that there is a last challenge at a given turn \(k\) raised to a pair of moves \((b,m)\), together with the number \(l\in \mathbb{N}\) associated to it and the type of challenge. Clearly these are disjoint. Since whether Player I is Pro or Con is determined during the first turn of the game, the winning condition is clearly a union of a \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\) set and a \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})^{ \breve{}}\) set separated by a clopen set and thus belongs to

as desired. [Note: in order to incorporate rules (1) and (2) into the winning set, we use treeability.] □

Lemma 75

Player I does not have a winning strategy for this game.

Proof

This is clear, since such a strategy would require winning games with the same starting position as both Pro and Con. If this were the case, we would be able to face off the two plays against each other and each a contradiction. □

Below, we suppose \(\tau \) is a winning strategy for Player II in the game.

Lemma 76

Suppose that \(\alpha \) is a wellorder such that \(\Phi ^{\alpha}\) and \(\leq _{\Phi ^{\alpha}}\) exist. Suppose Player I begins by playing \((b^{*}, m^{*}) \in \, \leq _{\Phi ^{\alpha}}\). Then, \(\tau \) must accept \((b^{*}, m^{*})\).

Proof

Let \(\alpha \) be as in the statement of the lemma. Suppose Player II rejects \((b^{*}, m^{*})\). We claim Player I has a winning strategy from this position. Using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) collect all the strategies for all games witnessing all sentences of the form \(a \in \Phi ^{\gamma}\) and \(a \notin \Phi ^{\gamma}\) for all \(\gamma \leq \alpha \) and all \(a\in \mathbb{N}\). This is possible because the family of all such games is computable from \(\alpha \) and \(\Phi ^{\alpha}\). Then, we consider the play in which Player I, as Pro, plays \(\leq _{\Phi ^{\alpha}}\) and all the strategies witnessing all memberships and non-memberships in \(\leq _{\Phi ^{\alpha}}\). This play must be won by Player I. □

Given a play \(x\) of the game, we denote by \((V^{x}, \leq _{V^{x}})\) the pre-order played by Pro in \(x\). Similarly if \(p\) is a partial play of the game, \(V^{p}\) denotes the portion of \(V\) which has already been played by Pro. Given a partial play \(p\), we say that \(m\) can be challenged in \(p\) if Con can challenge a claim \((b,m) \in V\) or \((b,m)\notin V\) by Player II without breaking rule (2). For an infinite play \(x\), we say that \(m\) can be challenged in \(x\) if \(m\) can be challenged in every sufficiently large initial segment of \(x\).

Lemma 77

Suppose that \(\alpha \) is a wellorder such that \(\Phi ^{\alpha}\) and \(\leq _{\Phi ^{\alpha}}\) exist and suppose \(m \in \Phi ^{\alpha}\). If \(x\) is a play by \(\tau \) in which Player II is Pro, \(m \in V^{x}\), and \(m\) can be challenged in \(x\), then we have

Proof

The proof is by transfinite induction. Let us first verify that we have access to enough induction. Let \(\gamma \) be a wellorder and let \(A_{\gamma}\) be the set of all \(\alpha \) for which the conclusion of the theorem holds, i.e., the \(\alpha \) such that for all positions \(p\) consistent with \(\tau \), all \(m \in \Phi ^{\alpha}\), and all \(b\in \mathbb{N}\), we have

This set is arithmetical in \((\Phi ^{\alpha},\leq _{\Phi ^{\alpha}})\) and \(\tau \) and thus exists, so we have access to \(\gamma \)-transfinite induction for it.

To prove the lemma, suppose \(x\) is any play by \(\tau \) in which \(m \in V^{x}\), for some \(m \in \Phi ^{\alpha}\) which can be challenged in \(x\). Without loss of generality, we have \(m \notin \Phi ^{<\alpha}\). We begin with the left-to-right direction

Claim 78

\(\leq _{\Phi ^{\alpha}} \upharpoonright _{\leq m}\, \subset \, \leq _{V^{x}} \upharpoonright _{\leq m}\).

Proof

Let \(b \leq _{\Phi ^{\alpha}} m\). Suppose that \(b\) is of minimal rank \(({\leq}\alpha )\) such that \(b\nleq _{V^{x}} m\). [Such a \(b\) exists because \(\alpha \) is a wellorder and the set of all \(\gamma <\alpha \) for which there is a play \(x\) and a pair \((b,m)\) as in the claim is \(\Sigma ^{1}_{1}(\leq _{\Phi ^{\alpha}},\tau )\). Since \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}\) holds, the set exists and must thus have a least element.] Then, Player II plays \(b\nleq m\) at some point in \(x\). Consider the play \(x'\) in which the players begin as in \(x\) until Player II has played \((b,m)\notin V^{x'}\) and \((m,m) \in V^{x'}\). Then, \((b,m)\notin V^{x'}\) can be negatively challenged by Player I, who can then play a number \(l\) and a strategy witnessing

By induction hypothesis, if \(b' <_{\Phi ^{\alpha}} b\), then \((b', m) \in V^{x'}\) must be played by Player II, so we have

and thus the strategy played by Player I witnesses

by monotonicity. Thus, \(x'\) must be won by Player I, which is impossible. This proves the claim. □

We now prove the right-to-left direction.

Claim 79

\(\leq _{V^{x}} \upharpoonright _{\leq m}\,\subset \, \leq _{\Phi ^{ \alpha}} \upharpoonright _{\leq m}\).

Proof

Let \(b \leq _{V^{x}} m\) and suppose towards a contradiction that \(b \nleq _{\Phi ^{\alpha}} m\). First, suppose \(b <_{V^{x}} m\). By induction hypothesis, there can be no \(m' <_{V^{x}} m\) such that \(b\leq _{V^{x}} m'\) and \(m' \in \Phi ^{<\alpha}\). Thus, if \(m' <_{V^{x}} m\) is such that \(m' \in \Phi ^{<\alpha}\), then \(m' <_{V^{x}} b\). Also by induction hypothesis it follows that if \(m' \in \Phi ^{<\alpha}\) and \(m' \leq _{V^{x}} m\), then in fact \(m' <_{V^{x}} m\). By Claim 78, we have

so that if \(b\) is as above, then \(m' <_{V^{x}} b\) for all \(m' \in \Phi ^{<\alpha}\). In other words,

Now, consider the play \(x'\) in which the players play as in \(x\) until Player II has asserted that \(b <_{V^{x}} m\). Since \(m\) can be challenged in \(x\) and \(b <_{V^{x'}} m\), \(b\) can be challenged in \(x\). Thus, have Player I place a negative challenge to Player II’s assertion that \((m, b) \notin V^{x'}\) and play an \(l\) and a strategy witnessing that

The inequality (5.10) was proved for arbitrary \(x\) (satisfying the hypothesis of the lemma) and thus holds also for \(x'\). By monotonicity, this play must thus be won by Player I, contradicting the fact that \(\tau \) is a winning strategy.

Suppose now that \(b \equiv _{V^{x}} m\). We have just shown that

Consider a play \(x'\) in which the players play as in \(x\) until Player II has asserted \(b \equiv _{V^{x}} m\). Have Player I play a positive challenge to \(b \leq _{V^{x}} m\) in \(x'\) and play a strategy witnessing

where \(l\) is chosen by Player II. By (5.11), we must have

so the play is won by Player I, which is again a contradiction. This proves the claim. □

With these two claims, the proof of the lemma is complete. □

The following lemma asserts that Player II can only play dishonestly by first telling the whole truth and only afterwards beginning to lie.

Lemma 80

Suppose that \(\alpha \) is a wellorder such that \(\Phi ^{\alpha}\) and \(\leq _{\Phi ^{\alpha}}\) exist. Suppose that \(x\) is a play in which Player I begins by playing \((b^{*}, m^{*})\) such that \((b^{*}, m^{*}) \notin \Phi ^{\alpha}\) and \(\tau \) accepts \((b^{*}, m^{*})\). Then, if \(b\) and \(m\) are such that \(b \leq _{\Phi ^{\alpha}} m\) and \(m^{*}\) can be challenged in \(x\), then \(b \leq _{V^{x}} m <_{V^{x}} m^{*}\).

Proof

By induction on ordinals \({\leq}\alpha \). Let \(x\) be such a play. Inductively, we have

Suppose \(b \leq _{\Phi ^{\alpha}} m\) but Player II plays \(b\nleq m\). By induction hypothesis we may assume \(m \in \Phi ^{\alpha}\setminus \Phi ^{<\alpha}\). By Lemma 77 we obtain a contradiction if \(m\) can be challenged in the play, so suppose that it cannot. Thus, Player II must play

Have Player I place a negative challenge to \((m, m^{*})\) together with some \(l\in \mathbb{N}\) and a strategy witnessing

By (5.12) we have \(\Phi ^{\alpha}\subset V^{x}\upharpoonright _{< m^{*}}\) so by monotonicity the play must be won by Player I, which is a contradiction. This shows that \(b\leq _{V^{x}} m\leq _{V^{x}} m^{*}\). However by Lemma 77 the second inequality must be strict. □

Observe that the set \(\Phi ^{\alpha}\) and its prewellordering do not depend on how \(\alpha \) is represented as a subset of ℕ (this is a simple proof by induction).

Below, define

Although it is not clear that \(W\) should have any structure itself (e.g., transitivity or reflexivity), it follows from Lemma 76 and Lemma 80 that it must contain \((\Phi ^{\alpha}, \leq _{\Phi ^{\alpha}})\) as an initial segment whenever \(\Phi ^{\alpha}\) and \(\leq _{\Phi ^{\alpha}}\) exist. Thus, it contains a pre-wellorder as an initial segment. We may thus let

We identify \((W^{*}, \leq _{W^{*}})\) with its field when convenient. In order to complete the proof, it remains to show the following:

Lemma 81

\(\Phi (W^{*}) = W^{*}\).

Proof

As we mentioned earlier, Lemma 76 and Lemma 80 imply that for all \(b^{*}\), \(m^{*}\),

By the monotonicity of \(\Phi \), we have

Using strategic replacement, collect the set \(A\) of strategies witnessing either

or

for each \(l\in \mathbb{N}\) and each \(a \in W^{*}\). Since \(W^{*}\) is a prewellordering of length, say, \(\alpha ^{*}\), we can use the set of these strategies to prove, by induction on \(\alpha ^{*}\), that \(W^{*}_{a} = \Phi ^{|a|}\) for each \(a \in W^{*}\). Thus,

Suppose towards a contradiction that \(m \in \Phi (W^{*})\setminus W^{*}\). Then once more using strategic replacement and \(W^{*}\) we can define the order \((\Phi ^{\alpha ^{*}+1}, \leq _{\Phi ^{\alpha ^{*}+1}})\), contradicting (5.13). □

This completes the proof of the Second Separation Reduction Theorem.

5.2.4 A truth-game version of the second separation reduction theorem

In this section, we make some comments on the proof of Theorem 69 and prove a related result. In the proof in §5.2.3, given a monotone operator \(\Phi \) belonging to some complexity class of the form \(\bigcup _{l\in \mathbb{N}}\Game \boldsymbol {\Gamma}_{l}\), we considered a game in which players I and II attempt to determine whether a number \(n\) belongs to the set inductively defined by \(\Phi \). In this game, Player I asked whether \(n\) belongs to \(\Phi \) and Player II answers “yes” or “no,” at which point the game proceeds according to Player II’s response. We then showed that from any winning strategy for Player II we can recover the inductively defined set.

This recovery process, however, was not recursive and in particular was not as simple as checking whether Player II responds “yes” or “no.” This raises the question of whether any winning strategy requires that Player II respond truthfully in the game in the previous section.

The purpose of this section is to consider a variant of the game from the proof of Theorem 69 in which Player II’s only winning strategy is to tell the truth. (We call games of this type “truth games.”) The theorem in this section will be used in a later section for our analysis of determinacy principles over \({\mathsf{RCA_{0}}}\), but not for our analysis of determinacy principles over \({\mathsf{KP}}\). The reason for this is that the determinacy principles whose analyses require truth games are all implied by strictly weaker determinacy principles over \({\mathsf{KP}}\). We remark that the proof of the theorem will make use of the existence of fixpoints of monotone operators which follows from Theorem 69.

Theorem 82

Let \(\boldsymbol {\Gamma}\) and \(\boldsymbol {\Gamma}_{l}\) (\(l\in \mathbb{N}\)) be as in Theorem 69. Suppose that \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}){-}\)Determinacy holds. Let \(\Phi = \bigcup _{l\in \mathbb{N}} \Phi _{l}\) be an operator in \(\bigcup _{l\in \mathbb{N}} \boldsymbol {\Gamma}_{l}\). Then, there is a game

for which the following hold:

1. (1)

   Player I has no winning strategy for \(G_{\Phi}\),

2. (2)

   if \(\sigma \) is a winning strategy for Player II in \(\sigma \), then \(\sigma \) restricted to moves of length 1 is the characteristic function of \(\Phi ^{\infty}\).

Proof

The game is similar to that in the proof of Theorem 69, but with some changes. Let \(\Phi \) be as in the statement of the theorem and suppose that \(\mathsf{SU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}){-}\)Determinacy holds. By Theorem 69, \((\Phi ^{\infty},\leq _{\Phi ^{\infty}})\) exists.

In the new game, Player I begins by asking whether Player II believes that a number \(n^{*}\) belongs to \(W^{*}\). Player II then answers “yes” or “no.” If Player II answers “yes,” then she takes on the role of Pro for the remainder of the game, and otherwise she takes on the role of Con. The game now changes: instead of Pro building a pre-order \(V\) to justify the fact that \(n^{*} \in \Phi ^{\infty}\), we force Con to disprove Pro’s claim. Thus, Con builds a pre-order \(V\) precisely as in the proof of Theorem 69 but with the condition that \(n^{*}\) does not belong to the field of \(V\). We allow Pro to place positive and negative challenges to Con exactly like Con could in the proof of Theorem 69, with the following new possibility: Pro may place a negative challenge to a play \(m \nleq m\) by Con, provided that Pro has not placed any challenges in the game yet, or that all challenges placed thus far have been of this new form. These challenges must, as before, be accompanied by a number \(l\in \mathbb{N}\) and a strategy played by Pro. This strategy is for the game which determines membership in \(\Phi _{l}(V)\) (where \(V\) is the pre-order played by Con). If Pro places a challenge of this type, Con must also play a strategy, hoping to show that \(m \notin \Phi _{l}(V)\). At any point during the game, Pro may opt out of the possibility of raising this new type of challenge and instead begin placing challenges according to rule (2) in the proof of Theorem 69. A challenge of the new kind raised to a move \(m\nleq m\) in a play \(x\) is successful if Pro’s strategy defeats Con in the game which determines membership in the set \(\Phi _{l}(V^{x})\), and it is failed otherwise.

As before, Pro wins a run of the game if and only if either Con breaks one of the basic rules of the game, or if no player does this, there is a last challenge placed, and it is successful.

Thus, Pro attempts to find mistakes in Con’s pre-order \(V\) but she may also challenge Con’s play by pointing out elements of \(\Phi ^{\infty}\) left out of \(V\). It is clear that the winning condition belongs to

Since Player II decides which role to adopt in the game, it is clear that Player I cannot have a winning strategy and so Player II must have one, say \(\sigma \); we claim it is as desired.

First, observe that if Player I begins by playing some \(n^{*} \notin \Phi ^{\infty}\), then Player II must take on the role of Con, for otherwise Player I could just play \(\Phi ^{\infty}\) and all strategies witnessing all instances of membership and non-membership in \(\Phi ^{\infty}\) (using \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\)) and win.

Conversely, if \(n^{*}\in \Phi ^{\infty}\), we claim that Player II must adopt the role of Pro. Suppose otherwise that Player II takes on the role of Con in this game. As in Lemma 77, one shows that if \(b\in \Phi ^{\infty}\) and Player II places \(b\) into \(V^{x}\) in a play \(x \in [\sigma ]\), then Player II must play in such a way that

Thus, Player I can counter Player II’s play as follows: wait for Player II to play false statements about elements of \(\Phi ^{\infty}\). If Player II ever asserts that some \(b\in \Phi ^{\infty}\) does not belong to the domain of \(V^{x}\), place a negative challenge (of the new type) together with a number \(l\) and a strategy witnessing

Afterwards, if Player II ever asserts that some \(b' \in \Phi ^{<|b|}\) does not belong to \(V^{x}\), place a negative challenge (of the new type) to this move, and so on. Since \(\Phi ^{\infty}\) is a wellfounded pre-order, this can only happen finitely many times and, letting \(b^{*}\) be the last number thus challenged, (5.14) implies that Player II must play in such a way that

so that by monotonicity the strategy played by Player I witnesses

contradicting the fact that \(\sigma \) was a winning strategy. This completes the proof of the theorem. □

Remark 83

The game in Tanaka [82] can be modified to yield a truth game for \(\Sigma ^{1}_{1}\)-monotone inductions with complexity \(B(\Delta ^{0}_{1},\Sigma ^{0}_{2})\), by following a similar idea. The modification of the game in [82] is: if Con makes infinitely many strictly descending challenges (the only ones which are allowed in Tanaka’s game), then Pro loses.

5.3 Consequences of the second separation reduction theorem

Below, Lemma 211 and Lemma 213 from Appendix B will be used without mention.

Corollary 84

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class. Then the following are equivalent:

1. (1)

   \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}){-}\)Determinacy,

2. (2)

   \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}){-}{\mathsf{SR}}\),

3. (3)

   \(\boldsymbol {\Gamma}{-}\)Strategic Replacement and

   $$ \Big(\Game \boldsymbol {\Gamma}\vee \Game \breve{\boldsymbol {\Gamma}} \Big){-}{\mathsf{MI}}. $$

Proof

This follows from Theorem 69 by setting \(\boldsymbol {\Gamma}_{2l} = \boldsymbol {\Gamma}\) and \(\boldsymbol {\Gamma}_{2l+1} = \breve{\boldsymbol {\Gamma}}\) for all \(l\in \mathbb{N}\). □

A particular case of this corollary is the following result which characterizes the strength of determinacy principle for levels of the difference hierarchy over \(\boldsymbol {\Sigma}^{0}_{2}\).

Corollary 85

For each countable ordinal \(\alpha \), the following are equivalent:

1. (1)

   \((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy,

2. (2)

   \((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{2}{-}\)Strategic Replacement,

3. (3)

   \(\alpha{-}\boldsymbol {\Sigma}^{0}_{2}{-}\)Strategic Replacement and

   $$ \Big(\Game (\alpha{-}\boldsymbol {\Sigma}^{0}_{2})\vee \Game (\alpha{-} \boldsymbol {\Sigma}^{0}_{2})^{\breve{}}\Big){-}{\mathsf{MI}}. $$

Proof

This follows from Corollary 84 using the identity

A proof of this identity can be found in Louveau [51, Lemma 1.11]. □

We also mention the analog of Corollary 85 for limit stages, for the sake of completeness:

Corollary 86

For each countable ordinal \(\alpha \), the following are equivalent:

1. (1)

   \(\lambda{-}\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy,

2. (2)

   \(\lambda{-}\boldsymbol {\Sigma}^{0}_{2}{-}\)Strategic Replacement,

3. (3)

   \({<}\lambda{-}\boldsymbol {\Sigma}^{0}_{2}{-}\)Strategic Replacement and

   $$ \Big(\bigcup _{\eta < \lambda}\Game (\eta{-}\boldsymbol {\Sigma}^{0}_{2}) \Big){-}{\mathsf{MI}}. $$

Proof

This follows from Theorem 69 applied to \(\boldsymbol {\Gamma}_{2l} = {\lambda _{l}}{-}\boldsymbol {\Sigma}^{0}_{2}\), where the sequence \(\{\lambda _{l}:l\in \mathbb{N}\}\) is chosen cofinal in \(\lambda \). This application of Theorem 69 uses Lemma 17. □

Using Corollary 85 and Corollary 86, we can inductively obtain reverse-mathematical characterizations of \(\alpha{-}\boldsymbol {\Sigma}^{0}_{2}\)-Determinacy in the style of MedSalem and Tanaka [61] and in particular show that

for all \(\alpha \).

Let us now turn to other general results. The first of these is the version of Corollary 84 for limit ordinals.

Corollary 87

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class closed under \(\boldsymbol {\Sigma}^{0}_{2}\)-separated unions and let \(\lambda \) be a limit ordinal. Then, the following are equivalent:

1. (1)

   \(B(\lambda{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy,

2. (2)

   \(B(\lambda{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Strategic Replacement,

3. (3)

   \(B({<}\lambda{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Strategic Replacement and

   $$ \Big(\bigcup _{\eta < \lambda}\Game B(\eta{-}\boldsymbol {\Sigma}^{0}_{2}, \boldsymbol {\Gamma})\Big){-}{\mathsf{MI}}. $$

Proof

By Lemma 14, we have

The result then follows from Theorem 69. □

Corollary 88

Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable Wadge class closed under unions and intersections with \(\boldsymbol {\Pi}^{0}_{2}\) sets and \(\boldsymbol {\Sigma}^{0}_{2}\)-separated unions and let \(\alpha \) be a countable ordinal and \(\lambda \) be a countable limit ordinal. Then, the following are equivalent:

1. (1)

   \(B(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\lambda{-} \boldsymbol {\Sigma}^{0}_{2})\)-Determinacy,

2. (2)

   \(B(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\lambda{-} \boldsymbol {\Sigma}^{0}_{2})\)-Strategic Replacement,

3. (3)

   \(B(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},{<} \lambda{-}\boldsymbol {\Sigma}^{0}_{2})\)-Strategic Replacement and

   $$ \Big(\bigcup _{\eta < \lambda}\Game B(\alpha{-}\boldsymbol {\Sigma}^{0}_{2}, \boldsymbol {\Gamma},\eta{-}\boldsymbol {\Sigma}^{0}_{2})\Big){-}{ \mathsf{MI}}. $$

Proof

By Lemma 16, sets in \(B(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\lambda{-} \boldsymbol {\Sigma}^{0}_{2})\) are those of the form

The result then follows from Theorem 69. □

Our next corollary of the Second Separation Reduction Theorem is a family of general determinacy transfer theorems provable over subsystems of \(Z_{2}\).

Corollary 89

Suppose that \(\boldsymbol {\Pi}^{1}_{n+2}{-}{\mathsf{TI}}\) and \(\boldsymbol {\Delta}^{1}_{n+2}{-}{\mathsf{MI}}\) holds. Let \(\boldsymbol {\Gamma}\) be a definable, effectively treeable \(\boldsymbol {\Delta}^{1}_{n}\) Wadge class closed under unions and intersections with \(\boldsymbol {\Pi}^{0}_{2}\) and \(\boldsymbol {\Sigma}^{0}_{2}\)-separated unions. Then, the following are equivalent:

1. (1)

   \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\), and

2. (2)

   \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}, \boldsymbol {\Delta}^{0}_{3}){-}{\mathsf{SR}}\).

Proof

We prove by transfinite induction that \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\eta{-} \boldsymbol {\Sigma}^{0}_{2}){-}{\mathsf{SR}}\) holds for all \(\eta <\omega _{1}\). Assuming that \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\eta{-} \boldsymbol {\Sigma}^{0}_{2}){-}{\mathsf{SR}}\) holds, we use the definability of \(\boldsymbol {\Gamma}\) and the hypothesis \(\boldsymbol {\Delta}^{1}_{n+1}{-}{\mathsf{MI}}\) to obtain monotone induction for the class

By Corollary 84, we obtain

We now use the identity

which follows from [51, Lemma 1.11] (the result is stated for Borel \(\boldsymbol {\Gamma}\), but the proof works in general). Thus, we have

as desired. For the limit case, suppose \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\eta{-} \boldsymbol {\Sigma}^{0}_{2}){-}{\mathsf{SR}}\) holds for all \(\eta <\lambda \). By \(\boldsymbol {\Delta}^{1}_{n+2}{-}{\mathsf{MI}}\), we have \(\boldsymbol {\Delta}^{1}_{2}{-}{\mathsf{CA_{0}}}\) and thus \(\boldsymbol {\Sigma}^{1}_{2}{-}{\mathsf{AC_{0}}}\). By Lemma 38 we obtain \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},{<}\lambda{-} \boldsymbol {\Sigma}^{0}_{2}){-}{\mathsf{SR}}\). As before, we use the definability of \(\boldsymbol {\Gamma}\) and the hypothesis \(\boldsymbol {\Delta}^{1}_{n+1}{-}{\mathsf{MI}}\) to obtain monotone induction for the class

By Corollary 88, we obtain \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\lambda{-} \boldsymbol {\Sigma}^{0}_{2}){-}{\mathsf{SR}}\), as desired. This proves the corollary. □

It seems unlikely that one can generalize Corollary 89 without additional assumptions on \(\boldsymbol {\Gamma}\) or without additional set-existence axioms. We mention an instance of this as a conjecture:

Conjecture 90

Optimal Transfer, II

\(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\) does not prove the implication:

The analog of Corollary 53 for sets in \(B(\Sigma ^{0}_{2},\Sigma ^{1}_{1},\Delta ^{0}_{3})(L)\) is left to the reader.

In this section, we present and prove our Third Separation Reduction Theorem, which we precede by the following discussion which, albeit possibly vague, hopefully provides some context.

Like the previous two Separation Reduction Theorems, this theorem deals with the relation between determinacy principles for sets represented in terms of separation operations versus set-existence axioms. The set existence axioms in question will be principles of \(\beta \)-reflection. In other words, we shall now be dealing with Wadge classes with enough closure properties that their determinacy implies the existence of models of various theories which are correct about wellfoundedness. Recall that (at least for Borel sets, but most likely also in general) the closure properties of a Wadge class are indirectly reflected by the closure properties of their (ordinal) Wadge ranks. While the Second Separation Reduction Theorem was suitable for the study of classes such as \(2{-}\boldsymbol {\Sigma}^{0}_{2}\) or \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) (whose Wadge ranks are \(\omega _{1}^{2}\) and \(\omega _{1}^{\omega _{1}+1}\)), the Third Separation Reduction Theorem is suitable for the study of classes such as \(S(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) (whose Wadge rank is \(\omega _{1}^{\omega _{1}+\omega _{1}}\)). In general, it appears that there is an intimate connection between the representation of \(o(\boldsymbol {\Gamma})\) in various ordinal denotation systems and the set-existence axioms to which \(\boldsymbol {\Gamma}{-}\)Determinacy is equivalent. While our work shows how to make this connection explicit for Wadge classes below

we are not quite sure what a reasonable conjecture in this direction should be.

Unlike the previous results, the theorem in this section appears not to be stated in its full generality. There are two degrees to which this occurs. The first degree is more serious, yet possibly more superficial, and relates to the extent to which the theorem can be phrased as an equivalence. Our proof of determinacy works for a very general collection of Wadge classes. However, we seem to run into (possibly methodological) difficulties when attempting to reverse the proof. We shall ultimately be able to do this in all cases of immediate interest for us here, as well as in some others. As a consequence of this, we have chosen to split the theorem into two parts, one dealing with the proof of determinacy, and the other dealing with the reversal for our main case of interest.

The second degree in which this (apparent) diminished generality is manifested is deeper and, unlike the first one, unavoidable. The theorem deals with sets in \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}, \boldsymbol {\Sigma}^{0}_{3})\). While the choice of \(\boldsymbol {\Gamma}\) is again free, the occurrence of the class \(\boldsymbol {\Sigma}^{0}_{3}\) seems unrelated to \(\boldsymbol {\Gamma}\). In a way, the theorem now has been promoted to having two distinct parameters (\(\boldsymbol {\Sigma}^{0}_{2}\) and \(\boldsymbol {\Sigma}^{0}_{3}\)). When attempting to phrase more general versions of the theorem, one needs to consider the interaction between the complexity of the sets in \(\boldsymbol {\Sigma}^{0}_{2}\) and in \(\boldsymbol {\Sigma}^{0}_{3}\) carefully. For instance, consider each the following models:

1. (1)

   \(L_{\beta}[x]\), where \(\beta \) is least such that \(L_{\beta}[x] \models \) “\({\mathsf{ZFC}}\) - Powerset + every set of reals has a sharp and \(\omega _{2}\) exists.”

2. (2)

   \(L_{\beta}[E,x]\), where \(L_{\beta}[E,x]\) is least such that \(L_{\beta}[E,x] \models \) “\({\mathsf{ZFC}}\) - Powerset + \(M_{1}^{\sharp}(y)\) exists for all \(y\) and \(\omega _{1}\) exists.”

The expectation is that hypotheses such as these can be expressed in terms of determinacy assertions for layered unions by varying the two parameters above, as well as \(\boldsymbol {\Gamma}\). Since any general result along the lines of the Third Separation Reduction Theorem must allow for such expressions, we think that the situation is subtle. There is a vast and extremely deep body of work to be carried out in this direction, hopefully not by the author.

Decreeing this vague discussion concluded, we now proceed to the statement of the Third Separation Reduction Theorem.

Theorem 91

Separation Reduction, III (Part I)

Let \(m\in \mathbb{N}\). Suppose that for each \(l \in \mathbb{N}\), \(\boldsymbol {\Gamma}_{l}\prec \boldsymbol {\Delta}^{1}_{m}\) is a definable, effectively treeable Wadge class. Let \(\boldsymbol {\Gamma}= \bigcup _{l\in \mathbb{N}} \boldsymbol {\Gamma}_{l}\).

Suppose that every \(x\in \mathbb{R}\) belongs to a \(\beta \)-model of \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) simultaneously satisfying \(\boldsymbol {\Gamma}_{l}\)-determinacy for all \(l\in \mathbb{N}\). Then, all sets in

are determined.

Remark 92

One could imagine relaxing the restriction \(\boldsymbol {\Gamma}_{l} \prec \boldsymbol {\Delta}^{1}_{m}\) in the statement of Theorem 91 by paying with stronger monotone-induction principles. We leave these generalizations to the reader’s imagination.

As mentioned before, we suspect that the conclusion of Theorem 91 reverses. In particular:

Conjecture 93

Separation Reduction Conjecture

Suppose that for each \(l\in \mathbb{N}\), \(\boldsymbol {\Gamma}_{l}\) is a Borel Wadge class and define \(\boldsymbol {\Gamma}= \bigcup _{l\in \mathbb{N}}\boldsymbol {\Gamma}_{l}\). Assume determinacy for all sets in

Then, every real \(x\in \mathbb{N}\) belongs to a \(\beta \)-model of \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) simultaneously satisfying \(\boldsymbol {\Gamma}_{l}\)-Determinacy for all \(l\in \mathbb{N}\).

As we mentioned before, we do not have a proof of the conjecture in full generality, though we have one in our main case of interest, and in a few others. It is possible that the conjecture will be proved by an argument along similar lines. Our main cases of interest are the Wadge classes in the separation hierarchy beyond \(\boldsymbol {\Sigma}^{0}_{3}\). This result will suffice for our complete analysis of determinacy principles below \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \Pi ^{1}_{4}{-}{ \mathsf{CA_{0}}}\). Hence, this partial reversal is what we call the second part of the Third Separation Reduction Theorem.

Theorem 94

Separation Reduction, III (Part II)

Suppose that \(\boldsymbol {\Pi}^{1}_{3}{-}\mathsf{TI}\) holds. Let \(x\in \mathbb{R}\). Suppose that all sets in \(S(\alpha{-}\Sigma ^{0}_{2}, \Sigma ^{0}_{3})(x)\) are determined. Then, there is a \(\beta \)-model of \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) satisfying \(S(\gamma{-}\boldsymbol {\Sigma}^{0}_{2}, \boldsymbol {\Sigma}^{0}_{3})\)-determinacy for all \(\gamma <\alpha \) and containing \(x\).

Here, recall that \(\boldsymbol {\Pi}^{1}_{3}{-}\mathsf{TI}\) is the schema of transfinite induction for \(\boldsymbol {\Pi}^{1}_{3}\) formulas along wellorders, i.e., a formalization of “if \(\alpha \) is a wellorder, then transfinite induction for \(\phi \) holds along \(\alpha \),” as \(\phi \) ranges over all \(\boldsymbol {\Pi}^{1}_{3}\) formulas.

Our proof of Theorem 94 is by induction on \(\alpha \) (as opposed to the proofs of the previous Separation Reduction Theorems, which were direct) and thus requires assuming some transfinite induction. We first turn to the proof of Theorem 91 in the following section, with the proof of Theorem 94 postponed to §6.4.

6.1 Proof of the third separation reduction theorem, part I

We need to begin the proof by establishing some notation. As usual, we assume by relativization that all relevant data are given recursively. Consider sets \(A_{l} \in \Gamma _{l^{*}}\) and \(C_{l} \in \Sigma ^{0}_{2}\), where the mapping \(l\mapsto l^{*}\) is recursive, and the sets \(C_{l}\) are disjoint (this is justified by Lemma 10). We let

and

be the envelope of \(A\). We represent

as an increasing union of \(\Pi ^{0}_{1}\) sets. Finally, we let \(B\) be a set in \(\Pi ^{0}_{3}\). We may assume without loss of generality that \(B\) is disjoint from \(C\), so that the winning set of the game under consideration is

Since \(B \in \Pi ^{0}_{3}\), we can choose sets \(B_{i}\) and \(B_{i,j}\) such that

We suppose that \(L_{\beta}\) is a model of \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) satisfying \(\boldsymbol {\Gamma}_{l}\)-determinacy for each \(l\in \mathbb{N}\). Most of the proof takes place entirely within \(L_{\beta}\). Note that \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) implies \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{CA_{0}}}\) (as instances of comprehension can be viewed as one-step inductions in which the inductive variable plays no role), which in turn implies \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{AC_{0}}}\) and \(\boldsymbol {\Pi}^{1}_{m+1}{-}\)Induction.

Remark 95

Even though we are assuming that all data, including the definition of \(A\) and \(C\), are given recursively, the hypothesis is that \(L_{\beta}\) is a model of boldface \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) and boldface \(\boldsymbol {\Gamma}_{l}\)-determinacy for each \(l\in \mathbb{N}\). The effective part of the hypothesis is that we are working with \(L_{\beta}\), as opposed to \(L_{\beta}[x]\) for some \(x\in \mathbb{R}\).

In his unpublished 1974 proof of \(\boldsymbol {\Delta}^{0}_{4}\)-Determinacy, Martin made use of certain properties \(P^{s}(T)\) which we call the Martin properties. We shall need the following conditions, which are inspired by (though different from) Martin’s:

Definition 96

Let \(i\in \mathbb{N}\) and \(T\) be a game tree. We define the properties \(Q^{\varnothing}(T)\) and \(Q^{i}(T)\) by

1. (1)

   \(Q^{\varnothing}(T)\) asserts that Player II has a winning strategy in \(G(W,T)\).

2. (2)

   \(Q^{i}(T)\) asserts that Player I has a quasi-strategy \(U\subset T\) such that the following hold:

   1. (a)

      \([U] \subset B_{i} \cup C\), and

   2. (b)

      \(Q^{\varnothing}(U)\) fails.

A strategy \(U\) witnessing \(Q^{i}(T)\) is said to strongly witness \(Q^{i}(T)\) if \(Q^{\varnothing}(U_{q})\) fails for all \(q\in U\).

Definition 97

Let \(i\in \mathbb{N}\). We define an operator \(\Phi _{i,T}\) by putting \(p \in \Phi _{i,T}(X)\) if and only if there are \(n, l\in \mathbb{N}\) such that for every strategy \(\sigma \) for Player II, there is \(x\in \mathbb{R}\) such that the following hold:

1. (1)

   \(x\in [\sigma ]\);

2. (2)

   \(x \in W\); and

3. (3)

   \(\forall k\in \mathbb{N}\, (x\upharpoonright k \in B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup X)\).

Lemma 98

The operator \(\Phi _{i,T}\) is \(\Pi ^{1}_{m+1}\) and monotone.

Proof

Monotonicity is immediate, as the inductive variable appears only positively in the definition of \(\Phi _{i,T}\). To see that it is \(\Pi ^{1}_{m+1}\) it suffices to contract the outermost natural-number quantifiers with the real-number quantifiers that follow. This is made possible by \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{AC_{0}}}\), which follows from \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{CA_{0}}}\), which follows from \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\). Note that this argument uses the fact that \(\boldsymbol {\Gamma}_{l} \prec \boldsymbol {\Delta}^{1}_{m}\) for each \(l\in \mathbb{N}\). □

Lemma 99

Work in \(L_{\beta}\) and let \(i\in \mathbb{N}\). Write \(\Phi = \Phi _{i,T}\) and suppose \(p\in \Phi ^{\infty}\). Then, \(Q^{i}(T_{p})\) holds and this is strongly witnessed by a strategy \(K\).

Proof

The entirety of the proof of the lemma takes place in \(L_{\beta}\). The proof of this lemma draws ideas from [11] (though this has not appeared in print at the time of writing this) as well as from Hachtman [36] and Montalbán-Shore [66]. The main difference is that we need to incorporate the sets \(C_{l}\) into the construction. While the situation is simplified here by the fact that we only deal with two Martin-like properties at a time, it is also made complex by the presence of the sets \(A_{l}\) and \(C_{l}\). We remark that the axiom \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) plays a completely different role in this argument. In [11], it is used to deal with multiple Martin conditions; here, it is used to deal with the complexity of the classes \(\boldsymbol {\Gamma}_{l}\). (When restricting to Borel classes, the hypothesis is \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\).)

The lemma is proved by induction on \(\alpha = \alpha ^{p} = \) rank of \(p\) in \(\Phi \). Let \(n = n^{p}\) be the least number \(n\) witnessing the outermost existential quantifier of the formula \(p \in \Phi ^{\alpha}\) and \(l = l^{p}\) be defined similarly. We describe the construction of the winning strategy \(K\). Suppose \(K_{q}\) has been described for all \(q\) with \(\alpha ^{q} < \alpha ^{p}\). Suppose also that \(p\) has odd length, so that \(p\) was obtained after a play by Player I. We need to decide, for each \(a \in \mathbb{N}\), which \(b\in \mathbb{N}\) is such that \(p^{\frown }a^{\frown }b\) gets put into \(K_{p}\). We put \(p^{\frown }a^{\frown }b\) into \(K_{p}\) if for every strategy \(\sigma \) for Player II, there is \(x\in [\sigma ]\) such that the following hold:

1. (1)

   \(p^{\frown }a^{\frown }b \sqsubset x\),

2. (2)

   \(x \in W\), and

3. (3)

   \(\forall k\in \mathbb{N} (x\upharpoonright k \in B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{<\alpha})\).

Continue adding positions to \(K_{p}\) this way (still using \(n = n^{p}\), \(l = l^{p}\) and \(\alpha = \alpha ^{p}\)) until a position \(q\) is reached such that

if ever. If so, then \(q \in \Phi ^{<\alpha}\) and \(K_{q}\) is defined by induction hypothesis. We continue playing according to \(K_{q}\).

Claim 100

\(K_{p}\) forms a set.

Proof

From its definition, one can readily see that \(K_{p}\) is definable by a Boolean combination of \(\Pi ^{1}_{m+1}\) formulas from the parameters \(\Phi ^{\infty}\) and \(T\), so the claim follows by \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{CA_{0}}}\), which follows from \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\). □

Claim 101

\(K_{p}\) is a quasi-strategy for Player I.

Proof

Otherwise, let \(q \in K_{p}\) and \(a\) be such that \(q^{\frown }a^{\frown }b \notin K_{p}\) for all \(b\). Let us assume, inductively, that \(\alpha ^{q} = \alpha ^{p}\). Thus, for each \(b\) there is a strategy \(\sigma _{b}\) for Player II such that \(q^{\frown }a \in \sigma _{b}\) but for all \(x \in [\sigma _{b}]\) extending \(q^{\frown }a^{\frown }b\), we have one of the following:

1. (1)

   \(x \notin W\), or

2. (2)

   \(\exists k\in \mathbb{N} (x\upharpoonright k \notin B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{<\alpha})\).

However, \(q \in K_{p}\) and \(\alpha ^{p} = \alpha ^{q}\), so \(q \in B_{i,n} \cup \bigcup _{l'< l} C_{l',n}\). Define a strategy \(\sigma \subset T_{q}\) for Player II by responding \(a\) to \(q\) and then responding according to \(\sigma _{b}\) to extensions of \(q^{\frown }a^{\frown }b\), for each \(b\). This is possible by \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{AC_{0}}}\) and our hypothesis that each class \(\boldsymbol {\Gamma}_{l}\) is contained in \(\boldsymbol {\Delta}^{1}_{m}\). Since \(q \in K_{p}\), there is \(x \in [\sigma ]\) such that the following hold:

1. (1)

   \(x \in W\), and

2. (2)

   \(\forall k\in \mathbb{N} (x\upharpoonright k \in B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{<\alpha})\).

But then letting \(b\) be the coordinate in \(x\) immediately following \(a\), we obtain a contradiction to the choice of \(\sigma _{b}\). □

Claim 102

\([K_{p}]\subset B_{i} \cup C\).

Proof

By induction on \(\alpha \). Let \(x \in [K_{p}]\). If every initial segment of \(x\) belongs to \(B_{i,n} \cup \bigcup _{l'< l} C_{l',n}\), then clearly we have

Otherwise, let \(q \sqsubset x\) be the least initial segment of \(x\) not in \(B_{i,n} \cup \bigcup _{l'< l} C_{l',n}\). Then, \(x \in [K_{q}]\) and the result follows by induction hypothesis. □

Claim 103

Suppose \(q \in K_{p}\) and \(\alpha ^{q} = \alpha ^{p}\). Then, \(n^{q} \leq n^{p}\) and \(l^{q} \leq l^{p}\), so that in particular \(n^{p}\) and \(l^{p}\) witness the outermost quantifiers of the formula \(q \in \Phi ^{\alpha}\).

Proof

This is immediate from the definition of \(\Phi \) and the fact that the sets \(B_{i,n}\) are increasing in \(n\), for each \(i\). □

Claim 104

For every \(q \in K_{p}\), Player II does not have a winning strategy for \(G(W,(K_{p})_{q})\).

Proof

This is proved again by induction on \(\alpha \). Towards a contradiction suppose the claim fails and without loss of generality, suppose it fails at \(p\), so that Player II has a winning strategy for \(G(W,K_{p})\), say \(\sigma \).

Subclaim 105

\(\alpha ^{q} = \alpha ^{p}\) for all \(q \in \sigma \).

Proof

Otherwise, letting \(q\in \sigma \) be minimal (with respect to extension) such that \(\alpha ^{q} < \alpha ^{p}\), the induction hypothesis yields that Player II does not have a winning strategy for \(G(W, (K_{p})_{q}) = G(W,K_{q})\). However, \(\sigma _{q}\) is clearly such a winning strategy, which is a contradiction. This proves the subclaim. □

Let us first expand \(\sigma \) into a strategy \(\sigma ^{+}\) in the sense of \(T_{p}\) (\(\sigma \) itself is only defined against moves in \(K_{p}\)). Suppose that \(q \in T_{p}\) is minimal such that \(q \notin K_{p}\) and \(p\) has odd length. By the subclaim, all predecessors of \(q\) of odd length, say \(\bar{q}\), were obtained from the definition of \(K_{p}\) using \(\alpha = \alpha ^{p}\), \(n = n^{p}\), and \(l= l^{p}\). Thus, that \(q \notin K_{q}\) means that there is some strategy \(\sigma ^{q}\) for Player II in \(T_{q}\) such that whenever \(x \in [\sigma ^{q}]\), one of the following holds:

1. (1)

   \(x \notin W\), or

2. (2)

   \(\exists k\in \mathbb{N} (x\upharpoonright k \notin B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{<\alpha})\).

Define \(\sigma ^{+}\) by playing according to \(\sigma ^{q}\) whenever such a \(q\) is reached. Note that \(\sigma ^{+}\) forms a set, by \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{AC_{0}}}\). More importantly, \(\sigma ^{+}\) is a strategy in the sense of the game tree \(T_{p}\).

Using the fact that \(p \in \Phi ^{\alpha}\), as witnessed by \(n\), \(l\) (as well as Claim 103 in order not to lose generality from our assumption that the claim fails at \(p\)) and applying this fact to \(\sigma ^{+}\), we obtain some \(x \in [\sigma ^{+}]\) such that the following hold:

1. (1)

   \(x \in W\), and

2. (2)

   \(\forall k\in \mathbb{N} (x\upharpoonright k \in B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{<\alpha})\).

Now, such an \(x\) must be consistent with \(K_{p}\), for otherwise, letting \(q\sqsubset x\) be least such that \(q \notin K_{p}\), we have \(x\in [\sigma ^{q}]\), from which it follows that one of \(x \in W\) or \(\forall k\in \mathbb{N} (x\upharpoonright k \in B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{<\alpha})\) must fail, by choice of \(\sigma ^{q}\). Hence, \(x \in [K_{p}]\). Since \(\sigma ^{+}\) agrees with \(\sigma \) when faced against moves in \(K_{p}\), we have

contradicting the fact that \(x \in W\). This proves the claim. □

Since we have proved all the necessary claims, the proof of Lemma 99 is complete. □

Lemma 106

Work in \(L_{\beta}\) and let \(i\in \mathbb{N}\). Write \(\Phi = \Phi _{i,T}\) and suppose \(p\notin \Phi ^{\infty}\). Then, \(Q^{\varnothing}(T_{p})\) holds.

Proof

Since \(p \notin \Phi ^{\infty }= \Phi (\Phi ^{\infty})\), we have, for each \(n,l\in \mathbb{N}\), the following statement \((\dagger )_{n,l}\): there exists a strategy \(\sigma _{n,l}\) for Player II such that whenever \(x \in [\sigma ]\), one of the following holds:

1. (1)

   \(x \notin W\), or

2. (2)

   \(\exists k\in \mathbb{N}\, (x\upharpoonright k \notin B_{i,n} \cup \bigcup _{l'< l} C_{l',n} \cup \Phi ^{\infty})\).

Apply \((\dagger )_{0,1}\) to obtain such a strategy \(\sigma _{0,1}\) and play according to it until a position

is reached, if ever. If so, use the fact that \(q \notin \Phi ^{\infty}\) to obtain, via \((\dagger )_{1,1}\), a strategy \(\sigma _{1,1} \subset T_{q}\), and so on (note: \(\sigma _{1,1}\) depends on \(q\)). Do this in a way such that every infinite play \(x\) constructed this way is either eventually consistent with a fixed strategy \(\sigma _{n,l}\), or otherwise all properties \((\dagger )_{n,l}\) were appealed to during the course of the game (e.g., by fixing some recursive enumeration of all pairs \((n,l)\) in order-type \(\omega \) in advance). Let \(\sigma \) be the strategy just described. The existence of \(\sigma \) is guaranteed by Strong \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{DC}}\), which follows from \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{CA_{0}}}\) (in \(L_{\beta}\)).

By construction, every \(x\in [\sigma ]\) either satisfies

in which case, letting \((n,l)\) be the least such pair, \(x\) is consistent with some strategy \(\sigma _{n,l}\) employed in the construction of \(\sigma \) and thus \(x \notin W\); or else \(x\) avoids all such sets, in which case we have

so \(\sigma \) is a winning strategy. □

We now proceed to the proof of Theorem 91. Suppose Player II does not have a winning strategy for \(G(W,T)\) in \(L_{\beta}\). We describe a winning strategy for Player I in \(G(W,T)\) definable over \(L_{\beta}\).

We describe the construction of the winning (quasi-)strategy \(\tau \) by stages. At each stage, Player I refines her current quasi-strategy to a sub-quasi-strategy, and possibly plays according to some other auxiliary strategies for some turns. Assume that the game is at stage \(n\) and that the play thus far is \(p_{n-1}\). Inductively, Player I has been playing according to a quasi-strategy \(U^{n-1}\) such that

where \(U^{-1} = T\) and \(B_{-1} = \mathbb{R}\). Inductively, Player II does not have a winning strategy for \(G(W, U^{n-1}_{p_{n-1}})\) from the current position. By Lemma 106, \(p_{n-1} \in \Phi _{i,U^{n-1}}^{\infty}\) for all \(i\in \mathbb{N}\) and in particular

Using this fact, we obtain, through Lemma 99, a quasi-strategy \(U^{n}\subset U^{n-1}_{p_{n-1}}\) strongly witnessing \(Q^{n}(U^{n-1}_{p_{n-1}})\). This will ensure that if \(x\) is according to \(\tau \), then

Now, using some fixed recursive bijection \(\rho : \mathbb{N}\to \mathbb{N}\times \mathbb{N}\), we consider the open game

If Player I has a winning strategy for \(G(\bar{C}_{\rho (n)}, U^{n})\), play according to it until a position

has been reached. Using the fact that \(p_{n} \in U^{n}\) and the choice of \(U^{n}\), we have that Player II does not have a winning strategy for \(G(W, U^{n}_{p_{n}})\). Proceed to stage \(n+1\).

If, on the other hand, Player II does have a winning strategy for \(G(\bar{C}_{\rho (n)}, U^{n})\), let \(N_{n}\) be Player II’s non-losing quasi-strategy for \(G(\bar{C}_{\rho (n)}, U^{n})\). We describe what \(\tau \) shall do as long as Player II plays according to \(N_{n}\). If Player II ever leaves \(N_{n}\), then the game is at a position at which Player I has a winning strategy \(G(\bar{C}_{\rho (n)}, U^{n})\), and we may continue as above in order to proceed to stage \(n+1\). Otherwise, as long as Player II plays according to \(N_{n}\), we proceed as follows.

Claim 107

Player II does not have a winning strategy for \(G(W, N_{n})\).

Proof

Recall that \(N_{n}\) is a quasi-strategy for Player II in the sense of the game tree \(U^{n}\). Thus, \(N_{n}\) only restricts Player II’s moves. Hence, any winning strategy for Player II in \(G(W, N_{n})\) is also a winning strategy for Player II in \(G(W, U^{n})\), and such a strategy cannot exist by choice of \(U^{n}\). □

Claim 108

Player I has a winning strategy for \(G(W, N_{n})\).

Proof

Put \(\rho (n) = (k,l)\). By definition of \(N_{n}\), we have

Since the sets \(C_{k}\) are pairwise disjoint, we have

the game \(W\) coincides with \(A_{k}\) when restricted to the game tree \(N_{n}\). By the previous claim, Player II does not have a winning strategy in this game. Since \(G(A_{k}, N_{n})\) is a game in \(\boldsymbol {\Gamma}_{k^{*}}\) for some \(k^{*}\) and

it follows that Player I has a winning strategy for \(G(A_{k}, N_{n}) = G(W, N_{n})\). Note that this use of \(\boldsymbol {\Gamma}_{k^{*}}{-}\)Determinacy hinges on the fact that \(\boldsymbol {\Gamma}_{k^{*}}\) is treeable. □

Let \(\tau _{n}\) be such a winning strategy for \(G(W, N_{n})\). As long as Player II plays within \(N_{n}\), we have \(\tau \) follow \(\tau _{n}\). This completes the description of \(\tau \). Although technically what we described was a quasi-strategy, standard methods can be used to further refine \(\tau \) into a single-valued strategy (namely, at each stage we may demand that the strategy choose the least possible value allowed by \(\tau \)).

Let \(x \in [\tau ]\). Let the degree of \(x\), \(\deg (x)\), be the number of stages reached during the course of the game \(x\). If \(\deg (x) < \infty \), then \(x\) is eventually consistent with a winning strategy \(\tau _{n}\) for some game \(G(A_{k}, N_{n})\) as in the proof of the last claim, and \(x\) is eventually consistent with a quasi-strategy \(N_{n}\) for Player II. It follows that

so \(x\) is won by Player I. If \(\deg (x) = \infty \), then the construction of \(\tau \) restricted to \(x\) involved infinitely many refinements of quasi-strategies \(U^{n}\) by Player I. By equation (6.1) for each \(n\), we have

However, for each \(n\), progressing from stage \(n\) to stage \(n+1\) requires Player I avoiding the set \(C_{\rho (n)}\) (which is a closed set). Hence, we have

Therefore, \(\tau \) is indeed a winning strategy. This completes the proof of Theorem 91.

The proof of Theorem 91 reveals details on the complexity of winning strategies for games in \(\mathsf{LU}(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma}, \boldsymbol {\Sigma}^{0}_{3})\). Since this fact will be used later, we mention it as a corollary:

Corollary 109

Let \(m\in \mathbb{N}\). Suppose that for each \(l \in \mathbb{N}\), \(\boldsymbol {\Gamma}_{l}\prec \boldsymbol {\Delta}^{1}_{m}\) is a definable, effectively treeable Wadge class. Let \(\boldsymbol {\Gamma}= \bigcup _{l\in \mathbb{N}} \boldsymbol {\Gamma}_{l}\).

Suppose that \(x\in \mathbb{R}\) and the game tree \(T\) belong to a \(\beta \)-model \(M\) of \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) simultaneously satisfying \(\boldsymbol {\Gamma}_{l}\)-determinacy for all \(l\in \mathbb{N}\). Then, for all

if Player I has a winning strategy for \(G(A,T)\), then she has one in \(M\). If Player II has a winning strategy for \(G(A,T)\), then she has one which is definable over \(M\).

6.2 Consequences of the third separation reduction theorem, part I

The corollaries we state in this section will concern only Borel Wadge classes. These could be generalized to projective Wadge classes in straightforward ways, by appealing to stronger hypotheses of monotone induction as in Theorem 91.

Corollary 110

Suppose that \(\lambda \) is a countable limit ordinal and \(\alpha \) is a countable ordinal. Suppose that \(\boldsymbol {\Gamma}\) is a Borel Wadge class closed under unions and intersections with \(\boldsymbol {\Sigma}^{0}_{2}\) and \(\boldsymbol {\Pi}^{0}_{2}\). Suppose that for every \(x\in \mathbb{R}\), there is a \(\beta \)-model of \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) satisfying \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy. Then, \(S((\alpha +1){-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy holds.

Proof

This follows from Theorem 91 and the representation Lemma 12. □

Corollary 111

Suppose that \(\lambda \) is a countable limit ordinal and \(\alpha \) is a countable ordinal. Suppose that \(\boldsymbol {\Gamma}\) is a Borel Wadge class and that for each \(x\in \mathbb{R}\), there is a \(\beta \)-model of \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) satisfying \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy for all \(\alpha <\lambda \). Then, \(S(\lambda{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma})\)-Determinacy holds.

Proof

This follows from Theorem 91 and the representation Lemma 13. □

It seems unlikely that one can generalize Corollary 89 without additional assumptions on \(\boldsymbol {\Gamma}\) or without additional set-existence axioms. We mention a result in this vein from a stronger hypothesis.

Definition 112

Let \(\Gamma \) be a class of formulae. \(\beta \)-model reflection for \(\Gamma \) sentences relative to a theory \(T\) is the schema asserting that if a formula \(\varphi \in \Gamma \) holds, then it also holds in some \(\beta \)-model of \(T\).

Corollary 113

Let \(\boldsymbol {\Gamma}\) be a definable \(\boldsymbol {\Delta}^{1}_{m}\) Wadge class closed under unions and intersections with \(\boldsymbol {\Sigma}^{0}_{2}\) and under \(\boldsymbol {\Sigma}^{0}_{2}\)-separated unions. Suppose also that \(\beta \)-model reflection for \(\boldsymbol {\Sigma}^{1}_{m+1}\) sentences relative to \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) holds. Then, the following are equivalent:

1. (1)

   \(\boldsymbol {\Gamma}{-}\)Determinacy, and

2. (2)

   \(B(\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Gamma},\Delta ( \boldsymbol {\Sigma}^{0}_{3}\wedge \boldsymbol {\Pi}^{0}_{3})){-}\)Determinacy.

Proof

We prove by induction that

holds. Suppose (6.2) holds for all \(\bar{\alpha}<\alpha \). If \(\alpha = \bar{\alpha}+1\), we use Lemma 11 to see that

By reflection, (6.2) holds in some \(\beta \)-model of \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\), so we can apply Theorem 91. The limit case is similar, using Lemma 16. □

Corollary (6.2) in particular says that \(\boldsymbol {\Pi}^{1}_{4}{-}{\mathsf{CA_{0}}}\) implies determinacy for sets in \(\Delta (\boldsymbol {\Sigma}^{0}_{3}\wedge \boldsymbol {\Pi}^{0}_{3})\). Of course, by Montalbán-Shore, we know that \(\boldsymbol {\Pi}^{1}_{4}{-}{\mathsf{CA_{0}}}\) in fact implies determinacy for sets in \(\boldsymbol {\Sigma}^{0}_{3}\wedge \boldsymbol {\Pi}^{0}_{3}\), but we will soon reduce our upper bound on the strength of \(\Delta (\boldsymbol {\Sigma}^{0}_{3}\wedge \boldsymbol {\Pi}^{0}_{3})\)-Determinacy considerably below the strength of \(\boldsymbol {\Sigma}^{0}_{3}\wedge \boldsymbol {\Pi}^{0}_{3}{-}\)Determinacy. Another consequence of Corollary 113 is that:

We conjecture that this is optimal in the following sense:

Conjecture 114

Optimal Transfer, III

\(\boldsymbol {\Pi}^{1}_{3}{-}{\mathsf{CA_{0}}}\) does not prove the implication:

6.3 \(\alpha \)-Suitable constructibility

The key concept for the proof of Part II of the Third Separation Reduction Theorem will be that of suitability.

Definition 115

We define the notion of an \(\alpha \)-suitable model by induction on \(\alpha \). A model of the form \(L_{\gamma}\) is called \(\alpha \)-suitable if \(\alpha <\gamma \) and one of the following holds:

1. (1)

   \(L_{\gamma}\models \boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) and for each \(\bar{\alpha}<\alpha \) we have \(L_{\gamma }\models \) “every \(x\in \mathbb{R}\) belongs to an \(\bar{\alpha}\)-suitable model,” or

2. (2)

   \(\gamma \) is a limit of ordinals satisfying (1).

We also call a model \(L_{\gamma}\) \({<}\alpha \)-suitable if it is \(\bar{\alpha}\)-suitable for all \(\bar{\alpha}<\alpha \). Finally, these notions relativize to real parameters in the obvious manner.

Definition 116

An ordinal \(\gamma \) is called \(\alpha \)-suitable if \(L_{\gamma}\) is \(\alpha \)-suitable.

Lemma 117

Suppose that \(L_{\gamma}\) is \(\alpha \)-suitable. Suppose moreover that \(x \in \mathbb{R}\cap L_{\gamma}\). Then,

and every \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})(x)\) game has a winning strategy definable over \(L_{\gamma}\).

Proof

This is proved by a straightforward induction, using the Third Separation Reduction Theorem, Part I, together with the representation lemmata (as in Corollary 110 and Corollary 111). □

Definition 118

Let \(\alpha < \omega _{1}\) and let \(L_{\gamma}\) be \(\alpha \)-suitable. We define the canonical strategy \(\sigma _{W}^{L_{\gamma}}\) for a game \(W \in S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\) relative to the model \(L_{\gamma}\).

1. (1)

   Suppose that \(L_{\gamma }\models \) “Player I has a winning strategy for \(W\).” Then \(\sigma _{W}^{L_{\gamma}}\) is the \(<_{L_{\gamma}}\)-least such strategy.

2. (2)

   Suppose that \(L_{\gamma}\models \) “Player I does not have a winning strategy for \(W\).” Then, let \(\sigma _{W}^{L_{\gamma}}\) be the strategy for Player II constructed in the proof of the Third Separation Reduction Theorem, Part I. Such a strategy is uniformly definable over all \(\alpha \)-suitable \(L_{\gamma}\).

If \(\sigma _{W}^{L_{\gamma}}\) is a strategy for Player I, then \(\sigma _{W}^{L_{\gamma}} \in L_{\gamma}\) by definition. If it is a strategy for Player II, then in general \(\sigma _{W}^{L_{\gamma}}\) will not be an element of \(L_{\gamma}\) (this will follow from the results of §6.4 e.g., when \(L_{\gamma}\) is the smallest \(\alpha \)-suitable model), but it will be definable over it, and indeed by inspecting the proof of Theorem 91, we see that

Canonical strategies will play an important role in the proof of the Third Separation Reduction Theorem, Part II. Before moving on to this proof, let us prove some results which impose upper bounds on the strength of suitability. Suitability should be thought of as a weak form of \(\boldsymbol {\Pi}^{1}_{3}{-}{\mathsf{CA_{0}}}\), and it could possibly play a role in Reverse Mathematics as a theory to gauge the strength of other principles (and this is precisely what it does here). We mention some open problems related to it in §9.

Theorem 119

Suppose that \(L_{\xi _{0}} \prec _{\Sigma _{2}} L_{\xi _{1}}\) and \(\xi _{1}\) is admissible. Then, \(L_{\xi _{0}}\) is a limit of \(\alpha \)-suitable ordinals for every \(\alpha <\xi _{0}\).

In order to prove the theorem, we need to introduce a definition due to Welch.

Definition 120

Let \(\beta \) be an ordinal. A \(\Sigma _{2}\)-nesting on \(\beta \) consists of an illfounded end-extension \(M\) of \(L_{\beta}\), together with sequences \(\{\zeta _{i}:i\in \mathbb{N}\}\) and \(\{s_{i}:i \in \mathbb{N}\}\) of \(M\)-ordinals such that for all \(i\in \mathbb{N}\), we have

1. (1)

   \(\zeta _{i} \leq \zeta _{i+1}\),

2. (2)

   \(s_{i+1} < s_{i}\), and

3. (3)

   \(L_{\zeta _{i}} \prec _{\Sigma _{2}} L_{s_{i}}\).

Lemma 121

Hachtman [36]

Suppose that \(\beta \) admits a \(\Sigma _{2}\)-nesting. Then,

We can now proceed to the proof of Theorem 119.

Proof of Theorem 119

This is done by a small variant of an argument of Welch [86], who first observed that the model \(L_{\xi _{0}}\) from the theorem contains winning strategies for all \(\Sigma ^{0}_{3}\) games. Welch’s argument shows that if \(L_{\xi _{0}} \prec _{\Sigma _{2}} L_{\xi _{1}}\) and \(\xi _{1}\) is admissible, then \(L_{\xi _{0}} \prec _{\Sigma _{2}} L_{\zeta}\) for some \(\zeta < \xi _{1}\). To see this, consider an enumeration of all \(\Sigma _{2}\) formulas with parameters in \(L_{\xi _{0}}\). For each of these formulas \(\phi \), either \(L_{\xi _{0}} \models \phi \), in which case \(L_{\zeta}\models \phi \) for all \(\xi _{0}\leq \zeta \leq \xi _{1}\) by the downwards correctness of \(\Pi _{1}\) formulas, or else

Let \(U\) be the set of all such \(\phi \) for which \(L_{\xi _{0}} \not \models \phi \), so \(U \in L_{\xi _{0}+1}\). Suppose that \(\phi = \exists x\,\forall y\, \phi _{0}(x,y) \in U\), and suppose without loss of generality that the quantifiers range over ordinals. Let

be defined by

Note that for all \(\phi \in U\), \(f_{\phi}\) must have a closure point below \(\xi _{1}\), by admissibility, and because \(f_{\phi}\) is a total function. Let \(\alpha _{\phi}\) be the least ordinal closed under \(f_{\phi}\). Then, the function

is total and \(\Sigma _{1}\) over \(L_{\xi _{1}}\) so its range must be bounded by some least \(\alpha <\xi _{1}\) closed under \(f\). Thus we have

But then by the same argument, we similarly obtain arbitrarily large \(\alpha <\xi _{1}\) for which

holds. It follows, by an overspill consideration, that if \(M\) is an illfounded model of \({\mathsf{KP}}\) with wellfounded part equal to \(L_{\xi _{1}}\), then there are arbitrarily small illfounded ordinals \(a \in M\) such that

Thus, we can find an infinite descending sequence of these, which will form a \(\Sigma _{2}\)-nesting on \(L_{\xi _{1}}\).

We have shown that \(L_{\xi _{1}}\) admits a \(\Sigma _{2}\)-nesting. However, Welch (unpublished) has shown that \(L_{\xi _{1}}\) is not the least ordinal admitting a \(\Sigma _{2}\)-nesting. Let us include his argument: given an ordinal \(\alpha \) with \({\xi _{0}} <\alpha \), we consider a certain theory \(\Sigma (\alpha )\) in a countable fragment of \(L_{\omega _{1},\omega}\). Using constants for ordinals \({<}\alpha \) and constants \(\dot{\xi}\) and \(\dot{s}_{i}\), \(\Sigma (\alpha )\) asserts that \({\mathsf{KP}}\) holds, \({\mathsf{Ord}}\) contains all ordinals \({<}\alpha \), \(L_{\dot{\xi}} \prec _{\Sigma _{2}} L_{\dot{s}_{i}}\) for each \(i\), and \(\dot{s}_{i+1} < \dot{s}_{i}\) for each \(i\). For each admissible \(\alpha \in (\xi _{0}, \xi _{1})\), \(\Sigma (\alpha )\) has a model, namely, \(M\) (from the previous paragraph). In particular, \(\Sigma (\xi _{0}^{+})\) has a model. This is a true \(\Sigma ^{1}_{1}\) fact about \(\xi _{0}^{+}\) and thus is witnessed by a model in \(L_{\xi _{0}^{++}+1}\), e.g., by the Gandy basis theorem, and thus by a model in \(L_{\xi _{1}}\). Hence, we have

By elementarity, we have

and indeed by relativizing, we have

By Hachtman’s theorem, if \(\xi \) admits a \(\Sigma _{2}\)-nesting, then \(L_{\xi}\models \boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\), so \(\xi \) is 1-suitable. We have shown that \(\xi _{0}\) is a limit of 1-suitable ordinals. By \(\Sigma _{2}\)-elementarity, \(\xi _{1}\) is too, so \(\xi _{1}\) is 1-suitable. Now repeating the same argument and by transfinite induction on ordinals \({<}\xi _{0}\) we see that \(L_{\xi _{0}}\) is a limit of \(\alpha \)-suitable ordinals for all \(\alpha <\xi _{0}\), as desired. This proves the theorem. □

Before moving on, we remark the following consequence of Lemma 117 and Theorem 119:

Theorem 122

Suppose that \(L_{\xi _{0}}\prec _{\Sigma _{2}} L_{\xi _{1}}\) and \(\xi _{1}\) is admissible. Then,

This is, of course, best possible, since \(\boldsymbol {\Sigma}^{0}_{3}\wedge \boldsymbol {\Pi}^{0}_{3}{-}\)Determinacy is much stronger than \(\boldsymbol {\Pi}^{1}_{3}{-}{\mathsf{CA_{0}}}\), e.g. by Montalbán-Shore [66] or by [11].

6.4 Proof of the third separation reduction theorem, part II

Let \(\alpha \) be as in the statement of the theorem and suppose that all \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) games are determined. We prove that there is an \(\alpha \)-suitable model. The proof is by induction on \(\alpha \) and relativizes to prove that every real belongs to an \(\alpha \)-suitable model. We suspect that there may be a different proof of the results in this section which is direct (i.e., avoids induction), but our argument is inductive. Thus, we decree:

Convention. Throughout §6.4, assume \(\boldsymbol {\Pi}^{1}_{3}{-}\mathsf{TI}\).

We shall assume (by relativization) that \(\alpha \) is recursive. Let us mention that the case \(\alpha = 0\) is known and due to Welch [84] and Hachtman [36]. The main result we will prove is:

Theorem 123

Let \(\alpha \) be a countable ordinal. For every \(x\in \mathbb{R}\) such that \(\alpha <\omega _{1}^{x}\), there is an \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) game \(G_{x,\alpha}\) such that the following hold:

1. (1)

   Player I does not have a winning strategy for \(G_{x,\alpha}\),

2. (2)

   If \(\sigma \) is a winning strategy for Player II for \(G_{x,\alpha}\), then there is an \(\alpha \)-suitable model \(L_{\gamma}[x]\) containing \(x\) and the theory of the least such model is recursive in the hyperjump of the theory of any \({<}\alpha \)-suitable model of the form \(L_{\bar{\gamma}}\) such that \(\sigma \in L_{\bar{\gamma}}\).

Moreover, the function mapping \(x\) and \(\alpha \) to the definition of \(G_{x,\alpha}\) is recursive and the (index of the) Turing reduction of the theory of \(L_{\gamma}[x]\) to the hyperjump of the theory of a model \(L_{\bar{\gamma}}\) as above does not depend on \(x\), \(\sigma \), or \(\bar{\gamma}\).

As we mentioned earlier, the proof of Theorem 123 is by induction on \(\alpha \). The induction, however, will make use not only of the statement of Theorem 123 itself, but also of some consequences of it, which we now record. All the results in §6.4.1 are proved together with Theorem 123 by simultaneous induction on \(\alpha \).

6.4.1 Consequences of Theorem 123 and its proof to be used in the induction

Theorem 124

Let \(\alpha \) be a recursive ordinal. Suppose that all \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) games are determined. Let \(\gamma \) be least such that \(L_{\gamma}\) is \(\alpha \)-suitable. Then,

(The relation \(\equiv _{1}\) is one-one reducibility in both directions.)

In fact, to each \(\Sigma _{1}\) formula \(\phi (\cdot )\) we can effectively associate the definition of a \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\) set \(G_{\phi}\subset \mathbb{R}\times \mathbb{R}\), such that for all \(z\in \mathbb{R}\cap L_{\gamma}\), the following are equivalent:

1. (1)

   \(L_{\gamma }\models \phi (z)\), and

2. (2)

   Player I has a winning strategy for \(G_{z,\phi} = \{x: (x,z) \in G_{\phi}\}\).

The theorem is proved in §6.4.3 from the induction hypothesis below \(\alpha \) by a small variation of the argument used to prove Theorem 123.

Corollary 125

Let \(\alpha \) be a countable ordinal. Suppose that all \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) games are determined. Then, every real \(x\) belongs to a \({<}\alpha \)-suitable model.

Proof of the Corollary for \(\alpha \) from the induction hypothesis below \(\alpha \)

We prove this for \(x=0\) and relativize. The claim is immediate from Theorem 123 for successor \(\alpha \), so we may assume that \(\alpha \) is a limit ordinal. We have

Here, the equality follows from Louveau [51, Lemma 1.4] and Lemma 215 in Appendix B. Alternatively, it is not hard to verify directly that

In any case, we have

where the second implication follows from the Second Separation Reduction Theorem applied to the set-theoretic union of \(S({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) and its dual.

Now, for each \(\gamma <\alpha \), let \(L_{\beta _{\gamma}}\) be the least \(\gamma \)-suitable model. This exists by Theorem 123 applied to all \(\gamma <\alpha \) (which we can do by the induction hypothesis on \(\alpha \)). The idea is now to argue that we can collect all the \(L_{\beta _{\gamma}}\) and form the union. This would be trivial if we had enough choice or collection, which we do not seem to have. The easiest solution is to find a model of choice where the rest of the argument can take place.

We use Theorem 124 for all ordinals \({<}\alpha \). Let \(S\) be the set of all pairs \((\gamma , d)\), where \(\gamma <\alpha \) and \(d\) is the definition of a game of the form \(G_{\varnothing , \phi}\) given by Theorem 124 for \(\phi \) some \(\Sigma _{1}\) sentence. This set exists by \({\mathsf{RCA_{0}}}\) since the definitions of these games can be obtained recursively from the \(\Sigma _{1}\) formulas. By hypothesis, all games referred to by elements of \(S\) are determined. Use \(S({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3}){-}{ \mathsf{SR}}\) to collect winning strategies for all such games into a set \(S^{*}\).

We now apply Theorem 123 to the case \(\alpha = 0\) to obtain a 0-suitable model containing \(S^{*}\). The least such model \(L_{\eta}\) satisfies \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) and thus \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{CA_{0}}}\). We now work in \(L_{\eta}\) with the set \(S^{*}\).

For each \(\gamma <\alpha \), we have

and the least one is \(L_{\beta _{\gamma}}\). Using the strategies for the games \(G_{\varnothing ,\phi}\) contained in \(S^{*}\), we can recover the theory of \(L_{\beta _{\gamma}}\) uniformly from \(S^{*}\) (since it is \(\Delta _{1}\) in \(L_{\beta _{\gamma +1}}\)). By the admissibility of \(\eta \), we then have

It remains to show that \(L_{\beta}\) is \({<}\alpha \)-suitable. Given \(\gamma <\alpha \) and \(\xi <\beta \), find \(\zeta <\alpha \) large enough so that \(\xi <\beta _{\zeta}\) and \(\gamma < \zeta \). By induction, \(L_{\beta _{\zeta}}\) is \(\gamma \)-suitable. We have shown that for each \(\gamma \), \(\beta \) is a limit of \(\gamma \)-suitable ordinals and thus \(\gamma \)-suitable too. This completes the proof of the corollary. □

Theorem 126

Let \(\alpha \) be a countable ordinal and \(x\in \mathbb{R}\). Suppose that all \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})^{ \breve{}}\) games are determined. Let \(\gamma \) be least such that \(L_{\gamma}[x]\) is \(\alpha \)-suitable and let \(G\) be an \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) game. Then one of the following holds:

1. (1)

   Player I has a winning strategy for \(G\) in \(L_{\gamma}[x]\), or

2. (2)

   Player II has a winning strategy for \(G\) which is \(\Delta _{2}\)-definable over \(L_{\gamma}[x]\).

However, not all \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) games have a winning strategy in \(L_{\gamma}[x]\).

The theorem is proved in §6.4.4 from Theorem 123 for \(\alpha \).

6.4.2 Proof of Theorem 123 from the induction hypothesis below \(\alpha \)

We shall consider a Friedman-style game such that from any winning strategy for it, we can recover the theory of an \(\alpha \)-suitable model. In this game, Players I and II play consistent and complete theories \(T_{I}\) and \(T_{II}\) satisfying the usual Skolem axioms. We will use the induction hypothesis below \(\alpha \) to assume that the game given by this construction for \(\gamma <\alpha \) has been defined. The induction hypothesis will also be used to obtain Corollary 125 for \(\alpha \). Games of this type have been considered in many instances in the literature for various purposes. However, the one here is somewhat more involved. The novel aspect in our construction is, roughly, that the game will seek to revert to an auxiliary game \(G\) of strictly lower complexity. This auxiliary game \(G\) will be chosen in such a way that \(G\) belongs to both models specified by the theories \(T_{I}\) and \(T_{II}\), but these disagree on who the winner of \(G\) should be. We will then choose strategies for \(G\) from \(T_{I}\) and \(T_{II}\) and face them off against each other, in a sort of “game within a game.” This game \(G\) will be another instance of this same game but for an ordinal strictly smaller than \(\alpha \). Hence, we avoid circularity with the aid of the induction hypothesis.

More specifically, players I and II alternate turns considering, according to some fixed ordering thereof, all formulas in the language of set theory and either “accepting” them, or “rejecting” them. The sets of accepted formulas form theories \(T_{I}\) and \(T_{II}\) in the language of set theory.

The game has some basic open rules which are closed for each players: these are

1. (1)

   \(T_{I}\) and \(T_{II}\) are consistent and complete.

2. (2)

   Whenever a player accepts a formula of the form \(\exists x\, \phi (x)\), she must also immediately name a (witnessing) formula of the form \(\psi (y)\) and (when the time comes) accept the formula

   $$ \big(\exists !y\, \psi (y)\big) \wedge \phi (y). $$

The interpretation of the second clause is that in any model \(M\) of \(T_{I}\) or \(T_{II}\), any true formula with an outermost existential quantifier can have this quantifier witnessed by an element of \(M\) which is definable. This implies that the theories \(T_{I}\) and \(T_{II}\) have uniquely determined minimum models \(M_{I}\) and \(M_{II}\) (the proof is standard so far). The remainder of the rules refer to various conditions which these models should satisfy. While the low complexity of the payoff set does not allow us to force the players to play wellfounded models, the rules of the game will encourage them not to play models with very simple infinite descending sequences. In particular, we will allow Player I infinitely many attempts at constructing an infinite descending sequence through \(M_{II}\). Each attempt consists of a “list” of terms. At any point during the game, Player I might add an entry to any of the lists \(l_{k}\) (this is done in addition to the other moves required). This entry must be a formula \(\psi (y)\) for which

1. (i)

   Player II has previously accepted the formula \(\exists !y \psi (y) \wedge \exists y\in {\mathsf{Ord}}\, \psi (y)\), and, moreover,

2. (ii)

   for every other entry \(\psi '\) in the list \(l_{k}\), Player II has previously accepted the formula \(\exists y, y' (\psi (y) \wedge \psi '(y') \wedge y < y')\).

The idea of this is that if Player I manages to fill in a list with infinitely many entries, then she will have identified an illfounded sequence through \(M_{II}\). Instead of giving Player I a single attempt at building such a sequence, we give her infinitely many. This idea of allowing Player I to point out an infinite descending sequence through Player II’s model is from [84]. The novel idea in our proof is given by rule (4) below, as well as the arguments below showing that it works.

The remaining rules of the game are:

1. (1)

   \(M_{I}\) and \(M_{II}\) are \(\omega \)-models.

2. (2)

   \(T_{I}\) and \(T_{II}\) extend \({\mathsf{KP}}\) or \({\mathsf{KPl}}\) and contain the axioms \(V = L\) and “I am \({<}\alpha \)-suitable.”

3. (3)

   If \(T_{II} \in M_{I}\) or if \(M_{I} = M_{II}\), then Player I wins. Otherwise, proceed to the following conditions.

4. (4)

   Suppose that for some \(\gamma <\alpha \), there are

   1. (a)

      a parameter \(x \in \mathbb{R}\cap M_{I} \cap M_{II}\), and

   2. (b)

      an \(S(\gamma{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) game \(G\)

   such that \(M_{II}\) thinks that Player I has a winning strategy for \(G\) but \(M_{I}\) does not. If so, choose minimal such \(\gamma \), \(x\), and \(G\) (according to their codes in ℕ; see the proof of Lemma 127 below for the precise meaning of this). Let \(\sigma _{G}^{M_{I}}\) and \(\sigma _{G}^{M_{II}}\) be the canonical strategies for \(G\) relative to \(M_{I}\) and \(M_{II}\), and let \(y\) be the result of facing off \(\sigma _{G}^{M_{I}}\) against \(\sigma _{G}^{M_{II}}\). Then, Player I wins the game if and only if \(y \notin G\).

5. (5)

   Suppose otherwise that for no \(\gamma <\alpha \) and no parameter \(x \in \mathbb{R}\) in \(M_{I}\cap M_{II}\) does such a game exist. Then, Player I wins if and only if one of her infinitely many attempts at identifying an infinite descending sequence through Player II’s model is successful.

Explanation: The idea of the game is that players I and II construct \(\omega \)-models \(M_{I}\) and \(M_{II}\) of \(V = L\) which think they are \({<}\alpha \)-suitable. Player I’s ultimate goal is to play a “longer” model, in the sense that either the theory of Player II’s model belongs to \(M_{I}\) or else \(M_{I} = M_{II}\). However, Player I would like to prevent Player II from cheating by playing an illfounded model, in which case such a goal would become harder to attain via a wellfounded model. Player I has two tools to help with this. The first one is to directly point out an illfounded sequence in \(M_{II}\). In this case, Player II will be disqualified. The other tool is to point out \(M_{II}\)’s mistaken beliefs that some \(S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\) game relative to a common parameter is determined in favor of Player I. Player I will then be able to win by defeating \(M_{II}\)’s purported winning strategy. These two tools will help Player I point out mistakes in Player II’s model, but only up to a certain extent. The first tool will be sufficient to defeat Player II’s plays if the wellfounded part of \(M_{II}\) does not satisfy enough reflection properties. The second tool will be sufficient to defeat Player II’s plays if the wellfounded part of \(M_{II}\) does not satisfy enough comprehension (in the form of determinacy). Ultimately, we will see that Player II will nonetheless be able to win the game; however, this will require playing a model whose wellfounded part is \(\alpha \)-suitable, provided that Player I plays her model \(M_{I}\) appropriately. Player I’s model must be any \({<}\alpha \)-suitable model containing Player II’s strategy. If it is, then Player II’s strategy \(\sigma \) must play an illfounded model whose wellfounded part is \(\alpha \)-suitable.

Let us point out that, according to the rules of the game, there is no direct mechanism for Player I to react to Player II’s mistaken claims that Player II has a winning strategy for a \(S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\) game. The reason is that incorporating such a mechanism into the rules directly would increase the complexity of the payoff set (for successor \(\alpha \)). However, this will cause no problems, and indeed we will see that making such mistaken claims is not a good idea for Player II, for a different reason.

Let us first show that the complexity of the payoff set is as required.

Lemma 127

The winning condition of the game is in \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\).

Proof

We show that the winning set belongs to

Note that this class is equal to \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\), by Lemma 12 if \(\alpha \) is a successor, or by Lemma 13 if \(\alpha \) is a limit, in which case we have

These two lemmata can be applied because \(\Sigma ^{0}_{3}\) is trivially closed under unions and intersections with \(\Sigma ^{0}_{2}\) and \(\Pi ^{0}_{2}\), under finite unions and intersections, and under recursive \(\Sigma ^{0}_{2}\)-separated unions (the last claim follows from the effective version of Louveau [51, Lemma 1.4]).

First, observe that the conditions on consistency and completeness, as well as \(T_{I} = T_{II}\) are all \(\Pi ^{0}_{1}\) for each player. Suitability is first-order expressible and thus \(\Delta ^{0}_{1}\). If in a given play \(x\), Player I satisfies these requirements, we say that \(x\) is reasonable; if Player II does not, we say that \(x\) is won by Player I for trivial reasons.

We will verify that the set \(W'\) of all reasonable plays \(x\) such that \(x\) is won by Player I due to (4) or (5) is in the class (6.3).

If so, the remaining clauses can be incorporated as follows: the winning set \(W\) is the set of all reasonable \(x\) such that Player I obeys condition (1) and one of the following holds:

1. (1)

   Player I wins \(x\) for trivial reasons,

2. (2)

   \(x\in W'\),

3. (3)

   Player II does not play an \(\omega \)-model, or

4. (4)

   \(T_{II} \in M_{I}\).

Thus, assuming \(W'\) is in (6.3), \(W\) is also in (6.3), since the sets in (6.3) are closed under intersections with \(\Pi ^{0}_{2}\) sets and unions with \(\Sigma ^{0}_{2}\) sets, a fact which follows from the corresponding closure properties of \(\Sigma ^{0}_{3}\) and \(S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})\) (cf. Appendix B).

Rule (4) of the game asks whether there is a formula \(\phi _{0}\) which over \(M_{I}\) defines a real \(x\) in the common part of \(M_{I}\) and \(M_{II}\) such that \(M_{I}\) and \(M_{II}\) satisfy a certain property about \(x\). Put \(x \in C_{l}\) if \(x\) is reasonable and \(l = \langle l_{0}, l_{1}, e, \gamma \rangle \) and the following hold for the run \(x\) of the game:

1. (1)

   \(\gamma < \alpha \) [Note: \(\alpha \) is recursive and \(\gamma \) is an integer coding an element of \(\alpha \)];

2. (2)

   \(l_{0}, l_{1} \in \mathbb{N}\) are the Gödel numbers of formulas \(\phi _{0}\), \(\phi _{1}\) defining the same real number \(x^{*}\) in \(M_{I}\) and \(M_{II}\);

3. (3)

   \(e\) is the index of a formula defining an \(S(\gamma{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x^{*})\) set for which \(M_{II}\) thinks Player I has a winning strategy but \(M_{I}\) does not;

4. (4)

   for all \(l' <_{\mathbb{N}} l\) with \(l' = \langle l_{0}', l_{1}', e', \gamma '\rangle \), one of the previous conditions fails.

It is easy to see that \(C_{l}\) is \(\Sigma ^{0}_{2}\) (indeed, a Boolean combination of \(\Sigma ^{0}_{1}\) sets) and that the sets \(C_{l}\) are pairwise disjoint.

Define \(A_{l}\) to be the collection of all plays \(x\) such that \(x \in C_{l}\) and, additionally, letting \(G^{*}\) be the game given by the index \(e\), and letting \(\sigma _{G^{*}}^{M_{I}}\), \(\sigma _{G^{*}}^{M_{II}}\), and \(y = \) the result of facing off \(\sigma _{G^{*}}^{M_{I}}\) against \(\sigma _{G^{*}}^{M_{II}}\) be as above, we have \(y\notin G^{*}\). Note that the canonical strategy \(\sigma _{G^{*}}^{M_{II}}\) for Player I (in the game \(G^{*}\)) in \(M_{II}\) is recursive in the play \(x\), since it is an element of \(M_{II}\). Similarly, the canonical strategy \(\sigma _{G^{*}}^{M_{I}}\) for Player II (in the game \(G^{*}\)) in the model \(M_{I}\) is recursive in \(x\). The reason is that the restriction of \(\sigma _{G^{*}}^{M_{I}}\) to moves of length \(k\in \mathbb{N}\) can be computed uniformly in \(k\) over all \(\gamma \)-suitable models by carrying out an iteration of \(k\) many monotone \(\Pi ^{1}_{2}\) operators (as in the proof of Part I of the Third Separation Reduction Theorem) and, since \(x\) is reasonable, \(M_{I}\) is \({<}\alpha \)-suitable. Since \(S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}\) is closed under recursive substitutions, it follows that \(A_{l} \in S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})\) (\(A_{l}\) demands that \(y\) not belong to \(G^{*}\)).

Finally, define \(B\) to be the set of all reasonable plays \(x\) such that, in \(x\), Player I succeeds at finding an infinite descending sequence through \(M_{II}\) in one of her infinitely many attempts. Then, the set

belongs to \(\mathsf{LU}(\Sigma ^{0}_{2}, S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3}), \Sigma ^{0}_{3})\), as is desired. □

Remark 128

In the proof of Lemma 127, we mentioned that the canonical strategies \(\sigma _{G^{*}}^{M_{I}}\) and \(\sigma _{G^{*}}^{M_{II}}\) were recursive in the play \(x\). Even in the case that \(M_{I}\) and \(M_{II}\) are wellfounded, Theorem 126 asserts that these are generally \(\Delta _{2}\)-definable over \(M_{I}\) and \(M_{II}\) and not necessarily \(\Delta _{1}\)-definable over \(M_{I}\) and \(M_{II}\). Since \(x\) contains the full theory of \(M_{I}\) and \(M_{II}\), the canonical strategies are recursive in \(x\) (uniformly).

Lemma 129

Player I does not have a winning strategy in the game.

Proof

Suppose otherwise, and let \(\sigma \) be such a strategy. By absoluteness, we may assume \(\sigma \in L\). By Corollary 125 (applied to \(\alpha \)) there is a \({<}\alpha \)-suitable model containing \(\sigma \).

Consider the run of the game in which Player I plays according to \(\sigma \) and Player II plays the theory of \(L_{\beta}\), where \(\beta \) is least such that \(\sigma \in L_{\beta}\) and \(L_{\beta}\) is \({<}\alpha \)-suitable. Since \(\sigma \) is a winning strategy, Player I must win this run. However, \(L_{\beta}\) is a wellfounded model, so Player I cannot win by finding an infinite descending sequence. Player I also cannot win by having \(M_{I} = M_{II}\), since in that play Player II would simply be copying Player I’s theory, which would imply that the run is recursive in \(\sigma \). This is impossible by Tarski’s theorem, however, since \(\sigma \in L_{\beta}\). Similarly, Player I cannot win by having \(T_{II} \in M_{I}\), since then Player I’s model would contain \(L_{\beta}\) and thus \(M_{I}\) would be an extension of \(L_{\beta ^{+}}\) by Ville’s lemma. Since the play is recursive in \(\sigma \) and the theory of \(L_{\beta}\), this is again impossible.

The only possibility left is that Player I wins via an auxiliary subgame. However, this is also impossible, for, by \({<}\alpha \)-suitability, if \(x \in \mathbb{R}\cap M_{I}\cap L_{\beta}\), then \(L_{\beta}\) correctly identifies winning strategies for Player I in all \(S({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) games, by the induction hypothesis applied to Theorem 126 (to all ordinals \({<}\alpha \)). □

Lemma 130

Let \(\sigma \) be a winning strategy for Player II in the game. Then, there is an \(\alpha \)-suitable model.

Proof

Let \(y\) be a real coding the least \(L_{\gamma}\) such that \(\sigma \in L_{\gamma}\). Let \(L_{\beta}[y]\) be the least \({<}\alpha \)-suitable model containing \(y\), so that \(L_{\beta }= L_{\beta}[y]\) is the least \({<}\alpha \)-suitable model extending \(L_{\gamma}\). We consider a specific run \(x\) of the game in which Player II plays by \(\sigma \) and Player I plays the theory of \(L_{\beta}\) and attempts to find an infinite descending sequence through \(L_{\beta}\) by following a procedure (to be described below) which is recursive in the theory of \(L_{\beta}\) and in Player II’s play (uniformly for all plays by Player II). If so, then \(M_{II}\) cannot contain \(L_{\beta}\), for then it would extend \(L_{\beta ^{+}}\), which would be a contradiction, since the play is recursive in \(\sigma \) and the theory of \(L_{\beta}\). Similarly, the fact that \(\sigma \) is a winning strategy implies that we cannot have \(M_{II} = L_{\beta}\). Finally, the condition \(T_{II} \notin M_{I}\) implies that Player II’s model cannot be wellfounded. Thus, \(M_{II}\) is an illfounded model with \(\alpha ^{*}:= {\mathsf{Ord}}\cap \text{wfp}(M_{II}) \leq \beta \).

We now describe Player I’s strategy for finding infinite descending sequences through Player II’s model. Player I will set aside infinitely many attempts in order to look for an infinite descending sequence through \(M_{II}\) by following the procedure of Welch [84]. As shown in [84], one of these attempts is guaranteed to succeed unless \(\alpha ^{*}\) admits a \(\Sigma _{2}\)-nesting. She will also set aside infinitely many attempts in order to look for an infinite descending sequence through \(M_{II}\) by following the procedure of [11, Chap. 5] (with \(m=2\) for \(m\) as in [11]). As shown in [11, Chap. 5], if there exists \(a \in M_{II}\setminus \text{wfp}(M_{II})\) such that

and \(L_{\alpha ^{*}} \models \Sigma _{1}{-}\)Separation, then one of these attempts is guaranteed to succeed unless \(\alpha ^{*}\) admits a strong \(\Sigma _{3}\)-nesting. We do not need to define what a strong \(\Sigma _{3}\)-nesting is, but simply mention that it is far too strong: the existence of \(\Sigma _{3}\)-nestings implies the existence of many pairs \((\xi _{0},\xi _{1})\) such that \(L_{\xi _{0}}\prec _{\Sigma _{3}} L_{\xi _{1}}\) (immediately from its definition). Since this is much stronger than the hypothesis of Theorem 119, this would yield the conclusion of the lemma.

Thus, we have:

Claim 131

\(L_{\alpha ^{*}}\models \boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\).

Proof

By the argument in the previous paragraph, if Player II wins the game, then \(L_{\alpha ^{*}}\) admits a \(\Sigma _{2}\)-nesting and thus \(L_{\alpha ^{*}}\models \boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) by Hachtman [36]. □

In order to finish the proof, it suffices to show that for all \(\gamma <\alpha \), and all \(\xi <\alpha ^{*}\), there is \(\zeta \) such that \(\xi < \zeta <\alpha ^{*}\) and \(L_{\zeta}\) is \(\gamma \)-suitable. Suppose otherwise, towards a contradiction. The plan is the following: we will show, using Theorem 124, that \(L_{\alpha ^{*}}\) has many proper \(\Sigma _{1}\)-elementary substructures which themselves are \(\Sigma _{1}\)-elementary substructure of some fixed initial segment of \(M_{II}\). This will imply that \(L_{\alpha ^{*}}\) is also a \(\Sigma _{1}\)-elementary substructure of some fixed initial segment of \(M_{II}\). By the comment above, this implies that \(L_{\alpha ^{*}}\) admits a strong \(\Sigma _{3}\)-nesting, leading to a contradiction.

Recall that, by the rules of the game, \(L_{\beta}\) and \(M_{II}\) are \({<}\alpha \)-suitable. Thus, they will contain \(\gamma \)-suitable models containing arbitrary real parameters for each \(\gamma <\alpha \), though these might in principle be different, even for shared parameters.

As in the proof of Lemma 129, \(L_{\beta}\) correctly determines whether Player I wins a \(S({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})^{ \breve{}}\) game with parameters in \(L_{\beta}\): by the induction hypothesis applied to Theorem 124 and \(\alpha \), whether Player I wins these games is \(\Sigma _{1}\) in any \(\gamma \)-suitable model containing the real parameters, and \(L_{\beta}\) is \({<}\alpha \)-suitable. Moreover, by choice of \(\beta \) and the induction hypothesis applied to Theorem 126, the canonical strategies for such games are all definable over \(L_{\beta}\) (and some of them might even be elements of \(L_{\beta}\)). Thus, rule (4) of the game can never be invoked, for that would result in a win for Player I. We have shown that if \(M_{II}\) believes that Player I wins a \(S({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})^{ \breve{}}\) game with parameters in \(\mathbb{R}\cap M_{I}\cap M_{II}\), then Player I really does win that game. In other words, for all \(x \in \mathbb{R} \cap M_{I} \cap M_{II}\), we have

Let us prove the converse.

Claim 132

For all \(x \in \mathbb{R} \cap M_{I} \cap M_{II}\), either

holds, or the conclusion of the lemma holds.

Proof

Suppose that the equation in the statement of the claim fails and let \(\gamma \) be least for which

for some \(x \in L_{\alpha ^{*}}\). We assume without loss of generality that \(x\) is a code for some initial segment of \(L\). Thus, there is some game in \(S(\gamma{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})(x)^{\breve{}}\) which \(M_{I}\) thinks is won by Player I but \(M_{II}\) does not think so. For such \(x\), let \(\eta _{I}^{x} = \) smallest \(\gamma \)-suitable ordinal such that \(x \in L_{\eta _{I}}\) and let \(\delta _{I}^{x}\) be least such that

and \(x \in L_{\delta _{I}^{x}}\). By the induction hypothesis applied to Theorem 126, we must have \(\alpha ^{*} < \delta _{I}^{x}\), for otherwise the strategy in \(M_{I}\) for Player I in the game would belong to \(L_{\alpha ^{*}}\), a limit of admissibles, and would thus also be a winning strategy in \(M_{II}\), contradicting the choice of \(x\). It follows that \(\alpha ^{*} < \eta _{I}^{x}\), so \(\eta _{I}^{x}\) is simply the smallest \(\gamma \)-suitable ordinal greater than \(\alpha ^{*}\) and does not depend on \(x\), so we may simply write \(\eta _{I}\). [By this, we mean that if \(x'\) is any other real for which (6.5) holds, then \(\eta _{I}^{x'} = \eta _{I}\).] Note that if (6.5) holds for \(x\) and \(x'\) codes some initial segment of \(L_{\alpha ^{*}}\) containing \(x\), then (6.5) holds also for \(x'\), so the set of such \(x'\) is unbounded in \(L_{\alpha ^{*}}\).

For \(x\) such that (6.5) holds, let \(\eta _{II}^{x} \in {\mathsf{Ord}}^{M_{II}} \cup \{{\mathsf{Ord}}^{M_{II}} \}\) be the \(\in ^{M_{II}}\)-least \(\gamma \)-suitable \(M_{II}\)-ordinal containing \(x\) and similarly let \(\delta _{II}^{x}\) be \(M_{II}\)-least such that

and \(x \in L_{\delta ^{x}_{II}}^{M_{II}}\). We cannot have \(\eta _{II}^{x} < \alpha ^{*}\), since then \(\eta _{II}^{x}\) would satisfy the definition of \(\eta _{I}\). Thus, \(\eta _{II}^{x}\) belongs to the illfounded part of \(M_{II}\). By definition, \(M_{II}\) thinks \(\eta _{II}^{x}\) is the least \(\gamma \)-suitable ordinal such that \(x\) belongs to \(L_{\eta _{II}^{x}}\), and so there is no smaller \(\gamma \)-suitable ordinal in the illfounded part of \(M_{II}\). Hence, \(\eta _{II}^{x}\) does not depend on \(x\), in the sense that if \(x'\) is any other real in \(L_{\alpha ^{*}}\) for which (6.5) holds, then \(\eta _{II}^{x} = \eta _{II}^{x'}\). In principle, \(\delta _{II}^{x'}\) might be different for such \(x'\), however.

Case I: There is an \(x \in L_{\alpha ^{*}}\) such that (6.5) holds and \(\delta _{II}^{x} \notin \alpha ^{*}\). Let \(\xi _{II}\) be a nonstandard \(M_{II}\)-ordinal smaller than \(\delta _{II}^{x}\) such that \(L_{\xi _{II}}^{M_{II}}\) satisfies some \(\Sigma _{1}\) fact \(\psi \) about \(x\) which does not hold in any smaller \(L_{\xi '}^{M_{II}}\). Note that such a \(\xi _{II}\) exists, since

so \(L_{\delta ^{x}_{II}}^{M_{II}}\) is the set of reals which are \(\Delta _{1}(x)\) in \(M_{II}\), and thus the set of such ordinals is cofinal in \(\delta ^{x}_{II}\).

Work in \(M_{II}\). By the induction hypothesis applied to Theorem 124, for each formula \(\theta \) in the language of set theory, we can uniformly define \(S(\gamma{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) games \(G_{x,\psi ,\theta}\) for which Player I has a winning strategy in \(M_{II}\) if and only if there is some initial segment of \(L_{\eta _{II}^{x}}^{M_{II}}\), satisfying \(\psi (x)\), and the least such initial segment satisfies \(\theta \).

Even if \(M_{I}\) agrees that there is some initial segment \(L_{\xi _{I}}\) of \(L_{\eta _{I}^{x}}\) satisfying \(\psi \), it cannot possibly agree with \(M_{II}\) on the theory of the least such initial segment, since we must have \(\alpha ^{*}< \xi _{I}\) and thus \(L_{\xi _{I}}\) must contain a wellordering of ℕ of length \(\alpha ^{*}\). The fact that \(\alpha ^{*}<\xi _{I}\) holds because otherwise \(\xi _{I}\) would satisfy the definition of \(\xi _{II}\) in \(M_{II}\), which was chosen to be non-standard. We have argued that \(M_{I}\) and \(M_{II}\) disagree about the \(\Delta _{1}\)-theory of the smallest \(\gamma \)-suitable model containing \(x\), so it follows from Theorem 124 that there is some game in \(S(\gamma{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) which \(M_{II}\) thinks is won by Player I but \(M_{I}\) does not. This contradicts (6.4). Thus, Case I is impossible.

Case II: For all \(x \in L_{\alpha ^{*}}\) such that (6.5) holds, we have \(\delta _{II}^{x} < \alpha ^{*}\). In this case, we use the fact that the set of \(x\in L_{\alpha ^{*}}\) for which (6.5) holds is unbounded in \(L_{\alpha ^{*}}\). From this follows that \(\alpha ^{*}\) is a limit of ordinals \(\delta \) for which

and hence

By the comment preceding Claim 131, the conclusion of the lemma must hold, for otherwise Player I would succeed at identifying an infinite descending sequence through \(M_{II}\) as in [11, Chap. 5] (and as mentioned in the proof of Lemma 130 before the statement of Claim 131), which would contradict the fact that Player II is following \(\sigma \), a winning strategy. This proves the claim. □

By Claim 131, we have

so to complete the proof of the lemma, it still remains to show that for all \(\xi <\alpha ^{*}\) and all \(\gamma <\alpha \), there is some \(\gamma \)-suitable \(\zeta \) with \(\xi <\zeta <\alpha ^{*}\). Suppose towards a contradiction that no such \(\zeta \) exists. Consider some \(x\in \mathbb{R}\cap L_{\alpha ^{*}}\) which (without loss of generality) codes some initial segment of \(L_{\alpha ^{*}}\) and for which

For any \(x\) for which (6.6) holds, we define \(\eta _{I}^{x}\) and \(\delta _{I}^{x}\) to be, respectively, the least \(\gamma \)-suitable ordinal such that \(x \in L_{\eta _{I}^{x}}\) and the least ordinal such that

As before, \(\eta _{I}^{x}\) does not depend on \(x\), so we may simply call it \(\eta _{I}\).

Similarly, we define \(\eta _{II}\) and \(\delta _{II}^{x}\) as in the proof of Claim 132 whenever \(x\) is such that (6.6) holds. Unlike the situation of Claim 132, we now use the statement of Claim 132 itself together with the induction hypothesis applied to Theorem 126 to conclude that \(\delta _{I}^{x} = \delta _{II}^{x}\) and in particular \(\delta _{II}^{x}<\alpha ^{*}\). Since the set of all \(x\) for which (6.6) holds is cofinal in \(L_{\alpha ^{*}}\), \(\alpha ^{*}\) is a limit of ordinals \(\delta \) for which

and hence

This leads to a contradiction as in the Case II in the proof of Claim 132. This completes the proof of the lemma. □

Theorem 123 for \(\alpha \) now follows from Lemma 127, Lemma 129, and Lemma 130. By Lemma 130, if \(\sigma \) is any winning strategy for Player II in the game and \(L_{\gamma}\) is any \({<}\alpha \)-suitable model containing \(\sigma \) (this exists by Corollary 125), then, letting \(x\) be the play described above (which is uniformly recursive in the theory of \(L_{\gamma}\)), \(\sigma (x)\) produces an illfounded model of \(V=L\) whose wellfounded part is \(\alpha \)-suitable. Thus, the least \(\alpha \)-suitable model \(L_{\beta}\) containing \(\sigma \) is recursive in \(\mathcal{O}^{\sigma ,Th(L_{\gamma})}\), and the Turing reduction does not depend on \(\sigma \), \(\gamma \), or \(\alpha \). Finally, the proof relativizes in a straightforward way to real parameters.

This completes the proof of Theorem 123 for \(\alpha \).

6.4.3 Proof of Theorem 124 for \(\alpha \) from Theorem 123

We will only sketch the proof, which is a simple modification of that of Theorem 123. Suppose \(\phi \) is a \(\Sigma _{1}\) sentence. We define a game as follows: players I and II must play theories \(T_{I}\) and \(T_{II}\) as in the proof of Theorem 123. Player I’s theory must contain the assertion “\(\phi ^{M}\) holds, where \(M\) is the least \(\alpha \)-suitable model if it exists, or \(M = V\) otherwise” and Player II’s theory must contain the assertion “\(\phi \) fails, where \(M\) is the least \(\alpha \)-suitable model if it exists, or \(M = V\) otherwise.” If these rules are respected, the game is decided on the basis of the rules of the game from Theorem 123.

By Theorem 123, there is an \(\alpha \)-suitable model \(L_{\gamma}\). If \(L_{\gamma }\not \models \phi \), then the proof of Lemma 129 shows as before that Player I cannot have a winning strategy. However, if \(L_{\gamma}\models \phi \), then Player II cannot have a winning strategy. This is because by the proof of Lemma 130 there is a play consistent with the strategy in which Player II must play an end-extension of \(L_{\gamma}\) (namely, the play considered in the proof of Lemma 130). But since \(\phi \) is \(\Sigma _{1}\), such a play by Player II cannot include the formula \(\lnot \phi \). This completes the proof of Theorem 124.

6.4.4 Proof of Theorem 126 for \(\alpha \) from Theorem 123

Let \(x\) and \(\gamma \) be as in the statement of the theorem. For every game in \(S(\alpha{-}\Sigma ^{0}_{2}, \Sigma ^{0}_{3})(x)\), it follows from Lemma 117 (the inductive form of the Third Separation Reduction Theorem, Part I) that either the player with \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})(x)\) payoff has a winning strategy in \(L_{\gamma}[x]\), or else the player with \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})^{\breve{}}(x)\) payoff has a winning strategy definable over it (in fact, \(\Delta _{2}\)-definable, by the proof of the Third Separation Reduction Theorem, Part I). Moreover, since \(L_{\gamma}[x]\) is the least \(\alpha \)-suitable model containing \(x\), it satisfies \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) and thus \(\Sigma _{1}\)-Separation. It follows that if all \(S(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})(x)\) games had winning strategies in \(L_{\gamma}[x]\), they would belong to \(L_{\xi}[x]\), where \(\xi \) is least such that

which, together by Theorem 123 would lead to a contradiction to Tarski’s theorem. This proves the theorem.

6.4.5 On truth games for suitability

The reader might wonder whether there is an analog of Theorem 82 for the classes \(S(\alpha{-}\boldsymbol {\Sigma}^{0}_{2})\); e.g., whether there is a game in

which is similar to that in the previous section but in which Player II is required to play the true theory of the least \(\alpha \)-suitable model.

We do not know if such a game exists. Naturally, the games in the previous section can be viewed as truth games for \(\alpha \)-suitability of complexity \(S((\alpha +1){-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})\). For limit cases one can do slightly better.

Theorem 133

Suppose that \(B({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3}){-}{\mathsf{SR}}\) holds. Let \(\alpha \) be a limit recursive ordinal. Then, there is a \(B(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})\) game \(H\) for which the following holds:

1. (1)

   Player I does not have a winning strategy for \(H\).

2. (2)

   If \(\sigma \) is a winning strategy for Player II for \(H\), then there is an admissible \(L_{\beta}\) such that for all \(\xi <\beta \) and all \(\gamma <\alpha \) there is a \(\gamma \)-suitable \(L_{\zeta}\) with \(\xi <\zeta <\alpha \).

Proof

We sketch the proof. The game \(H\) is a variant of the one considered in the proof of Theorem 123. In it, players I and II play theories \(T_{I}\) and \(T_{II}\) as before, but we do not allow Player I any attempts at identifying any infinite descending sequences through Player II’s model.

The rules of the game are obtained from those in the proof of Theorem 123 simply by omitting rule (5). Let us make some comments about this.

First, the payoff of the game is now in \(B(\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})\). This follows from Lemma 14, since the argument of Lemma 127 shows that the payoff belongs to

Second, since \(B({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3})\) is closed under complements, rule (4) is invoked whenever the models disagree on whether Player I has a winning strategy for some game in \(S({<}\gamma{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) (not only when \(M_{II}\) thinks that Player I has a winning strategy and \(M_{I}\) does not).

Third, the argument of Lemma 129 shows that Player I cannot have a winning strategy. Note that this argument requires Corollary 125 applied inductively, and its proof requires \(B({<}\alpha{-}\Sigma ^{0}_{2},\Sigma ^{0}_{3}){-}{\mathsf{SR}}\).

Finally, suppose that \(\sigma \) is a winning strategy for Player II. Consider a play as in the proof of Lemma 130 in which Player I plays the theory of some \({<}\alpha \)-suitable model \(L_{\beta}\). As in Lemma 130, Player II must play some illfounded \(M_{II}\) with wellfounded part \(L_{\alpha ^{*}}\) such that \(\alpha ^{*}\leq \beta \). As in Lemma 130, we see that in order for Player II not to lose via an auxiliary subgame, \(L_{\alpha ^{*}}\) must correctly determine whether Player I wins a game in \(S({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\).

Claim 134

For all \(\xi <\alpha ^{*}\) and all \(\gamma <\alpha \) there is a \(\gamma \)-suitable \(L_{\zeta}\) with \(\xi <\zeta <\alpha \).

Proof

Fix \(\xi <\alpha ^{*}\). For each \(\gamma <\alpha \) let \(\eta _{I,\gamma}^{\xi}\) and \(\eta _{II,\gamma}^{\xi}\) be the least \(\gamma \)-suitable ordinal greater than \(\xi \) in \(M_{I}\) and \(M_{II}\). These exist since \(\alpha \) is a limit and \(M_{I}\) and \(M_{II}\) are \({<}\alpha \)-suitable. let \(\delta _{I,\gamma}^{\xi}\) be least such that

and let \(\delta _{II,\gamma}^{\xi}\) be defined analogously. As in Claim 132, we use the fact that \(M_{I}\) and \(M_{II}\) agree on whether Player I has winning strategies for games in \(S({<}\alpha{-}\boldsymbol {\Sigma}^{0}_{2},\boldsymbol {\Sigma}^{0}_{3})\) to show that

(This is the argument that reaches a contradiction from the hypothesis in Case I in the proof of Claim 132.) However, this holds for every \(\gamma <\alpha \), so for all \(\gamma <\alpha \) we have

where the first inequality follows e.g., from Theorem 126. This proves the claim. □

To finish the proof, we observe that since \(\alpha ^{*}\) is the wellfounded part of an illfounded model of \(V = L\), we must have

by Ville’s lemma. □

6.5 Separation reduction for \(\Pi ^{1}_{n}{-}{\mathsf{CA_{0}}}\)

In this section, we briefly mention some results which, although not directly relevant for our main goals in this article, provide some broader context. These results will not be used in the following sections, so the reader who is interested in precise reverse-mathematical equivalences of determinacy principle might wish to proceed to §7.

By combining the proof of the Third Separation Reduction Theorem, Part I, with the methods of [11, Chap. 3], we can prove the following variant of Theorem 91:

Theorem 135

Let \(m_{0},m_{1}\in \mathbb{N}\) be nonzero. Suppose that for each \(l \in \mathbb{N}\), \(\boldsymbol {\Gamma}_{l}\prec \boldsymbol {\Delta}^{1}_{m_{0}}\) is a definable, treeable Wadge class. Let \(\boldsymbol {\Gamma}= \bigcup _{l\in \mathbb{N}} \boldsymbol {\Gamma}_{l}\).

Suppose that every \(x\in \mathbb{R}\) belongs to a \(\beta _{m_{1}}\)-model of \(\boldsymbol {\Pi}^{1}_{m_{0} + m_{1}}{-}{\mathsf{MI}}\) simultaneously satisfying \(\boldsymbol {\Gamma}_{l}\)-determinacy for all \(l\in \mathbb{N}\). Then, all sets in

are determined.

Unfortunately we do not have a reversal for Theorem 135, and indeed the hypothesis of Theorem 135 is much too strong. In fact, a weaker hypothesis which also suffices (and which is likely to be optimal) is demanding the existence of \(\Sigma _{m_{0}+m_{1}}\)-burrows (in the sense of [11]) satisfying \(\boldsymbol {\Gamma}_{l}{-}\)Determinacy for all \(l\in \mathbb{N}\). We mention this as a theorem:

Theorem 136

Let \(m_{0},m_{1}\in \mathbb{N}\) be nonzero. Suppose that for each \(l \in \mathbb{N}\), \(\boldsymbol {\Gamma}_{l}\prec \boldsymbol {\Delta}^{1}_{m_{0}}\) is a definable, treeable Wadge class. Let \(\boldsymbol {\Gamma}= \bigcup _{l\in \mathbb{N}} \boldsymbol {\Gamma}_{l}\).

Suppose that every \(x\in \mathbb{R}\) belongs to a \(\Sigma _{m_{0} + m_{1}}\)-burrow (in the sense of [11]) simultaneously satisfying \(\boldsymbol {\Gamma}_{l}\)-determinacy for all \(l\in \mathbb{N}\). Then, all sets in

are determined.

We shall not prove this refined result, which would require merging the ideas of Theorem 91 with the proof below and the machinery of [11, Chap. 4]. However, we shall prove Theorem 135 and deduce some interesting consequences from it.

6.5.1 Proof of Theorem 135

We sketch the proof, omitting some steps which are analogous to those in the proof of Theorem 91 and also some steps which are analogous to those in the proofs of the upper bounds for the strength of \(m{-}\boldsymbol {\Sigma}^{0}_{3}{-}\)Determinacy given in Chap. 3 of [11]. We shall, for simplicity of notation, focus on the case where \(m_{0} = 1\) and \(m= m_{1}\) is even. Let \(B \in m{-}\boldsymbol {\Pi}^{0}_{3}\) and let \(A \in m{-}\Pi ^{0}_{3}\) be written as

where

and where the sequence of \(\{B_{i}: i < m\}\) is decreasing, the sequence \(\{B_{i,j} : j\in \mathbb{N}\}\) is decreasing for each \(i\), and the sequence \(\{B_{i,j,n}:n\in \mathbb{N}\}\) is increasing for each \(i\) and each \(j\).

We also let \(A_{l} \in \Gamma _{l}\) and \(C_{l} \in \Sigma ^{0}_{2}\) for each \(l\). Write

with \(C_{l,n} \in \Pi ^{0}_{1}\) and, writing

we assume that \(W \cap C_{l} = A_{l} \cap C_{l}\) for each \(l\in \mathbb{N}\). We prove that \(W\) is determined.

Let \(T\) be a game tree. We shall make use of a modified version of the Martin properties for this game which we denote by \(Q^{s}(T)\); these are inspired by the properties in the proof of Theorem 91. Let \(s\in \mathbb{N}^{< m}\). By induction, we define:

1. (1)

   \(Q^{\varnothing}(T)\) asserts that Player I has a winning strategy in \(G(W,T)\).

2. (2)

   If \(s^{\frown }i\) has odd length, then \(Q^{s^{\frown }i}(T)\) asserts that Player II has a quasi-strategy \(U\subset T\) such that the following hold:

   1. (a)

      \([U]\subset \bar{W} \cup B_{m-\text{\textsc{lth}}(s)-1, i}\), and

   2. (b)

      \(Q^{s}(U)\) fails.

3. (3)

   If \(s^{\frown }i\) has even length \({<}m\), then \(Q^{s^{\frown }i}(T)\) asserts that Player I has a quasi-strategy \(U\subset T\) such that the following hold:

   1. (a)

      \([U]\subset W \cup B_{m-\text{\textsc{lth}}(s)-1, i}\), and

   2. (b)

      \(Q^{s}(U)\) fails.

4. (4)

   If \(s^{\frown }i\) has length equal to \(m\), then \(Q^{s^{\frown }i}(T)\) asserts that Player I has a quasi-strategy \(U\) such that the following hold:

   1. (a)

      \([U]\subset C \cup B_{0,i}\), and

   2. (b)

      \(Q^{s}(U)\) fails.

The conditions \(Q^{s}\) are similar to the Martin properties \(P^{s}\) (see Montalbán-Shore [66] or [11]), except that they are defined in terms of the set \(W\) rather than \(B\), when \(\text{\textsc{lth}}(s) < m\). When \(\text{\textsc{lth}}(s) = m\), \(Q^{s}\) is defined in terms of \(C\), much like the condition in the proof of Theorem 91. The notions of “witnessing” and “strongly witnessing” are defined as before. The main idea in the proof is considering the operator \(\Phi _{s,i,T}\) defined below:

Definition 137

We put \(p \in \Phi _{s,i,T}(X)\) if and only if there exist \(n,l\in \mathbb{N}\) such that for every quasi-strategy \(S\subset T_{p}\) for Player II,

either:

\(\exists x\in [S]\) such that the following hold:

1. (a)

   \(x \in W\setminus B_{1, s(m-2)}\), and

2. (b)

   \(\forall k\in \mathbb{N}\, x\upharpoonright k \in B_{0,i,n} \cup \bigcup _{l'< l} C_{l',n} \cup X\);

or:

\(\exists U \subset S\) a quasi-strategy for Player I such that the following hold:

1. (a)

   \(U\) witnesses \(Q^{s\upharpoonright m-2}(S)\), and

2. (b)

   \(\forall q \in U\, q \in B_{0,i,n} \cup \bigcup _{l'< l} C_{l',n} \cup X\).

Note that the disjunction in Definition 137 is inclusive. By combining the proofs of Lemma 99 and Lemma 106 with the proof of the “main lemma” of [11], we obtain:

Lemma 138

Let \(s \in \mathbb{N}^{m-1}\), \(i\in \mathbb{N}\), and \(\Phi = \Phi _{s,i,T}\). Suppose that strong \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{DC}}\) holds and that \(\Phi ^{\infty}\) exists. Suppose moreover that \(p\in \Phi ^{\infty}\). Then, \(Q^{s^{\frown }i}(T_{p})\) holds and this is strongly witnessed by a strategy \(K_{p}\).

Lemma 139

Let \(s \in \mathbb{N}^{m-1}\), \(i\in \mathbb{N}\), and \(\Phi = \Phi _{s,i,T}\). Suppose that strong \(\boldsymbol {\Sigma}^{1}_{m+1}{-}{\mathsf{DC}}\) holds and that \(\Phi ^{\infty}\) exists. Suppose moreover that \(p\notin \Phi ^{\infty}\). Then, \(Q^{s}(T_{p})\) holds and this is strongly witnessed by a strategy \(K_{p}\).

The following is the key lemma:

Lemma 140

Let \(s \in \mathbb{N}^{m-1}\) and \(i\in \mathbb{N}\). Suppose that \(L_{\beta}\) is a \(\beta _{m}\)-model of \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) with \(T \in L_{\beta}\). Suppose that \(L_{\beta}\models Q^{s^{\frown }i}(T)\). Then, there is a quasi-strategy \(U\subset T\) for Player I witnessing \(Q^{s\upharpoonright m-2}(T)\) definable over \(L_{\beta}\).

Proof

This is proved by a modification of the proof of Theorem 91 beginning under the proof of Lemma 106. Work in \(L_{\beta}\) and suppose that \(Q^{s^{\frown }i}(T)\) holds, so that \(Q^{s}(T)\) fails by \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\) together with Lemma 138 and Lemma 139. We describe the construction of a quasi-strategy \(U\) witnessing \(Q^{s\upharpoonright m-2}(T)\) by stages. Each stage can be carried out in \(L_{\beta}\) and thus the quasi-strategy will be definable over \(L_{\beta}\). There are two types of constructions we will carry out according as \(n\) is even or odd; these will respectively deal with the sets \(C_{\rho (n)}\) and with the sets \(B_{1,s(m-1),n}\). Recall that \(U\) must satisfy the following conditions:

1. (1)

   \([U] \subset W \cup B_{2,(m-3)}\), and

2. (2)

   \(Q^{s\upharpoonright m-3}(U)\) fails.

At each stage, Player I refines her current quasi-strategy to a sub-quasi-strategy and possibly plays according to some other auxiliary quasi-strategies for some turns. Assume that the game is at stage \(n\) and that the play thus far is \(p_{n-1}\). Inductively, Player I has been playing according to a quasi-strategy \(U^{n-1}\) such that

where \(U^{-1} = T\) and \(B_{0, -1} = \mathbb{R}\). Inductively, \(Q^{s}(U^{n-1})\) fails everywhere, in the sense that \(Q^{s}(U^{n-1}_{q})\) fails for all \(q \in U^{n-1}\). By Lemma 139, \(p_{n-1} \in \Phi _{s,l,U^{n-1}}^{\infty}\) for all \(l\in \mathbb{N}\) and in particular

Using this fact, we obtain, through Lemma 138, a quasi-strategy \(U^{n}\subset U^{n-1}_{p_{n-1}}\) strongly witnessing \(Q^{s^{\frown }n}(U^{n-1}_{p_{n-1}})\). In particular, if \(x\) is according to \(U^{n}\), then

We now proceed according to whether \(n\) is even or odd.

Even stages: Using some fixed recursive bijection \(\rho : 2\mathbb{N}\to \mathbb{N}\times \mathbb{N}\), we consider the open game

If Player I has a winning strategy for \(G(\bar{C}_{\rho (n)}, U^{n})\), play according to it until a position

has been reached. Using the fact that \(p_{n} \in U^{n}\) and the choice of \(U^{n}\), we have that \(Q^{s}(U^{n})\) fails everywhere. Proceed to stage \(n+1\).

If, on the other hand, Player II has a winning strategy for \(G(\bar{C}_{\rho (n)}, U^{n})\), let \(N_{n}\) be Player II’s non-losing quasi-strategy for \(G(\bar{C}_{\rho (n)}, U^{n})\). We describe what \(U\) shall do as long as Player II plays according to \(N_{n}\). If Player II ever leaves \(N_{n}\), then the game is at a position at which Player I has a winning strategy \(G(\bar{C}_{\rho (n)}, U^{n})\), and we may continue as above in order to proceed to stage \(n+1\). Otherwise, as long as Player II plays according to \(N_{n}\), we proceed as follows.

Claim 141

Player II does not have a winning strategy for \(G(W, N_{n})\).

Proof

Since \(N_{n}\) is a quasi-strategy for Player II in the sense of \(U^{n}\), such a winning strategy would be a winning strategy for Player II for \(G(W, U^{n})\) and in particular would witness \(Q^{s}(U^{n})\). Since \(U^{n}\) was chosen to witness \(Q^{s^{\frown }n}(U^{n-1}_{p_{n-1}})\), \(Q^{s}(U^{n})\) must fail, however. □

Claim 142

Player I has a winning strategy for \(G(W, N_{n})\).

Proof

As in the corresponding claim in the proof of Theorem 91, the point is that, for \(\rho (n) = (k,l)\), we have \([N_{n}] \subset C_{k}\) and

so that the game \(W\) coincides with \(A_{k}\) when restricted to the game tree \(N_{n}\). By the previous claim, Player II does not have a winning strategy in this game. Since \(G(A_{k}, N_{n})\) is a game in \(\boldsymbol {\Gamma}_{k^{*}}\) for some \(k^{*}\) and

it follows that Player I has a winning strategy for \(G(A_{k}, N_{n}) = G(W, N_{n})\). Note that this use of \(\boldsymbol {\Gamma}_{k^{*}}{-}\)Determinacy hinges on the fact that \(\boldsymbol {\Gamma}_{k^{*}}\) is treeable. □

Let \(\tau _{n}\) be such a winning strategy for \(G(W, N_{n})\). As long as Player II plays within \(N_{n}\), we have \(U\) follow \(\tau _{n}\).

Odd stages: Consider the open game

If Player I has a winning strategy for this game, play according to it until a position \(p_{n} \in U^{n} \cap \bar{B}_{1,s(m-1),n}\) has been reached. Using the fact that \(p_{n} \in U^{n}\) and the choice of \(U^{n}\), we have that \(Q^{s}(U^{n})\) fails everywhere. Proceed to stage \(n+1\).

If, on the other hand, Player II has a winning strategy for \(G(\bar{B}_{1,s(m-1),n}, U^{n})\), we let \(N_{n}\) be Player II’s non-losing quasi-strategy for \(G(\bar{B}_{1,s(m-1),n}, U^{n})\). Since \(Q^{s}(U^{n})\) fails, \(N_{n}\) cannot be a witness for it. However,

so the only possibility is that \(Q^{s\upharpoonright m-2}(N_{n})\) holds, as witnessed by some strategy \(S_{n}\). We have \(U\) follow \(S_{n}\) as long as Player II plays according to \(N_{n}\). As soon as Player II plays in a way that is inconsistent with \(N_{n}\), we will have reached a position from which Player I can win \(G(\bar{B}_{1,s(m-1),n}, U^{n})\), so we may proceed as in the first case above.

This completes the description of \(U\). Note that if \(x \in [U]\), in \(x\), there are three possibilities. The first one is that Player II eventually played according to a non-losing quasi-strategy for a game

considered at an even stage, in which case

as was verified earlier. The second is that Player I successfully avoided all closed sets \(C_{\rho (n)}\) and \(B_{1,s(m-1),n}\) in all even and odd stages, in which case

Moreover, the game in this case must have progressed through infinitely many stages, so that by (6.7) we have

and therefore

in which case it was won by Player I. The third possibility is that Player II eventually played according to a non-losing quasi-strategy for a game

considered at an odd stage, in which case Player I eventually played according to a strategy witnessing \(S_{n}\) witnessing \(Q^{s\upharpoonright m-2}(N_{n})\). We have shown that \(U\) satisfies the definition of local witnessing in [66, Definition 4.12] (except that with the properties \(Q^{s}\) used in place of \(P^{s}\)) and thus the argument of [66, Lemma 4.4] shows that \(U\) witnesses \(Q^{s\upharpoonright m-1}(T)\), as desired. □

From these lemmata, the proof of the theorem now mimics the one in the end of Chap. 3 of [11]: given \(W\), \(T\), \(s \in \mathbb{N}^{< m}\), and \(i\in \mathbb{N}\), one shows that if \(L_{\beta}\) is a \(\beta _{m}\)-model of \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{MI}}\), then one of \(Q^{s}(T)\) or \(Q^{s^{\frown }i}(T)\) holds. The case \(\text{\textsc{lth}}(s) = m-1\) follows from Lemma 138 and Lemma 139. The case \(\text{\textsc{lth}}(s) = m-2\) follows from Lemma 138 and Lemma 139 together with Lemma 140; this yields, under the assumption that \(Q^{s^{\frown }i}(T)\) fails, a quasi-strategy \(U\) witnessing \(Q^{s}(T)\) definable over \(L_{\beta}\). But then such a strategy also belongs to \(L_{\beta}\) by \(\boldsymbol {\Sigma}^{1}_{m}\)-elementarity. As in [11], the rest of the cases require only \(\boldsymbol {\Pi}^{1}_{m+1}{-}{\mathsf{CA_{0}}}\) and thus can be carried out in \(L_{\beta}\) using the argument in [66]. Hence, one obtains either \(Q^{\varnothing}(T)\) or else \(Q^{i}(T)\) for all \(i\in \mathbb{N}\), at which point the argument is finished as in [66]. This completes the sketch of the proof.

6.5.2 Consequences of Theorem 135

Theorem 143

Let \(m \in \mathbb{N}\) and suppose that \(L_{\xi _{0}}\prec _{\Sigma _{m+1}} L_{\xi _{1}}\) and

Then,

Proof Sketch

The proof of Theorem 135 in fact shows that all the strategies for games in

(for both players!) appear within the \(\beta _{m+1}\)-model in question.

We appeal to a theorem of Kaufmann [42] according to which if \(\xi _{1}\) is locally countable (which we might as well assume, for otherwise the conclusion of the theorem follows easily for \(\xi _{1}\)) and if

then there is an illfounded \(\Sigma _{m}\)-elementary end-extension \(M\) of \(L_{\xi _{1}}\). Thus, if \(\xi _{0}\) is as in the statement of the theorem, we have

We now argue in a similar way to Theorem 119 using transfinite induction on \(\gamma <\xi _{0}\) and the proof of Theorem 135 to see that all games in

with parameters in \(L_{\xi _{0}}\) have winning strategies in \(M\). By elementarity, these winning strategies belong to \(L_{\xi _{0}}\). The base step of this induction is carried out explicitly in [11] and the inductive step is similar, using Theorem 135 and the induction hypothesis that

(This determinacy assertion takes the role of suitability for \(m = 1\).) □

Theorem 143 is best possible, in the sense that \((m+1){-}\boldsymbol {\Sigma}^{0}_{3}{-}\)Determinacy is much stronger than \(\boldsymbol {\Pi}^{1}_{m+2}{-}{\mathsf{CA_{0}}}\) and there are no Wadge classes between \((m+1){-}\boldsymbol {\Sigma}^{0}_{3}\) and \(\Delta ((m+1){-}\boldsymbol {\Sigma}^{0}_{3})\).

Remark 144

The hypothesis of Theorem 143 can be weakened as follows: definition of \(\alpha \)-suitability in §6.3 could be rephrased by replacing \(\boldsymbol {\Pi}^{1}_{2}{-}{\mathsf{MI}}\) with the existence of \(\Sigma _{2}\)-nestings, according to Hachtman’s theorem. One could mimic this transfinite definition using the notion of \(\Sigma _{m+1}\)-burrows from [11] instead of \(\Sigma _{2}\)-nestings. Thus, iterating Theorem 136 would lead proofs of determinacy for Wadge classes in the separation hierarchy between \(m{-}\boldsymbol {\Sigma}^{0}_{3}\) and \((m+1){-}\boldsymbol {\Sigma}^{0}_{3}\) from weaker hypotheses than those of Theorem 143. This improvement is analogous to that in Chap. 4 of [11] relative to Chap. 3 of [11]. We conjecture that these bounds are optimal.

Theorem 146 below asserts that there is a large gap in consistency strength between \(\Delta (m{-}\boldsymbol {\Sigma}^{0}_{3}){-}\)Determinacy and \(m{-}\boldsymbol {\Sigma}^{0}_{3}{-}\)Determinacy. We need a definition:

Definition 145

The lightface principle \(\beta _{m}\Pi ^{1}_{n}{-}{\mathsf{CA_{0}}}\) asserts that there is a \(\beta _{m}\)-model of \(\Pi ^{1}_{n}{-}{\mathsf{CA_{0}}}\).

Theorem 146

Let \(m\in \mathbb{N}\). Then,

Proof

We first verify the last inequality. It is shown in [11] that \((m+2){-}\Sigma ^{0}_{3}{-} \text{Determinacy}\) implies the existence of many ordinals \(\beta \) admitting strong \(\Sigma _{m+3}\)-nestings. These are defined in [11] and it is immediately clear from their definition that they imply the existence of triples of ordinals satisfying

For such triples, we have

For the first inequality, suppose that \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \beta _{m+2}\Pi ^{1}_{m+3}{-}{ \mathsf{CA_{0}}}\) holds. Working in \(L\), we have ordinals \(\xi _{0}\) and \(\xi _{1}\) such that

But then, an inductive argument as in Theorem 143 shows that

as desired. □

By Tanaka [81], Heinatsch-Möllerfeld [38], Montalbán-Shore [66], the systems \(\boldsymbol {\Pi}^{1}_{n}{-}{\mathsf{CA_{0}}}\) are equiconsistent with schemata of determinacy principles for \(n \in \{1,2,\infty \}\). The following result asserts that this fact does not extend to \(3\leq n < \infty \).

Theorem 147

The system \(\boldsymbol {\Pi}^{1}_{m+3}{-}{\mathsf{CA_{0}}}\) is not equiconsistent to any schema of determinacy principles of Wadge classes.

Proof

By Welch [84] (for \(m=0\)) and Montalbán and Shore [66], \(\boldsymbol {\Pi}^{1}_{m+2}{-}{\mathsf{CA_{0}}}\) has strictly lower consistency strength than \((m+1){-}\boldsymbol {\Sigma}^{0}_{3}{-}\)Determinacy. By Theorem 146, \(\Delta ((m+1){-}\boldsymbol {\Sigma}^{0}_{3}){-}\)Determinacy is strictly weaker than \(\boldsymbol {\Pi}^{1}_{1}{-}{\mathsf{CA_{0}}}+ \beta _{m+2}\Pi ^{1}_{m+3}{-}{ \mathsf{CA_{0}}}\), which is clearly implied by \(\boldsymbol {\Pi}^{1}_{m+3}{-}{\mathsf{CA_{0}}}\). Since there are no Wadge classes between \(\Delta ((m+1){-}\boldsymbol {\Sigma}^{0}_{3})\) and \((m+1){-}\boldsymbol {\Sigma}^{0}_{3}\), the result follows. □

We conclude this section by mentioning the following consequence of Theorem 135. The proof of this result also shows that the implication in the statement of Conjecture 114 is provable in \(\boldsymbol {\Pi}^{1}_{4}{-}{\mathsf{CA_{0}}}\).

Corollary 148

Suppose that \(Z_{2}\) holds. Let \(\boldsymbol {\Gamma}\) be a definable \(\boldsymbol {\Delta}^{1}_{n}\) Wadge class, for some \(n\in \mathbb{N}\). Suppose that \(\boldsymbol {\Gamma}{-}{\mathsf{SR}}\) holds, then the schema

holds too.