The Limits of Determinacy in Second Order Arithmetic: Consistency and Complexity Strength

Antonio Montalbán^{∗} Department of Mathematics

University of California, Berkeley Berkeley CA 94720 USA

Richard A. Shore^{∗∗} Department of Mathematics Cornell University Ithaca NY 14853

April 17, 2014

Abstract

We prove that determinacy for all Boolean combinations of F_{σδ} (Π_{3}^{0}) sets implies the consistency of second-order arithmetic and more. Indeed, it is equivalent to the statement saying that for every set X and every number n, there exists a β-model of Π_{n}^{1}-comprehension containing X.

We prove this result by providing a careful level-by-level analysis of determinacy at the finite level of the difference hierarchy on F_{σδ} (Π_{3}^{0}) sets in terms of both reverse mathematics, complexity and consistency strength. We show that, for n ≥ 1, determinacy for sets at the nth level in this difference hierarchy lies strictly between (in the reverse mathematical sense of logical implication) the existence of β-models of Π_{n+2}^{1}-comprehension containing any given set X, and the existence of β-models of Δ_{n+2}^{1}-comprehension containing any given set X. Thus the nth of these determinacy axioms lies strictly between Π_{n+2}^{1}-comprehension and Δ_{n+2}^{1}- comprehension in terms of consistency strength. The major new technical result on which these proof theoretic ones are based is a complexity theoretic one. The nth determinacy axiom implies closure under the operation taking a set X to the least Σ_{n+1} admissible containing X (for n = 1, this is due to Welch [2012]).

1 Introduction

There are several common ways to calibrate the strength of mathematical or set theoretic assertions. One venerable one is proof theoretic. We say that a theory T is proof theoretically stronger (or of higher consistency strength) than one S, T >_{c} S, if T proves the consistency of S. (Here one assumes that the languages and theories being considered are countable, include basic arithmetic (or some natural interpretation of it as in set theory) and are equipped with a standard Gödel numbering of sentences and proofs so that the statement that S is consistent has a natural representation, Con(S), in the language as does T ⊢ Con(S).) This ordering is strict by Gödel’s incompleteness theorem, i.e. for no reasonable T can T ⊢ Con(T).

∗Partially supported by NSF grant DMS-0901169, and by a Packard fellowship.

∗∗Partially supported by NSF Grants DMS-0852811 and DMS-1161175.

Another important calibration is that provided by reverse mathematics. Here one works in the setting of second order arithmetic, i.e. the usual first order language and structure ⟨M, +, ×, <, 0, 1⟩ supplemented by distinct variables X, Y, Z that range over a collection S of subsets of the domain M of the first order part and the membership relation ∈ between elements of M and S. Most of countable or even separable classical mathematics can be developed in this setting based on very elementary axioms about the first order part of the model M, an induction principle for sets and various set existence axioms. At the bottom one has a weak system of axioms called RCA_{0} that correspond to recursive constructions. One typically then adds additional existence axioms to get other systems P.

The endeavor here is to calibrate the complexity of mathematical theorems by determining precisely which system P of axioms are needed to prove a give theorem Θ. This is done in one direction in the usual way showing that P ⊢ Θ. The other direction is a “reversal” that shows that RCA_{0} + Θ ⊢ P. The standard text here is Simpson [2009] to which we refer the reader for general background. There is also a brief presentation of the subject and the standard systems in Montalbán and Shore [2012] of which this paper is really a continuation. We henceforth refer to Montalbán and Shore [2012] as [MS] and rely heavily on its proofs and results.

One natural hierarchy of axiomatic (or proof theoretic) systems is given by Π_{n}^{1}-CA_{0} and Δ_{n}^{1}-CA_{0}: the axioms that say that every set defined by a Π_{n}^{1} formula (with set parameters) or, respectively, by both Π_{n}^{1} and Σ_{n}^{1} formulas exists. (We assume familiarity with the usual hierarchy of formulas and relations Σ_{n}^{0}, Π_{n}^{0}. Δ_{n}^{0} and Σ_{n}^{1}, Π_{n}^{1}, Δ_{n}^{1} that measure the complexity of prenex normal formulas by the number of alternations of first or second order quantifiers, respectively.) The system at the bottom of this hierarchy, Π_{1}^{1}-CA_{0} is the strongest of the systems usually studied in reverse mathematics and so far suffices for almost all mathematical theorems. The systems we consider are all stronger than Π_{1}^{1}-CA_{0} and indeed exhaust the hierarchy with examples provable from Π_{n}^{1}-CA_{0} but not Δ_{n}^{1}-CA_{0} for each n ≥ 3 and even one not provable in full second order arithmetic, Z_{2} = ∪{Π_{n}^{1}-CA_{0}|n ∈ ω}.

These systems are taken from the realm of axioms of determinacy. This subject has played an important role historically as an inspiration for increasingly strong axioms (as measured by consistency strength) both in reverse mathematics and set theory. We have given a brief overview of this history in [MS, §1] and refer the reader to that paper for more historical details and other background.

In that paper we analyzed the reverse mathematical strength of a hierarchy of low levels of determinacy axioms, n-Π_{3}^{0}-DET and ω-Π_{3}^{0}-DET, which we now define.

Definition 1.1 (Games and Determinacy). Our games are played by two players I and II. They alternate playing 0 or 1 with I playing first to produce a play of the game which is a sequence x ∈ 2^{ω}. A game G_{A} is specified by a subset A of 2^{ω}. We say that I wins a play x of the game G_{A} specified by A if x ∈ A. Otherwise II wins that play. A strategy for I (II) is a function σ from binary strings p of even (odd) length into {0, 1}. It is a wining strategy if any play x following it (i.e. x(n) = σ(x ↾ n) for every even (odd) n) is a win for for I (II). We say that the game G_{A} is determined if there is a winning strategy for I or II in this game. If Γ is a class of sets A, then we say that Γ is determined if G_{A} is determined for every A ∈ Γ. We denote the assertion that Γ is determined by Γ determinacy or Γ-DET.

Recall that the Π_{3}^{0} subsets of 2^{ω} are the F_{σδ} ones, i.e. the countable intersections of countable unions of closed sets or equivalently the ones definable by formulas of the Π_{3}^{0} form ∀n∃m∀kR(x, n, m, k, Z) for some recursive predicate R and Z ∈ 2^{ω}. There are a couple of equivalent definitions of the natural hierarchy on the Boolean combinations of these sets (or ones from any class Γ) called the (finite) difference hierarchy. Here is one that generalizes into the transfinite. If carried out through ℵ_{1} many steps, it exhausts all of the Δ_{4}^{0} sets (those representable by both Σ_{4}^{0} and Π_{4}^{0} formulas of arithmetic or equivalently in both G_{δσδ} and F_{σδσ}).

Definition 1.2 (Finite Differences on Π_{3}^{0}). A set A ⊆ 2^{ω} is m-Π_{3}^{0} if there are Π_{3}^{0} sets A_{0}, A_{1}, …, A_{m−1}, A_{m} = ∅ such that

x ∈ A ⇔ the least i such that x ∉ A_{i} is odd.

It is ω-Π_{3}^{0} if it is m-Π_{3}^{0} for some m < ω.

While we used this standard definition for our proofs of determinacy in [MS] (see Theorem 1.5 below), we there used another one for our negative results (see Theorem 1.6 below). We utilize that representation for our major technical result, Theorem 1.8, here as well.

Definition 1.3. A set A ⊆ 2^{ω} is Π_{3,n}^{0} if there exist Π_{3}^{0} sets A_{0}, ..., A_{n} such that A_{n} = 2^{ω} and

x ∈ A ⇔ the least i such that x ∈ A_{i} is even.

We say that the sequence ⟨A_{i}|i ≤ m⟩ represents A (as a Π_{3,n}^{0} set).

For the purposes of establishing or contradicting determinacy the two hierarchies are equivalent and so we may use either class in our proofs about n-Π_{3}^{0}-DET.

Remark 1.4 ([MS, Corollary 2.7]). For every n, determinacy for n-Π_{3}^{0} sets is equivalent to that for Π_{3,n}^{0}.

The major reverse mathematical results of [MS] are the following:

Theorem 1.5. For each m ≥ 1, Π_{m+2}^{1}-CA_{0} ⊢ m-Π_{3}^{0}-DET.

Theorem 1.6. For every m ≥ 1, Δ_{m+2}^{1}-CA ⊬ m-Π_{3}^{0}-DET.

Corollary 1.7. Determinacy for the class of all finite Boolean combinations of Π_{3}^{0} classes of sets (ω-Π_{3}^{0}-DET) cannot be proved in second order arithmetic.

In [MS], we also showed that ω-Π_{3}^{0}-DET does not prove even Δ_{2}^{1}-CA_{0} (or Π_{n+2}^{1}-CA_{0} even over Δ_{n+2}^{1}-CA_{0}) and so ω-Π_{3}^{0}-DET and Z_{2} are reverse mathematically incomparable.

When we spoke about these results at Berkeley, John Steel asked the natural question of whether we could improve our reverse mathematical result that ω-Π_{3}^{0}-DET is not provable in Z_{2} to show that it actually implies the consistency of Z_{2}. If so, while the two theories are incomparable in the sense of reverse mathematics, ω-Π_{3}^{0}-DET would be strictly stronger than Z_{2} in the proof theoretic one. This appears to be a delicate proof theoretic question falling outside the scope of our usual recursion or set theoretic methods as the results of [MS] show that ω-Π_{3}^{0}-DET does not prove the existence of an ω-model of Z_{2}. (See Corollary 1.16.) Nonetheless, in this paper we show that this is indeed the case and that much more is true by proving stronger results at every step along the finite difference hierarchy. Our goals here are thus primarily proof theoretic but we also prove reverse mathematical and recursion (complexity) theoretic results and then use them to establish the proof theoretic ones.

In this setting, all the theories we might consider are formulated in the language of second order arithmetic and include at least RCA_{0} although we generally omit explicitly mentioning the inclusion of RCA_{0} in our theories. Thus we can take a standard formulation of Con(T).

We also note that, in the context of reverse mathematics, a structure for a first order language is an, of course countable, set and collection of relations and functions as usual but we also assume the elementary diagram is given as well. If the theory is one of second order arithmetic we add on a countable set S of subsets of the domain M of the model M as the range of the second order quantifiers. (Simpson [2009] calls these countably coded models as its collection of allowed sets must be coded into a single set.) Such a model M = ⟨M, S, ∈, +, ×, <, 0, 1⟩ is an ω-model if M = ℕ (the “true” natural numbers). It is a β-model if, in addition, every Π_{1}^{1} sentence (with parameters in M) is true in M if and only if it is “true”. (One makes sense of the notions of ω and β submodels in the obvious way.)

