The Strength of Turing Determinacy within Second Order Arithmetic

Antonio Montalbán^{∗} Department of Mathematics University of California, Berkeley Berkeley CA 94720 e-mail: antonio@math.berkeley.edu

Richard A. Shore^{∗∗} Department of Mathematics Cornell University Ithaca NY 14853 e-mail: shore@math.cornell.edu

April 14, 2015

Abstract We investigate the reverse mathematical strength of Turing determinacy up to

Σ_{5}^{0} which is itself not provable in second order arithmetic.

1 Introduction

Reverse mathematics endeavors to calibrate the complexity of mathematical theorems by determining precisely which system P of axioms are needed to prove a given theorem Θ. This is done in one direction in the usual way showing that P ⊢ Θ. The other direction is a “reversal” that shows that relative to some weak base theory Θ ⊢ P. 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 the weak system of axioms called RCA_{0} that correspond to recursive constructions. One typically then adds additional comprehension (i.e. existence) axioms to get other systems P. Many of these systems are given by Γ comprehension (Γ-CA_{0}) which is gotten from RCA_{0} by adding on the axiom that all sets defined by formulas in some class Γ exist. So one gets ACA_{0} for Γ the class or arithmetic formulas and Π_{n}^{1}-CA_{0} for Γ the class of all Π_{n}^{1} formulas. (In each case the formulas may contain set parameters.) Full second order arithmetic, Z_{2}, is the union of all the Π_{n}^{1}- CA_{0}. The standard text here is Simpson [2009] to which we refer the reader for general background.

∗Partially supported by NSF Grant DMS-0901169, and by a Packard Foundation Fellowship.

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

MSC 2010: 03B30,03D80,03F60,03F35. Keywords: Turing Determinacy, Reverse Mathematics

This paper is concerned with the analysis of various principles connected with 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 §1 of Montalbán and Shore [2012] (henceforth denote by MS [2012]) and refer the reader to that paper for more historical details and other background for both reverse mathematics and determinacy. Here we give some basic definitions and cite a few results.

Definition 1.1 (Games and Determinacy). Our games are played by two players I and II on {0, 1} [or ω]. They alternate playing an element of {0, 1} [or ω] with I playing first to produce a play of the game which is a sequence f ∈ 2^{ω} [ω^{ω}]. A game G_{A} is specified by a subset A of 2^{ω} [ω^{ω}].We say that I wins a play f of the game G_{A} specified by A if f ∈ A. Otherwise II wins that play.

Definition 1.2. A strategy for I (II) is a function s from strings σ in 2^{<ω} [ω^{<ω}] of even (odd) length into {0, 1} [ω]. It is a wining strategy if any play f following it (i.e. f(n) = s(f ↾ 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.

The classical reverse mathematical results are (essentially Steel [1976] see also Simpson [2009 V.8]) that Σ_{1}^{0}-DET is equivalent to ATR_{0} a system asserting the existence of transfinite iterations of arithmetic comprehension that lies strictly between ACA_{0} and Π_{1}^{1}-CA_{0}; and (Tanaka [1990]) that Π_{1}^{1}-CA_{0} is equivalent to determinacy for conjunctions of Π_{1}^{0} and Σ_{1}^{0} sets. Results on Π_{2}^{0}, Δ_{3}^{0} and Π_{3}^{0} determinacy (Tanaka [1991], MedSalem and Tanaka [2007] and Welch [2011]) show that they are significantly stronger with the last provable in Π_{3}^{1}-CA_{0} but not Δ_{3}^{1}-CA_{0}. Friedman [1971] in what was really the first foray into reverse mathematics, proved that Σ_{5}^{0}-DET is not provable in full second order arithmetic and Martin [1974a], [n.d.] improved this to Σ_{4}^{0}-DET.

In MS [2012] we delineated the limits of determinacy provable in Z_{2} as encompassing each level of the finite difference hierarchy on Π_{3}^{0} sets. Indeed each level n of the this hierarchy is provable from Π_{n+2}^{1}-CA_{0} but not at any lower level of the comprehension axiom hierarchy. (So the union of the hierarchy (which is far below Δ_{4}^{0}) is not provable in Z_{2}.) Then, in Montalbán and Shore [2014] (hereafter MS [2014]) we analyzed the consistency strength of all these statements, getting a much clearer picture. In this paper we analyze, to the extent we can, the reverse mathematical strength of a variation on determinacy where one is thinking of the underlying space as the Turing degrees in place of 2^{ω} or ω^{ω}.

Definition 1.3. An A ⊆ 2^{ω}[ω^{ω}] is Turing invariant or degree closed if (∀f ∈ 2^{ω}[ω^{ω}])(∀g ∈ 2^{ω}[ω^{ω}])(f ≡_{T} g → (f ∈ A ↔ g ∈ A)). We denote by Γ Turing determinacy or Γ-TD the assertion that every degree closed A ∈ Γ is determined.

Remark 1.4. For any reasonable Γ including each of the Σ_{n}^{0} classes, it is clear that Γ-DET is equivalent (in RCA_{0}) to Γ̆-DET where Γ̆ = {Ā|A ∈ Γ}. So we can use these two assertions interchangeably and similarly for Γ-TD. We also note that while it is easy to code sets as functions recursively (and so determinacy or Turing determinacy for classes in ω^{ω} imply the corresponding result for 2^{ω}) the converse is not obvious at the very lowest level. However, for any of the arithmetic classes at or above Δ_{3}^{0}, it does not matter for determinacy or Turing determinacy if we work in 2^{ω} or ω^{ω} as we can code functions in ω^{ω} by sets in 2^{ω} as long as we include the Π_{2}^{0} condition that the sets are infinite. So once we are at that level we work in whichever setting is more convenient.

It is a classical theorem of Martin that a degree closed set A is determined if and only if it contains a cone, i.e. a set of Turing degrees of the form {x|x ≥ z} for some degree z called the base of the cone or is disjoint from a cone. (In the first case I has a winning strategy; in the second, II.) In the realm of set theory, this induces a 0 − 1 valued measure on sets of degrees (with measure 1 corresponding to containing a cone). This result is the basis for many interesting set theoretic investigations. The question of the relationship between determinacy axioms and Turing determinacy axioms is an interesting one in the set theoretic setting. Perhaps the most striking early result is that for Γ = Σ_{1}^{1} the two notions coincide and and are equivalent with the axiom asserting the existence of x^{#} for every x ∈ ω^{ω} (Martin [1970] and Harrington [1978]). At the level of determinacy for all sets, later work by Woodin showed that for full determinacy and Turing determinacy are not only equiconsistent but are equivalent (over DC) in L(ℝ). (See Koellner and Woodin [2010 and other articles in the same handbook] for this and much more on the role of TD in set theory.) The main results for Turing determinacy at lower levels of the arithmetic hierarchy show some differences from full determinacy at the same levels. There are a few classical ones given in Harrington and Kechris [1975], primarily from recursion theoretic or ZFC points of view and Martin [1974] and [n. d.] from the viewpoint of working in ZFC without the power set axiom and replacement only for Σ_{1} formulas.

Their results either directly, or can be refined to, give ones in reverse mathematics. In this paper we present them from the viewpoint of reverse mathematics and fill in some of the gaps. We begin with determining how much Turing determinacy is provable in weak systems. The base theory RCA_{0} proves Π_{2}^{0}-TD (Theorem 2.5). The next step is, of course, Δ_{3}^{0}-TD.

The standard tool in analyzing the Δ_{n+1}^{0} levels is the finite level version of a classical theorem appearing in Kuratowski [1966]. It gives a representation of Δ_{n+1}^{0} subsets of 2^{ω} in terms of the transfinite difference hierarchy on Π_{n}^{0} or Σ_{n}^{0} sets. One can then use determinacy at the lower level to bootstrap up to Δ_{n+1}^{0}. There are various formulations and we state a couple of variants. That this theorem can be proven for n ∈ ω in ACA_{0} with some extra recursion theoretic conclusions is due to MedSalem and Tanaka [2007]. Our notation is slightly different from theirs. It follows more closely that used by Martin [1974, 1974a, 1974b, n. d.]. We also incorporate a few normalizations of the sequences that appear in different presentations.

Theorem 1.5 (Kuratowski; Martin; MedSalem and Tanaka for ACA_{0}). For any Z ∈ 2^{ω}, a set A ⊆ 2^{ω} is Δ_{n+1}^{Z} if and only if there is an ordinal α recursive in Z and a sequence of uniformly Π_{n}^{Z} sets A_{ξ} for ξ ≤ α which are decreasing (A_{η} ⊇ A_{ξ} for η < ξ), continuous (for limit ordinals λ, A_{λ} = ∩{A_{η}|η < λ}) with A_{0} = 2^{ω} and A_{α} = ∅ such that ∀X(X ∈ A ⇔ μβ(X ∉ A_{β} is odd). Dually (by taking complements) A ∈ Δ_{n+1}^{Z}if and only if there is an ordinal α recursive in Z and a sequence of uniformly Σ_{n}^{Z} sets A_{ξ} for ξ ≤ α which are increasing (A_{η} ⊆ A_{ξ} for η < ξ), continuous (for limit ordinals λ, A_{λ} = ∪{A_{η}|η < λ}) with A_{0} = ∅ and A_{α} = 2^{ω} such that ∀X(X ∈ A ⇔ μβ(X ∈ A_{β} is even).

Remark 1.6. If a Δ_{n}^{0} set A is degree invariant and n ≥ 3 then, in the above Σ_{n}^{0} representation, we may take the A_{ξ} to be degree invariant as well. The first point here is that ≤_{T} is a Σ_{3}^{0} relation and so if A is Σ_{n}^{0} then so is its Turing closure Â = {f|∃e(Φ_{e}^{f} ∈ A & ∃i(Φ_{i}^{Φ_{e}^{f}} = f)}. The second point is that Â still gives a representation of A: If ξ is the first with X in the degree closed version Â_{ξ} of A_{ξ}, then some Y ≡_{T} X is in A_{ξ} and not in any A_{η} ⊆ Â_{η} and so in A.

This theorem allows us to prove Δ_{3}^{0}-TD at the expense of moving from RCA_{0} to ACA_{0} (Theorem 2.6). We point out that there can be no reversals from any Turing determinacy assumption to any system stronger than RCA_{0}. The key fact here is that the standard model of RCA_{0} with just the recursive sets (or the sets recursive in any X) is obviously a model of Γ-TD for any Γ. Thus we can hope for implications from any Γ-TD only over stronger systems. In this case, we can, however, prove that Δ_{3}^{0}-TD is not provable in RCA_{0} (Proposition 2.8). This supplies a natural principle that lies strictly between RCA_{0} and ACA_{0} but does not imply the existence of a nonrecursive set.

We next move on to Σ_{3}^{0}-TD. Combining the implication from ATR_{0} to Σ_{1}^{0}-DET (Steel [1976] in RCA_{0}) and from Σ_{1}^{0}-DET to Σ_{3}^{0}-TD (Harrington an Kechris [1975]) we see that ATR_{0} ⊢ Σ_{3}^{0}-TD. In this case, we prove a reversal over ACA_{0} (Theorem 3.7). This supplies an example of a natural theory strictly weaker than ATR_{0} (and indeed does not even imply the existence of a nonrecursive set) but which joins ACA_{0} up to it. In particular, Σ_{1}^{0}-DET is equivalent to Σ_{3}^{0}-TD over ACA_{0}.

Using the representation of Theorem 1.5, we can now hope to prove Δ_{4}^{0}-TD in ATR_{0}. We do so in Theorem 3.3 but we need an additional induction axiom.

Definition 1.7. For S a class of formulas, S transfinite induction, S-TI, is the scheme of axioms stating that for every well-ordering α (formally coded as a set X of ordered pairs ⟨β, γ⟩ prescribing its ordering relation <_{X} on its domain which is also a subset of ω) and every formula φ ∈ S, {(∀γ)[((∀β <_{X} γ)φ(β)) → φ(γ))] → (∀β <_{X} α)φ(β)}.

The version that we need to prove Δ_{4}^{0}-TD over ACA_{0} in Theorem 3.3 is Π_{1}^{1}-TI_{0}. Over ACA_{0} this axioms scheme is equivalent to the dependent choice axiom for Σ_{1}^{1} formulas (Simpson [2009, VIII.5.12]) and so provable in Π_{1}^{1}-CA_{0} but not in ATR_{0}.

As our last stop inside Z_{2}, we analyze Σ_{4}^{0}-TD and Δ_{5}^{0}-TD based on results of Harrington and Kechris [1975], Martin [1974] and Welch [2011] to show that Π_{3}^{1}-CA_{0} proves both. We can have no meaningful reversal even over relatively strong systems. Even full Borel determinacy can prove neither Δ_{2}^{1}-CA_{0} (even with TI for all formulas) nor Π_{3}^{1}-CA_{0} even over Δ_{3}^{1}-CA_{0} and TI for all formulas (MS [2012, Corollaries 6.2 and 6.6]). Still, using methods and results of MS [2012] and Montalbán and Shore [2014] working, however, with Σ_{4}^{0}-TD in place of Σ_{3}^{0}-DET, we prove that not much less than Π_{3}^{1}-CA_{0} will suffice. Indeed, Π_{1}^{1}-CA_{0} + Σ_{4}^{0}-TD proves the existence of a Σ_{2} admissible ordinal (Lemma 4.7) and so in terms of consistency strength, Π_{1}^{1}-CA_{0} + Σ_{4}^{0}-TD is much stronger than Δ_{3}^{1}-CA_{0} (Corollary 4.8).

Finally, we use these methods to derive Martin’s result that Σ_{5}^{0}-TD implies the existence of β_{0} (the least ordinal α such that L_{α} ⊨ Z_{2}) in Π_{1}^{1}-CA_{0} (Lemma 4.4). Thus Π_{1}^{1}-CA_{0} + Σ_{5}^{0}-TD implies the consistency of Z_{2} (and more) and so takes us well beyond the reach of full second order arithmetic (Corollary 4.6).

We close this section with some notational conventions.

Notation 1.8. We use ω to denote the set of natural numbers. Members of 2^{ω} are generally called sets and symbols such as X, Y, Z are used to denote them. Members of ω^{ω} are often called reals and we use symbols such as f, g, h to denote them. (Of course a real may be a set when its range is contained in {0, 1}.) The (Turing) degrees of these sets and functions are, as usual, denoted by the corresponding small boldface roman letter. So for example f ∈ f and X ∈ x. The eth partial recursive function and r.e. set relative to f are denoted by Φ_{e}^{f} and W_{e}^{f},respectively.

Notation 1.9. Subsets of both 2^{ω} and ω^{ω} are generally denoted by symbols such as A, B, C. We use symbols such as σ, τ to denote strings in either 2^{<ω} or ω^{<ω} and rely on the context to determine which is intended. The length of σ is denoted |σ| and its initial segment of length n ≤ |σ| is denoted by σ ↾ n. We use standard concatenation and pairing functions, conventions and notations such as σˆ τ, σˆ f, ⟨σ, τ⟩ ⟨σ, f⟩ ⟨σ, X⟩ , ⟨f, g⟩ , ⟨u, v, w⟩ = ⟨u, ⟨v, w⟩⟩ in the usual way. The precise formulations do not matter as long as they are done recursively.

We assume a basic familiarity with recursive ordinals and the hyperarithmetic hierarchy and at times their formal development in ATR_{0} as in Simpson [2009, VII]. Note also that we generally prove theorems in their lightface version and leave relativization to the reader unless some desired uniformity is brought out by carrying along the set parameter.

2 The trivial levels

In this section we prove Π_{2}^{0}- and Δ_{3}^{0}-Turing Determinacy. Only the first proof is carried out in RCA_{0}. It is helpful to introduce a weaker but more easily definable notion of closure than under ≡_{T}.

Definition 2.1. Given k ∈ ω and f ∈ ω^{ω} we define k × f ∈ ω^{ω} by (k × f)(kn) = f(n) and (k × f)(m) = 0 for m not a multiple of k. We say that an A contained in ω^{ω} or 2^{ω} is sufficiently closed if (∀f ∈ A)(∀σ)(∀k)(σˆ (k × f) ∈ A). Here and elsewhere σ is in ω^{<ω} or 2^{<ω} appropriate. The smallest sufficiently closed set containing f is the sufficient closure of f. Let E be the set of even strings, i.e. those whose nonzero values occur only at even numbers such as all initial segments of 2 × f for any f.

Remark 2.2. Note that, for every m, n, f, m × (n × f) = mn × f. It is then easy to see that, for every f in ω^{ω} or 2^{ω}, {σˆ (k × f)|k ∈ ω and σ a string} is the sufficient closure of {f}.

Also, for any A ⊆ 2^{ω}, the set Â = {X : (∀σ, k)(σˆ (k × X)) ∈ A} is sufficiently closed. The advantage of using sufficient closure instead of Turing closure is that if A is Π_{2}^{0}, then so is Â.

Lemma 2.3 (RCA_{0}). For every Z ∈ ω^{ω}, every Π_{2}^{Z} set A ⊆ ω^{ω} [2^{ω}] which is sufficiently closed is either empty or contains an element of every Turing degree above Z.

Proof. Let A ≠ ∅ be such a set. There is then an r.e. operator W (given by some W_{e}) such that f ∈ A ⇔ f ∈ W^{Z⊕f} is infinite. Let

X = {σ : W^{Z⊕σ} − W^{Z⊕σ^{−}} ≠ ∅},

(where W^{Z⊕σ} only runs for |σ| many steps and σ^{−} = σ ↾ |σ|−1). So, we have that f ∈ A if and only if f ↾ n ∈ X for infinitely many n. Note that X ≤_{T} Z. Say f ∈ A, then for every σ, σˆ (2 × f) ∈ A. Thus every σ there is a τ ∈ E (e.g. some initial segment of 2 × f) such that σˆ τ ∈ X.

Now, given any infinite Y ∈ 2^{ω} with Z ≤_{T} Y, we build an h ∈ A, with h ≡_{T} Y. We construct h as the union of finite initial segments ∅ = σ_{0} ⊆ σ_{1} ⊆ ⋯ all of even length.

We just need to make sure that h meets X infinitely often and is of the same Turing degree as Y. Suppose we have σ_{s}. Let τ_{s} be the first τ ∈ E found in a standard search recursive in Z such that σ_{s}ˆ τ ∈ X. Let k_{s} be least such that |σ_{s}ˆ τ_{s}ˆ 0^{k_{s}}| = 2 ⟨x, y_{s}⟩ + 1 for y_{s} the sth element of Y and some x. Now set σ_{s+1} = σ_{s}ˆ τ_{s}ˆ 0^{k_{s}}ˆ 1. Clearly h ≤_{T} Y (by construction as Z ≤_{T} Y), h ∈ A and Y ≤_{T} h (its members can be read off in order from the list of odd numbers m such that h(m) = 1) as required.

As degree-invariant sets are obviously sufficiently closed we have the following corollaries.

Corollary 2.4. For every Z ∈ 2^{ω}, every nonempty degree invariant Π_{2}^{Z} set A ⊆ ω^{ω} [2^{ω}] contains all f ≥_{T} Z.

Corollary 2.5. RCA_{0} ⊢ Π_{2}^{0}-TD.

Lemma 2.6 (ACA_{0}). For every Z ∈ 2^{ω}, every nonempty, degree-invariant Δ_{3}^{Z} subset A of 2^{ω} contains all X ≥_{T} Z.

Proof. Let A be a Δ_{3}^{Z} degree invariant subset of 2^{ω}. By Theorem 1.5, there is a decreasing, continuous sequence {A_{ξ} : ξ ≤ α} of uniformly Π_{2}^{Z} subsets of 2^{ω} with A_{α} = ∅ such that

X ∈ A ⇔ μξ(X ∉ A_{ξ}) is odd.

Now, let Â_{ξ} = {X : (∀σ, k)(σˆ (k×X)) ∈ A_{ξ}}. The Â_{ξ} are clearly Π_{2}^{Z} and, by Remark 2.2, sufficiently closed and so dense. By Lemma 2.3, each Â_{ξ} is either ∅ or contains a member Y of every degree above that of Z. As A_{α} = ∅ = Â_{α}, there is, by ACA_{0}, a least ξ such that Â_{ξ} = ∅. (By Lemma 2.3, Â_{ξ} being empty is equivalent to ¬∃X(X ≡_{T} Z & X ∈ A).) Note that as the A_{ξ} are continuous, so are the Â_{ξ}: Consider any limit ordinal λ. If X ∈ Â_{λ} then its sufficient closure is contained in A_{λ} and so in every A_{ξ} for ξ < λ and thus in ∩{Â_{ξ}|ξ < λ}. On the other hand, if X ∈ Â_{ξ} for every ξ < λ, then its sufficient closure is contained in each Â_{ξ} ⊆ A_{ξ} and so in A_{λ} and in Â_{λ}. Thus ξ cannot be a limit ordinal by the Baire category theorem. (The Â_{ξ} are dense Π_{2}^{Z} and so themselves intersections of open (and hence dense open) sets.)

We now claim that A is either ∅ or contains every Y ≥_{T} Z depending on the parity of ξ (or if it is α). To see this consider any degree y ≥ z. By the leastness of ξ and Lemma 2.3, there is a Y ∈ Â_{ξ−1} of degree y. Of course, Y ∉ Â_{ξ} = ∅ and so, by definition, there are σ and k such that σˆ (k × Y) ∉ A_{ξ}. On the other hand, since Â_{ξ−1} is sufficiently closed, σˆ (k×Y) ∈ Â_{ξ−1}. Thus the membership of σˆ (k×Y) (and so of Y ≡_{T} σˆ (k×Y)) in A is determined by the parity of ξ as required.

Corollary 2.7. ACA_{0} ⊢ Δ_{3}^{0}-TD.

Note that by Remark 1.4 the corollary holds in ω^{ω} as well as 2^{ω}. From now on we will be concerned with Turing determinacy at levels above Δ_{3}^{0} and so work in whichever setting is more convenient.

We conclude this section by showing that Δ_{3}^{0}-TD is not provable in RCA_{0}. If we are looking for a standard model of RCA_{0} in which Δ_{3}^{0}-TD fails we have serious restrictions on the method of attack. Suppose the formulas (with parameter Z) defining a Δ_{3}^{0} set A of reals determining a game in a standard model M actually define a Δ_{3}^{0} set of reals in the universe or even in any extension of the sets of M to a model of ACA_{0}. In this case, Theorem 1.5 provides a representation of A in the extension and Lemma 2.6 applies. Its conclusions, however, are clearly absolute downwards to M and so the given game is determined in M. Thus the only hope of finding a standard model counter-example is to consider formulas which define a Δ_{3}^{0} set in M but not in any extension to a model of ACA_{0}.

Proposition 2.8. RCA_{0} ⊬ Δ_{3}^{0}-TD.

Proof. Consider an initial segment of the degrees below 0′ of order type ω given by representatives X_{n} which are uniformly Δ_{2}^{0} (Lerman [1983, XII.5.1], Epstein [1983]). Our model M of RCA_{0} consists of all sets recursive in some X_{n}. Our Δ_{3}^{0} degree invariant class is given by two Σ_{3}^{0} formulas φ and ψ. The first says that there is an n such that X ≡_{T} X_{2n} and the second that there is an n such that X ≡_{T} X_{2n+1}. These sets are clearly complementary in M. To see that they are Σ_{3}^{0} write out the definitions, for example, φ(X) ⇔ ∃n{∃e(Φ_{e}^{X} is total & ∀m(Φ_{e}^{X}(m) = X_{2n}(m)) & ∃i(Φ_{i}^{Φ_{e}^{X}} = X)} and remember that the X_{n} are uniformly Δ_{2}^{0}. Thus φ and ψ define a Δ_{3}^{0} set of reals in M while both sets are clearly unbounded in the Turing degrees of M. Thus M ⊭ Δ_{3}^{0}-TD as required.

3 Σ_{3}^{0} and Δ_{4}^{0} sets

In this section we show that Σ_{3}^{0}-TD is equivalent to ATR_{0} over ACA_{0} and that Δ_{4}^{0}-TD is provable from ATR_{0} + Π_{1}^{1}-TI_{0}. As mentioned in §1, Π_{1}^{1}-TI_{0} is equivalent to Σ_{1}^{1}-DC_{0} over ACA_{0} and ATR_{0} + Π_{1}^{1}-TI_{0} the lies strictly between ATR_{0} and Π_{1}^{1}-CA_{0}. On the other hand, we show that Δ_{4}^{0}-TD is not provable from ATR_{0}. The situation here is similar to, but much more subtle than that for Δ_{3}^{0}-TD in Proposition 2.8.

Theorem 3.1 (essentially Harrington and Kechris [1975]). ATR_{0} ⊢ Σ_{3}^{0}-TD.

Proof. We follow the proof of Harrington and Kechris [1975, §2] but make explicit a property of their construction that we will need in the proof of Theorem 3.3. Let a given game be specified by a Σ_{3}^{0} degree invariant subset of ω^{ω}, B = {f|∃i∀j∃kR(i, j, f̄(k))} where R is a recursive predicate and f̄(k) is the sequence ⟨f(0), …, f(k − 1)⟩. We define a Π_{1}^{0} set A which has members of the same degrees as B: A = {⟨i, f, g⟩ |∀j(g(j) = μkR(i, j, f̄(k))}. Clearly, if ⟨i, f, g⟩ ∈ A then g ≤_{T} f and so ⟨i, f, g⟩ ≡_{T} f ∈ B. Conversely, if f ∈ B then there is an i such ∀j∃kR(i, j, f̄(k)) and so a g ≤_{T} f such that ⟨i, f, g⟩ ∈ A. Thus A and B have elements of exactly the same degrees.

We next consider another Π_{1}^{0} set C = {⟨⟨i, f, g⟩ , h⟩ |g ∈ A & ∀n(Φ_{i}^{g}(n) converges in exactly f(n) many steps) & h is II’s play when he follows the strategy given by Φ_{i}^{g} against I playing ⟨i, f, g⟩}. Note that if ⟨⟨i, f, g⟩ , h⟩ ∈ C then ⟨⟨i, f, g⟩ , h⟩ ≡_{T} g and g ∈ A.

Now apply Π_{1}^{0}-determinacy (which follows from ATR_{0} as in Simpson [2009, V.8.2]), to the game specified by C. If I has a strategy s then, we claim that every degree t ≥ s has a representative in A: As usual, let I play s against any real t ∈ t. The resulting play ⟨s(t), t⟩ has degree t and is in C and so of the form ⟨⟨i, f, g⟩ , h⟩ with g ∈ A and ⟨⟨i, f, g⟩ , h⟩ ≡_{T} g as required. Thus, in this case, as B is degree invariant, it contains a cone with base the strategy for I in the game specified by C. On the other hand, if II has a strategy s for this game, we claim that B is disjoint from the cone above s. If not then there is a ĝ ∈ B and hence one g ∈ A which computes s. Suppose Φ_{i}^{g} = s. Let f(n) ≤_{T} g be the number of steps it takes Φ_{i}^{g}(n) to converge and h be II’s play following his supposedly winning strategy given by Φ_{i}^{g} = s against I playing ⟨i, f, g⟩. It is clear from the definitions that the play of this game is ⟨⟨i, f, g⟩ , h⟩ and it is in C for the desired contradiction.

We now calculate the complexity of the property of a Σ_{3}^{0} degree invariant subset of ω^{ω} containing a cone. We use this calculation in the proof of Theorem 3.3.

Proposition 3.2 (ATR_{0}). The predicate that (the formula defining) a Σ_{3}^{0} degree invariant set of reals contains a cone of degrees is Σ_{1}^{1}.

Proof. Let B be a degree invariant Σ_{3}^{0} set of reals. Define Π_{1}^{0} sets A and C as in the proof of Theorem 3.1. It is easy to see that the existence of a strategy s for the closed game given by C is a Σ_{1}^{1} property: for every σ the result of playing s against σ satisfies the Σ_{1}^{0} predicate of not being in C. If this condition holds then the proof of Theorem 3.1 shows that A intersects every degree above that of a strategy and hence B contains a cone. On the other hand, If there is no such strategy, then by ATR_{0} there is one for II in this game and so again as in the proof of Theorem 3.1, B is disjoint from the cone above II’s strategy.

We now give a proof of Δ_{4}^{0}-TD in ATR_{0} + Π_{1}^{1}-TI_{0} which, as pointed after Definition 1.7, is lies strictly between ATR_{0} and Π_{1}^{1}-CA_{0}. Thus Δ_{4}^{0}-TD is strictly weaker than Π_{1}^{1}-CA_{0} even over ATR_{0}.

Theorem 3.3. ATR_{0} + Π_{1}^{1}-TI_{0} ⊢ Δ_{4}^{0}-TD.

Proof. Represent a given Δ_{4}^{0} degree invariant set B ⊆ 2^{ω} using the difference hierarchy on Σ_{3}^{0} sets as in Theorem 1.5. By Remark 1.6, we may assume that each B_{ξ}, ξ ≤ α is itself Turing invariant and so (by Theorem 3.1) either disjoint from a cone or contains one. As B_{α} = 2^{ω} and the B_{ξ} are increasing, there is, by Proposition 3.2 and Π_{1}^{1}-TI_{0}, a least γ such that B_{γ} contains a cone. If γ is a successor ordinal, then we have a cone disjoint from B_{γ−1} and contained in B_{γ}. Depending on the parity of γ, this cone is either disjoint from, or contained in, B as required.

To finish the proof we show that γ cannot be a limit. For each ξ < γ, let A_{ξ} be a Π_{1}^{0} set reals with members of the same Turing degrees as B_{ξ} and C_{ξ} the associated Π_{1}^{0} set as defined in Theorem 3.1. Consider the Π_{1}^{0} game specified by C = {⟨⟨⟨ξ, i⟩ , f, g⟩ , h⟩ | ⟨⟨i, f, g⟩ , h⟩ ∈ C_{ξ}}, i.e. I first chooses a ξ and then plays the game determined by C_{ξ}. If I has a winning strategy in this game, say his first move is to play ⟨ξ, i⟩. The rest of his strategy then gives him a wining strategy in C_{ξ} which (by the proof of Theorem 3.1) would be the base of cone in B_{ξ} contrary to the assumption that it is disjoint from a cone. Thus (by Π_{1}^{0}-DET), II has a strategy s for the game specified by C. Restricting I to play a given ξ < γ as the first part of his first move gives a strategy s_{ξ} for II in C_{ξ} uniformly recursive in s. As, by the proof of Theorem 3.1, each s_{ξ} is the base of a cone disjoint from B_{ξ}, s is the base of a cone disjoint from all the B_{ξ} for ξ < γ and so disjoint from B_{γ} = ∪_{ξ<γ}B_{ξ} for the desired contradiction.

We now prove that one cannot get Δ_{4}^{0}-TD from ATR_{0} alone. A crucial ingredient is H. Friedman’s [1967, II] ω-incompleteness theorem (see Simpson [2009, VIII.5.6]). Note that a countable coded ω model specified by a set M is a structure for second order arithmetic in which the numbers are the numbers (in the ambient universe) and its sets are the columns (M)_{n} = {x| ⟨x, n⟩ ∈ M}.

Theorem 3.4 (H. Friedman). Let S be a recursive set of sentences of second order arithmetic which includes ACA_{0}. If there exists a countable coded ω-model of S, then there exists a countable coded ω-model of S ∪ {¬∃countable coded ω-model of S}.

Theorem 3.5. ATR_{0} ⊬ Δ_{4}^{0}-TD.

Proof. For convenience we work in the real world although certainly Π_{1}^{1}-CA_{0} suffices. All models M or M_{n} in our proof, beginning with M_{0} ⊨ T_{0}, will be countable coded ωmodels of T_{0} = ATR_{0}. By Theorem 3.4, there is an M_{1} ⊨ S_{1} where S_{1} = T_{0} & ¬∃M ⊨ T_{0}. As M_{1} is a coded ω-model there is an M̂_{1} containing it such that M̂_{1} ⊨ T_{1} where T_{1} = T_{0} & ∃M ⊨ S_{1}. Applying Theorem 3.4 again, we get an M_{2} ⊨ S_{2} where S_{2} = T_{1} & ¬∃M ⊨ T_{1}. We now set T_{2} = T_{0} & ∃M ⊨ S_{2} and continue similarly to get M̂_{2} ⊨ T_{2} and M_{3} ⊨ S_{3} with S_{3} = T_{2} & ¬∃M ⊨ T_{2} and M̂_{3} ⊨ T_{0} & ∃M ⊨ S_{3}. Then we proceed similarly by induction to get M_{n+1} ⊨ S_{n+1} with S_{n+1} = T_{n} & ¬∃M ⊨ T_{n} and M̂_{n+1} ⊨ T_{n+1} with T_{n+1} = T_{0} & ∃M ⊨ S_{n+1}.

We now let T be the theory containing T_{0} with new constants M_{n} and assertions saying that for all n, the M_{n} are countable coded ω-models of S_{n} and that M_{n} is a member of M_{n+1} (in the sense that as a set it is coded in M_{n+1} by being one of the columns of M_{n+1}). Any finite subset of T is satisfied by one of the M_{n} just constructed. (Unravelling the definitions of T_{n} and S_{n} shows that any model M_{n+1} of S_{n+1} contains an M_{n} ⊨ S_{n} and so by induction a sequence of M_{i} for i < n as required in T.) Thus there is a model N̂ of T. (Note that this model is only given by a compactness argument so is expected to be nonstandard.)

We now consider the ω-submodel N of N̂ specified by taking as its second order part all sets coded in any of the M_{n} in N̂. First note that N ⊨ ATR_{0}: If there is a wellordering α in N then it is a member of some M_{n} ⊂ N and so also well-ordered in M_{n}. If we have any arithmetic predicate S for which we want a hierarchy to witness ATR_{0} in N, consider the same formula interpreted in M_{n} (which we may assume contains the set parameters in S as well as α). As M_{n} ⊨ ATR_{0}, the desired hierarchy of sets exists in M_{n}. As the properties required of it are arithmetic they hold in N as well.

We now define, in N, degree invariant classes A, B ⊂ N: A = {X| the least n, such that X does not compute both an M ⊨ S_{n} and its satisfaction predicate, is even} and B = {X| the least n, such that X does not compute both an M ⊨ S_{n} and its satisfaction predicate, is odd}. Clearly A and B are disjoint. We claim that A ∪ B = N. Consider any X ∈ N so X ∈ M_{i} for some i. We see, by the definition of the M_{n}, that no member of M_{i} can be an M ⊨ S_{i} and so no such is computable from X. (If M ∈ M_{i} and M ⊨ S_{i} then, by the definition of S_{i}, M ⊨ T_{i−1} but , again by the definition of S_{i}, M_{i} ⊨ ¬∃M ⊨ T_{i−1} for the desired contradiction.) Thus there is some n ∈ ω and so a least one such that no M computable from X can be a model of S_{n}. (Notice that if X ∈ M_{i} computes a model M then, as M_{i} is a model of ATR_{0}, the satisfaction predicate for M is also in M_{i}.) Thus X ∈ A ∪ B as required. Next, we claim that both A and B are unbounded in the Turing degrees of N. The point here is that M_{n} ⊨ S_{n} but it and every model M computable from it together with its satisfaction predicate is in M_{n+1} and so M ⊭ S_{n+1}. Thus M_{n} ⊕ Sat(M_{n}) ∈ A for n odd and M_{n} ⊕ Sat(M_{n}) ∈ B for n even where Sat(M) is the full satisfaction predicate (elementary diagram) for M. Of course, the degrees of the M_{n} are cofinal in those of N for both the even and odd n.

All that remains to see that A is a counterexample to Δ_{4}-TD in N is to show that it (and analogously B) is Σ_{4}^{0}. To this end we write out the definition of A: X ∈ A ⇔ ∃n(∃m(n = 2m) & (∀Y, W ≤_{T} X(Y is not a countable coded ω-model of S_{n} with W its satisfaction predicate) & (∃Z, V ≤_{T} X)(Z is a countable coded ω-model of S_{n−1} with satisfaction predicate V). As usual, we represent a set Z ≤_{T} X by an index of a characteristic function Φ_{e}^{X} computable from X. Thus to say (∃Z, V ≤_{T} X)Θ(Z, V) is to say ∃e, i(Φ_{e}^{X} and Φ_{i}^{X} are total characteristic functions & Θ(Φ_{e}^{X}, Φ_{i}^{X})). Now being total is a Π_{2}^{X} property. Once we have guaranteed totality for Φ_{e}^{X} and Φ_{i}^{X}, the substitution of Φ_{e}^{X} and Φ_{i}^{X} for Z and V can be done at no additional quantifier costs since quantifier free formulas in Z, V and X now have Δ_{1}^{X} equivalents. Thus if Θ is Σ_{3}^{X,Z,V}, (∃Z, V ≤_{T} X)Θ(Z, V) is equivalent to a Σ_{3}^{X} formula. Similarly, (∀Y, W ≤_{T} X)Ψ(Y, W) is equivalent to a Π_{3}^{X} formula if Ψ is Π_{3}^{X,Z,V}. Thus we are left with analyzing the rest of the relations in the formula.

Any set Z can be effectively viewed as a sequence of its columns ⟨(Z)_{n}⟩ and the associated structure for second order arithmetic is given by specifying the (Z)_{n} = {m| ⟨n, m⟩ ∈ X} as its second order part. The first order part remains the same as in the ambient universe. So each Z is, in this way, recursively interpreted as an ω-model. That V is the satisfaction predicate for the model coded in this way by Z is then a Π_{2}^{0} relation. (See Simpson [2009, V.2] for these definitions.) Once we have the satisfaction set V for Z, to say that a formula is true in Z is then, of course, a Δ_{1}^{0} relation. Thus the whole formula is of the form ∃(∃ & Π_{3} & Σ_{3}) and so Σ_{4}^{0} as required.

Next we prove a reversal of Theorem 3.1 over ACA_{0}. We begin by pointing out that a standard fact on iterations of the Turing jump holds in ACA_{0}.

Lemma 3.6 (ACA_{0}). Let α be a well-ordering. If 0^{η} ≤_{T} X for every η < α, i.e. there is an e such that Φ_{e}^{X} is a total characteristic function for a set satisfying the Π_{2}^{0} formula determining 0^{η}, then 0^{α} exists and indeed 0^{α} ≤_{T} X′′.

Proof. If α is a successor ordinal, the result follows immediately from ACA_{0}. Otherwise, say α is a limit ordinal. The function f taking η < α to the least e satisfying the conditions of the Lemma is total by hypothesis and exists by ACA_{0}. Indeed, f ≤_{T} X′′. The set {⟨n, η⟩ |Φ_{f(e)}^{X}(n) = 1} then also exists, satisfies the definition of 0^{α} and is recursive in X′′.

Theorem 3.7. ACA_{0} + Σ_{3}^{0}-TD ⊢ATR_{0}.

Proof. Let α be a well-ordering. We want to prove that 0^{α} exists. Let W be a low nonrecursive REA operator, i.e. ∀X(X <_{T} W^{X} & X′ ≡_{T} (W^{X})′) and the indices for the required Turing reductions are the same for all X. (The standard construction for such an operator clearly works in ACA_{0}.)

Consider the set P = {X|(∃β < α)(0^{β} ⊕ X ≡_{T} W^{X})}. To see that this set is Σ_{3}^{0} rewrite its defining condition by saying that there is a β < α and an e such that Φ_{e}^{W^{X}} is a total characteristic function for a set that satisfies the Π_{2}^{0} defining condition for 0^{β} and W^{X} ≡_{T} Φ_{e}^{W^{X}} ⊕ X. As (W^{X})′ is uniformly recursive in X′, totality of Φ_{e}^{W^{X}} is Π_{2}^{X} as is every Π_{2}^{W^{X}} predicate (uniformly). Thus the condition defining P is Σ_{3}^{0}. Let P̂ be the Turing closure of P, i.e. P̂ = {X|∃Y (Y ∈ P & X ≡_{T} Y). Similarly, P̂ ∈ Σ_{3}^{0}.

By Σ_{3}^{0}-TD there is a cone of degrees in P̂ or its complement. Let X̂ be a set in the base of such a cone. If X̂ ∈ P̂ let X ≡_{T} X̂ be in P. If not, let X = X̂. By Lemma 3.6, it suffices to prove that 0^{η} ≤_{T} X for every η < α to get that 0^{α} exists. If not, then, by ACA_{0}, there is a least γ < α such that 0^{γ} ≰_{T} X. Note that, again by Lemma 3.6, 0^{γ} exists. We now work toward a contradiction.

If X ∈ P, let β < α be as required in the definition of P and so by the leastness of γ, γ ≤ β (and 0^{γ} ≤_{T} 0^{β}) as 0^{β} ⊕ X ≡_{T} W^{X} >_{T} X. Now we have X <_{T} X ⊕ 0^{γ} ≤_{T} X ⊕ 0^{β} ≡_{T} W^{X} <_{T} (W^{X})′ ≡_{T} X′. By Posner and Robinson [1981, Theorem 3 relativized to X], which can easily be proven in ACA_{0}, there is a Ŷ such that X <_{T} Ŷ and X′ ≡_{T} Ŷ′ ≡_{T} Ŷ ⊕X ⊕0^{γ}. By our choice of W, Ŷ <_{T} W Ŷ <_{T} Ŷ′. On the other hand, our assumptions guarantee that Ŷ ∈ P̂ and so that there is a Y ∈ P with Y ≡_{T} Ŷ. Let δ be the witness for Y being in P, i.e. Y ⊕ 0^{δ} ≡_{T} W^{Y}. If δ < γ, 0^{δ} ≤_{T} X ≤_{T} Y which contradicts Y <_{T} W^{Y}. On the other hand, if δ ≥ γ, 0^{γ} ≤_{T} 0^{δ} and so 0^{δ}⊕Y ≥_{T} Y′ >_{T} W^{Y} for another contradiction.

Finally, suppose X ∉ P. As 0^{γ} ≰_{T} X, we have, again by Posner and Robinson, a Y >_{T} X with Y′ ≡_{T} Y ⊕0^{γ} ≡_{T} Y ⊕0^{γ} ⊕X′. By pseudojump inversion for REA operators (Jockusch and Shore [1984]), which can also easily be proven in ACA_{0}, there is an Z with Z >_{T} Y such that W^{Z} ≡_{T} Y′. Now, as Z ⊕ 0^{γ} ≡_{T} Y ⊕ 0^{γ} ≡_{T} Y′ ≡_{T} W^{Z}, γ is a witness that Z ∈ P ⊆ P̂. This is the desired final contradiction to X̂ being the base of a cone outside of P̂ and so to the existence of γ as required.

4 Σ_{4}^{0}, Δ_{5}^{0} and Σ_{5}^{0} sets

We now prove generalizations to all levels of the arithmetic hierarchy of weaker versions of Theorems 3.1 and 3.3 due to Harrington and Kechris [1975] and Martin [1974], respectively. We prove the first in RCA_{0} and the second in Π_{1}^{1}-CA_{0}.

Lemma 4.1 (essentially Harrington and Kechris). RCA_{0} ⊢ Σ_{n}^{0}-Determinacy → Σ_{n+1}^{0}-TD.

Proof. We follow the proof of Theorem 3.1. Given a Σ_{n+1}^{0} degree invariant set B = {f|∃nQ(n, f)} with Q ∈ Π_{n}^{0}, set A = {⟨n, f⟩ |Q(n, f)}. Clearly, A is Π_{n}^{0} and has elements of exactly the same degrees as B. Now as in Theorem 3.1 let C = {⟨⟨i, f, g⟩ , h⟩ |g ∈ A & ∀n(Φ_{i}^{g}(n) converges in exactly f(n) many steps) & h is II’s play when he follows the strategy given by Φ_{i}^{g} against I playing ⟨i, f, g⟩}. Note that C ∈ Π_{n}^{0} and if ⟨⟨i, f, g⟩ , h⟩ ∈ C then ⟨⟨i, f, g⟩ , h⟩ ≡_{T} g and g ∈ A. By Σ_{n}^{0}-Determinacy, C is determined. The analysis to show that B contains or is disjoint from a cone is now exactly as in Theorem 3.1.

Lemma 4.2 (essentially Martin). Π_{1}^{1}-CA_{0} ⊢ Σ_{n}^{0}-TD ↔ Δ_{n+1}^{0}-TD.

Proof. As Δ_{n+1}^{0}-TD is a Π_{3}^{1} sentence, we can use Δ_{2}^{1}-CA_{0} and its equivalent Σ_{2}^{1}-AC_{0} to prove it as Δ_{2}^{1}-CA is Π_{3}^{1}-conservative over Π_{1}^{1}-CA_{0}. (See Simpson [2009, VII.6.9.1 and IX.4.9].) Let a game be specified by a degree invariant Δ_{n+1}^{0} set A ⊆ 2^{ω}. Apply the Kuratowski analysis (Theorem 1.5 and Remark 1.6) to represent A by a sequence A_{ξ} of degree invariant uniformly Σ_{n}^{0} sets. By Σ_{n}^{0}-TD each of these sets either contains or is disjoint from a cone. By Δ_{2}^{1}-CA_{0} we have the sequence telling us which is the case. We may then take the least γ such that A_{γ} contains a cone (A_{α} = 2^{ω} if no other). Now by Σ_{2}^{1}-AC_{0} we have a sequence s_{η} of bases of cones disjoint from A_{η} for η < γ. The degree of this sequence is then the base of a cone disjoint from all the A_{η} for η < γ. Its join with the base of a cone contained in A_{γ} is then the base of a cone contained in or disjoint from A depending on the parity of γ.

As Π_{3}^{1}-CA_{0} proves Σ_{3}^{0}-Determinacy (Welch [2011]), we now have a bound on what is needed to prove Σ_{4}^{0} and so Δ_{5}^{0} Turing determinacy.

Corollary 4.3. Π_{3}^{1}-CA_{0} ⊢ Σ_{4}^{0}-TD & Δ_{5}^{0}-TD.

4.1 A lower bound for Σ_{5}^{0}-TD

As mentioned in §1, there can be no reversals here. While we have seen that Δ_{5}^{0}-TD is provable already in Π_{3}^{1}-CA_{0} (Corollary 4.3), this is the end of provable Turing determinacy in full second order arithmetic, Z_{2}. Martin ([1974] and [1974a]; see [n.d.]) has shown that Σ_{5}^{0}-TD implies the existence of β_{0}, the least ordinal γ such that L_{γ} is a model of Z_{2}. None of these results have been published so we indicate how to modify arguments of Martin’s and ours from MS [2014] to give a slightly different proof of this result in Π_{1}^{1}-CA_{0}.

Lemma 4.4 (Martin). Π_{1}^{1}-CA_{0} + Σ_{5}^{0}-TD ⊢ β_{0} exists.

Proof. Here we work in Π_{1}^{1}-CA_{0} + Σ_{5}^{0}-TD but assume β_{0} does not exist and consider the same theory as in MS [2014]:

T = KP + “V = L” + ∀γ(L_{γ} is countable inside L_{γ+1})

which implies that β_{0} does not exist.

We first note that as in MS [2014, Lemma 2.1] the set

A = {α |L_{α} ⊨ T and every member of L_{α} is definable in L_{α}}

is unbounded in the ordinals: If not, let δ = sup A, and let α be the least admissible ordinal greater than δ. (Note that Π_{1}^{1}-CA_{0} implies that for every X the least ordinal admissible in X exists.) Let M be the elementary submodel of L_{α} consisting of all its definable elements. Then δ ∈ M. Since β_{0} 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 α ∈ A for the desired contradiction.

We now define a Σ_{5}^{0} set and so a game Q using the same r.e. operator W as in the proof of Theorem 3.7 as well as some notions from MS [2014]. As there, we consider complete extensions of T defined from the play of the game whose term models are ωmodels (albeit in ways more complicated than simply being the plays of the two players). (The term model of such an extension is the structure whose members are (equivalence classes) of formulas φ(x) which, in the appropriate theory, define unique elements. It is an ω-model if its natural numbers are the terms x = 1 + 1 + … + 1.)

The idea of the following definition is that Q is the set of all X such that there is a completion of T with degree W^{X} which is “better” than all completions of degree X. Here, the “better” of two completions is the one whose term model is either well-founded or has a larger well-founded part than the other.

Q = {X | ∃T̂[T̂ ≡_{T} W^{X} & T̂ is a complete extension of T whose term model M_{I} is an ω-model &

∀T̃(T̃ ≡_{T} X & T̃ is a complete extension of T

whose term model M_{II} is an ω-model →

On^{M_{I}}\On^{A_{I}} is either empty or has a least element)]}.

We need some terminology from MS [2014] to explain the notation in this definition. 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} which can be coded by reals that belong to both M_{I} and M_{II}. (Recall that since every set in these models is countable, every such L_{β} can be coded by a real in M_{I}.) Note that by MS [2014, Claim 2.6] A_{I} is Σ_{2}^{0}. We use On^{M_{I}} to denote the set of ordinals in M_{I}.

To see that Q is Σ_{5}^{0}, we rewrite the definition in terms of indices of reductions (from W^{X} and X) as in Theorem 3.7 and use the quantifier counting from MS [2014]. To say that some Z is a complete (consistent) extension of T is Π_{1}^{0} and that its term model is an ω-model is Π_{2}^{0} (MS [2014, Claim 2.4]). The term model of such a theory is obviously recursive in the theory as is its satisfaction relation. Since A_{I} is Σ_{2}^{0}, saying that On^{M_{I}} \ On^{A_{I}} is empty is Π_{3}^{0} and that it has no least element is Π_{4}^{0}. Using these calculations the defintiion of Q has the form ∃[Σ_{3} & Π_{1} & Π_{2} & ∀(Σ_{3} & Π_{1} & Π_{2} → Π_{3} ∨ Π_{4})]. The set Q is thus Σ_{5}^{0}, and so is its closure Q̂ under Turing degree.

By Σ_{5}^{0}-TD, Q̂ contains or is disjoint, from a cone. By Shoenfield’s absoluteness theorem (which is provable in Π_{1}^{1}-CA_{0} (Simpson [2009, VII.4.14]), the base z of the cone can be taken to be in L. Let α be an admissible ordinal such that L_{α} ⊧ T and every element of L_{α} is definable in L_{α} and such that Z ∈ L_{α}. (Such an ordinal exists by the unboundedness result at the beginning of this proof.) Let T h_{α} be the theory of L_{α}. So, in particular Z, Z′ ≤_{T} T h_{α}.

We first claim that T h_{α} ∉ Q̂. Take Y ≡_{T} T h_{α}; we will show that Y ∉ Q. To see this, consider any T̂ ≡_{T} W^{Y} with term model M_{I} as in the definition of Q. Let T̃ = T h_{α} with term model M_{II}= L_{α}. So, we have that M_{I} ≠ L_{α} because their theories have different Turing degrees, and we have that (T h(M_{I}))′ ≡_{T} (T h_{α})′ because W^{Y} is low over Y.

Claim 4.5. If M_{I} ≠ L_{α}, M_{I} ⊧ T and (T h(M_{I}))′ ≡_{T} (T h_{α})′, then M_{I} is ill-founded and its well-founded part is at most L_{α}.

Let L_{β} be the well-founded part of M_{I}. We cannot have β > α because we would then have (T h_{α})′ ≤_{T} (T h(M_{I})). If β = α, then M_{I} must be ill-founded because M_{I} ≠ L_{α}. If β < α, then M_{I} must be ill-founded because otherwise (T h(M_{I}))′ = (T h(L_{β}))′ ≤_{T} T h_{α} contradicting our assumption that (T h(M_{I}))′ ≡_{T} (T h_{α})′. This proves the claim.

It follows that A_{I} = L_{β} and that On^{M_{I}}\On^{A_{I}} is nonempty and has no least element, showing that Y ∉ Q.

Second, we find another degree X ≥_{T} Z which is in Q and hence in Q̂. As Z′ ≤_{T} T h_{α}, there is (by pseudojump inversion) an X >_{T} Z such W^{X} ≡_{T} T h_{α}. Let T̂ = T h_{α} and its term model M_{I}= L_{α}. Since M_{I} is well-founded, whatever A_{I} is, On^{M_{I}}\On^{A_{I}} is always either empty or has a least element.

Thus, we have T h_{α} ∉ Q̂ and X ∈ Q̂ with both above z, the supposed base of a cone inside or disjoint from Q̂, for the final contradiction.

Corollary 4.6 (Martin). Z_{2} does not prove Σ_{5}^{0}-TD. Indeed, Π_{1}^{1}-CA_{0} + Σ_{5}^{0}-TD proves that for every set Y there is a β-model of Z_{2} containing Y and hence much more than the consistency of Z_{2}.

Proof. Recall that L_{β_{0}} ∩ℝ is a model of Z_{2} and indeed a β-model. Thus Π_{1}^{1}-CA_{0} + Σ_{5}^{0}-TD proves the consistency of Z_{2}. As the Lemma relativizes to any Y, Π_{1}^{1}-CA_{0} + Σ_{5}^{0}-TD proves that, for every set Y, there is a β-model of Z_{2} containing Y.

4.2 A lower bound for Σ_{4}^{0}-TD

As mentioned before we cannot find reversals from Σ_{4}^{0}-TD. Relying on several notions and results of MS [2012] and [2014], we do, however, show that we cannot get by with much less than Corollary 4.3. The following proof is somewhat complicated and builds on the proof of Lemma 4.4. Recall that α_{2} is the least 2-admissible ordinal, and equivalently, the least ordinal such that L_{α_{2}} ∩ ℝ ⊧ Δ_{3}^{1}-CA_{0}.

Lemma 4.7. Π_{1}^{1}-CA_{0} + Σ_{4}^{0}-TD ⊢ α_{2} exists.

Proof. We assume, for the sake of a contradiction, that α_{2} does not exist. We extend the theory T of MS [2014, §2] by setting

T = KP + “V = L” + ∀γ(L_{γ} is countable inside L_{γ+1}) + no ordinal is Σ_{2}-admissible.

By the same proof as in the second paragraph of the proof of Lemma 2.1 of MS [2014] (or at the beginning of the proof of Lemma 4.4 above), if α_{2} does not exist then

A = {α |L_{α} ⊨ T and every member of L_{α} is definable in L_{α}}

is unbounded in the ordinals.

We now define a set P which plays the role of Q in the previous proof. Again, P is the set of all X such that there is a model of T of degree W^{X} which is better than any of degree X, but this time we need P to be Σ_{4}^{0}.

P = {X | ∃T̂[T̂ ≡_{T} W^{X} & T̂ is a complete extension of T

whose term model M_{I} is an ω-model &

∀T̃(T̃ ≡_{T} X & T̃ is a complete extension of T

whose term model M_{II} is an ω-model →

conditions R_{I}new or R_{I}3 hold)]}.

The conditions R_{I}new and R_{I}3 are defined in Section 2 of MS [2014]. Instead of repeating the whole background developed there, we just use a few lemmas from that section to prove below the few properties we need. Before doing that, let us notice that since every element of M_{I} and M_{II} is definable by a real (because T says that every set is countable), we can compare their elements by looking at the reals coding them. Thus, when we say M_{I} ⊆ M_{II}, we mean that every element of M_{I} is coded by a real in M_{I} which also belongs to M_{II}. (As both models are standard, we can confidently talk about reals, i.e. subsets of ω, being in one or both of them.) The main properties about R_{I}new, R_{I}3, and R_{II}3 are the following:

1. If one of M_{I} and M_{II} is well-founded, then R_{I}new holds if and only if M_{I} is isomorphic to the well-founded part of M_{II}.

2. If M_{I} and M_{II} are incomparable, then either R_{I}3 or R_{II}3 holds.

3. If R_{I}3 holds, then M_{II} is ill-founded, and if If R_{II}3 holds then M_{I} is ill-founded.

4. The conditions R_{I}new and R_{I}3 are Π_{3}^{0}.

The first property is proved in Lemma 2.9 of MS [2014] with the fact that the definition of R_{I}new implies that M_{I} ⊆ M_{II}. For the second, we have, by MS [2014, Lemma 2.17], that if neither of R_{I}3 and R_{II}3 hold, then there are ordinals β_{1} and β_{2} such that ⋆_{1}(β_{1}, β_{2}) holds, which by MS [2014, Lemma 2.18(b)] implies that α is 2-admissible, where α is such that A = L_{α}. But since α_{2} doesn’t exists, there are no 2-admissible ordinals, and hence this is a contradiction. The third property follows from the definition of R_{I}3, MS [2014, Definition 2.16] which asserts that a subset of the ordinals in M_{II} has no least element. Finally, the fourth property follows from MS [2014, Claim 2.7] for R_{I}new and from MS [2014, Definition 2.16 and Claim 2.11] for R_{I}3.

The rest of the proof is similar to that of the previous lemma. To see that P is Σ_{4}^{0}, we again rewrite the definition in terms of indices of reductions (from W^{X} and X). The conditions R_{I}new and R_{I}3 are Π_{3}^{0}. As remarked above, Π_{2}^{W^{X}} relations are uniformly Π_{2}^{X} and, of course, the relation Z ≤_{T} Y is Σ_{3}^{0}. It is then routine to calculate that P is Σ_{4}^{0}.

The closure P̂ of P under ≡_{T} is then also a Σ_{4}^{0} set. By Σ_{4}^{0}-TD, P̂ contains or is disjoint, from a cone. By Shoenfield’s absoluteness theorem, the base z of the cone can be taken to be in L. Let α be an admissible ordinal such that L_{α} ⊧ T and every element of L_{α} is definable in L_{α} and such that Z ∈ L_{α}. (Such an ordinal exists by the unboundedness result at the beginning of this proof.) Let T h_{α} be the theory of L_{α}. So, in particular Z, Z′ ≤_{T} T h_{α}.

We first claim that T h_{α} ∉ P̂. Take Y ≡_{T} T h_{α}; we will show that Y ∉ P. To see this, consider any T̂ ≡_{T} W^{Y} with term model M_{I} as in the definition of P. Let T̃ = T h_{α} with term model M_{II}= L_{α}. So, we have that M_{I} ≠ L_{α} because their theories have different Turing degrees. Thus, M_{I} cannot be the well-founded part of M_{II}, and hence R_{I}new cannot hold. Since M_{II} is well-founded, R_{I}3 cannot hold either. So Y ∉ P.

Second, we find a degree X ≥_{T} Z which is in P, and hence in P̂. As Z′ ≤_{T} T h_{α}, there is (by pseudojump inversion) an X >_{T} Z such W^{X} ≡_{T} T h_{α}. We claim that X ∈ P.

Let T̂ = T h_{α} with term model M_{I}= L_{α}. Consider any T̃ ≡_{T} X with term model M_{II} as in the definition of P. So, we have that M_{II} ≠ L_{α} because their theories have different Turing degrees, and we have that (T h(M_{II}))′ ≡_{T} (T h_{α})′ because W^{X} is low over X. By Claim 4.5, M_{II} is ill-founded and its well-founded part is at most L_{α}. If A_{II} = L_{α}, then M_{I} is isomorphic to the well-founded part of M_{II}, and hence R_{I}new holds. Otherwise, M_{I} and M_{II} are incomparable. Since R_{II}3 does not hold (because M_{II} is well-founded) R_{I}3 must hold, proving that X ∈ P.

As T h_{α}, X ≥_{T} Z, we see that z is not the base of a cone for P̂ for the final contradiction and so α_{2} exists as required.

Corollary 4.8. Δ_{3}^{1}-CA_{0} does not prove Σ_{4}^{0}-TD. Indeed, Π_{1}^{1}-CA_{0} + Σ_{4}^{0}-TD proves that for every set Z there is a β-model of Δ_{3}^{1}-CA_{0} containing Z and hence much more than the consistency of Δ_{3}^{1}-CA_{0}.

Proof. By Simpson [2009, VII.5.17 and the notes thereafter], L_{α_{2}} ∩ ℝ is a model of Δ_{3}^{1}- CA_{0} and indeed a β-model. Thus Π_{1}^{1}-CA_{0} + Σ_{4}^{0}-TD proves the consistency of Δ_{3}^{1}-CA_{0}. As the Lemma relativizes to any Z, Π_{1}^{1}-CA_{0} + Σ_{4}^{0}-TD proves that, for every set Z, there is a β-model of Δ_{3}^{1}-CA_{0} containing Z.

5 Questions

There are several natural questions left open here. We first point to two for which we expect that answers should require some new interesting models of fragments of Z_{2}.

Question 5.1. Does WKL_{0} or some other known principle strictly between RCA_{0} and ACA_{0} prove Δ_{3}^{0}-TD?

Question 5.2. Does Δ_{3}^{0}-TD (or some stronger version) prove ACA_{0} over WKL_{0}?

Question 5.3. Clarify the status of Δ_{4}^{0}-TD over ACA_{0}. In particular does ATR_{0} + Σ_{1}^{1}-TI_{0} (or equivalently Σ_{1}^{1}-IND) or ATR_{0} with full induction prove Δ_{4}^{0}-TD? If not, does ACA_{0} + Δ_{4}^{0}-TD prove Π_{1}^{1}-TI_{0}?

Question 5.4. Does Δ_{4}^{0}-TD (or some stronger version) prove Π_{1}^{1}-CA_{0} over ATR_{0}?

6 Bibliography

Epstein, R. L., Initial Segments of the Degree below 0′, Memoirs of the American Mathematical Society 30, Providence , R.I.

Friedman, H. [1967], Subsystems of Set Theory and Analysis, Ph.D. Thesis, M.I.T. Friedman, H. [1971], Higher set theory and mathematical practice, Annals of Mathe-

matical Logic 2, 325-357.

Harrington L., Analytic determinacy and 0# [1978], Journal of Symbolic Logic 43 685–693.

Harrington, L. A. and Kechris, A. S. [1975], A basis result for Σ_{3}^{0} sets of reals with an application to minimal covers, Proceedings of the American Mathematical Society 53, 445–448.

Jockusch, C. G. Jr. and Shore, R. A. [1984], Pseudo-jump operators I: the r.e. case, Transactions of the American Mathematical Society 275, 599-61.

Koellner, P. and Woodin, W. H. [2010], Large Cardinals from Determinacy, Handbook of Set Theory Vol. 3, M. Foreman and A. Kanamori eds., Springer, Dordrecht 1951-2119.

Lerman, M. [1983], Degrees of Unsoivability, Springer-Verlag, Berlin. Martin, D. A. [1970], Measurable cardinals and analytic games, Fundamenta Mathe-

matica 66 287–291.

Martin, D. A. [1974], Two Theorems on Turing Determinacy, circulated handwritten notes dated May, 1974.

Martin, D. A. [1974a], Σ_{4}^{0}-determinacy, circulated handwritten notes dated March 20, 1974.

Martin, D. A. [1974b], A direct proof of the difference hierarchy, circulated handwritten notes dated June 4, 1974.

Martin, D. A. [n.d.] Determinacy, circulated drafts, about 578 pp. MedSalem, M. O. and Tanaka, K. [2007], Δ_{3}^{0}-Determinacy, Comprehension and In-

duction, Journal of Symbolic Logic 72, 452–462.

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

Montalbán, A. and Shore, R. A. [2014], The Limits of Determinacy in Second Order Arithmetic: Consistency and Complexity Strength, Israel Journal of Mathematics, to appear.

Posner, D. B. and Robinson, R. W., Degrees joining to 0′ [1981], Journal of Symbolic Logic 46, 714–722.

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

Steel, J. R. [1976], Determinateness and Subsystems of Analysis, Ph.D. Thesis, University of California, Berkeley.

Tanaka, K. [1990], Weak axioms of determinacy and subsystems of analysis I: Δ_{2}^{0} games), Zeitschr. f. math. Logik und Grundlagen d. Math. 36, 481-491.

Tanaka, K. [1991], Weak axioms of determinacy and subsystems of analysis II (Σ_{2}^{0} games), Annals of Pure and Applied Logic 52, 181-193.

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