In fact, all the theories we actually consider imply Π_{1}^{1}-CA_{0} (over RCA_{0}) and so we use the available interpretations between second order arithmetic and the language of set theory and the development of L and its fine structure in Π_{1}^{1}-CA_{0} in Simpson [2009] and [MS] as well as some standard fine structure facts. In particular, for n ≥ 2, if α_{n} is the least Σ_{n} admissible ordinal greater than ω then L_{α_{n}} is the least β-model of Δ_{n+1}^{1}-CA_{0}. Similarly, if ρ_{n} is the least Σ_{n} nonprojectable ordinal greater than ω, then L_{ρ_{n}} is the least β-model of Π_{n+1}^{1}-CA_{0} and if β_{0} is the least ordinal which is Σ_{n} admissible for every n (or equivalently Σ_{n} nonprojectable for every n), then L_{β_{0}} is the least β-model of Z_{2}, (In all these situations when we refer to an L_{γ} as a structure for second order arithmetic we mean the ω-model with sets S taken to be L_{γ} ∩ ℝ.)

These relations between admissible fragments of L and our strong proof theoretic systems are really an extension of the usual correspondences between the standard weaker proof theoretic systems and standard recursion theoretic constructions. In particular, the system ACA_{0} corresponds to closure under the Turing jump; ATR_{0}, to closure under transfinite iterations of the Turing jump; and Π_{1}^{1}-CA_{0} to closure under the hyperjump. (See Shore [2010] for an exposition of the correspondences between the recursion theoretic structures and ω-models of the proof theoretic systems.) The natural extensions of the jump and hyperjump operators to larger ordinals are given by the master code hierarchy for countable initial segments of L (see, for example, Hodes [1980]). In particular, the jumps corresponding to Δ_{n+1}^{1}-CA_{0} and Π_{n+1}^{1}-CA_{0} for n ≥ 2 are the closures under the operators taking X to the least Σ_{n} admissible and Σ_{n} nonprojectable sets containing X, respectively. Here the correspondence moves from ω-models to β-models. In this language, our results (Corollary 1.11) show that the natural operator taking X to the least model of n-Π_{3}^{0}-DET containing X lies strictly between the closure under the next Σ_{n+1} admissible and under the next Σ_{n+1} nonprojectable. We do not know of any other similar natural operators.

We use this correspondence to achieve our primary goal of locating the consistency strength of n-Π_{3}^{0}-DET for each n and of ω-Π_{3}^{0}-DET with respect to the standard fragments of Z_{2}. To be precise, we will prove (Corollaries 1.14 and 1.16) that, Π_{n+2}^{1}- CA_{0} >_{c} n-Π_{3}^{0}-DET >_{c} Δ_{n+2}^{1}-CA_{0} for each n ≥ 1 and that ω-Π_{3}^{0}-DET >_{c} Z_{2} (and so ω-Π_{3}^{0}-DET >_{c} ZF C^{−} as well). (ZF C^{−} is ZF C without the power set axiom and, as is pointed out in [MS Proposition 1.4], is a Π_{4}^{1} conservative extension of Z_{2}.) In fact, we will prove that, in each case, the distance between each side of the inequality is much greater than simple >_{c}. The main technical result we need will be recursion theoretic in the sense just described:

Theorem 1.8. For n ≥ 1, n-Π_{3}^{0}-DET ⊢ α_{n+1} exists.

The case n = 1 is due to Welch [2011, 2012]. We prove this result for n ≥ 2 in §2. To facilitate our proof theoretic goals, it is also helpful to introduce an operation on theories T of second order arithmetic that significantly increases consistency strength.

Definition 1.9. If T is a theory in the language of second order arithmetic, then β(T) is the theory which says that for every set X there is a β-model of T containing X.

Note that for any (at least reasonably definable theory) T, not only is β(T) >_{c} T but it is significantly stronger than T in terms of consistency strength. Indeed, while the provability of the existence of a model of T always implies consistency, and is equivalent to the provability of Con(T) (even over the theory WKL_{0}), the provability of the existence of even an ω-model of T implies not only Con(T) but also, for example, Con(T +Con(T)) and iterations of this operation into the transfinite. The point here is that for any, say arithmetic, T, Con(T) is a sentence of arithmetic and so, if provable from S, S also proves that it is true in any ω-model of T. Thus if S proves that there is an ω-model of T then it also proves that there is one of T + Con(T) etc. Of course, by Gödel’s incompleteness theorem, it can never be the case that T ⊢ β(T). With this terminology we can state our main reverse mathematical theorem in which we include for convenience the main results of [MS] and some simple facts and consequences.

Theorem 1.10. For every n ≥ 1 we have the following provability relations none of which can be reversed.

1. Π_{n+2}^{1}-CA_{0} ⊢ n-Π_{3}^{0}-DET.

2. Π_{n+2}^{1}-CA_{0} ⊢ β(n-Π_{3}^{0}-DET).
3. β(Π_{n+2}^{1}-CA_{0}) ⊢ β(n-Π_{3}^{0}-DET).
4. β(n-Π_{3}^{0}-DET) ⊢ n-Π_{3}^{0}-DET.
5. n-Π_{3}^{0}-DET⊢ β(Δ_{n+2}^{1}-CA_{0}).
6. Δ_{n+2}^{1}-CA_{0} ⊢ β(Π_{n+1}^{1}-CA_{0}).

\xymatrix{Π_{n+2}^{1}-CA_{0} \ar@{=>}[dr] \ar@{=>}[ddd] & β(Π_{n+2}^{1}-CA_{0}) \ar@{=>}[d] \\ & β(n-Π_{3}^{0}-DET) \ar@{=>}[d] \\ & n-Π_{3}^{0}-DET \ar@{=>}[d] \\ Δ_{n+2}^{1}-CA_{0} \ar@{=>}[dr] \ar@{=>}[d] & β(Δ_{n+2}^{1}-CA_{0}) \ar@{=>}[d] \\ Π_{n+1}^{1}-CA_{0} & β(Π_{n+1}^{1}-CA_{0})}

Proof. When we want to establish β(T) for some theory T, we simply show that there is a β-model of T and note that β(T) always follows by a straightforward relativization. Similarly, when proving some assertion with set parameters from β(T), we ignore the set parameter and argue from the existence of a β-model of T and leave the insertion of parameters to relativization.

The first implication is Theorem 1.1 of [MS]. For (2), we note that the proof of Theorem 6.1 of [MS] can be carried out in Π_{n+2}^{1}-CA_{0}. Given (1) applying that theorem to n-Π_{3}^{0}-DET, produces a δ which is a limit of admissibles such that L_{δ} is a model of n-Π_{3}^{0}-DET. Recall that if δ is a limit of admissibles, L_{δ} is a β-model. That (1) cannot be reversed follows from (2) as for all of these theories T, T ⊬ β(T). That (2) cannot be reversed follows from noticing that the proof of (2) above shows that, from Π_{n+2}^{1}-CA_{0}, one can prove the existence of a δ such that L_{δ} is a β-model of n-Π_{3}^{0}-DET. Iterating this construction ω many times and taking the limit produces an ordinal γ such that L_{γ} is a model (even a β-model) of β(n-Π_{3}^{0}-DET ). The fact that this iteration is possible follows, for example, from Σ_{2}^{1}-DC_{0} which is a consequence of Π_{n+2}^{1}-CA_{0} by Simpson [2009, Theorem VII.6.9].

Now (3) follows from (1) by applying it inside the β-model of Π_{n+2}^{1}-CA_{0} given by the hypothesis of (3). That it is not reversible follows from (2) and the fact that Π_{n+2}^{1}- CA_{0} ⊬ β(Π_{n+2}^{1}-CA_{0}).

The next implication, (4), follows from the definition of being a β-model: Each instance of n-Π_{3}^{0}-DET is a Σ_{2}^{1} sentence which is true in some β-model and so has a witness in that model. Being a witness is a Π_{1}^{1} fact and so truth in the β-model implies truth. This one is clearly non-reversible.

The next implication, (5), is the proof theoretic heart of this paper. It follows from our main recursion or complexity theoretic result, Theorem 1.8. It gives the existence of the least Σ_{n+1} admissible ordinal α_{n+1} and so of L_{α_{n+1}} which as noted above is the smallest β-model of Δ_{n+2}^{1}-CA_{0}. Of course, this argument relativizes to any X to give the result required in (5). That (5) cannot be reversed takes some work, and we will do this in Section 3, where we show that n-Π_{3}^{0}-DET does not hold in L_{α}_{n}^{∗} where α_{n}^{∗} is the first limit of n-admissibles.

The final implication follows from a standard fact about admissible ordinals: The Σ_{n}-nonprojectables are cofinal in the first (n + 1)-admissible. So, by the remarks above, L inside any model of Δ_{n+2}^{1}-CA_{0} is n+1-admissible and within it the Σ_{n}-nonprojectables are β-models of Π_{n+1}^{1}-CA_{0}.

One recursion/complexity theoretic corollary of these results is placing the “jump” operator taking a set X to the least ordinal δ such that L_{δ}[X] is a (necessarily β) model of n-Π_{3}^{0}-DET among the more usual operators.

Corollary 1.11. For every X, the least δ such that L_{δ}[X] ⊨ n-Π_{3}^{0}-DET is a limit of admissible ordinals strictly between α_{n}^{∗}[X], the first limit of Σ_{n}-admissibles containing X, and ρ_{n}[X], the least Σ_{n}-nonprojectable containing X.

Proof. That δ is between these two ordinals follows from (5), i.e. Theorem 1.8, and (1). That the ordering is strict follows from the proof of nonreversability of (5) in Theorem 3.1 and (2).

Another corollary of (the uniformities in the proofs of) implications (1), (3), (4) and (5) of Theorem 1.10 and standard absoluteness properties are reverse mathematical and recursion theoretic characterizations of ω-Π_{3}^{0}-DET. The reverse mathematical characterization is as being equivalent to another Π_{3}^{1} sentence closely tied to Z_{2}. The recursion/complexity theoretic one is in terms of the least ordinal δ such that L_{δ} ⊨ ω-Π_{3}^{0}-DET.

Corollary 1.12. Over RCA_{0}, the following are equivalent:

• ω-Π_{3}^{0}-DET.

• ∀n(β(Π_{n}^{1}-CA_{0})), that is, for every n and every X there is a β-model of Π_{n}^{1}-CA_{0} containing X.

Corollary 1.13. The least ordinal δ such that L_{δ} ⊨ ω-Π_{3}^{0}-DET is ∪α_{n}, the supremum of the least Σ_{n} admissibles over n ∈ ω. As can be seen from the proof of Theorem 1.8, this ordinal is also the least such that L_{δ} contains winning strategies for all light-faced ω-Π_{3}^{0} games.

Our basic assertions about consistency strength along the hierarchies follow immediately from the numbered implications (2), (5) and (6) of Theorem 1.10.

Corollary 1.14. For every n ≥ 1 we have the following chain of consistency strength relations:

⋯ Π_{n+1}^{1}-CA_{0} <_{c} Δ_{n+2}^{1}-CA_{0} <_{c} n-Π_{3}^{0}-DET <_{c} Π_{n+2}^{1}-CA_{0} · · ·.

An immediate corollary of this chain (and compactness) is an equiconsistency result for Z_{2}.

Corollary 1.15. (RCA_{0}) The following are equiconsistent:

1. Z_{2}, i.e., the scheme which contains, for each n ∈ ℕ, the axiom Π_{n}^{1}-CA_{0}.

2. The scheme which contains, for each n ∈ ℕ, the axiom n-Π_{3}^{0}-DET.

3. ZF C^{−}, i.e. ZF C without the power set axiom.

Proof. The equiconsistency of the first two is our immediate corollary. That for Z_{2} and ZF C^{−} follows from the usual interpretation of ZF C^{−} in Z_{2} as in Simpson [2009, Ch. VII] and in particular Theorem VII.5.10 and VII.5.17 there as well as remarks in [MS].

We can say more at level ω but not too much.

Corollary 1.16. Z_{2} <_{c} Z_{2} + Con(Z_{2}) <_{c} Z_{2} + Con(Z_{2}) + Con(Z_{2} + Con(Z_{2})) <_{c} ⋯ <_{c} ω-Π_{3}^{0}-DET. However, ω-Π_{3}^{0}-DET does not prove that there is an ω-model of Z_{2}. These same relations hold between ω-Π_{3}^{0}-DET and ZF C^{−} in place of Z_{2}.

Proof. The chain of consistency strengths is immediate. As for ω-Π_{3}^{0}-DET, the proof of Theorem 1.10(5) shows that it proves (over RCA_{0}, or equivalently, Π_{1}^{1}-CA_{0}) that, for each n, there is a β-model of Π_{n+1}^{1}-CA_{0}, uniformly in n. Compactness now directly gives a model of Z_{2}, i.e. ω-Π_{3}^{0}-DET ⊢ Con(Z_{2}). As Con(Z_{2}) is a sentence of first order arithmetic it is true in every β-model (indeed every ω-model). In particular, it is true in all the β-models of Π_{n+1}^{1}-CA_{0} proven to exist by ω-Π_{3}^{0}-DET. Thus ω-Π_{3}^{0}-DET proves that, for every n, there is a β-model of Π_{n+1}^{1}-CA_{0} + Con(Z_{2}) and so Con(Z_{2} +Con(Z_{2})). We can now iterate this argument by induction.

Finally, ω-Π_{3}^{0}-DET does not prove that there is an ω-model of Z_{2} because from (1) of Theorem 1.10 we get that ω-Π_{3}^{0}-DET holds in any ω-model of Z_{2}. That the same assertions hold for ZF C^{−} follows as in the previous Corollary.

One more version of the connection between Z_{2} and n-Π_{3}^{0}-DET is given by the following Corollary:

Corollary 1.17. The Π_{3}^{1} consequences of Z_{2} are the same as those of RCA_{0} + {n-Π_{3}^{0}- DET|n ∈ ω}.

Proof. All the consequences of RCA_{0} + {n-Π_{3}^{0}-DET |n ∈ ω} are included in those of Z_{2} by Theorem 1.10(1). For the other direction, consider any Π_{3}^{1} sentence φ = ∀X∃Y ∀Zψ(X, Y, Z) which follows from Z_{2}, any model M of RCA_{0} + {n-Π_{3}^{0}-DET |n ∈ ω} and any set X in M. Now φ is a consequence of Π_{n+1}^{1}-CA_{0} for some n. By Theorem 1.10(5), there is, in M, a β-model M̂ of Π_{n+1}^{1}-CA_{0} containing X. The witness Y in M̂ for ∀Zψ(X, Y, Z) is a also a witness in M as M̂ is a β-model in M. Thus φ is true in every model of RCA_{0} + {n-Π_{3}^{0}-DET |n ∈ ω} as required.

2 β-models and Δ_{n+2}^{1}-CA_{0}

In this section we prove our main result.

Theorem 1.8. For n ≥ 1, n-Π_{3}^{0}-DET ⊢ α_{n+1} exists.

Welch [2012] has characterized the complexity of Π_{3}^{0}-DET in terms of the level of L at which strategies must first appear by a condition reminiscent of those used here and in [MS §5]. The case n = 1 in the Theorem follows easily from his characterization and a simple fact cited in Welch [2011, Proposition 1] from Burgess [1986] (Welch, personal communication). (The fact that an ordinal ζ for which there is a Σ such that L_{ζ} ⪯_{2} L_{Σ} is Σ_{2} admissible is true even if Σ is a nonstandard element of a model of V = L.) Our proof does not work for n = 1, so we fix an n ≥ 2 and proceed by defining a class G of games G and proving two lemmas.

Lemma 2.1. If α_{n+1} does not exists, then no G ∈ G is determined.

Lemma 2.2. If α_{n+1} does not exists, then there is a n-Π_{3}^{0} game G ∈ G.

We begin with the class G of games. It is formally defined as consisting of all the games whose winning conditions satisfy four properties given below. Informally, we specify the objectives of the game in terms of building models of the theory T = KP +V = L + ¬∃β[(ω, (2^{ω})^{L_{β}}) ⊨ Z_{2}]. Now L_{γ} is countable inside L_{γ+1} for γ < β_{0} by [MS, Lemma 3.5]. Thus by the relations described above between nonprojectability and models of Π_{n+1}^{1}-CA_{0}, T is equivalent to KP +V = L + ∀γ(L_{γ} is countable inside L_{γ+1}). So a model of T looks like an admissible initial segment of L less than β_{0}. In particular, in it all sets are countable. Of course, if the model is well-founded then it is an L_{α} for an admissible ordinal α ≤ β_{0}. Intuitively, the objective of each player in these games is to build a model of T whose well-founded part is longer than the opponent’s (with ties going to I). The games are designed so that being determined would force the existence of α_{n+1}. To be precise, we interpret the play of each player in one of our games as the characteristic function of a set of sentences in the language of set theory and specify conditions that, if satisfied, determine a winner of the game. We do this by giving a sequence of conditions with the understanding that the first one to be satisfied tells us which player wins the game. If none of the conditions is satisfied, any determination of a winner places the game in G. (Once we see how to describe the conditions by Π_{3}^{0} sets this will fit the Π_{3,n}^{0} hierarchy of Definition 1.3. Determinacy for that hierarchy is equivalent to that for the n-Π_{3}^{0} one level by level as noted in Remark 1.4. We then also have to organize the conditions into a sequence of the required length.)

We begin with easily defined (i.e. simpler even than Π_{3}^{0}) conditions that set the basic conditions for our models.

G1. Each player has to play a complete consistent theory extending T in the sense that if I fails to do this then II wins while if II fails to do this (while I does play such a theory), then I wins. Next, i.e. assuming neither player has lost yet in this way, we let M_{I} and M_{II} be the term-models of these theories, i.e. the structures whose members are (equivalence classes) of formulas φ(x) which, in the appropriate theory, define unique elements. (See [MS, pp. 241-242]). We next require that these models are ω-models. (In the same sense as before, i.e. if M_{I} is not an ω-model then II wins while if M_{II} is not an ω-model (but M_{I} is), then I wins.)

We are now faced with the problem of comparing the two models M_{I} and M_{II}. Intuitively we want to compare them in the sense of containment but we only have them as term models so all we can hope for is an isomorphism from one to an initial segment of the other. If they were both well-founded, this is not hard to understand as both are then admissible initial segments of L. However, the models may be ill-founded. We need a definition that makes sense in all cases and does the right thing when at least one is well-founded. The crucial idea is to reduce everything to subsets of ω by the countability of every L_{β} inside each model. As both are ω-models, there is an easily definable isomorphism between ω^{M_{I}} and ω^{M_{II}} (the identity on the terms x = 1+1 ⋯+1). This isomorphism then carries over to the whole model using the definable countings. The following definition captures this notion and slightly abuses notation by naming the relation between models as containment. We use notations such as On^{M_{I}} and ℝ^{M_{I}} to denote the obvious sets in M_{I} (the ordinals in M_{I} and the subsets of ω^{M_{I}} in M_{I}, respectively) and similarly for M_{II}. We will use M_{::} when we want to consider either or both of M_{I} and M_{II} ambiguously and will use similar notation for other objects subscripted by I and II.

Definition 2.3. We say that M_{I} is contained in M_{II}, M_{I} ⊆ M_{II}, if

∀α ∈ On^{M_{I}} ∃x ∈ ℝ^{M_{I}}, y ∈ ℝ^{M_{II}}, β ∈ On^{M_{II}}[(M_{I} ⊨ x codes L_{α})
∧(M_{II} ⊨ y codes L_{β}) ∧ ∀n ∈ ω(M_{I} ⊨ n ∈ x ⟺ M_{II} ⊨ n ∈ y)].  (1)

By a real x coding a structure such as < on an ordinal or ∈ on an L_{β} (in M_{::}), we mean that when we view x as a set of pairs of natural numbers the relation defined by that set of pairs is isomorphic to the one in M_{::}. (We note that while not the definition given in [MS, §5] this one, with β in place of L_{β}, in the form of Claim 5.3 of [MS], is what is actually used there and should there be taken to be the definition.) We here code all of L_{β} (and so, of course, β recursively in that code) simply because we primarily need the L_{β} and this version eliminates the need to think about going from β to L_{β} in the codes.

Armed with this definition we can state the remaining winning conditions

G2. If M_{II} = M_{I} (in the sense that M_{I} ⊆ M_{II} and M_{II} ⊆ M_{I}) then I wins.

G3. If M_{I} is well-founded, then I wins if

(a) M_{II} is contained in M_{I}, or

(b) M_{II} is ill-founded and M_{I} contains the well-founded part of M_{II}.

G4. If M_{II} is well-founded, then II wins if

(a) M_{I} is contained in M_{II}, or

(b) M_{I} is ill-founded and M_{II} contains the well-founded part of M_{I}.

We next turn to Lemma 2.1. Its proof is fairly short if somewhat tricky. Most of the ideas in the proof appear in the hint for Exercise 1.4.2 in a draft of a book by Martin [n.d.]. In that exercise one is asked to prove H. Friedman’s result [1971] that Σ_{4}-DET implies the existence of β_{0}.

Proof of Lemma 2.1. Suppose G ∈ G and assume that α_{n+1} does not exist. We show that no player has a winning strategy for G.

We first claim that the set Y = {α| L_{α} ⊧ T and every member of L_{α} is definable in L_{α}} is unbounded. If not, let δ = sup Y, and let α be the least admissible ordinal greater than δ. Let M be the elementary submodel of L_{α} consisting of all its definable elements. Then δ ∈ M. Since α_{n+1} does not exist, every ordinal is countable, and hence there is a bijection between ω and δ and the <_{L}-least such bijection belongs to M. Thus δ ⊆ M, indeed δ + 1 ⊆ M. Since the Mostowski collapse of M is admissible and contains δ + 1, it must be L_{α}. It follows that every member of L_{α} is definable in L_{α} and hence that α ∈ Y for the desired contradiction.

Suppose now that player I has a winning strategy σ for G. Let α ∈ Y be such that σ ∈ L_{α}. We claim, for our desired contradiction, that if I follows σ and II plays T h_{α}, the theory of L_{α}, II wins. First, player I will not play T h_{α}, because if he did, then following σ would produce exactly the same moves as playing against a strategy for II that just copies I’s moves. Hence σ could compute the full play of this game and so T h_{α}. However, T h_{α} ∉ L_{α} because every member of L_{α} is definable in L_{α} and truth for L_{α} is not.

So, M_{I} ≠ M_{II}. Now we have to consider conditions G3 and G4. As we are assuming M_{II} = L_{α} it is well-founded. (The term model of T h(L_{α}) is (isomorphic to) L_{α} for α < α_{n+1}.) Since σ ∈ L_{α} and T h_{α} ∈ L_{α+2}, T h(M_{I}) ∈ L_{α+2}, and hence the reals in M_{I} all belong to L_{α+2}. So if M_{I} is well-founded it is an admissible proper initial segment of L_{α} = M_{II} and G3 does not apply but G4(a) does and II wins G. If M_{I} is ill-founded, then the well-founded part of M_{I} is included in L_{α} as otherwise it would go beyond L_{α} and so contain reals beyond L_{α+2}. So II wins again. Thus, in any case, we have contradicted the assumption that I has a winning strategy for G.

Finally, suppose that II has a winning strategy σ for G. Again, let α ∈ Y be such that σ ∈ L_{α}. We claim that if I plays T h_{α}, he wins. Note that II cannot copy I’s moves, or he would loose by G2. The rest of the argument is analogous to the one above with I winning by either G3(a) or G3(b) depending on whether M_{II} is well-founded or not.

We now turn to the new and much more difficult Lemma 2.2. Our proof adapts and extends the machinery developed in §5 of [MS].

2.1 Proof of Lemma 2.2

We begin by describing various Π_{3}^{0} conditions (i.e. sets) a Boolean combination of which could be used to specify a game G ∈ G. We then show how to reorganize the game so as to get one that is Π_{3,n}^{0} and show that it is in G. (Making G a Π_{3,n}^{0} game suffices by Remark 1.4.) Note that to show that a game G is in G it suffices to prove that for every play of the game which has a winner determined by the rules of G, the specification of G determines the same winner.

Our description incorporates variants of most of the conditions of [MS, §5] as well as some new ones. To make our treatment more nearly self-contained, we repeat, at times with modifications, some of the definitions and proofs from [MS].

First we can clearly guarantee that G1 is satisfied by using the following conditions:

(R_{I}0): II does not play a complete consistent extension of T.
(R_{II}0): I does not play a complete consistent extension of T.
(R_{I}1): M_{II} is not an ω-model.
(R_{II}1): M_{I} is not an ω-model.

For most of the quantifier complexity assertions below a crucial fact to keep in mind is that the plays of our game specify T h(M_{::}) and so saying that some sentence of set theory is true in M_{::} is recursive in the play. Also the map from n to the term denoting n in M_{::} is recursive.

Claim 2.4. Conditions (R_{I}1) and (R_{II}1) are Σ_{1}^{0}. Conditions (R_{I}1) and (R_{II}1) are Σ_{2}^{0}.

Proof. For the first assertion, saying that the set of sentences played form a complete and consistent theory is Π_{1}^{0}. Saying that the axioms of T_{n} are included in these sets is also Π_{1}^{0}.

For the second, to say that a term model M is an ω-model, we have to say that for every term t, if M ⊨ t ∈ ω (i.e. in M, the unique element satisfying the associated formula is a member of ω), then there exists a number n such that M ⊨ t = 1+1+....+1, where 1 is added n times. This is a Π_{2}^{0} formula about M.

Next, we can guarantee that G2 is satisfied using the condition

(R_{I}2): M_{I} = M_{II}.

Claim 2.5. Condition (R_{I}2) is Π_{3}^{0}.

Proof. Note that containment in each direction is Π_{3}^{0} by inspecting Definition 2.3.

An inspection of the remaining rules for G shows that if M_{I} ⊊ M_{II} we need to let II win if M_{II} is well-founded and let I win if M_{II} is not and M_{I} is its well-founded part. In §2.2 we introduce a new condition (R_{I}new) to handle this case. Similarly if M_{II} ⊊ M_{I} we need to let I win if M_{I} is well-founded and let II win if M_{I} is not and M_{II} is its well-founded part. We here use an analogous condition (R_{II}new).

If M_{I} and M_{II} are incomparable, then the only cases we are interested in, i.e. for which the definition of G determines a winner of the game, are ones when one of the models is well-founded. In these cases we will use conditions (R_{I}2 + k) and (R_{II}2 + k) for k ≥ 1 as defined below to verify that the definition of G is satisfied.

We now turn to a description of the conditions not yet described. We assume from now on that M_{I} and M_{II} are distinct ω-models of T as will be guaranteed by our final organization of the conditions (R_{I}0), (R_{II}0), (R_{I}1), (R_{II}1) and (R_{I}2) in §2.4. As M_{I} ≠ M_{II}, the rules for G only specify a winner when at least one of them is well-founded. Thus we can restrict ourselves to this case. We begin with the cases corresponding to G3a and G4a.

2.2 Comparable models

We define conditions that will be used to recognize if M_{II} is ill-founded in the case when M_{I} ⊂ M_{II} and if M_{I} is ill-founded in the case when M_{II} ⊂ M_{I} with an eye toward satisfying the rules given by G3(a) and G4(a).

(R_{I}new): M_{I} ⊆ M_{II} and, for every β ∈ On^{M_{II}} \ A_{II}, M_{I} ⪯̸_{n} L_{β}^{M_{II}}.
(R_{II}new): M_{II} ⊆ M_{I} and, for every β ∈ On^{M_{I}} \ A_{I}, M_{II} ⪯̸_{n} L_{β}^{M_{I}}.

Here A_{I} is the image inside M_{I} of the “intersection” of M_{I} and M_{II}, i.e. the union of all the L_{β} in M_{I} with codes that are in M_{II} as reals which, in M_{II}, also code some L_{δ}. This makes sense since we are assuming that one of the models is well-founded and so isomorphic to an L_{β}. The notation for II is analogous and we use A to denote ambiguously the structure which is (isomorphic to) A_{I} and A_{II} and the isomorphism between them, i.e. the set of pairs ⟨a_{1}, a_{2}⟩ such that the isomorphism takes a_{1} ∈ A_{I} to a_{2} ∈ A_{II}.

Claim 2.6. The sets A, A_{I} and A_{2} are Σ_{2}^{0}.

Proof. For A we have the following Σ_{2}^{0} definition.

(z, w) ∈ A ⟺ ∃x ∈ ℝ^{M_{I}}, y ∈ ℝ^{M_{II}} (M_{I} ⊨ x codes z ∧ M_{II} ⊨ y codes w ∧ ∀n ∈ ω(M_{I} ⊨ n ∈ x ⟺ M_{II} ⊨ n ∈ y)).

For A_{I} we have that z ∈ A_{I} ⟺ ∃w ((z, w) ∈ A), and analogously for A_{II}.

Claim 2.7. (R_{I}new) and (R_{II}new) are Π_{3}^{0} conditions.

Proof. Consider (R_{I}new). As noted in the proof of Claim 2.5, M_{I} ⊆ M_{II} is a Π_{3}^{0} condition. Since A_{II} is Σ_{2}^{0} by Claim 2.6, the set On^{M_{II}} \ A_{II} is Π_{2}^{0}. Finally, as we are assuming that M_{I} ⊆ M_{II}, M_{I} ⪯̸_{n} L_{β}^{M_{II}} means that there is a Σ_{n} formula φ(x) and a pair of parameters (x_{1}, x_{2}) ∈ A such that ¬(M_{I} ⊨ φ(x_{1}) ⟺ L_{β}^{M_{II}} ⊨ φ(x_{2})). As membership in A is Σ_{2}^{0} by Claim 2.6 and satisfaction in each structure or members of it such as L_{β} is recursive in the theories the whole relation is Π_{3}^{0} as required. The argument for (R_{II}new) is analogous.

Now the crucial fact for our analysis is that certain failures of these conditions produce a well founded Σ_{n+1} admissible and so would contradict our hypothesis that α_{n+1} does not exist.

Lemma 2.8. Suppose M_{I} is the well-founded part of M_{II} and

∃β ∈ On^{M_{II}} (M_{I} ⪯_{n} L_{β}^{M_{II}}).

Then M_{I} is Σ_{n+1} admissible. The same is true with I and II interchanged.

Proof. We prove that M_{I} is Σ_{k} admissible by induction on k ≤ n + 1. For k = 1, this holds by our condition that M_{I} is a model of KP. (It would also follow from [MS Lemma 3.4] without this assumption on T.) So assume it is k −1 admissible but not k admissible for k ≤ n + 1. Let a function f witnessing the failure of k admissibility be defined by the Σ_{k} formula ∃uφ(x, y, u) where φ is Π_{k−1}. As every set in M_{I} is countable we may assume that the domain of f is ω. Of course, f is unbounded in M_{I}. Consider now the formula θ(x, ⟨y_{0}, y_{1}⟩) ≡ φ(x, y_{0}, y_{1}) & ∀z <_{L} y_{1}¬φ(x, y_{0}, z). By Σ_{k−1} admissibility the second conjunct is equivalent (in M_{I}) to a Σ_{k−1} formula saying that there is a function from {z|z <_{L} y_{1}} to the associated witness that φ(x, y_{0}, z) fails.

Consider now the set S defined in M_{II} as {⟨y_{0}, y_{1}⟩ |∃x ∈ ω(L_{β} ⊨ θ(x, ⟨y_{0}, y_{1}⟩) & L_{β} ⊨ (∀ ⟨z_{0}, z_{1}⟩ <_{L} ⟨y_{0}, y_{1}⟩)(¬θ(x, ⟨z_{0}, z_{1}⟩)}. It is clear from the definition of S that, for each x ∈ ω, there is at most one ⟨y_{0}, y_{1}⟩ ∈ L_{β} put into S by x. On the other hand, for each x ∈ ω there is a unique ⟨y_{0}, y_{1}⟩ satisfying θ in M_{I} (as f is a function y_{0} is unique and y_{1} was defined to be least such that φ(x, y_{0}, z)). This ⟨y_{0}, y_{1}⟩ must also satisfy θ in L_{β}^{M_{II}} as θ is a conjunct of a Π_{k−1} and a Σ_{k−1} formula and M_{I} ⪯_{k−1} L_{β}^{M_{II}}. As M_{I} is an initial segment of L_{β}^{M_{II}}, any ⟨z_{0}, z_{1}⟩ <_{L} ⟨y_{0}, y_{1}⟩ in L_{β}^{M_{II}} is in M_{I} and so if it satisfied θ(x, ⟨z_{0}, z_{1}⟩) in L_{β}^{M_{II}} it would satisfy it in M_{I} but, as above, there is only one such pair in M_{I}. So the only pair put into S by x ∈ ω in M_{II} is the unique ⟨y_{0}, y_{1}⟩ such that M_{I} ⊨ θ(x, ⟨y_{0}, y_{1}⟩). Thus S ⊆ M_{I} and, as f was unbounded in M_{I}, we have that ∪S = ∪M_{I} and so we have defined the well founded part of M_{II} in M_{II} for a contradiction.

The same proof works with I and II interchanged.

The consequence of this key fact that we need to satisfy G3(a) and G4(b) is the following:

Lemma 2.9. If M_{I} ⊆ M_{II} and M_{I} is well-founded, then (R_{I}new) holds if and only if M_{I} is equal to the well-founded part of M_{II}. The same is true with I and II interchanged

Proof. If M_{I} is not equal to the well-founded part of M_{II}, then the well-founded part of M_{II} is strictly greater than that of M_{I} by our assumptions. Thus there is a β ∈ On^{M_{II}} − A_{II} such that M_{I} = L_{β}^{M_{II}}. For this β we have M_{I} ⪯_{n} L_{β}^{M_{II}} and so the required failure of (R_{I}new).

For the other direction of our if and only if, suppose that M_{I} is the well-founded part of M_{II}, but that (R_{I}new) does not hold. By Lemma 2.8, M_{I} is n + 1-admissible contradicting our basic assumption that α_{n+1} does not exist.

The same proof works with I and II interchanged.

For the remaining cases, we have to primarily consider those where neither M_{I} nor M_{II} is contained in the other. In this case, we can assume that exactly one of them is well-founded. (Two well founded models of V = L are always comparable and we already know that one has to be well-founded for the play to be relevant.) In this case, it suffices, by the definition of G, to guarantee the player producing the well-founded model wins.

2.3 Incomparable models

If M_{I} and M_{II} are incomparable (as will be guaranteed at some point in our game by the failure of previous conditions) we may assume that exactly one of them is well-founded. We denote the well-founded one by M and the ill-founded one by N. We want to identify the one which is well founded to determine the winner so as to satisfy G3(b) and G4(b). Each condition in the sequence to be described below asks for a descending chain in one of the models. The failure of each successive condition produces a model with one more level of admissibility. If one condition succeeds then we identify the well founded model and can declare a winner consistent with G3(b) and G4(b). If all of them fail we produce a Σ_{n+1} admissible for the desired contradiction.

The idea in the definition of the remaining conditions (R_{::}2 + k) is that we want them to provide evidence that one of the models is ill-founded by finding a nonempty set of ordinals without a least element. (The nonemptyness was inadvertently left out in [MS] but this makes no significant difference in the proofs provided there.) To this end we define various sets of ordinals in the two models and establish some of their properties.

Looking ahead to our proof of the nonreversal of Theorem 1.10(5) in §3, it would be useful for the readers of this section to note that all the Lemmas apply to similar games. To be specific, in §3 we have a theory T_{n}^{∗} in place of T here. This theory implies that there are unboundedly many n-admissibles but that the universe has Σ_{1}-cofinality ω rather than being admissible. It still satisfies all sets are countable. While some of the conditions defining the game there are different, the general set up is quite similar. When we consider a play of the game there the cases of interest will be that exactly one of the two models is the standard model of the theory (L_{α}_{n}^{∗}) and the other is a nonstandard model of the theory incomparable (in the above sense of containment) with the standard model. It is routine to verify that all the Lemmas of this section apply to such a situation.

Definition 2.10.

C_{M_{II},1} = {β ∈ On^{M_{II}} : ∃(x_{1}, x_{2}) ∈ A, φ ∈ Δ_{0},

((∃z ∈ L_{β}^{M_{II}} M_{II} ⊨ φ(z, x_{2})) ∧ (M_{I} ⊨ ¬∃yφ(y, x_{1})))}.

C_{M_{I},1} is defined analogously.

Claim 2.11. The sets C_{M_{II},1} and C_{M_{I},1} are Σ_{2}^{0}.

Proof. By Claim 2.6, A is Σ_{2}^{0} while the second line of the definition is computable from the elementary diagrams of M_{I} and M_{II}.

We now have our first level of the (R_{::}2 + k) conditions:

(R_{I}3): C_{M_{II},1} is not empty and has no least element.
(R_{II}3): C_{M_{I},1} is not empty and has no least element.

Clearly these conditions are Π_{3}^{0}.

At this point in [MS] we could assume that the models were incomparable. Unfortunately, in our game will not be able to know that the models are incomparable until after we consider (R_{I}3), (R_{II}3) and (R_{I}4). This necessitates a real modification in the definition of C_{M_{II},k}^{β_{1},β_{2}} and (⋆_{k−1}) which are used below to define the (R_{::}(2 + k)) for k > 1. We must now allow for the possibility that β_{1} or β_{2} might take on the value ∞. (Looking ahead, the advantage of this change is that, if M_{I} ⊆ M_{II}, we might still have that (⋆_{1})(∞, β_{2}) for some β_{2} when it might fail for every β_{1} ∈ M_{I} (which is well-founded).)

Definition 2.12. For k ≥ 1 we define the condition (⋆_{k})(β_{1}, β_{2}) by

β_{1} ∈ (On^{M_{I}} ∖ A_{I}) ∪ {∞} ∧ M_{I} ⊨ β_{1} is (k − 1)-admissible ∧ β_{2} ∈ (On^{M_{II}} ∖ A_{II}) ∪ {∞} ∧ M_{II} ⊨ β_{2} is (k − 1)-admissible ∧

L_{β_{1}}^{M_{I}} ≡_{k,A} L_{β_{2}}^{M_{II}}.

Here 0-admissibility is taken to be just transitivity and L_{∞}^{M_{::}} is taken to be M_{::}. The symbol ≡_{k,A} denotes Σ_{k}-elementary equivalence with parameters from A. In other words, L_{β_{1}}^{M_{I}} ≡_{k,A} L_{β_{2}}^{M_{II}} means that for every Σ_{k} formula φ(z), and every x_{1} ∈ A_{I} and x_{2} ∈ A_{II}, if x_{1} and x_{2} represent the same set (i.e. (x_{1}, x_{2}) ∈ A), then L_{β_{1}}^{M_{I}} ⊨ φ(x_{1}) ⟺ L_{β_{2}}^{M_{II}} ⊨ φ(x_{2}).

Claim 2.13. The relation ⋆_{k} is a Π_{2}^{0} property of β_{1} and β_{2}.

Proof. By Claim 2.6, On^{M_{::}} ∖ A_{::} are Π_{2}^{0}. Whether β_{i} is (k − 1)-admissible is just one sentence in the theory of the structure. To check that L_{β_{1}}^{M_{I}} ≡_{k,A} L_{β_{2}}^{M_{II}}, we need to say that, for every Σ_{k} formula φ(x), and for every pair of parameters (x_{1}, x_{2}) ∈ A, M_{I} ⊨ φ(x_{1}) ⟺ M_{II} ⊨ φ(x_{2}). As A is Σ_{2}^{0} by Claim 2.6, counting quantifiers shows that (⋆_{k}) is Π_{2}^{0}.

We next define the sets C_{M_{II},k}^{β_{1},β_{2}} and C_{M_{I},k}^{β_{1},β_{2}} (correcting two typos in [MS]).

Definition 2.14. For k > 1,

C_{M_{II},k}^{β_{1},β_{2}} = {β < β_{2} : ∃(x_{1}, x_{2}) ∈ A, ∃φ ∈ S_{k−1}

(∃z ∈ L_{β}^{M_{II}} L_{β_{2}}^{M_{II}} ⊨ φ(z, x_{2})) ∧ (L_{β_{1}}^{M_{I}} ⊨ ¬∃yφ(y, x_{1}))}.

Here S_{k−1} is the class of formulas that are Boolean combinations of formulas of the form (∀x ∈ z)ψ(x, z, ȳ) where ψ is Σ_{k−1}. Again β_{1} or β_{2} may be ∞ and L_{∞}^{M_{::}} is taken to be M_{::}. C_{M_{I},k}^{β_{1},β_{2}} is defined analogously.

We note the following property of S_{k} sentences for any ω-models M_{I} and M_{II} produced according to the rules of our game so far.

Lemma 2.15. If L_{β_{1}}^{M_{I}} ≡_{k,A} L_{β_{2}}^{M_{II}}, then L_{β_{1}}^{M_{I}} and L_{β_{2}}^{M_{II}} satisfy the same S_{k}-sentences with parameters from A substituted for the free variables z and ȳ.

Proof. Let φ be a sentence of the form (∀x ∈ z)ψ(x, z, ȳ) with parameters from A where ψ is Σ_{k}. Since φ has no free variables, z and ȳ are parameters from A, and so every x ∈ z is also in A. Since L_{β_{1}}^{M_{I}} ≡_{k,A} L_{β_{2}}^{M_{II}}, we have that for every x ∈ z, L_{β_{1}}^{M_{I}} ⊨ ψ(x, z, ȳ) ⇔ L_{β_{2}}^{M_{II}} ⊨ ψ(x, z, ȳ). So, of course, L_{β_{1}}^{M_{I}} ⊨ φ ⇔ L_{β_{2}}^{M_{II}} ⊨ φ. Finally, if ϕ is a Boolean combination of sentences of this form, then we also have L_{β_{1}}^{M_{I}} ⊨ ϕ ⇔ L_{β_{2}}^{M_{II}} ⊨ ϕ.

We can now define the remaining conditions R_{::}(2 + k) for k > 1.

Definition 2.16. For k > 1,

(R_{I}(2 + k)): For every β_{1}, β_{2}, if (⋆_{k−1})(β_{1}, β_{2}), then C_{M_{II},k}^{β_{1},β_{2}} is not empty and

has no least element.

(R_{II}(2 + k)): For every β_{1}, β_{2}, if (⋆_{k−1})(β_{1}, β_{2}), then C_{M_{I},k}^{β_{1},β_{2}} is not empty and

has no least element.

Here again β_{1} and β_{2} may be ∞ as well as ordinals of M_{I} and M_{II}, respectively.

We must now verify the key properties of the conditions ((R_{::}(2+k))). When M_{I} and M_{II} are incomparable, as remarked above, one of them, denoted by M, is well-founded and the other, denoted by N, is not. In this case, we only need some modifications of the proofs in [MS] to accommodate the possibility that β_{1} or β_{2} is ∞.

Lemma 2.17. If G1 does not determine the winner of a play of our game (i.e., R_{I}i and R_{II}i fail for i < 2), the models M and N produced are incomparable (i.e. G2 does not determine the winner of the play) and both R_{I}3 and R_{II}3 fail, then there is a β ∈ On^{N} ∖A such that A ≼_{1} L_{β}^{N} and so β_{1} and β_{2} such that ⋆_{1}(β_{1}, β_{2}) holds.

Proof. Suppose the first assertion fails, that is, for every γ ∈ On^{N} ∖ A, there is a Σ_{1} formula with parameters in A, that is true in L_{γ} but not in A. Since conditions (R_{I}3) and (R_{II}3) are not satisfied, C_{N ,1} is empty or has a least element δ. If C_{N ,1} is empty, then, by definition, A ≼_{1} L_{β}^{N} for every β ∈ On^{N} ∖ A. Thus, we may assume that C_{N ,1} has a least element δ. Notice that δ cannot be in A because if the witness z for a Δ_{0} formula φ(z, x_{2}) is in L_{N_{δ}} ⊆ A, then ∃yφ(y, x_{1}) also holds in M. Let δ > γ_{0} > γ_{1} > γ_{2} > ... be a descending sequence in On^{N} ∖ A, converging down to the cut (On^{A}, On^{N} ∖ A). For each i, there is a Δ_{0} formula φ_{i} with parameters from A and a <_{L}-least witness z_{i} ∈ L_{γ_{i}} such that N ⊨ φ_{i}(z_{i}) but A ⊨ ¬∃yφ_{i}(y). By thinning out the sequence if necessary, we may assume that z_{i} ∈ L_{γ_{i}} but z_{i} ∉ L_{γ_{i+1}}. So {z_{i} : i ∈ ω} is an <_{L}^{N} -descending sequence. Since γ_{i} ∉ C_{N ,1}, M ⊨ ∃yφ_{i}(y). Let y_{i} be the <_{L}^{M}-least such witness. Since M is well-founded, the sequence {y_{i} : i ∈ ω} cannot be a <_{L}^{M}-descending sequence. So, there exists i < j such that z_{j} <_{L}^{N} z_{i} but y_{i} <_{L}^{M} y_{j}. Therefore, L_{γ_{j}} is a witness in L_{γ_{j}+1} for x showing the truth in N of the Δ_{0} formula

ψ(x) ≡ ∃z ∈ xφ_{j}(z) ∧ ∀z ∈ x¬φ_{i}(z)

but there is no witness for ψ(x) in M. This shows that γ_{j} + 1 is in C_{N ,1}, contradicting our choice of δ as the least element of C_{N ,1}.

Now choose α such that L_{α} = A and so α ∈ M and β the ordinal of N such that A ≼_{1} L_{β}^{N}. By the definition of ⋆_{1}, α and β, in the appropriate order, provide the required witnesses for ⋆_{1}.

Lemma 2.18. Suppose that β_{1}, β_{2} satisfy (⋆_{k}). As the definition of ⋆_{k} is symmetric we may suppose that β_{1} ∈ M and β_{2} ∈ N. Then

1. L_{α} ≼_{k} L_{β_{1}} and A ≼_{k} L_{β_{2}}.

2. α is (k + 1)-admissible.

3. There exists a descending sequence of N -ordinals γ converging down to On^{A} such that L_{γ} ≼_{k} L_{β_{2}}.

Proof. If β_{1} ≠ ∞, it is simply an ordinal in the well-founded M and L_{β_{1}}^{M} = L_{β_{1}}. If β_{1} = ∞ then as usual L_{β_{1}}^{M} = M but note that in this case, as M is well-founded, we may also view β_{1} as the (true) ordinal of M = L_{β_{1}}. For β_{2} = ∞, we simply view L_{β_{2}}^{N} as N.

First, we note that {α} is not Σ_{k} definable in L_{β_{1}} with parameters from L_{α}. Suppose otherwise. Since α ∈ M ⊨ T, every α is countable in L_{α+1} ∈ M by [MS Lemma 3.5]. Thus there is a definable over L_{α} map from ω onto α (possibly with parameters). This defines in L_{α}, an ordering of ω of order type α. This ordering cannot belong to N as it would then define its well-founded part. In L_{β_{1}} we can define this ordering with a Σ_{k} formula using the Σ_{k} definition of α and quantification over L_{α}. Since L_{β_{1}} = L_{β_{1}}^{M} ≡_{k,A} L_{β_{2}}^{N}, this ordering is definable in L_{β_{2}}^{N} by the same formula, and hence belongs N for the desired contradiction.

Now for part (1), since β_{1} is (k −1)-admissible, L_{β_{1}} has a Σ_{k}-Skolem function without parameters ([MS Lemma 3.1]). Let H be the Σ_{k}-Skolem hull of L_{α} in L_{β_{1}}. We show that H = L_{α}. Note that this implies that L_{α} ≼_{k} L_{β_{1}} (as desired) and also A ≼_{k} L_{β_{2}} since L_{β_{1}}^{M} ≡_{k,A} L_{β_{2}}^{N} by ⋆_{k}. Suppose that H ⊋ L_{α}. Let L_{γ} be the Mostowski collapse of H, so α < γ ≤ β_{1}. Let α′ be the ordinal in H that is sent to α ∈ L_{γ} by the collapse. As α′ is in the image of the Σ_{k} Skolem function, {α′} is Σ_{k} definable in H with parameters from L_{α} . The same formula then gives a definition of {α} in L_{γ} as the collapse is the identity on members of L_{α}. Thus {α} is Σ_{k} definable in L_{γ} with parameters from L_{α} but clearly

L_{γ}^{M} ≡_{k,A} H ≡_{k,A} L_{β_{1}}^{M}.

So {α} would be Σ_{k} definable in L_{β_{1}}^{M} contradicting our first observation.

(2) Suppose α is not (k +1)-admissible and so (since every ordinal is countable in M) there is a Π_{k}/L_{α} function f from ω onto α. Since A ≼_{k} L_{β_{2}}^{N}, the same formula defining f over L_{α} defines a function from ω onto α in L_{β_{2}}^{N}. But then, in N we could define its well-founded part, L_{α}, for a contradiction.

(3) Now since α is (k + 1)-admissible, there are unboundedly many γ < α such that L_{γ} ≼_{k} L_{α} ([MS, Lemma 3.3]). For all these γ we also have L_{γ}^{N} ≼_{k} L_{β_{2}}^{N}. The set of γ < β_{2} such that L_{γ}^{N} ≼_{k} L_{β_{2}}^{N} is definable in N. If for some δ ∈ On^{N} ∖ A, the set of γ < δ such that L_{γ}^{N} ≼_{k} L_{β_{2}}^{N} had supremum α, then α would be definable in N and we know it is not. So for every δ ∈ On^{N} ∖ A, there exists γ < δ, γ ∈ On^{N} ∖ A such that L_{γ}^{N} ≼_{k} L_{β_{2}}^{N}.

Lemma 2.19. If in a play of our game the resulting real does not satisfy any condition (R_{I}i) or (R_{II}i) for i ≤ 2 + k, then there are β_{1} and β_{2} satisfying (⋆_{k}).

Proof. Lemma 2.17 shows that there are β_{1} and β_{2} satisfying (⋆_{1}). The proof now proceeds by induction, so, without loss of generality, we assume that we have witnesses β_{1}, β_{2} satisfying (⋆_{k−1}).

We claim that no δ ∈ A is in C_{N ,k}^{β_{1},β_{2}}. Consider δ ∈ A and any S_{k−1} formula ∀x ∈ zφ(z, ȳ) and z_{2}, ȳ_{2} ∈ L_{δ}^{N} ⊆ A such that L_{β_{2}}^{N} ⊨ ∀x ∈ z_{2}φ(z_{2}, ȳ_{2}). Since L_{β_{1}} and L_{β_{2}} satisfy the same Σ_{k−1} formulas with parameters from A (by (⋆_{k−1})), L_{β_{1}}^{M} ⊨ ∀x ∈ z_{1}φ(z_{1}, ȳ_{1}), where z_{1} and ȳ_{1} are the images of z_{2}, ȳ_{2} in M. Thus δ ∉ C_{N ,k}^{β_{1},β_{2}} by its definition.

Since the conditions (R_{I}(2 + k)) and (R_{II}(2 + k)) are not satisfied, C_{N ,k}^{β_{1},β_{2}} is empty or has a least element δ, necessarily not in A. By clause (3) of the previous lemma, there is a descending sequence γ_{0} > γ_{1} > γ_{2} > ... in On^{N} (all below δ if it exists), converging down to α = On^{A}, such that for each i L_{γ_{i}}^{N} ≼_{k−1} L_{β_{2}}^{N}. We now argue much as for Lemma 2.17. We claim that, for some i, L_{α} ≼_{k} L_{γ_{i}}^{N}. If not, there is, for each i, a Π_{k−1} formula φ_{i}(z) with parameters from A and a <_{L}^{N} -least z_{i} ∈ L_{γ_{i}} such that L_{γ_{i}} ⊨ φ_{i}(z_{i}) and z_{i} ∉ A. As L_{γ_{i}}^{N} ≼_{k−1} L_{β_{2}}^{N}, L_{β_{2}}^{N} ⊨ φ_{i}(z_{i}). By thinning out the sequence if necessary, we may assume that z_{i} ∈ L_{γ_{i}}^{N} but z_{i} ∉ L_{γ_{i+1}}^{N}. So {z_{i} : i ∈ ω} is an <_{L}^{N} -descending sequence. Since γ_{i} ∉ C_{N ,k}^{β_{1},β_{2}}, L_{β_{1}}^{M} ⊨ ∃yφ_{i}(y). Let y_{i} be the <_{L}^{M}-least such witness. Since M is well-founded, the sequence {y_{i} : i ∈ ω} cannot be a <_{L}^{M}-descending sequence. So, there exist i < j such that z_{j} <_{L}^{N} z_{i} but y_{i} <_{L}^{M} y_{j}. Therefore, L_{γ_{j}}^{N} ∈ L_{γ_{j}+1}^{N}is a witness for x showing the truth in L_{β_{2}}^{N}of the S_{k−1} formula

ψ(x) ≡ ∃z ∈ xφ_{j}(z, x) ∧ ∀z ∈ x¬φ_{i}(z, x)

while there is no such witness for the corresponding formula in L_{β_{1}}^{M}. This contradicts our choice of δ as the least element of C_{N ,k}^{β_{1},β_{2}}. Thus we have an i such that L_{α} ≼_{k} L_{γ_{i}}^{N} ≼_{k−1} L_{β_{2}}^{N}.

Now L_{γ_{i}}^{N} is Σ_{k−1} admissible by [MS Lemma 3.4] as L_{β_{2}}^{N} is Σ_{k−2} admissible by (⋆_{k−1}) while α is (even) Σ_{k} admissible by our induction hypothesis and the previous Lemma and so (⋆_{k})(α, γ_{i}) as required.

As we shall see in our final organization of the conditions in the next section, the only situation in which we have to rely on any of these facts without being able to assume that M_{I} and M_{II} are incomparable is the argument that ⋆_{1} holds for some β_{1} and β_{2} if (R_{I}3) and (R_{II}3) both fail. We analyze this situation when it occurs in the next section.

For now we suggest how the final arguments will produce the desired (n+1)-admissible ordinal by combining Lemmas 2.17-2.19.

Corollary 2.20. If M and N are incomparable ω-models of T derived from a play of our game with (in our notation as above) M = L_{α} and (R_{I}i) and (R_{II}i) both fail for i ≤ 2 + k, then α is (k + 1)-admissible.

Proof. For k = 1, Lemma 2.17 shows that ⋆_{1}(β_{1}, β_{2}) holds for some β_{1} and β_{2}. Lemma 2.19 then shows that there are also β_{1} and β_{2} such that ⋆_{k}(β_{1}, β_{2}) holds if k > 1. Finally Lemma 2.18(2) says that α is (k + 1)-admissible as required.

2.4 Organizing the Conditions and Verifications

Formally we define our Π_{3,n}^{0} game G by a list of n many Π_{3}^{0} sets A_{0}, A_{1} …, A_{n−1} followed by A_{n} = 2^{ω}. Remember that I wins if the first of these sets containing the play of our game has an even index and otherwise, i.e. the first one has an odd index, II wins. The table below contains the definition of the A_{i} arranged with the even index ones in column I and the odd index ones in column II in alternating blocks.

win for I  win for II
(¬R_{II}0&¬R_{II}1)&  ⋮
A_{0}  \begin{matrix}[R_{I}0 ∨ R_{I}1∨ \\ M_{I} = M_{II}∨ \end{matrix}
(R_{I}new)∨
(R_{I}3)]

\begin{matrix}R_{II}0 ∨ R_{II}1∨ \\ M_{I} ⊆ M_{II}∨ \end{matrix}

A_{1}  (R_{II}new)∨

(R_{II}3)∨ (R_{II}4)

M_{II} ⊆ M_{I}∨
A_{2}  (R_{I}4)∨
(R_{I}5)

(R_{II}5)∨

A_{3}  (R_{II}6)
⋮
A_{n−1}  ⋮

We end this list with A_{n−1} corresponding to (R_{II}(1 + n)) ∨ (R_{II}(2 + n)) if n ≥ 2 is even and (R_{I}(1 + n)) ∨ (R_{I}(2 + n)) if n > 2 is odd. (Recall that we are only proving our theorem for n ≥ 2.) This gives us n many conditions. We finish the description of the game in standard Π_{3,n}^{0} format by adding on the the full space 2^{ω} as our (n + 1)st and last set A_{n}. We now argue that the game G specified by this sequence of Π_{3}^{0} sets is in G. If not, then there is a play of G that violates the defining conditions of G. We consider any play and the set in our sequence in which it first appears and verify that we have not violated the definition of G.

We begin with a play in A_{0}. By the definition of A_{0}, I has played a complete consistent extension of T whose term model M_{I} is an ω-model (as ¬R_{II}0 and ¬R_{II}1 hold and so I has not lost the game yet according to G1). We now check each of the disjunctions in the rest of the definition of A_{0} to see that a win by I given by satisfying the disjunction is consistent with our definition of G. If R_{I}0 or R_{I}1 holds then I wins by G1. If they fail then II has played a complete consistent extension of T whose term model M_{II} is an ω-model. If M_{I} = M_{II} then I wins by G2. Suppose now that M_{I} ≠ M_{II}. Remember that from now on we only need to consider plays of the game in which at least one of the models is well-founded to verify that the winner declared by G is consistent with the definition of G. If (R_{I}new) holds then M_{I} ⊂ M_{II} by our assumption and the definition of the condition. As we are assuming that (at least) one of the models is well-founded, M_{I} is certainly well-founded. Then by Lemma 2.9, M_{I} is the well-founded part of M_{II} but, as the models are not equal, M_{II} is not well-founded and I wins according to G3b. Next, if (R_{I}3) holds we only have to verify that the play cannot be a win for II according to the rules for G, i.e. G4a or G4b. Now both of these require that M_{II} is well-founded but (R_{I}3) says that it is not. So neither condition can require a win for II as desired.

We now move to A_{1} under the assumption that the play is not in A_{0}. First if R_{II}0 or R_{II}1 hold then II wins the game according to G1. If not, we again have the two models M_{I} and M_{II} being distinct and we need only consider the case that at least one is well-founded.

Suppose then that the next condition, M_{I} ⊆ M_{II}, holds and so M_{I} must be wellfounded. Under these conditions, the failure of (R_{I}new) implies, by Lemma 2.9, that M_{I} is not the well-founded part of M_{II} and so neither G3a nor G3b can apply. Thus it is consistent with the definition of G that we declare a win for II.

The next case is that (R_{II}new) holds and so in particular, M_{II} ⊆ M_{I}, M_{II} at least must be well-founded and, by Lemma 2.9 again, M_{II} is the well-founded initial segment of M_{I} which cannot be well-founded as M_{I} ≠ M_{II}. Once again neither G3a nor G3b can apply and we are safe.

Next we have (R_{II}3). If it holds then M_{I} is not well-founded and once again we can safely declare a win for II. Finally, we have to consider the case that all the previous conditions have failed but (R_{II}4) holds. If we knew that there were β_{1} and β_{2} for which ⋆_{1} holds, we would again know that M_{I} is not well founded and we can declare a win for II. If M_{I} and M_{II} are incomparable then Lemma 2.17 tells is that ⋆_{1} holds as desired for the α and β described there. Thus we may assume that M_{II} ⊂ M_{I} and M_{II} is well-founded. The failure of (R_{II}new) then tells us that, by Lemma 2.9, M_{II} is not equal to the well-founded part of M_{I}. Thus there is a β ∈ On^{M_{I}} − A and indeed that α = ∪On^{M_{II}} ∈ M_{I} − A. We then have ⋆_{1}(∞, α) as required.

Now if the play of the game is not in A_{0} or A_{1} then we have our models M_{I} and M_{II}. If both are well founded then they are comparable and, by the failure to get into A_{0} or A_{1}, M_{II} ⊂ M_{I} and according to G3a I should win the game. We claim this outcome is always in A_{2} as desired. If we are considering n = 2 (and the sequence of sets from our table ends with A_{1}) then this is trivial since A_{2} = 2^{ω}. If n > 2 then it is in A_{2} by the first clause of its definition. Thus we may assume from now on (in our check of consistency with the definition of G) that exactly one of the models is well-founded.

Next suppose that M_{II} ⊆ M_{I} so M_{II} is well-founded and not M_{I}. The failure of (R_{II}new) and Lemma 2.9 then says that M_{II} is not the well-founded initial segment of M_{I}. Thus both G4a and G4b fail and it is safe for us to declare a win for I. From this point on in our argument we may assume that M_{I} and M_{II} are incomparable as well as that exactly one is well-founded. At this point (R_{I}i) and (R_{II}i) fail for i ≤ 3 as does (R_{II}4). If (R_{I}4) holds, M_{II} is not well-founded since there are, by Lemma 2.17, β_{1} and β_{2} such that ⋆_{1} holds. It is then safe to declare a win for I. If (R_{I}4) fails, then, by Corollary 2.20, we have a Σ_{3} admissible ordinal which is the desired contradiction for the case n = 2 and we have finished our verification. If n > 2, (R_{I}4) fails but (R_{I}5) holds, M_{II} is once again not well-founded by Lemma 2.19. Thus we may safely declare a win for I.

Next consider n = 3. We already know that our play getting into A_{0}, A_{1} or A_{2} is consistent with being in G. If it fails to get into A_{0}, A_{1} or A_{2}, but satisfies (R_{II}5) or ¬(R_{II}5) ∧ (R_{II}6) then M_{I} is not well-founded as in the previous cases and it is safe to declare a win for II. If both fail, then Corollary 2.20 provides a Σ_{4} admissible ordinal for the desired contradiction. The analysis for all n > 3 is now the same as for n = 3 and we have that for every n ≥ 2 our Π_{3,n}^{0} game given by the specifications above is in G to complete the proof of Lemma 1.6.

3 No reversal

We now prove that (5) in Theorem 1.10 does not reverse. That is, for every n ≥ 2, β(Δ_{n+1}^{1}-CA_{0}) ⊬ (n − 1)-Π_{3}^{0}-DET.

Let α_{n}^{∗} be the first limit of n-admissibles. Thus, ℝ∩L_{α}_{n}^{∗} ⊧ β(Δ_{n+1}^{1}-CA_{0}) and is itself a β-model. We will modify the proofs of Theorem 1.8 and Lemma 2.2 to provide a witness to the nonreversal.

Theorem 3.1. The model given by L_{α}_{n}^{∗}, i.e. ℝ ∩ L_{α}_{n}^{∗}, does not satisfy (n − 1)-Π_{3}^{0}-DET.

The crucial lemma is the following:

Lemma 3.2. For every n ≥ 2, there is a game G_{n}^{∗} that is (n-1)-Π_{3}^{0}, such that, if we interpret the play of each player as the characteristic function of a set of sentences in the language of set theory, then

1. If I plays T h_{α}_{n}^{∗}, he wins.

2. If I does not play T h_{α}_{n}^{∗} but II does, then II wins.

We first provide the proof of the Theorem from the Lemma.

Proof of Theorem 3.1 from Lemma 3.2. As we mentioned above, ℝ ∩ L_{α}_{n}^{∗} is a β-model of β(Δ_{n+1}^{1}-CA_{0}) and so it suffices to show that L_{α}_{n}^{∗} ⊭ (n-1)-Π_{3}^{0}-DET. Let G be as in the Lemma; and suppose it is determined in L_{α}_{n}^{∗}. Player II cannot have a winning strategy for G in L_{α}_{n}^{∗} because if II has a winning strategy σ in L_{α}_{n}^{∗}, σ would also be a winning strategy in V as ℝ ∩ L_{α}_{n}^{∗} is a β-model (and σ being a winning stratgey for G is a Π_{1}^{1} property). But, I has a winning strategy for G in V by clause (1) of the Lemma. So, I must have a winning strategy σ for G in L_{α}_{n}^{∗}. Again, as ℝ ∩ L_{α}_{n}^{∗} is a β-model, σ is truly a winning strategy for I (in V). We claim that if II plays so as to simply copy I’s moves, then σ has to play T h_{α}_{n}^{∗}. If not, then at some first point I plays a bit that is different from T h_{α}_{n}^{∗}. At this point II could stop copying I and just continue playing T h_{α}_{n}^{∗} and he would win (by clause (2) of the Lemma). Thus σ would not be a truly winning strategy for I (in V). We conclude that σ computes T h_{α}_{n}^{∗} as the sequence of I’s plays against II’s copying his moves and so T h_{α}_{n}^{∗} ∈ L_{α}_{n}^{∗} for the desired contradiction.

The proof of Lemma 3.2 is similar to that of Lemma 2.2 and we adopt much of its notation.

We do, however, replace the theory T with the following:

T_{n}^{∗} = V = L + there are unboundedly many n-admissibles, but only finitely many below each ordinal.

So, L_{α}_{n}^{∗} is the least well-founded model of T_{n}^{∗} and is also a β-model. The general set up is as in Lemma 2.2 including the notations such as M_{I}, M_{::}, A, A_{I}, (R_{::}i), etc. One new fact that simplifies the conditions needed for our game is a simple one:

Lemma 3.3. If M_{I} ≠ M_{II} are ω-models of T_{n}^{∗} then they are incomparable (all in the sense of the notion of containment from Definition 2.3).

Proof. If M_{I} ⊊ M_{II} then there are unboundedly many n-admissibles in M_{I} and some β ∈ On^{M_{II}} − A and so infinitely many n-admissibles in M_{II} below β contradicting M_{II} being a model of T_{n}^{∗}.

We also change the conditions (R_{::}new) to reflect the new theory:

(R_{Inew∗}):

M_{I} is an ω-model of a complete consistent extension of T_{n}^{∗} and

(∀β ∈ On^{M_{I}} \ A_{I} ∀m ∀ ⟨γ_{1}, …, γ_{m}⟩ an increasing sequence of n-admissibles ≤ β in M_{I}) {[∃γ ∈ On^{M_{I}}(∀i ≤ m(γ ≠ γ_{i}) and M_{I} ⊨ γ ≤ β is n-admissible] or [∃i ≤ m(L_{γ_{i}}^{M_{I}} = A_{I})]}.

(R_{IInew∗}):

M_{II} is an ω-model of a complete consistent extension of T_{n}^{∗} and

(∀β ∈ On^{M_{II}} \ A_{II} ∀m ∀ ⟨γ_{1}, …, γ_{m}⟩ an increasing sequence of n-admissibles ≤ β in M_{II}) {[∃γ ∈ On^{M_{II}}(∀i ≤ m(γ ≠ γ_{i}) and M_{II} ⊨ γ ≤ β is n-admissible] or [∃i ≤ m(L_{γ_{i}}^{M_{II}} = A_{II})]}. Using the Claims above about quantifier complexity, we can easily verify that saying

that L_{γ_{i}}^{M::} = A_{::} is Π_{3}^{0} and that the conditions (R_{Inew∗}) and (R_{IInew∗}) are also Π_{3}^{0}.

We now replace the old conditions (R_{::}new) on our list by the (R_{::new∗}). Because of Lemma 3.3 we can omit the conditions M_{I} ⊆ M_{II} and M_{II} ⊆ M_{I} in the A_{1} and A_{2} groups, respectively. Otherwise, our new game G_{n}^{∗} is defined by the same sequence of conditions given in §2.4 except that we are producing a Π_{3,n−1}^{0} game rather than a Π_{3,n}^{0} one:

win for I  win for II
(¬R_{II}0&¬R_{II}1)&  ⋮
A_{0}  \begin{matrix}[R_{I}0 ∨ R_{I}1∨ \\ M_{II} = M_{I}∨ \end{matrix}
(R_{I}new^{∗})∨
(R_{I}3)]
R_{II}0 ∨ R_{II}1∨
A_{1}  (R_{II}new^{∗})∨
(R_{II}3)∨
(R_{II}4)
A_{2}  (R_{I}4)∨
(R_{I}5)
(R_{II}5)∨
A_{3}  (R_{II}6)
⋮
A_{n−2}  ⋮

Again, we add on 2^{ω} as the last entry but here in the A_{n−1} slot. We must verify that these conditions define a game G_{n}^{∗} as required for Lemma 3.2. We begin with characterizing the relevant situations in which (R_{::new∗}) holds.

Lemma 3.4. If M_{I} and M_{II} are distinct ω-models of T_{n}^{∗} then (R_{::new∗}) holds if and only if

(i) ∃γ[(M_{::} ⊨ γ is n-admissible) and L_{γ}^{M_{::}} = A_{::}].

Proof. Suppose (i) holds and consider any β and ⟨γ_{1}, …, γ_{m}⟩ as in the definition of (R_{::new∗}). (There is such a β by Lemma 3.3.) If (i) holds with witness γ, then either γ can be added to the list of γ_{i} or it is already one of them and so (R_{::new∗}) holds as required. On the other hand, if (R_{::new∗}) holds and (i) fails then, by Lemma 3.3, there is a β ∈ M_{::} − A_{::} and so by the definition of T_{n}^{∗} there is an m and a sequence ⟨γ_{1} … γ_{m}⟩ containing all the n-admissibles ≤ β in M_{::}. For this sequence, (R_{::new∗}) guarantees that, for some i ≤ m, L_{γ}^{M_{::}} = A_{::} as required.

We must now verify that these conditions cannot cause a loss for the first player to play T h_{α}_{n}^{∗} as required. If I plays T h_{α}_{n}^{∗} and so M_{I} = L_{α}_{n}^{∗}, then the first worry is that (R_{Inew∗}) and all the other clauses of the first group fail but (R_{IInew∗}) holds. (The two preceding disjuncts in group A_{1} clearly contradict M_{I} = L_{α}_{n}^{∗} by asserting that it is not an ω-model of T_{α}_{n}^{∗}.) By the failure of the clauses in A_{0}, M_{II} ≠ M_{I} and so by Lemma 3.4 there is an n-admissible γ ∈ M_{II} such that L_{γ}^{M_{II}} = A_{II}. As γ is admissible it is not α_{n}^{∗} and so is strictly less than α_{n}^{∗}. In this case we would have γ + 1 in both M_{I} and M_{II} and so in A for a contradiction. Now R_{II}3 cannot hold as it implies that M_{I} is not well-founded. The next worry in this case is then that R_{II}4 holds.

We recall that the proofs for the Lemmas of §2.3 apply for theories such as T_{n}^{∗} whose models are limits of admissibles and games of the sort we have here when considering play for which exactly one of the two models constructed is standard and the two are incomparable. That is precisely our situation at this point in our analysis. Thus we may use all the Lemmas of §2.3. This suffices, for example, for our current case as Lemma 2.17 shows that there are β_{1} and β_{2} such that ⋆_{1}(β_{1}, β_{2}) holds and so R_{II}4 would imply that M_{I} is not well-founded for a contradiction.

We now show that if II plays T h_{α_{n}} (and so M_{II} = L_{α}_{n}^{∗}) but I does not, then I does not win by group A_{0} being true. The first conjunct in A_{0} makes M_{I} an ω-model of T_{α}_{n}^{∗}. That M_{II} = L_{α}_{n}^{∗} means that R_{I}0, R_{I}1 and R_{I}3 all fail. By Lemma 3.3, M_{II} ≠ M_{I}. Finally, if R_{I}new^{∗} held then we would contradict M_{II} = L_{α}_{n}^{∗} using Lemma 3.4 as in the previous argument.

Suppose now that our play has passed the A_{0} and A_{1} groups without a winner having been declared. We are still only concerned with plays in which one player plays L_{α}_{n}^{∗}, the other does not, the two models are incomparable (and so the one not equal to L_{α}_{n}^{∗} is not well-founded) and both R_{::}new^{∗} fail. The Lemmas from §2 and, in particular their Corollary 2.20, show that if we pass through all the R_{::}2 + i for 1 ≤ i ≤ k without declaring a winner (i.e. they all fail), then α is Σ_{k+1} admissible. For k = n−1 this would contradict the assumed situation and, in particular, the failure of R_{::}new^{∗} by Lemma 3.4. Thus one player must win the game and there is a first R_{::}2 + i which holds. Whichever it is, the associated ⋆ has witnesses by Lemma 2.18 and so the other model is not well-founded. Thus only the player playing L_{α}_{n}^{∗} can win the game as required.

4 Bibliography

Burgess, John P. [1986], The truth is never simple, Journal of Symbolic Logic 51, 663–681.

Friedman, H. [1971], Higher set theory and mathematical practice, Annals of Mathematical Logic 2, 325-357.

Hodes, H. T. [1980], Jumping through the transfinite: The mastercode hierarchy of Turing degrees, Journal of Symbolic Logic 45, 204-220.

Martin, D. A. [n.d.] Determinacy, circulated drafts, about 578 pp.

Montalbán, A. and Shore, R. A. [2012], The limits of determinacy in second order arithmetic, Proceedings of the London Mathematical Society (3) (2012) 104, 223-252.

Shore, R. A. [2010], Reverse Mathematics: the Playground of Logic, Bulletin of Symbolic Logic 16, 378-402.

Simpson, S. G. [2009], Subsystems of Second Order Arithmetic 2^{nd} ed., Perspectives in Logic, ASL and Cambridge University Press, New York.

Welch, P. D.[2011], Weak systems of determinacy and arithmetical quasi-inductive definitions, Journal of Symbolic Logic 76, 418–436.

Welch, P. D. [2012], G_{δσ}-games, Isaac Newton Institute Preprint Series No. NI12050-SAS, 2012.