Lecture notes on the Turing degrees, AII Graduate Summer School in Logic Singapore, 28 June - 23 July 2010

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

January 4, 2012

1Partially supported by NSF Grant DMS-0852811 and as a Visiting Professor in the Department of Mathematics and the Institute for Mathematical Sciences at the National University of Singapore with partial funding from the John Templeton Foundation. These lecture notes are based on a short course given at the Institute as part of the Computational Prospects of Infinity II: AII Graduate Summer School (15 June - 13 July 2011). Earlier versions were based on our courses at Cornell and especially one in the fall of 2007. That semester all the students took turns taking notes and one, Mia Minnes, took notes for essentially all the lectures. These notes formed the basis for a first draft for much of the material presented here and more. We thank all our students and especially those from that semester.

ii

Contents

1 Introduction 1 1.1 Some background material . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Embeddings into the Turing Degrees 7 2.1 Embedding Partial Orders in D . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Extensions of embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Forcing in Arithmetic and Recursion Theory 19 3.1 Notions of Forcing and Genericity . . . . . . . . . . . . . . . . . . . . . . 19 3.2 The Forcing Language and Deciding Classes of Sentences . . . . . . . . . 23 3.3 Embedding Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 Effective Successor Structures . . . . . . . . . . . . . . . . . . . . . . . . 35

4 The Theories of D and D(≤ 0′) 39 4.1 Interpreting Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Slaman-Woodin Forcing and T h(D) . . . . . . . . . . . . . . . . . . . . . 41 4.3 T h(D ≤ 0′) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Domination Properties 53 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2 R.E. and Δ_{2}^{0} degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3 High and \overline{GL}_{2} degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.4 Definability and Biinterpretability in D(≤ 0′) . . . . . . . . . . . . . . . 67

6 Bibliography 75 iv CONTENTS

Chapter 1

Introduction

Our goal in these lectures is to explore the fundamental notion of effective computability (recursiveness) and, more specifically that of relative complexity of computation (relative recursiveness). The formal definitions that best captures the intuitions, first, that some function (or set) is computable and, second, that one set (or function) is easier to compute than another are those of Turing. We work with the natural numbers ℕ and subsets of and functions on them. Turing machines supply a formalism for describing what are generally agreed to be all the intuitively computable functions and the basic notion of general computability of one set (or function) from another. While there were many other formalisms introduced in an attempt to capture these notions we now know that they are all equivalent and we can simply think of the programs in any general purpose computer language as supplying our basic list of such functions. To describe the notion of computing one set from another we equip our (Turing) machines with an “oracle”. For A, B ⊆ ℕ, we say that A is recursive in (or (Turing) computable from ) B, A ≤_{T} B, if, when we want to decide if n ∈ A, we allow our basic machines at any point in their computation to generate an m ∈ ℕ, ask if m ∈ B and receive the correct answer from the oracle for B. The machine may then continue on with its computation. We say that A and B are (Turing) equivalent, A ≡_{T} B, if A ≤_{T} B and B ≤_{T} A.

This notion of relative recursiveness (computability) defines a symmetric, transitive relation on the subsets of (or functions on) ℕ. As usual, we move to the equivalence classes of this relation which are called the (Turing) degrees. The degree of a set A, deg(A), is then {B|B ≡_{T} A}, often denoted by a. These degrees then form a partial order under the induced ordering a ≤ b. (Note that we can pass between sets A and functions f by using graphs of functions ({⟨x, y⟩ |f(x) = y}) in one direction and characteristic functions of sets (C_{A}(n) = 1 if n ∈ A and C_{A}(n) = 0 if n ∉ A) in the other. We generally abuse notation and confuse sets and functions in this way. It is a basic fact (or an exercise to check) that these procedures preserve Turing degree.) We denote the structure of these degrees and partial ordering by D. It is our primary object of study in these lectures.

It is easy to see that this partial order has a least element 0 the degree of the empty set 0 (or equivalently of any recursive set, i.e. one computable by a Turing machine). It also has join operator a ∨ b = deg(A ⊕ B) where A⊕B = {2n|n ∈ A}∪{{2n+1|n ∈ B}. (It is an exercise to see that this defines the least upper bound of a and b in D.) A deeper fact about the ordering is that it has the countable predecessor property, i.e. {b|b < a} is at most countable for any degree a. The point here is that there is computable listing of the Turing machines (which have “space” for an oracle) and so of the functions they compute Φ_{e} (Φ_{e}^{A} when relative to the oracle A). Thus {B|B ≤_{T} A} is countable for every set A and so, a fortiori, {b|b < a} is at most countable. One of our major goals is to see what more we can say about this ordering in first order or algebraic terms. Is it a linear ordering? It is an uppersemilattice (usl) but is it a lattice? What orderings can be embedded into it, etc.?

There are also important and remarkable connections between relative computability as expressed in structural properties of D and approximations to, and growth rates of, functions on the one hand and definability in arithmetic on the other. This story begins with the halting problem and its generalization, the (Turing) jump to all sets and degrees. The halting problem is traditionally defined as 0′ = {e|Φ_{e}(e) converges} with degree 0′. Its generalization is given by A′ = {e|Φ_{e}^{A}(e) converges} with degree a′. (Again it is a basic fact (or an exercise to see) that this operation is well defined on degrees. The fact that it is strictly increasing is essentially the classical result on the undecidability of the halting problem but relative to arbitrary oracles.) In terms of definability in arithmetic, A′ is essentially the same as the set of existential formulas true in ℕ. (It is certainly of the same degree as this set but even more closely related to it.) For A′, the corresponding set is that of the existential formulas in arithmetic with an added unary relation for A. Iterations of this operator move up the levels of quantifier complexity. (See Theorem 1.1.10.) As for approximations, the sets computable from A′ are precisely those with approximations recursive in A. (See Theorem 1.1.11.) The connections to rates of growth are a bit more subtle but quite important. (See Chapter 5.) Thus another important concern in these lectures will the jump operator and its relation to the order structure on D. In particular, in parallel with our study of D, we will extensively study the structure of the degrees recursive in the halting problem, D(≤ 0′).

Finally, in addition to investigating the algebraic or first order properties of these structures we will analyze their second order or metamathematical properties. For example, we will characterize the complexity (in terms of Turing degree and more) of their theories, T h(D) and T h(D(≤ 0′), the sets of sentences true in these structures as well as as well as study the sets and relations definable in them.

We give a brief list of some of the notations, conventions and basic results that are used later in §1.1. We begin our main task of analyzing D and D(≤ 0′) in Chapter 2. There we introduce the idea of dividing up a complex property into simpler ones (called requirements) and the method of approximating the sets we want to build having the desired property by finite initial segments. In a construction by such approximations we want to satisfy the requirements in terms of these approximations in such way that we guarantee the sets constructed have the desired properties. These ideas all come from the seminal paper on degree theory by Kleene and Post [1954]. In hindsight, these constructions can be seen as simple examples of Cohen’s later method of forcing but implemented in the setting of arithmetic instead of set theory. In the rest of these lectures, we formalize and develop a more general approach to forcing in recursion theory. We then apply it to prove most of our results about the structures D and D(≤ 0′), both mathematical and metamathematical.

We do not attempt to give a historical account of the material presented in these lectures. Indeed, most of the proofs are not the original ones. However, we do give, in Notes at the end of most sections, basic attributions and references for most of the results to provide some historical perspective.

1.1 Some background material

We hope that almost all of the material in this section is already known to the readers. If so, it can be skipped, If not, it can be taken on faith, worked out as exercises or found in the first couple of chapters of any standard text.

We begin with a few facts about Turing computations and how the basic programs Φ_{e} work with oracles.

Definition 1.1.1 There is master (universal) recursive function,

φ(σ, e, x, s) = y

where the variables are σ a finite binary string (initial segment of a characteristic function or set), e a number (index), x a number (input), s a number (steps of the computation). The expression means that the Turing machine with index e and oracle restricted to σ given input x and run for s many steps converges and outputs y.

Conventions: If the computation asks question outside the domain of σ or does not converge in s steps we announce that the computation is divergent.

Properties:

(i) Use: If σ ⊆ τ and φ(σ, e, x, s) ↓= y then φ(τ, e, x, s) = y

(ii) Permanence: If s < t and φ(σ, e, x, s) ↓= y then φ(σ, e, x, t) ↓= y

(iv) The domain of φ is computable, in other words there is a procedure to decide whether φ converges on any given tuple (σ, e, x, s). This procedure simply runs the machine with index e on input x and oracle σ. If the machine arrives at an output by step s, then answer yes (and otherwise, answer no).

Definition 1.1.2 (Computations from Oracles) Φ_{e}^{A}(x) = y means that ∃σ ⊆ A∃s [φ(σ, e, x, s) ↓= y]. So Φ_{e}^{A}(x) is a partial function (recursive in A). We define the use of a computation Φ_{e}^{A}(x) = y as the least n such that φ(A ↾ n + 1, e, x, s) = y. We also say that σ = A ↾ n is the axiom (about the oracle A) that gives this computation. Note that if A is changed at or below the use then this axiom no longer applies and we no longer have the same computation giving the output y.

Definition 1.1.3 We adopt two additional conventions when the oracle is a finite string σ. First, we run the Turing machine for only |σ|, the length of σ, many steps so we write Φ_{e}^{σ}(x) for Φ_{e,|σ|}^{σ}(x). Second, we require that for Φ_{e}^{σ}(x) to converge we must have x < |σ|.(Roughly speaking we must read the input before giving an output.)

Definition 1.1.4 (Turing Reducibility) A ≤_{T} B means ∃e(Φ_{e}^{B} = A). A ≡_{T} B means that A ≤_{T} B and B ≤_{T} A. The equivalence classes under this relation are the (Turing) degrees a and b (of A and B, respectively). They are ordered by the induced partial order, a ≤ b.

Intuitively this means that there is a Turing machine with oracle B that computes A.

Exercise 1.1.5 Turing reducibility is symmetric and transitive.

Definition 1.1.6 A set is recursively enumerable (r.e.) in A if it is the domain of a partial function recursive in A, i.e. of some Φ_{e}^{A}.

Exercise 1.1.7 For any sets A and B, A ≤_{T} B if and only if both A and Ā are r.e. in B.

The archetypic r.e. in A set is its jump A′.

Definition 1.1.8 (Jump Operator) The jump of A, A′, is {e|Φ_{e}^{A}(e) ↓}. The iterations of this operator are defined by A^{(n+1)} = (A^{(n)})′. (We use ↓ to stand for “converges”.)

Exercise 1.1.9 A′ is r.e. in A. Moreover, the jump operator is order preserving and hence well defined on the degrees, i.e., if A ≤_{T} B then A′ ≤_{T} B′. In addition, A <_{T} A′ for every set A.

We assume some standard language for first order arithmetic containing for example the functions + and ×, the relation ≤ and the constants 0 and 1 (or also an additional unary predicate for a set A). The standard syntactic hierarchy of Σ_{n} (or Σ_{n}^{A}) and Π_{n} (Π_{n}^{B}) formulas in prenex normal form are defined by counting the number of alternations or quantifiers as usual. Typically one includes bounded quantification ∃x < s and ∀x < s in the matrix of these formulas. One can instead add the master function φ of Definition 1.1.1 into the language. There are normal forms for these formulas that show that, for example, one can assume that there is only one quantifier of each sort as the types of the quantifiers at the beginning of the formula alternate. The primary connection between the classes of sets defined by such formulas which are also denoted by Σ_{n}^{A} and Π_{n}^{B} are given by the hierarchy theorem. (We say that a set is Δ_{n}^{A} if it is both Σ_{n}^{A} and Π_{n}^{A}.)

Theorem 1.1.10 (Post’s Hierarchy Theorem) 1. B ∈ Σ_{n+1}^{A} ⇔ B is RE in some Π_{n}^{A} set.

2. A^{(n)} is Σ_{n}^{A} m-complete for n > 0,i.e. for any B ∈ Σ_{n}^{A} there is a recursive function f such that ∀n(n ∈ B ⇔ f(n) ∈ A^{(n)}). This is even stronger than the assertion that B ≤_{T} A.

3. B ∈ Σ_{n+1}^{A} ⇔ B is r.e. in A^{(n)}.

4. B ∈ Δ_{n+1}^{A} ⇔ B ≤_{T} A^{(n)}.

There is an important connection between the Δ_{2}^{B} sets (which are those recursive in B′) by clause 4 of this theorem and those with approximations computable in B:

Theorem 1.1.11 (Shoenfield Limit Lemma) A ≤_{T} B′ ⇔ ∃f ≤_{T} B such that ∀x(A(x) = lim_{s→∞} f(x, s)). Note that asserting that lim_{s→∞} f(x, s) exists means that f(x, s) is eventually constant for each x.

The jump and its iterations are important markers along the highway of complexity for sets. Thus we will often take some construction and ask where along this road the sets or degrees constructed lie or can be made to lie, such as below 0′ or 0′′ or some other 0^{(n)}. Another measure of complexity is where the jump(s) of the set constructed lie. For example, we might ask if A′ ≡_{T} 0′ (the smallest possible value) or if A′′ ≡_{T} 0′′ (the largest possible value for any r.e. set or one recursive in 0′). These ideas are captured in the definition of the jump hierarchy and the generalized jump hierarchy.

Definition 1.1.12 For n ≥ 1, X ∈ GL_{n} if and only if X^{(n)} ≡_{T} (X ∨ 0′)^{(n−1)} (by convention, Z^{(0)} = Z for every Z); X ∈ GH_{n} if and only if X^{(n)} ≡_{T} (X ∨ 0′)^{(n)}. If X ≤_{T} 0′ then these conditions simplify and we say that X ∈ L_{n} if X^{(n)} ≡_{T} 0^{(n)} and X ∈ H_{n} if X^{(n)} ≡_{T} 0^{(n+1)}. We indicate the corresponding degree classes by boldfacing: GL_{n}, GH_{n}, L_{n} and H_{n}. The complementary classes are indicted by \overline{GL}_{n}, \overline{GH}_{n}, L̄_{n} and H̄_{n} where the last two refer to the complement within the degrees below 0′. These notations are read as (generalized) low_{n} or (generalized) high_{n}.

Notes: For basic background including the material of this section we recommend the classics texts on recursion theory Rogers [1987] and Soare [1987] or the more encyclopedic Odifreddi [1989] and [1999].

6 CHAPTER 1. INTRODUCTION

Embeddings into the Turing Degrees

2.1 Embedding Partial Orders in D

Based on only the background information on the Turing degrees mentioned in the Introduction, we know only that D is an uppersemilattice of size 2^{ℵ_{0}} (Exercise) with least element and the countable predecessor property. It also has an operator, the Turing jump, which is strictly increasing and closely related to the quantifier complexity of the definitions of sets and functions in arithmetic. The only specific degrees we know are 0 and the iterations of the jump beginning with 0′. Are there others? Is D a linear order? If not, how “wide” is it? How far away from being a linear order? Where do these other degrees lie with respect to the ones we already know? We begin answering these questions by considering what is perhaps the simplest question and showing that D is not a linear order.

Notation 2.1.1 We write A|_{T} B, A is Turing incomparable with B, for A ≰_{T} B & B ≰_{T} A.

Theorem 2.1.2 (Kleene and Post) ∃A_{0}, A_{1}(A_{0}|_{T} A_{1}).

How can we approach such a result. We recast the desired properties of the sets we want to construct into a list of simpler ones R_{e} called requirements. Then we choose an approximation procedure so that we can build a sequence of approximations α_{i,s} “converging” to A_{i} such that the information in an an approximation ⟨α_{i,s}⟩ can be sufficient to guarantee that we satisfy one of the requirements in the sense that R_{e} is true of any pair A_{i} ⊃ α_{i,s}. Proof. We build A_{0}, A_{1}. The requirements necessary to guarantee the theorem are:

R_{⟨e,j⟩} : Φ_{e}^{A_{j}} ≠ A_{1−j}

for all e ∈ ℕ, j ∈ {0, 1}. It is clear that if the sets we construct satisfy each requirement then the sets satisfy the demands of the theorem. Our approximations in this case are finite binary strings (so initial segments if characteristic functions) α_{j,s} such that A_{j} = ∪_{s}α_{j,s}.

The construction cannot be recursive because A_{0}, A_{1} can’t both be recursive and incomparable. But, the approximations won’t change once defined at some x; in other words, α_{j,s} ⊆ α_{j,s+1} so we get better and better approximations.

What actions satisfy a requirement? Given α_{j,s} (j = 0, 1), we want α_{j,s+1} ⊇ α_{j,s} to guarantee that we satisfy R_{⟨e,j⟩}. For definiteness, let j = 0. We want α_{0} ⊇ α_{0,s}, α_{1} ⊇ α_{1,s} such that for any A_{0} ⊇ α_{0}, A_{1} ⊇ α_{1}, Φ_{e}^{A_{0}} ≠ A_{1}. In other words,

∃x¬(Φ_{e}^{A_{0}}(x) = A_{1}(x))

We can choose x as the first place x at which α_{1,s} is not defined (formally x = dom(α_{1,s}) = |α_{1,s}|). Ask if ∃α_{0} ⊇ α_{0,s}(Φ_{e}^{α_{0}}(x) ↓ ). If so, we can choose the “least” such α_{0}. To which ordering does the “least” refer here? We make a master list of all convergent computations φ(σ, e, x, t), i.e. {⟨σ, e, x, t⟩ : φ(σ, e, x, t) ↓} where we write φ(σ, e, x, t) or Φ_{e,t}^{σ}(x) to mean the result of running the eth Turing machine on input x for t many steps with oracle questions answered by the finite string σ (which must be long enough to answer them) and then least refers to the least quadruple ⟨σ, e, x, s⟩ in this list. From now on we, usually without comment, use “least” in this sense of being the first object enumerated in some given search.

Then, we set α_{0,s+1} = α_{0} and α_{1,s+1} = α_{1,s}^{∧}(1 − Φ_{e}^{α_{0}}(x)). By the standard properties of Turing machines, if A_{0} ⊇ α_{0} = α_{0,s+1} and A_{1} ⊇ α_{1,s+1} then

Φ_{e}^{A_{0}}(x) = Φ_{e}^{α_{0}}(x) ≠ 1 − Φ_{e}^{α_{0}}(x) = A_{1}(x).

What if no such α_{0} exists? We do nothing, i.e. we set α_{i,s+1} = α_{i,s}. This finishes the construction.

A general principle of our constructions is do the best you can, and if you can’t do anything useful, then do nothing and hope for the best (i.e. that what you can is enough). In this case, it is enough because if A_{0} ⊇ α_{0,s} then Φ_{e}^{A_{0}}(x) ↑. (If Φ_{e}^{A}(x) ↓ for any A ⊇ α_{0,s} then the computation only requires finitely much information about A and so Φ_{e}^{α}(x) ↓ for some finite initial segment α of A. As A_{0} ⊇ α_{0,s} we can certainly take this α to extend α_{0,s} as well if Φ_{e}^{A_{0}}(x) ↓.) So Φ_{e}^{A_{0}} is not total and can certainly then not be the characteristic function of a set, i.e. Φ_{e}^{A_{0}} ≠ A_{1}.)

Thus we have actually verified that the construction satisfies all the requirements and so provides the desired sets: Consider R_{⟨e,j⟩}. Look at the stage s at which we acted for this requirement. Either we did something (defined α_{i,s+1} ≠ α_{i,s}) which guaranteed the requirement by guaranteeing that Φ_{e}^{A_{j}}(x) ↓≠ A_{1−j}(x) at some x; or we did nothing by setting α_{i,s+1} = α_{i,s} but in that case we also guaranteed that the requirement is satisfied by making Φ_{e}^{A_{j}}(x) ↑ for some x.

2.1. EMBEDDING PARTIAL ORDERS IN D 9

Question 2.1.3 How do we know that this construction keeps going, i.e. that there is no point after which we always “do nothing”. If that were the case, then both A_{0}, A_{1} would be finite, so certainly not Turing incomparable. Why doesn’t this happen? Is it necessary to include another requirement to guarantee this: Q_{e} : α_{j,s} ≥ e? (These would be easy to satisfy.) Whenever we do act on a requirement, we make one of the α’s longer and since infinitely often there is an index e which doesn’t look at its oracle and outputs 0, at the stage at which we deal with the requirement with index e, we automatically extend the approximation. Hence, both strings are extended infinitely often. This is a common phenomenon. Constructions often do more than one expects.

Question 2.1.4 How complicated are A_{0} and A_{1}? We want a bound on their complexity such as A_{0,}A_{1} ≤_{T} 0^{(n)} (this would also give definability properties). To determine what n is, let’s look back at the construction. By recursion, we have α_{j,s}. To calculate α_{j,s+1}, we asked one question:

∃α_{0} ⊇ α_{0,s}(Φ_{e}^{α_{0}}(x) ↓ )?

This is a Σ_{1} question so 0′ can answer it and tell us which case to implement. The “do nothing” case is easy to do. For the other case, we have to enumerate the master list {⟨σ, e, x, t⟩ : φ(σ, e, x, t) ↓}, which we can do effectively. So, once 0′ told us which case we’re in, everything else is recursive. Hence, A_{0}, A_{1} ≤ 0′.

Question 2.1.5 Where do A_{0}, A_{1} lie in the jump hierarchy? Because of the symmetry of the construction, even though A_{0} ≢_{T} A_{1}, they should have some of the same properties. Are they low (or can we add something to the construction to make sure that they’re low)?

Recall: A_{0} is low iff A′_{0} ≤_{T} 0′ iff {e : Φ_{e}^{A_{0}}(e) ↓} ≤_{T} 0′.

We can add a new requirement:

N_{e,j} : make Φ_{e}^{A_{j}}(e) ↓ if we can.

Suppose that at stage s we are acting on N_{e,0}. We have α_{j,s} and ask if

∃α_{0} ⊇ α_{0,s}(Φ_{e}^{α_{0}}(e) ↓ )?

If the answer is yes, let α_{0,s+1} be the least such α_{0} and let α_{1,s+1} = α_{1,s}. On the other hand, if the answer is no, then do nothing and put α_{j,s+1} = α_{j,s} This is called deciding or forcing the jump. The terminology will be better understood after §3.2.

Claim 1: The construction is still recursive in 0′: Our actions for requirements P_{e,j} are the same as before. For N_{e,j}, 0′ can decide if ∃α_{0} ⊇ α_{0,s}(Φ_{e}^{α_{0}}(e) ↓ ).

Claim 2: We can compute A′_{0} from 0′. Since the whole construction is recursive in 0′, 0′ can go along the construction until it gets to the stage s at which we act for N_{e,0}. Then, it sees what the construction does and can compute A′_{0} from this action.

Claim 3: We can relativize the construction to any degree x to get incomparables A_{j}^{X} between X, X′ such that (A_{j}^{X})′ = X′. By relativizing, we mean that at each part of the computation where we have oracle α_{j}, we instead have the oracle X ⊕ α_{j}. At the end, we build X ⊕ A_{j}. The verification of the construction goes through as before.

Claim 4: It is easy to extend the construction to more than two incomparables. We can change the requirements to

P_{e,i,j} : Φ_{e}^{A_{j}} ≠ A_{i} i ≠ j.

Thus, we can produce countably many low pairwise incomparables between 0 and 0′, indeed all with jumps uniformly recursive in 0′.

Exercise 2.1.6 Show that the sets A_{i} of the original construction (for Theorem 2.1.2) are already low.

Notation 2.1.7 Given any sequence ⟨A_{i}|i ∈ I⟩ of sets we let ⊕{A_{i}|i ∈ I} = {⟨i, x⟩ |i ∈ I & x ∈ A_{i}}. Conversely, given any set A we let A^{[i]} denote the set {⟨i, x⟩ | ⟨i, x⟩ ∈ A}. We let A^{[î]} = ⊕{A_{j}|i ≠ j} = {⟨j, x⟩ |i ≠ j & x ∈ A_{j}}

In general, given a countable partial order P, can we embed it in D or in D(≤ 0′) or in the low degrees? Let P = {p_{0}, p_{1}, …}, ≤_{P}. Without loss of generality, we can assume that p_{0} is the least element of P. (If P doesn’t have a least element, add one in and then any embedding of this enlarged partial order gives an embedding of the original P.) We build A_{i} such that A_{i} ≤_{T} A_{j} if and only if p_{i} ≤_{P} p_{j}. To do so, we build C_{i} and let A_{j} = ⊕{C_{i} : p_{i} ≤_{P} p_{j}}. Does p_{i} ≤_{P} p_{j} imply that A_{i} ≤_{T} A_{j}? By transitivity,

⟨k, x⟩ ∈ A_{i} ⇔ x ∈ C_{k} ∧ p_{k} ≤_{P} p_{i}  ⇒  ⟨k, x⟩ ∈ A_{j} ⇔ x ∈ C_{k} ∧ p_{k} ≤_{P} p_{j}

so if ≤_{P} is recursive, i ≤_{P} j implies that A_{i} ≤_{T} A_{j}. We can use this fact to embed recursive partial orders in the low degrees by using the construction above to guarantee incomparability when needed and the recursiveness of P with this simple argument to guarantee comparability when needed. If a partial order is not recursive, it is at least recursive in some oracle so relativizing the proof for recursive partial orders gives an embedding into D. Perhaps this is the best we can do – it may not intuitively obvious that D(≤ 0′) is a universal countable partial order. We begin by constructing a recursive universal partial order. The construction is an example of the method of finite approximations being used to build sets with properties not necessarily expressed in terms of Turing degrees. We then embed it into D(≤0′).

Theorem 2.1.8 There is a recursive universal partial order P, i.e. one such that every countable partial order Q can be embedded in P Proof. We build P by finite approximations, P = ∪P_{s}. At stage s we have a finite partial order P_{s} and extend it to P_{s+1} such that for every subset of P_{s}, every one element partial order extension is realized in P_{s+1}. That is, for every subset M ⊂ P_{s}, and a particular partial order relation on M ∪ {z} (z, a new element), add z to P and define its relation to the elements in P_{s} \ M as dictated by the axioms of partial orders. Thus we can prove that given any partial order and any finite subset and any extension by one element, there is a new partial order that realizes that extension. We can apply this finitely many times to take care of each finite subset and each possible one-element partial order extension. This construction is recursive so we have a recursive partial order.

To see that P is universal, consider any countable partial order Q. We use a forth argument to embed Q into P. That is, if Q = {q_{0}, q_{1}, …} we define the embedding f by recursion. Start with f(q_{0}) = p_{0} and then, given f(q_{m}) for m < n, define f(q_{n}) to be an element of P realizing (up to this finite isomorphism) the same extension of {f(q_{m})|m < n} that q_{n} does of {q_{0}, … q_{n−1}}.

Proposition 2.1.9 Every recursive partial order P = (P, ≤_{P}) can be embedded in D.

Proof. Let p_{i} enumerate the elements of P. We build sets C_{i} and let A_{i} = ⊕{C_{j} : p_{j} ≤_{P} p_{i}} so if p_{k} ≤_{P} p_{j} then A_{k} ≤_{T} A_{j} since ≤_{P} is recursive.

Requirements: R_{k,j,e} : p_{k} ≰_{P} p_{j} implies A_{k} ≰_{T} A_{j} i.e. ∀eΦ_{e}^{C_{j}} ≠ C_{k}.

Approximations: Finitely many finite binary strings γ_{j,s}. We set C_{j} = ∪γ_{j,s}. Then we approximate the A_{i} by

A_{i,s} = ⊕{γ_{j,s} : p_{j} ≤_{P} p_{i}}

i.e. A_{i,s} is defined at ⟨j, x⟩ if γ_{j,s}(x) is defined. Think of each γ_{j,s} as partial function and A_{i,s} is the sum of these partial functions. To make A_{i} a total characteristic function we set A_{i}(⟨j, x⟩ (x) = 0 if p_{j} ≰_{P} p_{i}.

Suppose we wish to act for R_{k,j,e} at stage s = ⟨k, j, e⟩. We have A_{j,s}, A_{k,s} finite characteristic functions determined by the γ_{i,s} so far defined. To guarantee that Φ_{e}^{A_{j}} ≠ A_{k}, could we take x = |γ_{k,s}| and ask if there is extension of the γ’s such that Φ_{e}^{A_{j}}(x) ↓ to diagonalize? The problem is that an extension of the γ’s which guarantees convergence might also determine the value A_{k}(x), so we might not be able to diagonalize.

To make x not interfere with the computation from A_{j}, we want an x = ⟨n, y⟩ such that p_{n} ≰_{P} p_{j}. Also, to be able to define A_{k} at x, we need p_{n} ≤ p_{k} (otherwise the relevant column is always empty). We also need ⟨n, y⟩ ≥ |γ_{k,s}|. So we want p_{n} ≰ p_{j} and p_{n} ≤_{P} p_{k}. By assumption, p_{k} ≰_{P} p_{j}, so choose n = k. Then let x = ⟨k, |γ_{k,s}|⟩.

Now, ask for least extension of the γ’s which makes Φ_{e}^{A_{j}}(x) ↓. This only depends on γ_{i} for p_{i} ≤_{P} p_{j}. If such an extension exists, put A_{k}(x) = 1 − Φ_{e}^{A_{j}}(x). If there is no such extension, do nothing. Then, go to stage s + 1.

To verify that the construction satisfies all the requirements, for R_{k,j,e} consider the stage s = ⟨k, j, e⟩. Either we extended some γ or we didn’t. If we extended some γ, then there is x such that Φ_{e}^{A_{j}}(x) ↓≠ A_{k}(x). If we didn’t, then no such extension exists and since A_{j} extends γ_{j,s}, Φ_{e}^{A_{j}}(x) ↑.

Corollary 2.1.10 Every countable partial order can be embedded in D.

Corollary 2.1.11 The one-quantifier theory of (D, ≤_{T}) is decidable.

Proof. A one-quantifier existential sentence is equivalent to a disjunction of ones of the form

φ ≡ ∃x_{1}∃x_{2} ⋯ ∃x_{n}(x_{i} ≤ x_{j} ∧ ⋯ ∧ x_{j} ≰ x_{k} ∧ ⋯ ∧ x_{n} = x_{n}).

Note that if we can decide whether an existential sentence is true or false then we can flip the answers to decide if universal sentences are true and false. Given such a disjunct, we ask if there is a partial order that satisfies one of the disjuncts. If not, then (D, ≤_{T}) cannot because it itself is a partial order. So suppose (P, ≤_{P}) ⊨ P. If we can embed P into D then we’re done because embedding preserves atomic sentences. Not every partial ordering can be embedded into D (for example, huge ones can’t). But if there is any partial order that satisfies φ then there is a finite partial order that satisfies it, because φ only mentions n elements. So, we can assume that P is finite, hence recursive. Then, the theorem above says that P embeds into D. The last piece of the proof is to verify that we can answer the question of whether φ is satisfiable by a partial order. Well, we can enumerate all partial orders of size at most n and then check each one. And, if φ is satisfiable by a partial order then it is satisfiable by a member of the list.

Exercise 2.1.12 If the recursive partial order P of Proposition 2.1.9 has a least element 0, then embedding f into D can be chosen such that f(0) = 0. Then Corollary 2.1.10 can be extended to partial orders with least element and Corollary 2.1.11 to the language with a constant for 0.

Question 2.1.13 We ask the following questions about the proof of embedding theorem, Proposition 2.1.9:

1. How complicated are the images of the partial order under the embedding? We claim that A_{i} ≤_{T} 0′ uniformly. Indeed the whole construction and so the C_{i} are (uniformly) recursive in 0′. To compute A_{i}(x) where x = ⟨j, n⟩ we first ask if p_{j} ≤ p_{i} (the partial ordering is recursive). If not, A_{i}(x) = 0. If so, we can follow the construction recursively in 0′ until it is decided if x ∈ C_{j}.

2. Can we ensure that all the A_{i} are low? We can add requirements

N_{e} : make Φ_{e}^{⊕A_{i}}(e) ↓ if we can.

To act for N_{e} still takes just a 0′ question. Alternatively, instead of adding infinitely many requirements we can add a top element 1 to P. The construction then gives A_{1} = ⊕C_{j} ≤ 0′ and we can then just make sure that A_{1} is low.

Corollary 2.1.14 Every countable partial older can be embedded in D(≤ 0′) and so its one quantifier theory is decidable.

An alternative approach to these results begins with strengthened versions of incomparability.

Definition 2.1.15 The set {A_{i} : i ∈ ℕ} is independent if no A_{i} is computable from the join of finitely many of the other A_{j}. The set {A_{i} : i ∈ ℕ} is very independent if A_{i} ≰_{T} ⊕_{j≠i}A_{j} for all i.

Very independent implies independent because A_{i_{1}} ⊕ ⋯ ⊕ A_{i_{n}} ≤_{T} ⊕_{j≠i}A_{j} if no i_{k} = i (x ∈ A_{i} ⇔ ⟨i, x⟩ ∈ ⊕_{j≠i}A_{j}). However, while independence is a degree theoretic notion, very independence is not. This is proved in the following exercises.

Exercise 2.1.16 Find {A_{i} : i ∈ ℕ} very independent. (Hint: either write down requirements and use finite approximations or use partial order embedding).

Exercise 2.1.17 Find {A_{i} : i ∈ ℕ}, {B_{i} : i ∈ ℕ} such that {A_{i} : i ∈ ℕ} is very independent, {A_{i} : i ∈ ℕ} is not, but A_{i} ≡_{T} B_{i}.

Definition 2.1.18 An uppersemilattice (usl) is a partially ordered set P such that every pair of elements x, y in P, has a least upper bound, x ∨ y.

Exercise 2.1.19 Every usl L is locally countable, i.e. for any finite F ⊂ L the subusl F of L generated by F (i.e. the smallest one containing F) is finite. Moreover, there is a uniform recursive bound on |F| that depends only on |F |.

Exercise 2.1.20 Given usls Q ⊂ P and an usl extension Q̂ of Q generated over Q by one new element (with Q̂∩P = Q), prove that there is an usl extension P̂ of P containing Q̂.

Exercise 2.1.21 Prove that there is a recursive usl L such that every countable usl can be embedded in it (as an usl).

Exercise 2.1.22 Every countable usl L can be embedded in D and even in D(≤ 0′) (preserving ∨ as well as ≤). Hint: Use a very independent set C_{i}. If L = {l_{i}} send l_{i} to ⊕{C_{j}|l_{j} ≱ l_{i}}.

Notes: The finite extension method for constructing degrees was developed in Kleene and Post [1954]. It was the seminal paper on the structure of the Turing degrees. They proved, among others, Theorem 2.1.2, the existence of a countable family of independent sets and Proposition 2.1.9 for finite partial orders and that these theorems are true in the degrees below 0′. Sacks [1961] and [1963] contain Corollary 2.1.10 and much more. Corollary 2.1.11 is pointed out in Lerman [1972].

We will see in Theorem 3.3.1 that every countable lattice can be embedded in D but not by the methods used here in the sense that there is no countable lattice L which is countably universal, let alone a recursive one. Indeed local finiteness fails and there are 2^{ℵ_{0}} many lattices generated by four elements. We provide such with seven generators in §3.4.

What about uncountable partial orders, usls and lattices? Of course, they must have the countable predecessor property, i.e. {y|y ≤ x} is countable for every x. Sacks [1961] shows that all partial orders of size ℵ_{1} with the countable predecessor property can be embedded into D. For lattices this follows from Abraham and Shore [1986] where the embedding is made onto an initial segment of D. Sacks [1961] shows that all those with the countable successor property can be embedded. However, it is consistent that 2^{ℵ_{0}} = ℵ_{2} and there is an usl of size ℵ_{2} with the countable predecessor property which cannot be embedded in D (Groszek and Slaman [1983]. It is a long standing open question if every partial order of size 2^{ℵ_{0}} with the countable predecessor property can be embedded in D (Sacks [1963]).

2.2 Extensions of embeddings

We now look at extensions of embedding results which give information about the 2quantifier theory of (D, ≤_{T}).

Theorem 2.2.1 (Avoiding cones) For every A > 0 there is B such that A|_{T} B.

Proof. Given a set A, we build B such that A ≰_{T} B, B ≰_{T} A. There are two kinds of requirements:

P_{e} : Φ_{e}^{A} ≠ B Q_{e} : Φ_{e}^{B} ≠ A.

The construction is by finite binary string approximations β_{s} for B. At the end, we let B = ∪_{s}β_{s}.

Suppose at stage s we work to satisfy P_{e}. We have β_{s} and construct β_{s+1} guaranteeing that B meets the requirement. We ask for the value of Φ_{e}^{A}(|β_{s}|). If Φ_{e}^{A}(|β_{s}|) ↑ then P_{e} is satisfied so do nothing. Otherwise, put β_{s+1} = β_{s}ˆ (1 − Φ_{e}^{A}(|β_{s}|)). So, B(|β_{s}|) = β_{s+1}(|β_{s}|) ≠ Φ_{e}^{A}(|β_{s}|). Observe that at this stage we ask a question that A′ can answer and then carry out a recursive procedure.

Likewise, suppose at stage s we work to satisfy Q_{e}. We ask if there is an x and an extension σ of β_{s} such that Φ_{e}^{σ}(x) ↓≠ A(x). If no such extension exists, do nothing. If there is such an extension, let β_{s+1} be the least such extension. Note that this is a Σ_{1}^{A} question followed by a recursive procedure, so this step is recursive in A′.

To verify that this construction works, observe that all the P_{e} are clearly satisfied. Suppose we fail to satisfy Q_{e}. Then at stage s there was no x and σ ⊃ β_{s} such that Φ_{e}^{σ}(x) ↓≠ A(x). If Φ_{e}^{B}(x) ↑ for any x then Q_{e} is satisfied. Otherwise, we claim that A is recursive: To compute A(x), look for a σ ⊇ β_{s} such that Φ_{e}^{σ}(x) ↓. There is one since Φ_{e}^{B}(x) ↓. The value computed with oracle σ must be A(x). This contradicts our assumption that A is not recursive. Thus, Q_{e} is satisfied.

Exercise 2.2.2 The B of theorem 2.2.1 can be made recursive in A′ and indeed we can guarantee (or the construction already does) that B′ ≡_{T} A′.

Exercise 2.2.3 Every maximal chain (i.e. linearly ordered subset) in D is uncountable.

Exercise 2.2.4 For every countable set of nonrecursive degrees there is a degree incomparable with each of them.

Exercise 2.2.5 Every maximal antichain (i.e. pairwise incomparables) in D is uncountable.

Exercise 2.2.6 Every maximal independent set of degrees is uncountable.

Theorem 2.2.7 (Minimal Pair) There are A, B > 0 such that A ∧ B = 0. In other words, for all C, if C ≤_{T} A, B then C ≡_{T} 0.

Proof. We build A, B by finite approximations α_{s}, β_{s}. There are three kinds of requirements:

P_{e} : Φ_{e} ≠ B, Q_{e} : Φ_{e} ≠ A and N_{e,i} : Φ_{e}^{A} = Φ_{i}^{B} = C ⇒ C is recursive.

To satisfy P_{e}, Q_{e} (respectively): given α_{s} (β_{s}), ask if Φ_{e}(|α_{s}|) ↑ (or Φ_{e}(|β_{s}|) ↑). If yes, then the requirement is already satisfied so let α_{s+1}(|α_{s}|) = 0 (β_{s+1}(|β_{s}|) = 0). Otherwise, let α_{s+1}(|α_{s}|) = 1 − Φ_{e}(|α_{s}|) ( β_{s+1}(|β_{s}|) = 1 − Φ_{e}(|β_{s}|)).

Suppose at stage s we work on N_{e,i}. Ask if (∃α ⊇ α_{s}) (∃β ⊇ β_{s})∃x(Φ_{e}^{α}(x) ↓≠ Φ_{i}^{β}(x) ↓). If such extensions exist, pick the first pair (α, β) which satisfy the condition and put α_{s+1} = α, β_{s+1} = β. If no such extensions exist, do nothing.

To verify that the construction works, first notice that all the P_{e} and Q_{e} are satisfied so A, B > 0. For N_{e,i}, we may assume that Φ_{e}^{A} = Φ_{i}^{B} = C as otherwise the requirement is automatically satisfied. We want to show that C is recursive. Consider α_{s}, β_{s} for the stage s at which we work on N_{e,i}. To compute C(x), find any finite extension α ⊇ α_{s} such that Φ_{e}^{α}(x). (There is one since A ⊇ α_{s} and Φ_{e}^{A}(x) ↓.) We claim that Φ_{e}^{α}(x) = C(x). If not, there is a β ⊇ β_{s} with β ⊆ B such that Φ_{e}^{β}(x) = Φ_{e}^{B}(x) = C(x) and so we would have acted at s with α and β contrary to our assumption.

We frequently use the idea seen in this proof of searching for extensions that give different outputs when used as oracles for a fixed Φ_{e} and, if we find them, doing some kind of diagonalization. If there are none, we generally argue that Φ_{e}^{A} is recursive (or recursive in the relevant notion of extension as in Theorem 2.2.11). We extract the appropriate notion and provide some terminology.

Definition 2.2.8 We say that two strings σ and τ e-split (or form an e-splitting) if ∃x(Φ_{e}^{σ}(x) ↓≠ Φ_{e}^{τ}(x) ↓). We denote this relation by σ|_{e}τ and say that σ and τ e-split at x. Note that by our conventions in Definition 1.1.3, Φ_{e}^{σ}(x) = Φ_{e,|σ|}^{σ}(x) is a recursive relation as is ∃x(Φ_{e}^{σ}(x) ↓≠ Φ_{e}^{τ}(x) ↓), i.e. σ|_{e}τ.

Exercise 2.2.9 We may make the A and B of Theorem 2.2.7 low or note that as constructed they are already low. We can also relativize the result: ∀C∃A, B(A ∧ B ≡ C & A′ ≡ B′ ≡ C′).

We want a notion similar to minimal pairs but with an arbitrary countable ideal of degrees playing the role of 0.

Definition 2.2.10 C ⊆ D is an ideal in the uppersemilattice D if it is closed under joins and is closed downwards (i.e. if y ∈ C and x ≤ y then x ∈ C).

Theorem 2.2.11 (Exact Pair) If C is any countable ideal in D, there are a, b such that C = {x : x ≤_{T} a, b} = {x : x ≤_{T} a} ∩ {x : x ≤_{T} b}.

An alternative statement of the theorem is the following:

Theorem 2.2.12 If C_{1} ≤_{T} C_{2} ≤_{T} ⋯ is an ascending sequence, then there are A, B such that {X : X ≤_{T} A, B} = {X : ∃n(X ≤_{T} C_{n})}.

Exercise 2.2.13 These two statements are equivalent. We can list all the sets D_{j} with degrees in a countable ideal C and then consider the ascending sequence C_{i} = ⊕_{j<i}D_{j}.

We prove the second formulation of the theorem. Proof. Given ⟨C_{n}⟩ ascending in Turing degree, we build A, B such that

• for all n, C_{n} ≤_{T} A, B and

• C ≤_{T} A, B implies that C ≤_{T} C_{n} for some n.

Therefore, we need to satisfy the requirements

R_{n} : C_{n} ≤_{T} A, B N_{e,i} : Φ_{e}^{A} = Φ_{i}^{B} = C ⇒ ∃n(C ≤_{T} C_{n}).

We build A, B by finite approximations α_{s}, β_{s}. Instead of these being thought of as finite strings, however, they are matrices. In each matrix, finitely many columns are entirely determined and there is finitely much additional information. Suppose at stage s we work for R_{n}. Choose the first column in each of α_{s}, β_{s} which has no specifications as yet. Let α_{s+1} (β_{s+1}) be the result of putting C_{n} into that column of α_{s} (β_{s}) and leaving the rest of the approximation unchanged. This action is computable in C_{n}. Otherwise, suppose at stage s we work to satisfy N_{e,i}. Ask if ∃x(∃α ⊇ α_{s}) (∃β ⊇ β_{s})(Φ_{e}^{α}(x) ↓= Φ_{i}^{β}(x) ↓) with the domains of α and β being only finitely larger than those of α_{s} and β_{s}, respectively. If such extensions exist, let (α_{s+1}, β_{s+1}) be the least such pair of extensions. If no such extensions exist, do nothing.

A, B meet the condition that C_{n} ≤_{T} A, B for all n because all the R_{n} requirements are satisfied. Consider the stage s at which we deal with requirement N_{e,i}. We may assume that Φ_{e}^{A} = Φ_{i}^{B} = C as otherwise the requirement is automatically satisfied. We want to prove C ≤_{T} C_{n} for some n. Indeed let n be the largest m such that we have coded C_{m} into A and B by stage s. To compute C(x), find any finite extension α of α_{s} such that Φ_{e}^{α}(x) ↓. (There is one since A ⊇ α_{s} and Φ_{e}^{A}(x) ↓.) We claim that Φ_{e}^{α}(x) = C(x). If not, there is a finite extension β of β_{s} with β ⊆ B such that Φ_{e}^{β}(x) = Φ_{e}^{B}(x) = C(x) and so we would have acted at s with α and β contrary to our assumption. The crucial point now is that checking whether α ⊇ α_{s} is recursive in C_{n}.

Corollary 2.2.14 D is not a lattice.

Proof. Let C_{i} be strictly ascending in Turing degree. (Such exist, for example, by Theorem 2.1.9.) Now let A and B be as in Theorem 2.2.12. If there were a C whose degree is the infimum of those of A and B then C ≤_{T} A, B and so C ≤_{T} C_{n} for some n. In this case, C <_{T} C_{n+1} ≤_{T} A, B for a contradiction.

Exercise 2.2.15 What is a bound on the complexity (degrees) of the A and B of Theorem 2.2.12 in terms of the C_{n}? Does (⊕C_{n})′ work? How about a better bound? How low can we make this bound? Consider also the special case that C_{n} = 0^{(n)}.

Exercise 2.2.16 Use the results of the previous exercise and Corollary 2.1.14 to show that D(≤ 0′) is not a lattice.

Exercise 2.2.17 (Extensions of Embeddings ) Given a finite usl P and a finite partial ordering Q extending P with no x ∈ Q − P below any y ∈ P and an usl embedding f : P → D prove that there is an extension g of f embedding Q into D as a partial order.

Notes: Theorems 2.2.1 and 2.2.7 and Corollary 2.2.14 are due to Kleene and Post [1954]. Exercises 2.2.4 and 2.2.5 to Shoenfield [1960]. Sacks [1961] proves Exercise 2.2.6 but Groszek and Slaman [1983] shows that it is consistent that 2^{ℵ_{0}} = ℵ_{2} but there is a maximal independent set of size ℵ_{1}. Theorem 2.2.11 and Exercise 2.2.16 are due to Spector [1956].

18 CHAPTER 2. EMBEDDINGS INTO THE TURING DEGREES

Forcing in Arithmetic and Recursion Theory

3.1 Notions of Forcing and Genericity

Forcing provides a common language for, and generalization of, the techniques we have developed in Chapter 2. It captures the idea of approximation to a desired object and how individual approximations guarantee (force) that the object we are building satisfies some requirement. Now approximations usually come with some sense of when one is better, or gives more information, than another. Of course, an approximation may have improvements which are incompatible with each other, i.e. the set of approximations is partially ordered. The intuition is that p ≤ q means that p refines, extends or has more information than q. We are generally thinking that the conditions are approximations to some object G : ℕ → ℕ (typically a set) and that if p ≤ q then the approximation p gives more information than q and so the class of potential objects that have p as an approximation is smaller then the one for q. In addition, we have some notion of what, at least at a basic level, the approximation p says about G. We formalize these ideas as follows:

Definition 3.1.1 A notion of forcing is a partial order P with domain a set P and binary relation ≤_{P}. We call an element of P a (forcing) condition. For convenience, we assume that the partial order has a greatest element 1. (For further restrictions see Definition 3.1.11.)

Example 3.1.2 If the notion of forcing is (2^{<ω}, ⊇), then σ ≤ τ ≡ σ ⊇ τ. In many of our previous constructions we used such binary strings σ as approximations to a set G such that σ ⊂ G. So the longer the string, the fewer sets that “satisfy” it, i.e. have it as an approximation (initial segment). This example is often called Cohen forcing.

Example 3.1.3 In Theorem 2.2.12, we used partial characteristic functions α defined on some finite set of columns and some finitely many additional points. Again we were approximating a set G ⊃ α.

Example 3.1.4 If the notion of forcing is the set of perfect (i.e. every node has two incomparable extensions) recursive binary trees under ⊆ then S ≤ T ≡ S ⊆ T. (Here trees T are simply sets of finite strings, i.e. subsets of ω^{<ω}, which are downward closed, i.e. if τ ⊆ σ ∈ T then τ ∈ T.) Think of such a tree T as approximating the set [T] of its paths, i.e. [T] = {f|∀n(f ↾ n ∈ T }, so more information means fewer paths, i.e. more information about which path is being approximated. This notion of forcing is often called Spector forcing (or perfect forcing or Sacks forcing or other names for different variations).

What object is it exactly or what class of objects is it that a condition p approximates? For Cohen forcing a condition (string) σ approximates the class of sets {G|G ⊃ σ}. So the collection of all approximations to a single set G is simply {σ|σ ⊂ G}, the class of all the initial segments of G. We want to isolate the salient features of this set of conditions or any set G ⊆ P that might considered as an object its members are approximating. The general approach that we want for an arbitrary notion of forcing begins with that of a filter.

Rather than simply comparing any two elements, the idea is to compare each of them with the imaginary end point that we’re approximating. That is, between two given positions and end goal, there is an element extending both of the given ones.

Definition 3.1.5 Two elements p, q are compatible if and only if ∃r(r ≤ p ∧ r ≤ q). If p, q are incompatible we write p ⊥ q (as opposed to incomparables which are written as p | q to denote that p ≰ q and q ≰ p).

Definition 3.1.6 F ⊆ P is a filter on P if and only if F is upward closed and for every p, q ∈ F there is an r ∈ F with r ≤_{P} p, q.

We are thinking of filters as connected with the object we are approximating, the end goal.

Example 3.1.7 Suppose we want to approximate a set G ∈ 2^{ω} and our notion of forcing is (2^{<ω}, ⊇) (finite binary strings). Then the set {σ : σ ⊂ G} is a filter. In particular, the union of this set (filter) is the characteristic function G. It will commonly be the case that the object we want is defined from a filter by some “simple” operation such as union. We formalize this idea in Definition 3.1.11. Note that for finite strings, being comparable is the same as being compatible.

Example 3.1.8 Suppose we want to approximate a set G ∈ 2^{ω} and our notion of forcing is some countable set of infinite binary trees (not necessarily perfect) such as the recursive ones. Then the set {T : G ∈ [T]} = {T : ∀σ ⊂ G(σ ∈ T)} is a filter: Suppose two trees both have G as a path. Then the tree which is the (set) intersection of the two trees is a common refinement. For upward closure, if G is a path on T and T ⊆ S then G is also a path on S. In this case, the intersection of this filter is the characteristic function of G.

Suppose F is a filter on some notion of forcing P. We can often associate some set or function with F in a canonical way. For example, for Cohen forcing we can naturally try ∪F. For forcing with binary trees we might try ∩{[T]|T ∈ F}. Does this always make sense even for Cohen or Spector forcing? For Cohen forcing it might be that ∪F is a finite string so itself a condition. For Spector forcing ∩{[T]|T ∈ F} could be a set of paths through a binary tree with more than one branch which might not necessarily be recursive or perfect. We need to add conditions on our filter to make sure we get a total function or a single set at the end. We might for example require for Cohen forcing that F contain strings of every (equivalently arbitrarily long) length, i.e. (∀n)(∃σ ∈ F)(|σ| ≥ n). For Spector forcing we could require that there are trees in F with arbitrarily long nodes σ before the first branching (i.e. σ has two immediate successors in the tree but no τ ⊂ σ does). To this end we add a function V (p) representing the atomic information about our generic object determined by the condition p and the requirement that all generic filters meet certain dense sets defined in terms of V.

Definition 3.1.9 D ⊆ P is dense in P if ∀p ∈ P∃q ∈ D(q ≤_{P} p). D is dense below r if ∀p ≤_{P} r∃q ∈ D(q ≤ p).

In general we want the conditions guaranteeing (forcing) each of our requirements to be dense.

Definition 3.1.10 If C is a class of dense subsets of P, we say that G is C-generic if G ∩ D ≠ ∅ for all D ∈ C. We say that a sequence ⟨p_{n}⟩ of conditions is C-generic if ∀i(p_{i+1} ≤_{P} p_{i}) and ∀D ∈ C∃n(p_{n} ∈ D).

Definition 3.1.11 We always require that a notion of forcing have a valuation function V : P → ω^{<ω} which is recursive on P and continuous in the sense that if p ≤_{P} q then V (p) ⊇ V (q). (We say that a partial recursive function φ is recursive on a set X if X ⊆ dom(φ).) Moreover, we require that the sets V_{n} = {p| |V (q)| ≥ n)} are dense. We also require that any collection of dense sets that we consider for the construction of a generic filter or sequence include the V_{n}.

Example 3.1.12 In the Examples above we may define V (p) = p for Cohen forcing. When the conditions are trees T, we may let V (p) be the largest σ such that every τ ∈ T is comparable with σ. Show that the corresponding V_{n} are dense. What should V be for the forcing that constructs an exact pair?

Proposition 3.1.13 If ⟨p_{n}⟩ is a C-generic sequence then G ={p|∃n(p_{n} ≤ p} is a Cgeneric filter containing each p_{n}.

Proof. G is C-generic because it contains an element, p_{n}, of D_{n} for all n. It is upward closed because if p ∈ G then p ≥ p_{e} for some e so if q > p ≥ p_{e} then q ≥ p_{e} as well. Finally, it is pairwise compatible because given p ≥ p_{e_{1}}, q ≥ p_{e_{2}} then p, q ≥ p_{e} where e = max{e_{1}, e_{2}}.

If our collection of dense sets is countable then generic sequences and filters always exist.

Theorem 3.1.14 If C is countable and p ∈ P, then there is a C-generic sequence ⟨p_{n}⟩ with p_{0} = p and so, by Proposition 3.1.13, a C-generic filter G containing p.

Proof. Let C = {D_{n}|n ∈ ℕ}. We define ⟨p_{n}⟩ by recursion beginning with p_{0} = p. If we have p_{n} then we choose any q ≤ p_{n} in D_{n} as p_{n+1}. One exists by the density of D_{n}. It is clear that ⟨p_{n}⟩ is a C generic sequence and so G ={p|∃n(p_{n} ≤ p} is C-generic filter containing p.

Exercise 3.1.15 If C is countable (as it always is in our applications) and G is a Cgeneric filter containing p, then there is a C-generic sequence ⟨p_{n}⟩ ≤_{T} G with p_{0} = p such that G ={p|∃n(p_{n} ≤ p}. (This is a converse to Proposition 3.1.13.)

Definition 3.1.16 We associate to each C-generic sequence ⟨p_{n}⟩ or filter G the generic function (or set) G = ∪V (p_{n}) or {V (p)|p ∈ F}.

Proposition 3.1.17 If G is associated with the C-generic sequence ⟨p_{n}⟩ (filter G) then G ≤_{T} ⟨p_{n}⟩ (G).

Proof. As V is recursive on P and the sets V_{n} of Definition 3.1.11 are included in C, we can compute G(n) by searching for a k such that p_{k} ∈ V_{n} (or p ∈ G) and then noting that G(n) = V (p_{k}) (V (p)).

As is our general practice, we often care about how hard it is to compute a C-generic sequence, filter or function. We must begin with the complexity of P and then consider how hard it is to compute the generic sequence ⟨p_{e}⟩ and so the associated generic G. We view the elements of P as being (coded by) natural numbers. For convenience we let the natural number 1 be the greatest element of P.

Definition 3.1.18 A notion of forcing P is A-recursive (or a-recursive) if the set P and the relation ≤_{P} are recursive in A (∈ a). (As usual if A = ∅ (a = 0) we omit it from the notation.) If C = {C_{n}} is a collection of dense sets in P then f is a density function for C if ∀p ∈ P ∀n ∈ ℕ(f(p, n) ∈ C_{n}).

Proposition 3.1.19 If P is an A-recursive notion of forcing and C = {C_{n}} is a uniformly A-recursive sequence of dense subsets of P and p ∈ P then there is a C-generic sequence ⟨p_{n}⟩ with p_{0} = p which is recursive in A. More generally, for an arbitrary notion of forcing P, p ∈ P and a class C of dense sets, if f is a density function for C, then there is a C-generic sequence ⟨p_{n}⟩ ≤_{T} f with p_{0} = p. The generic G function associated with these filters or sequences are also recursive in A or f, respectively.

Proof. If P is an A-recursive notion of forcing and C = {C_{n}} is a uniformly A-recursive sequence of dense subsets of P, then we can define a density function f ≤_{T} A by letting f(p, n) be the least (in the natural order of ℕ) q ≤_{P} p with q ∈ C_{n}. The desired generic sequence is now given by setting p_{0} = p and p_{n+1} = f(n, p_{n}). That G is recursive in A or f now follows from Proposition 3.1.17.

Note that the generic filter G defined from the generic sequence ⟨p_{n}⟩ in Proposition 3.1.13 is Σ_{1} in ⟨p_{n}⟩ but not necessarily recursive in it. While in the other direction some such sequence is recursive in the filter. (Exercise 3.1.15)

3.2. THE FORCING LANGUAGE AND DECIDING CLASSES OF SENTENCES 23

3.2 The Forcing Language and Deciding Classes of Sentences

The ad hoc approach to constructions presented in Chapter 2 looks at the specific theorem we want to prove, decides what are the specific requirements we need to meet, and then builds the desired sets accordingly. For example, this is what we did to build A|_{T} B. Our approximations were P = {⟨α, β⟩}. The requirements were Φ_{e}^{A} ≠ B (and Φ_{e}^{B} ≠ A). Given α, β, we could find ⟨α̂, β̂⟩ ≤ ⟨α, β⟩ which would guarantee the requirement. In particular, if one exists, we chose a specific ⟨α̂, β̂⟩ ≤ ⟨α, β⟩ such that ∃xΦα̂ ; e(x) ↓≠ β̂(x) ↓; if not, we took ⟨α, β⟩. In the terminology of forcing, we had dense sets

D_{e} = {⟨α, β⟩ : ∃xΦ_{e}^{α}(x) ↓≠ β(x) ↓ or (∀⟨α̂, β̂⟩ ≤ ⟨α, β⟩)(¬[∃xΦα̂ ; e(x) ↓≠ β̂(x) ↓])}

Likewise, we defined dense sets C_{e}, which guaranteed that Φ_{e}^{B} ≠ A. Then if G is {D_{e}, C_{e}}- generic, G_{0} |_{T} G_{1}.

In this manner, each of the proofs we did earlier by constructions with requirements can be translated to dense sets and generics for the dense sets D_{e} determined by the conditions that guarantee (force) that we satisfy the eth requirement. However, the benefit of the forcing technology comes in the form of the generality it allows. For example, we could try to tackle many of the constructions at once. We need to define the forcing relation (⊩) more generally, by induction on formulas φ that somehow say that if p ⊩ φ then φ(G) holds for the set or function G determined by any sufficiently generic filter G.

Thus we want a relation ⊩ between conditions p ∈ P and sentences ϕ(G) (where we use G as the formal symbol that is to be interpreted as our generic set or function G). This relation should approximate truth in the sense just described. We could use a standard language of arithmetic (in set theoretic forcing, one would use the language of set theory) augmented with another parameter (G) for the set we are building, and possibly other parameters (F̄) for given sets or functions. For our purposes it is more convenient to use the master (universal) partial recursive predicates ϕ(G, F̄, e, x̄) and the standard normal form theorems mentioned in §1.1 and described below.

We fix some finite sequence of functions or sets F̄ and view them as fixed parameters that appear in our formulas. This allows us to formalize relativizations to such F̄ as well as other notions. For the most part, however, we can ignore them in our proofs as the relativizations are almost always straightforward.

We use ϕ_{n}(G, F̄, e, x_{0}, … x_{n−1}) to mean that the eth Turing machine with oracles G and F̄ (which we are viewing as a fixed (possibly empty) set or function parameters that depends on the notion of forcing and is included in the oracle) running for x_{0} many steps on inputs x_{1}, … x_{n−1} converges. Our conventions are that if the machine runs for s many steps then it must first read the program and inputs and then can ask about the value of any one of the oracles at n only after writing out n and must then read the answer. So, in particular, ϕ_{n}(G, F̄, e, x_{0}, … x_{n−1}) can hold only if e, x_{1}, …, x_{n−1} < x_{0} and for any information G(m) or F (m) about the oracles used in the computation m, G(m) and F (m) are also less than x_{0}. Thus if ϕ_{n}(G, F̄, e, x_{0}, … x_{n−1}) holds then it only depends on G ↾ x_{0} (and F̄ ↾ x_{0} although we ignore this fact as we are thinking of the F̄ as given parameters) in the sense that it is also true for any G′ ⊇ G ↾ x_{0} and. In this case we also say that ϕ(σ, F̄, e, x_{0}, … x_{n−1}) holds for any σ ⊇ G ↾ x_{0}. Thus, crucially, the predicates ϕ_{n}(σ, F̄, e, x_{0}, … x_{n−1}) are uniformly recursive in F̄. Moreover, every Σ_{1} sentence about G and F̄ is equivalent to one of the form ∃x_{0}ϕ(G, F̄, e, x_{0}) and so to ∃x_{0}ϕ(G ↾ x_{0}, F̄, e, x_{0}). Every Π_{1} sentence about G and F̄ is equivalent to one of the form ∀x_{0}¬ϕ(G, F̄, e, x_{0}) and so to ∀x_{0}¬ϕ(G ↾ x_{0}, F̄, e, x_{0}). More generally, for n > 0, every Σ_{2n+1} sentence about G and F̄ is equivalent to one of the form ∃x_{2n}∀x_{2n−1} … ∃x_{0}ϕ(G, F̄, e, x_{0}, …, x_{2n}); every Σ_{2n} sentence about G and F̄ is equivalent to one of the form ∃x_{2n}∀x_{2n−1} … ∀x_{0}¬ϕ(G, F̄, e, x_{0}, …, x_{2n}) and similarly for Π_{n} sentences about G and F̄. Thus, it suffices to consider only formulas beginning with a list of quantifiers of alternating type followed by a predicate of the form ϕ(G, F̄, e, x_{0}, … x_{n−1}) (if the final quantifier is ∃) or ¬ϕ(G, F̄, e, x_{0}, … x_{n−1}) (if the final quantifier is ∀). (Note that n may be larger than the number of quantifiers and we include constants m in our language for every m ∈ ℕ.)

Notation 3.2.1 We use ¬φ to stand for the canonical equivalent of the negation of φ, i.e. change each quantifier (∃ to ∀ and vice versa) and the matrix (ϕ to ¬ϕ and vice versa). So, in particular, ¬¬φ = φ.

Notation 3.2.2 We use G for the generic filter, G for ∪{V (p)|p ∈ G}, the set or function that we are building and G for the symbol in language that stands for that set or function.

We define the forcing relation p ⊩ φ for p ∈ P and φ a sentence of our language by induction on the complexity of sentences. The usual definition in standard languages proceeds by induction on the full range of formulas with the crucial steps (after the atomic variable free formulas) being p ⊩ ∃xψ ⇔ ∃n (p ⊩ φ(n)); p ⊩ ¬φ ⇔ ∀q ≤ p(q ⊮ φ) and so p ⊮ ∀xφ ⇔ ∀n∀q ≤ p (q ⊮ ¬φ(n)) ⇔ ∀n∀q ≤ p∃r ≤ q (r ⊩ φ(n)). (The definitions for conjunction and disjunction are given by p ⊩ φ ∧ ψ ⇔ p ⊩ φ and p ⊩ ψ and p ⊩ φ∨ψ ⇔ p ⊩ φ or p ⊩ ψ.) With our restricted language we can simply the definitions and so the calculation of the complexity of the relation p ⊩ φ.

Definition 3.2.3 We define the relation p forces φ, p ⊩ φ, by induction.

• If φ is a Σ_{1} formula ∃x_{0}ϕ_{n}(G, F̄, e, x_{0}, m_{1}, … m_{n−1}) then p ⊩ φ if and only if there is an m_{0} such that ϕ_{n}(V (p), F̄, e, m_{0}, m_{1}, … m_{n−1}) holds (or equivalently, for every G ⊇ V (p), ϕ_{n}(G, F̄, e, m_{0}, m_{1}, … m_{n−1}) holds.

• If φ is a Π_{1} formula ∀x_{0}¬ϕ_{n}(G, F̄, e, x_{0}, m_{1}, … m_{n−1}) then p ⊩ φ if and only if ∀m_{0}∀q ≤ p(¬ϕ_{n}(V (q), F̄, e, m_{0}, m_{1}, … m_{n−1}).

• If φ is a Σ_{n+1} formula ∃xψ(x) then p ⊩ φ if and only if ∃m(p ⊩ ψ(m)).

• If φ is a Π_{n+1} formula ∀xψ(x) then p ⊩ φ if and only if ∀m∀q ≤ p(q ⊩ ¬ψ(m).

Exercise 3.2.4 Unravel the definition for p to force a Π_{2} sentence ∀x∃yψ(x, y) to see that it means that for every m there is a n and a q ≤ p such that ψ(m, n).

Theorem 3.2.5 If P is a notion of forcing recursive in A then, for n ≥ 1, forcing for Σ_{n} (Π_{n}) sentences φ (i.e. whether p ⊩ φ) is a Σ_{n} (Π_{n}) in A (and F̄) relation.

Proof. As we generally do from now on, we assume that the sequence F̄ of parameters is empty and leave the relativization of results to the reader. We proceed by induction on n and for notational convenience ignore A (i.e. assume it is recursive) as well. If φ is Σ_{1} or Π_{1} then p ⊩ φ is directly defined as a Σ_{1} or Π_{1} formula, respectively. (The point here is that the ϕ_{n} are uniformly recursive.) For n ≥ 1 the result follows by induction and our definition of forcing.

Exercise 3.2.6 If p ⊩ φ and q ≤ p then q ⊩ φ.

We now want to tackle the question of how much genericity do we need to make forcing equal truth for generic filters/sets in the sense that if p ⊩ φ, p ∈ G and G is sufficiently generic then φ(G) holds and, in the other direction, if φ(G) holds then there is a p ∈ G such that p ⊩ φ.

Definition 3.2.7 The filter G is n-generic (for n ≥ 1) if and only if for every Σ_{n} (in P) subset S of P,

∃p ∈ G(p ∈ S ∨ ∀q ≤ p(q ∉ S)).

We say that G is (ω-) generic if it is n-generic for all n. Similarly the descending sequence ⟨p_{n}⟩ of conditions is n-generic iff for every Σ_{n} (in P) subset S of P, there is an n such that p_{n} ∈ S or ∀q ≤ p_{n}(q ∉ S). The sequence is called (ω-) generic if it is n-generic for all n. We also say that the function or set G determined by an (n-)generic filter or sequence is itself (n-)generic. These notions all relativize to an arbitrary X in the obvious way. We then say, for example, that G is n-generic relative to (or over) X.

The following equivalence is now immediate.

Proposition 3.2.8 Let C_{n} be the class of dense sets {p : p ∈ S_{e} ∨ ∀q ≤ p(q ∉ S_{e})} = D_{n,e} for all Σ_{n} (in P) subsets S_{e} of P. Then a filter G (or a descending sequence ⟨p_{n}⟩) is n-generic iff G (⟨p_{n}⟩) is C_{n}-generic.

Exercise 3.2.9 If D ⊆ P is dense and Σ_{n} then D meets every n-generic G. If D is dense below p (i.e. ∀q ≤_{P} p∃r ≤_{P} q(r ∈ P)) and Σ_{n} then D meets every n-generic G containing p.

To build an n-generic G we proceed as in the construction of a generic for a given countable class of dense sets. We can now also calculate how hard it is to carry out this construction.

Proposition 3.2.10 For any notion of forcing P and each n ≥ 1, there is an n-generic sequence ⟨p_{k}⟩ ≤_{T} 0^{(n)} (P^{(n)}) and so its associated n-generic G is also recursive in 0^{(n)} (P^{(n)}). There is also a generic sequence ⟨p_{k}⟩ such that it and its associated G are recursive in 0^{(ω)} (P^{(ω)}). Moreover, for any p ∈ P we may require that p_{0} = p and so V (p) ⊆ G.

Proof. Fix n. We build a generic sequence ⟨p_{n}⟩ for the C_{n} of Proposition 3.2.8 recursively in 0^{(n)} (as usual assuming P is recursive). We begin with p_{0} the given p ∈ P. If we have already defined p_{s} we find, recursively in 0^{(n)}, a q ≤_{P} p_{s} which is in D_{n,s+1}. This procedure clearly constructs the desired sequence and is recursive in 0^{(n)} by definition of the D_{n,e}. For ω-genericity one simply carries out this construction for the collection {D_{n,e}|n, e ∈ ω)} recursively in 0^{(ω)}. That G is recursive in P^{(n)}(P^{(ω)}) follows from Proposition 3.1.17.

Definition 3.2.11 We say that a condition p decides a sentence φ if p ⊩ φ or p ⊩ ¬φ.

Theorem 3.2.12 If G is n-generic and φ ∈ Σ_{n} (Π_{n}) then there is p ∈ G which decides φ. Moreover, if p ⊩ φ then φ(G) holds while if p ⊩ ¬φ then ¬φ(G) holds. Moreover, if q ∈ G and q ⊩ φ then φ(G) holds.

Proof. We proceed by induction on n ≥ 1. Consider φ = ∃xψ(x, G). Now the set S = {p : p ⊩ ∃xψ(x, G)} is Σ_{n} by Theorem 3.2.5. So by the definition of n-genericity, either there is p ∈ G in S which forces φ or one with no extension forcing φ. If p ∈ G and p ⊩ ∃xψ(x, G), then (by definition) there is an n such that p ⊩ ψ(n, G) (or ϕ_{m}(V (p), …) for some m, if n = 1). Now by induction (or the basic properties of ϕ_{m} for n = 1), ψ(n, G) holds and then so does ∃xψ(x, G) as required. On the other hand, suppose there is p ∈ G such that (∀q ≤ p)(q ⊮ ∃xψ(x, G)). In this case, we claim that that ¬∃xψ(x, G). If not, there would be an n such that ψ(n, G) and so by induction (or definition for n = 1), a q ∈ G such that q ⊩ ψ(n, G) (or ϕ_{m}(V (q), …) if n = 1). So, q ⊩ ∃xψ(x, G). But, since p, q ∈ G they are compatible and there is an r ∈ G with r ≤ p, q. This would contradict Exercise 3.2.6. Finally, we claim that in this case p ⊩ ¬φ. First, (∀q ≤ p)(q ⊮ ∃xψ(x, G)) implies that (∀q ≤ p)(∀x)(q ⊮ ψ(x, G)), and so p ⊩ ∀x¬ψ (by the definition of forcing) which is the same as p ⊩ ¬φ as required. As for the last claim of the Theorem, note that there is some p ∈ G that p decides φ in the way that corresponds to the truth of φ(G). The conditions p and q are compatible and so p ⊩ φ and φ(G) holds as required.

The case that φ is Π_{n} clearly follows as then ¬φ is Σ_{n} and ¬¬φ = φ.

We now look at degree theoretic properties of sets with various amounts of genericity. We begin with some connections between genericity and lowness. The first improves Proposition 3.2.10. The second is specific to notions of forcing similar to that of Cohen.

Proposition 3.2.13 For any notion of forcing P and each n ≥ 1, there is an n-generic sequence ⟨p_{k}⟩ ≤_{T} P^{(n)}. For any G associated with such a sequence, G^{(n)} ≤_{T} P^{(n)}. There is also a generic ⟨p_{k}⟩ ≤_{T} P^{(ω)} and for any G associated with such a sequence, G^{(ω)} ≤_{T} P^{(ω)}. Moreover, for any p ∈ P we may require that p ∈ G (p_{0} = p).

Proof. A sequence ⟨p_{k}⟩ as required exists by Proposition 3.2.10. Now note that the question of whether x ∈ G^{(n)} is uniformly Σ_{n} and so we can find the D_{n,e} that corresponds to the the Σ_{n} formula p ⊩ e ∈ G^{(n)} and, recursively in P^{(n)} (P^{(ω)}), find a k such that p_{k} forces this formula or no extension of it does. By Theorem 3.2.12, this determines if x ∈ G^{(n)}(G^{(ω)}) or not.

Exercise 3.2.14 If every condition in P has two incompatible extensions then we can replace ≤_{T} by ≡_{T} in Proposition 3.2.13. Indeed we can make G^{(n)} ≡_{T} C for any C ≥_{T} P^{(n)} or G^{(ω)} ≡_{T} C for C ≥_{T} P^{(ω)}. This is a generalization of the Friedberg Completeness Theorem (∀c ≥ 0′)(∃a)(a′ = c) to iterations of the jump.

Proposition 3.2.15 If G is n-generic for Cohen forcing then G^{(n)} ≡_{T} G ∨ 0^{(n)}. Similarly, if G is generic, G^{(ω)} ≡_{T} G ∨ 0^{(ω)}

Proof. It is immediate that for any G, G ∨ 0^{(n)} ≤_{T} G^{(n)}. Thus, it suffices to show that if G is n-generic then G^{(n)} ≤_{T} G ∨ 0^{(n)}. The formula φ(e, G) which says that e ∈ G^{(n)} is uniformly Σ_{n}. Therefore, by Theorem 3.2.12 and the n-genericity of G, either there is p ∈ G such that p ⊩ φ(e, G) or there is p ∈ G such that p ⊩ ¬φ(e, G). However, p forcing φ is a Σ_{n} relation and forcing ¬φ is Π_{n} so to see if e ∈ G^{(n)} we can search for a p ∈ G such that p ⊩ φ(e, G) or p ⊩ ¬φ(e, G). This is a G ∨ 0^{(n)} question since for Cohen forcing p ∈ G if and only if V (p) ⊆ G. By Theorem 3.2.12, the one forced is the true fact about G. The uniformity of this argument gives the desired result for generic G.

Exercise 3.2.16 The results of Proposition 3.2.15 relativized to P hold for any notion of forcing P such that for every 1-generic G there is a filter G ≤_{T} G such that G = ∪{V (p)|p ∈ G}.

Exercise 3.2.17 Find an A-recursive notion of forcing for which the analog of Proposition 3.2.15 does not hold, i.e. there is an n-generic G with G^{(n)} ≰_{T} G ∨ A^{(n)}.

The next proposition gives almost all our previous incomparability and embeddability results in one fell swoop.

Proposition 3.2.18 If G is Cohen 1-generic then the columns G^{[i]} = {⟨i, x⟩|⟨i, x⟩ ∈ G} of G form a very independent set, i.e. ∀j(G^{[j]} ≰_{T} G^{[ĵ]}).

Proof. For each e we want to show that Φ_{e}^{G^{[ĵ]}} ≠ G^{[j]}. We consider the following set of conditions:

S_{e} = {p : ∃x (Φ_{e}^{p^{[ĵ]}}(x) ↓≠ p^{[j]}(x))}.

Here we use the natural extension of our notation for columns of a set to finite binary strings: p^{[j]}(⟨j, x⟩ = p(⟨j, x⟩) and p^{[j]}(⟨j, x⟩ = 0 for p(⟨j, x⟩) ↓ and i ≠ j. We define p^{[ĵ]} similarly. Since S_{e} ∈ Σ_{1} and G is 1-generic, there is p ∈ G ∩ S_{e} or there is p ∈ G no extension of which is in S_{e}. If p ∈ G ∩ S_{e} then p ⊆ G so the requirement is satisfied.

Suppose that p ⊆ G and (∀q ⊇ p)q ∉ S_{e} then we claim that Φ_{e}^{G^{[ĵ]}} is not total. If it were, let ⟨j, x⟩ be outside the domain of p. We must then have some q ⊂ G with q ≤ p, q(⟨j, x⟩) ↓ and Φ_{e}^{q^{[j]}}(x) ↓. Now let q̂(⟨j, x⟩) = 1 − q(⟨j, x⟩) and q̂(z) = q(z) for z ≠ ⟨j, x⟩. So q̂^{[ĵ]} = q^{[ĵ]} and Φ_{e}^{q^{[ĵ]}}(x) ↓= Φ_{e}^{q̂^{[ĵ]}}(x) ↓ but q̂(⟨j, x⟩) ≠ q(⟨j, x⟩. Thus one of q and q̂ (both of which extend p) is in S_{e} for the desired contradiction.

Exercise 3.2.19 The Theorems and Propositions of this section relativize to an arbitrary X. For example, Proposition 3.2.18 now says that if G is 1-generic relative to X, then the independence results hold even relative to X, i.e. ∀j(G^{[j]} ≰_{T} X ⊕ G^{[ĵ]}).

Exercise 3.2.20 If G is Cohen 1-generic over X and A, B ≤_{T} X then

A ≤_{T} B ⇔ A ⊕ G ≤_{T} B ⊕ G.

Also, G |_{T} X if X > 0.

Exercise 3.2.21 Prove that if G is Cohen n-generic then the G^{[i]} are very mutually Cohen n-generic in the sense that each G^{[i]} is Cohen n-generic over G^{[î]}.

Exercise 3.2.22 Translate the Exact Pair Theorem into the language of forcing. Hint: Given ⟨C_{i}⟩, define a notion of forcing P with conditions ⟨α, β, n⟩ for α, β ∈ ω^{<ω} and n ∈ ℕ. The ordering is given by ⟨α′, β′, n′⟩ ≤ ⟨α, β, n⟩ if α′ ⊇ α, β′ ⊇ β, n′ ≥ n and, for i < n, if α′(⟨i, x⟩) ↓ but α(⟨i, x⟩) ↑ then α′(⟨i, x⟩) = C_{i}(x) and similarly for β′ and β.

Exercise 3.2.23 Construct a 1-tree T such that every G ∈ [T] is Cohen 1-generic. To be precise we want a function F : ℕ → {0, 1, 2}such that if {d_{n}} lists the x such that F (x) = 2 in increasing order and for any A ∈ 2^{ω}, we let F_{A}(x) = A(n) if x = d_{n} for some n and F_{A}(x) = F (x) otherwise, then F_{A} is Cohen 1-generic for every A ∈ 2^{ω}. Hint: make F 1-generic for conditions p ∈ {0, 1, 2}^{<ω}.

Exercise 3.2.24 Show that the Cohen 1-generic degrees generate D. Hint: Fix an A ∈ 2^{ω}. Make the F of the previous construction 1-generic relative to A. Show that for any

j ≠ k, (F_{A}^{[j]} ∨ F [j] ; Ā) ∧ (F_{A}^{[k]} ∨ F [k] ; Ā) ≡_{T} A where for any i F^{[i]}(x) = F (⟨i.x⟩.

We close this section with a slightly variation of our previous constructions that is needed in §5.4.

Proposition 3.2.25 If P is a recursive notion of forcing and C_{0} and C_{1} are low sets, i.e. C′_{0} ≡_{T} 0′ ≡_{T} C′_{1} then there is a G which is 1-generic for P over C_{0} and over C_{1} so that, in particular, both G ⊕ C_{0} and G ⊕ C_{1} are low.

Proof. Build a generic sequence meeting the dense sets {p : p ∈ S_{e} ∨ ∀q ≤ p(q ∉ S_{e})} = D_{e,i} for all Σ_{n} in C_{i} subsets S_{e,i} of P for i ∈ {0, 1˙} as in the proof of Proposition 3.2.13.

The point is that as both C_{i} are low, 0′ can uniformly compute a density function for all of these sets. The argument for lowness is now exactly as above.

Notes: Forcing in arithmetic was introduced in Feferman [1965]. It has since been used in various formulations by many people. Hinman [1969] introduced a version of n-genericity. Two important early papers applying forcing to degree theory are Jockusch [1980] in which many of the results of this section appear for the special but typical case of Cohen forcing and Jockusch and Posner [1978]. A systematic development of degree theory based on forcing was first presented in Lerman [1983]. Our approach attempts to both simplify and generalize previous versions. A very similar version has been presented in Cai and Shore [2012].

3.3 Embedding Lattices

We have so far studied questions of embedding countable partial orders (and usl’s) in D which is itself an usl. Now we know that D is not a lattice (Corollary 2.2.14) but we also know that some pairs of degrees do have greatest lower bounds in D (Theorem 2.2.7). Thus we can ask which lattices can be embedded in D preserving the full lattice structure. We now prove that every countable lattice can be embedded in D.

Theorem 3.3.1 (Lattice Embedding Theorem) Every countable lattice L with least element 0 is embeddable in D preserving the lattice structure and 0.

For later convenience, we actually want to prove an a priori stronger statement about partial lattices.

Definition 3.3.2 A partial lattice L is a partial order ≤_{L} on its domain L together with partial functions ∧, ∨ which satisfy the usual definitions when defined, i.e. if x ∧ y = z then z is the greatest lower bound (glb) of x and y in ≤_{L}; if x ∨ y = z then z is the least upper bound (lub) of x and y in ≤_{L}. We say that L is recursive (in A) if L and ≤_{L} are recursive (in A) and ∨ and ∧ are recursive (in A) functions on L.

Now, actually every partial lattice can be embedded into a lattice.

Theorem 3.3.3 If L is a partial lattice with least element 0 and greatest element 1 then there is a lattice L̂ and an embedding f : L → L̂ which preserves 0, 1, order and all meets and joins that are defined in L̇.

Proof. Consider the lattice I of nonempty ideals of L, i.e. nonempty subsets I of L closed downward and under join in L (when defined). The ordering on I is given by set inclusion. Meet is set intersection and the join of I_{1} and I_{2} is the smallest ideal containing both of them. The map that sends x ∈ L to I_{x} = {y ∈ L|y ≤_{L} x}, the principle ideal generated by x, is the desired embedding into the sublattice L̂ of I generated by the principle ideals.

Thus as far as an embedding theorem is concerned, it may seem that there is no reason to use partial lattices but both effectiveness considerations and convenience come into play. It is certainly often more convenient to specify a partial lattice than to decide all the meets and joins. Thus we state our theorem for partial lattices.

Theorem 3.3.4 (Partial Lattice Embedding) If L is a partial lattice recursive in A with least element 0 and greatest element 1 then there is an embedding f : L → D with f(0) = 0 (or with f(0) = deg A) which preserves order and all meets and joins that are defined in L̇. Moreover, for x ∈ L, f(x) is uniformly recursive in f(1), in the sense that we have sets G_{x} of degree f(x) which are uniformly recursive in f(1) ≥_{T} A.

To prove Theorem 3.3.4, we need some lattice theory. In particular, we use a type of lattice representations called lattice tables.

Definition 3.3.5 A lattice table for the partial lattice L is a collection, Θ, of maps α : L → ℕ such that for every x, y ∈ L and α, β ∈ Θ

1. α(0) = 0.

2. If x ≤_{L} y and α(y) = β(y) then α(x) = β(x).

3. If x ≰_{L} y then there are α, β ∈ Θ such that α(y) = β(y) but α(x) ≠ β(x).

4. If x ∨ y = z, α(x) = β(x) and α(y) = β(y) then α(z) = β(z).

5. If x ∧ y = z and α(z) = β(z) then there are γ_{1}, γ_{2}, γ_{3} ∈ Θ such that α(x) = γ_{1}(x), γ_{1}(y) = γ_{2}(y), γ_{2}(x) = γ_{3}(x), γ_{3}(y) = β(y). Such γ_{i} are called interpolants for α and β (with respect to x, y and z).

Notation 3.3.6 We define equivalence relations on Θ for each x ∈ L by α ≡_{x} β if and only if α(x) = β(x). For sequences p, q from Θ of length n and x ∈ L, we say p ≡_{x} q if p(k) ≡_{x} q(k) for every k < n. In general, we say an equivalence relation E on a set S is larger or coarser than another one Ê if for every (∀a, b ∈ S)(a ≡Ê b ⇒ a ≡_{E} b). Similarly, E is finer or smaller than Ê if (∀a, b ∈ S)(a ≡_{E} b ⇒ a ≡Ê b). With this ordering on equivalence relations, the lub of E and Ê is simply their intersection. Their glb is the smallest equivalence class on S that contains their union. This is also the transitive closure of their union under the two relations.

The conditions of Definition 3.3.5 can now be restated in terms of these equivalence relations:

1. α ≡_{0} β for all α and β and so ≡_{0} is the coarsest congruence class, i.e. the one identifying all elements.

2. If x ≤ y then α ≡_{y} β implies α ≡_{x} β for all α and β and so ≡_{x} is larger than ≡_{y}.

3. If x ≰_{L} y then there are α and β such that α ≡_{y} β but α ≢_{x} β and so ≡_{x} is not larger than ≡_{y}.

4. If x ∨ y = z and α ≡_{x} β and α ≡_{y} β then α ≡_{z} β and so ≡_{z} is the glb of ≡_{x} and ≡_{y}.

5. If x ∧ y = z then there are γ_{1}, γ_{2}, γ_{3} ∈ Θ such that α ≡_{x} γ_{1} ≡_{y} γ_{2} ≡_{x} γ_{3} ≡_{y} β. So ≡_{z} is certainly contained in the lub of ≡_{x} and ≡_{y}. It is part of the theorem that we can arrange it so that chains of length three suffice to generate the entire transitive closure.

Thus a lattice table Θ produces a representation by equivalence relations with the dual ordering. A reason for reversing the order is that D is only an uppersemilattice. So joins always exist and we want them to correspond to the simple operation on equivalence relations of intersection. On the other hand, meets do not always exist and they then correspond to lub on equivalence relations which requires work to construct. Note that α(1) uniquely determines each α ∈ Θ, i.e. ≡_{1} is the finest congruence, i.e. equality which makes all elements distinct.

We now prove our representation theorem in terms of lattice tables.

Theorem 3.3.7 (Representation Theorem) If L is a recursive (in A) partial lattice with 0, 1 then there is a uniformly recursive (in A) lattice table Θ for L.

Proof. Define β_{x,i} for x, y ∈ L, i = 0, 1 by

β_{x,0}(y) = \begin{cases}⟨x, 0⟩ if y ≠ 0 \\ 0 if y = 0 \end{cases} β_{x,1}(y) = \begin{cases}β_{x,0}(y) if y ≤_{L} x \\ ⟨x, 1⟩ if y ≰_{L} x \end{cases}

The set of these β_{x,i} satisfy (1), (2), (3) and (4). We now want to sequentially close off under adding interpolants as required in (5) for each relevant instance . To do so, we have some dovetailing procedure which does the following. Consider x ∧ y = z and α ≡_{z} β. We want to add γ_{1}, γ_{2}, γ_{3} as required in (5) and preserve the truth of (1)-(4) in the expanded set. If x ≤_{L} y or y ≤_{L} x, it is easy to do so just using α and β. If not (i.e. x ≰_{L} y and y ≰_{L} x), then choose new numbers a, b, c, d not used yet and for w ∈ L let

γ_{1}(w) = \begin{cases}α(s) if w ≤_{L} x \\ a if w ≰_{L} x \end{cases} γ_{2}(w) = \begin{cases}γ_{1}(w) if w ≤_{L} y \\ b if w ≤_{L} x and w ≰_{L} y \\ c otherwise \end{cases} γ_{3}(w) = \begin{cases}β(w) if w ≤_{L} y \\ a if w ≤_{L} x and w ≰_{L} y \\ d otherwise \end{cases}

This is a recursive (in A) procedure and it is an Exercise to check that it works.

Exercise 3.3.8 The construction given above provides a lattice table for L.

Now we can turn to the proof of our embedding theorem for partial latices.

Proof (of Theorem 3.3.4). We begin with a lattice table Θ for L which is recursive in L. We define a notion of forcing P with elements p ∈ Θ^{<ω}, the natural ordering p ≤_{P} q if p ⊇ q and V (p) = p. Our generics are then maps G : ℕ →L. Define, for x ∈ L, G_{x} : ℕ → ℕ by G_{x}(n) = G(n)(x). The desired embedding is given by 0 ↦ 0 if we want to preserve 0 and 0 ↦ a if we want to send 0 to a. In either case, for x ≠ 0, x ↦ deg(G_{x}) ∨ a. We use a sufficient amount of genericity to prove that this map really is an embedding that preserves all the required structure. For notational convenience we assume that A is recursive but at times point out the notational changes needed when it is not. We follow the numbering of clauses in Definition 3.3.5.

1. By definition, 0 is preserved by our embedding (or sent to a if so desired). (Note, however, that G_{0}(n) = 0 for all n and so G_{0} is recursive for any L.)

2. Suppose x ≤_{L} y. We must show that G_{x} ≤_{T} G_{y}. Given n, we want to compute G_{x}(n) = G(n)(x). Find any α ∈ Θ such that α(y) = G(n)(y) = G_{y}(n), i.e. α ≡_{y} G(n). One exists because G(n) is one such. As Θ is uniformly recursive we can search for one. Then since x ≤_{L} y and G(n) ≡_{y} α, by Definition 3.3.5(2) we have that G(n) ≡_{x} α so G(n)(x) = α(x) = G_{x}(n).

4 Suppose x ∨ y = z. We must show that G_{z} ≡_{T} G_{x} ⊕ G_{y}. By the preservation of order, G_{z} ≥_{T} G_{x} ⊕ G_{y}, so it suffices to compute G_{z}(n) = G(n)(z) from G_{x}(n) and G_{y}(n). We search for an α ∈ Θ such that α(x) = G(n)(x) and α(y) = G(n)(y), i.e. α ≡_{x,y} G(n). There is one and we can find it as above. Now as α ≡_{x,y} G(n), α ≡_{z} G(n) by Definition 3.3.5(3), so α(z) = G(n)(z).

We can also say something about the image of 1 under the embedding. Given n, G_{1}(n) = G(n)(1) so G_{1} ≡_{T} G since by Definition 3.3.5(2) for any α ∈ Θ, α(1) determines α uniquely and uniformly recursively. Thus the greatest degree in the embedding is the degree of the generic G (G ⊕ A when L is not recursive).

Until this point, we have not used any genericity. We now turn to nonorder and infimum.

3 Suppose x ≰ y. We want to prove that Φ_{e}^{G_{y}} ≠ G_{x} for every e. Suppose that G is 1-generic (over A) and consider the sets

S_{e} = {p ∈ Θ^{<ω} : (∃n)[Φ_{e}^{p_{y}}(n) ↓≠ p_{x}(n)]}

where p_{x} ∈ ω^{<ω} is defined in the obvious way by p_{x}(m) = p(m)(x). S_{e} ∈ Σ_{1} because given σ we can compute p(n)(x) (since Θ is uniformly recursive ). Therefore, the 1-genericity of G implies that there is a p ∈ G ∩ S_{e} or there is a p ∈ G no extension of which is in S_{e}. Suppose p ∈ G ∩ S_{e}, then Φ_{e}^{G_{y}}(n) ≠ G_{x}(n) as p_{y} ⊂ G_{y} and p_{x} ⊂ G_{x} and we are done. Otherwise, no extension of p is in S_{e}. Suppose then, for the sake of a contradiction, that Φ_{e}^{G_{y}} = G_{x}. Let α and β be as in Definition 3.3.5(3) for x and y. By the obvious density of the sets D_{n} = {p|∃m > n(p(m) = α} and the 1-genericity of G, there is a q ≤ p and an m > |p| such that q(m) = α and q ∈ G. Moreover as Φ_{e}^{G_{y}}(m) ↓ by our assumptions, we may also guarantee that Φ_{e}^{q_{y}}(m) ↓ by simply choosing q as a long enough initial segment of G. Consider now the condition q̂ such that q̂(k) = q(k) for k ≠ m and q̂(m) = β. Our choice of α, β and q guarantees that q̂ ≤ p, q ≡_{y} q̂ and q ≢_{x} q̂. Thus Φ_{e}^{q_{y}}(m) ↓= Φq̂_{y} ; e(m) ↓ but q_{x}(m) ≠ q̂_{x}(m). So one of q and q̂ is in S_{e} by definition for the desired contradiction.

5 Suppose that x ∧ y = z and Φ_{e}^{G_{x}} = Φ_{e}^{G_{y}} = D. We want to prove that D ≤_{T} G_{z}. Now the assertion that Φ_{e}^{G_{x}} and Φ_{e}^{G_{y}} are total and equal is Π_{2}. So let us assume that G is 2-generic (over A) and so there is (by Theorem 3.2.12) a p ∈ G such that p forces this sentence. Thus for each n and q ≤ p, there is an r ≤ q such that r ⊩ Φ_{e}^{G_{x}}(n) ↓= Φ_{e}^{G_{y}}(n) ↓. We now wish to compute D(n) from G_{z}. As above, we can recursively in G_{z} find a q ≤ p such that q ⊩ Φ_{e}^{G_{x}}(n) ↓= Φ_{e}^{G_{y}}(n) ↓ and q_{z} ⊂ G_{z} (since some initial segment of G does this). We claim that Φ_{e}^{q_{x}}(n) = D(n). To see this consider a t ∈ G such that t ≤ p, t_{z} ⊆ G_{z} and t ⊩ Φ_{e}^{G_{x}}(n) ↓= Φ_{e}^{G_{y}}(n) ↓. Necessarily, Φ_{e}^{t_{x}}(n) ↓= Φ_{e}^{t_{y}}(n) ↓= D(n) and t ≡_{z} q. By suitably lengthening t or q we may assume that they have the same length m. Let l = |p| < m. We now use both the interpolants guaranteed by Definition 3.3.5(5) and the fact that p forces Φ_{e}^{G_{x}} and Φ_{e}^{G_{y}} to be total and equal.

For each k with l ≤ k < m we choose interpolants γ_{k,i} (for i ∈ {1, 2, 3}) between q(k) and t(k) as in Definition 3.3.5(5). We let q_{i}(k) = p(k) = t(k) for k < l and q_{i}(k) = γ_{k,i} for l ≤ k < m. We also let q_{0} = q and q_{4} = t. So q = q_{0} ≡_{x} q_{1} ≡_{y} q_{2} ≡_{x} q_{3} ≡_{y} q_{4} = t. We now extend the q_{i} in turn to make them force convergence at n but remain congruent modulo z. In fact, we make a single extension for all of them. By the fact that p ⊩ Φ_{e}^{G_{x}} = Φ_{e}^{G_{y}} and q_{1} ≤ p, we can find an r_{1} = q_{1}ˆ s_{1} such that r_{1} ⊩ Φ_{e}^{G_{x}}(n) ↓= Φ_{e}^{G_{y}}(n) ↓. We now extend q_{2}ˆ s_{1} to r_{2} = q_{2}ˆ s_{1}ˆ s_{2} such that r_{2} ⊩ Φ_{e}^{G_{x}}(n) ↓= Φ_{e}^{G_{y}}(n) ↓. Finally we extend q_{3}ˆ s_{1}ˆ s_{2} to r_{3} = q_{3}ˆ s_{1}ˆ s_{2}ˆ s_{3}. Let s = s_{1}ˆ s_{2}ˆ s_{3} and consider q_{i}ˆ s for i ≤ 4. Looking at each successive pair we see by the alternating (between x and y) congruences that they all force the same equal values for Φ_{e}^{G_{x}}(n) and Φ_{e}^{G_{y}}(n). Thus, by transitivity of equality and permanence of computations under extension, Φ_{e}^{q_{x}}(n) = Φ^{t_{x}}(n) = D(n) as required.

By Theorem 3.2.5, the embedding of L given by the generic G produced in Theorem 3.3.4 can be taken to be into the degrees below the double jump of L. We can improve this by a direct construction recursive in 0′.

Exercise 3.3.9 If L is a recursive lattice with 0 and 1 then it can be embedded in D(≤0′) preserving 0. Moreover, we may take the image of 1 to be low and the image of L to be uniformly recursive in it. This result relativizes to an arbitrary L and (deg L)′. Hint: Do a direct construction of the sort done in Chapter 2 following the proof above but when it relies on 2-genericity to guarantee the existence of extensions forcing some convergence ask 0′ instead if they exist and if not terminate the search and declare the requirement satisfied (by nonconvergence).

Alternatively we may use the following Exercise.

Exercise 3.3.10 The proof given above that infima are preserved used 2-genericity. Give a proof that uses only 1-genericity. Indeed, given a partial recursive lattice L and any 1-generic G for the recursive notion of forcing P of the proof of Theorem 3.3.4 the map from L to the degrees below that of G given by x ⟼ deg(G_{x}) is a lattice embedding. This implies the results of the previous exercise. More specifically, G is low. Hint: Suppose that x ∧ y = z and Φ_{e}^{G_{x}} = Φ_{e}^{G_{y}} = D. Consider the Σ_{1} sets T_{e} = {t|∃n(Φ_{e}^{t_{x}}(n) ↓≠ Φ_{e}^{t_{y}}(n) ↓} and S_{e} = {s : ∃n, ∃q, s_{0}, s_{2}, r(of the same length) Φ_{e}^{q_{x}}(n) ↓= Φ_{i}^{q_{y}}(n) ↓≠ Φ_{e}^{r_{x}}(n) ↓= Φ_{i}^{r_{y}}(n) ↓ and q ≡_{x} s_{0} ≡_{y} s ≡_{x} s_{2} ≡_{y} r so q ≡_{z} r} restricted to the conditions extending a t witnessing the 1-genericity condition for T_{e}. This also supplies a proof for Exercise 3.3.9.

Exercise 3.3.11 If L is a recursive lattice with 0 and 1 then it can be embedded into D(≤ g) preserving both 0 and 1 for any Cohen 1-generic g. Hint: Show that for any infinite recursive set Θ, the degrees which are 1-generic for Θ^{<ω} are the same as the Cohen 1-generic degrees by defining a recursive isomorphism between Θ^{ω} and the elements of 2^{ω} with infinitely many values equal to 1 that “preserves denseness”.

Next, we disprove the homogeneity conjecture for D′ = ⟨D, ≤_{T} ,′ ⟩. This conjecture, like the analogous one for D, was based on the empirical fact that every theorem about the degrees or the degrees with the jump operator relativizes and so if true in D (or D′) then it is true in D(≥ c) or D′(≥ c) for every c. The conjectures asserted then that D ≅ D(≥c) and even that D′ ≅ D′(≥c) for every degree c.

Theorem 3.3.12 There is c such that (D, ≤,′) ≇ (D(≥ c), ≤,′).

Proof. If not, then [0, 0′′] ≅ [c, c′′] for every c. To find a contradiction, it is sufficient (by Theorem 3.3.4) to find partial lattice recursive in c which cannot be embedded in [0, 0′′].

Now it is a fact of lattice theory that there are continuum many finitely generated lattices indeed ones with only four generators. We supply ones with seven generators in the next section. On the other hand, only countably many finitely generated lattices can be embedded in [0, 0′′] since the lattice embedded is determined by the image of its generators. Thus we may choose an L which is finitely generated but not embeddable in [0, 0′′]. L has some degree, say c. By theorem, L is embeddable in [c, c′′]. Thus [0, 0′′] ≇ [c, c′′] as required.

Corollary 3.3.13 The homogeneity conjecture for D′ fails.

Notes: Representations by equivalence relations is an old subject in lattice theory. In degree theory they were first used to embed all finite lattices in D and certain special lattices as initial segments of D by Thomason [1970]. The version used here in terms of tables is particularly suited to degree theory and was introduced in Lerman [1971] and extensively presented in his [1983]. Their use to embed lattices not as initial segments appears in Shore [1982] where it is used to prove Theorem 3.3.1 and Exercise 3.3.9 and various strengthenings of Theorem 3.3.12. The first proof of Theorem 3.3.12 and so the failure of the homogeneity conjecture for D′ is due to Feiner [1970] but it depended on the construction of Σ_{1} but not recursively presented Boolean algebras and known but much more complicated embeddings of lattices as initial segments of D. Exercises 3.3.10 and 3.3.11 and some aspects of our treatment of lattice tables come from Greenberg and Montalbán [2003].

3.4 Effective Successor Structures

For later applications, we would like to have a specific family of size 2^{ℵ_{0}} of finitely generated partial lattices that code arbitrary sets S in a relatively simple way and can be embedded below various degrees related to S in ways that we specify later. These partial lattices begin with ones that are effective successor structures.

Definition 3.4.1 An effective successor structure is a partial lattice generated by five elements e_{0}, e_{1}, d_{0}, f_{0}, f_{1} with (for each n ≥ 0) relations

(d_{2n} ∨ e_{0}) ∧ f_{1} = d_{2n+1} (d_{2n+1} ∨ e_{1}) ∧ f_{0} = d_{2n+2}.

where the d_{n} are all distinct (and pairwise incomparable). For any fixed S ⊆ ω, we define the class of effective successor structures L_{S}, by adding on two additional generators g_{0} and g_{1} and the additional relations

n ∈ S ⇔ d_{n} ≤ g_{0}, g_{1}.

It is clear that the class of effective successor structures L_{S} provides us with continuum many different finitely generated partial lattices (at least one for each S ⊆ ω) that we can use in the proof of Theorem 3.3.12.

Thus, we have represented S in a partial lattice L_{S}. For later applications we now analyze the relations between the complexities of S and L_{S} or more precisely its embeddings in D. To make these relations as simple as possible we want to impose some additional conditions on our partial lattices and slightly modify the coding procedure for S.

Definition 3.4.2 A nice effective successor structure is a partial lattice extension of an effective successor structure gotten by adding a least element 0 and additional elements b_{0}, b_{1} and d̂_{n} for each n ∈ ω such that b_{0} ≱ b_{1} and (∀n ∈ ω)(d_{n} ∨ b_{0} ≥ b_{1} & d_{n} ∧ d̂_{n} = 0 & (∀m ≠ n)(d̂_{n} ≥ d_{m}).

Note that any embedding f of a nice effective successor structure in D makes the images f(d_{n}) of d_{n} very independent and so it can be extended to an L_{S} representing S as above for any S by adding on an exact pair for the ideal generated by the f(d_{n}) for n ∈ S. We now want to analyze the complexity of sets coded by a slightly different method in such substructures of D.

Proposition 3.4.3 If b_{0},b_{1}, e_{0}, e_{1}, d_{0}, f_{0}, f_{1}≤a are the generators in a nice effective successor structure (necessarily contained in D(≤a)) and g_{0}, g_{1}≤a then we say that g_{0}, g_{1} code the set Ŝ = {n|∃x(x∨b_{0}≥b_{1} & x≤ d_{n}, g_{0}, g_{1}}. In this situation, Ŝ ∈ Σ_{3}^{A}.

Proof. We first compute the complexity of the structure D(≤a). We represent this structure in terms of indices i such that Φ_{i}^{A} is total. (So this assigns countably many indices to each degree.) This set is Π_{2}^{A}. The order of Turing reducibility on these indices is given by k ≤_{T} i if an only if

∃j(Φ_{j}^{Φ_{i}^{A}} = Φ_{k}^{A}) ⇔ ∃j∀n∃s(Φ_{j,s}^{Φ_{i,s}^{A}}(n) = Φ_{k,s}^{A}(n))

and so is Σ_{3}^{A}. (Thus the relation that i and k represent the same degree is also Σ_{3}^{A}. We can now choose a unique representative from the class of indices coding a single set Φ_{i}^{A} uniformly in a Σ_{3}^{A} way by taking the j such that ⟨i, j⟩ is the first enumerated by A′′ in a fixed enumeration of the pairs such that Φ_{i}^{A} ≡_{T} Φ_{j}^{A}.)

Next note that there is a recursive function h on indices such that Φ_{i}^{A} ⊕ Φ_{j}^{A} = Φ_{h(i,j)}^{A}. So the function corresponding to join is recursive on the indices. Now infimum would naturally be Π_{4} on the indices but we have added enough additional structure so as to be able of avoid using infima directly in the recovery of Ŝ.

By recursion on n, we define positive Σ_{1} formulas φ_{n} in ≤, ∨ (i.e. no negation symbols are used in the formula which has ≤ and ∨ but not ∧ in it) such that D or equivalently D(≤a) satisfies φ_{n}(x) if and only if 0 < x ≤ d_{n}.

φ_{0}(x) ≡ x = d_{0}; φ_{2n+1}(x) ≡ x ∨ b_{0} ≥ b_{1} & ∃y(φ_{2n}(y) & x ≤ (y ∨ e_{0}), f_{1});
φ_{2n+2}(x) ≡ x ∨ b_{0} ≥ b_{1} & ∃y(φ_{2n+1}(y) & x ≤ (y ∨ e_{1}), f_{0})

It is easy to see by induction that, for any degree x, φ_{n}(x) is true in D or equivalently in D(≤a) if and only if 0 < x ≤_{T} d_{n} (Exercise). By our analysis of the complexity of the structure D(≤a), the φ_{n} are uniformly Σ_{3}^{A} on the indices.

Note now that n ∈ Ŝ if and only if there is an index i such that Φ_{i}^{A} ⊕ C ≥ B, φ_{n}(Φ_{i}^{A}) and Φ_{i}^{A} ≤_{T} G_{0}, G_{1} where we are using G_{0,}G_{1}, C and B for some fixed Φ_{g_{0}}^{A}, Φ_{g_{1}}^{A}, Φ_{b_{0}}^{A} and Φ_{b_{1}}^{A} of degrees g_{0}, g_{1},b_{0} and b_{1}, respectively. By the uniformity of the φ_{n} being Σ_{3}^{A}, this suffices to show that Ŝ is Σ_{3}^{A}.

Remark 3.4.4 If g_{0}, g_{1} ≤ a are an exact pair for the ideal generated by {d_{n}|n ∈ S} then the set they code is {n|d_{n} ≤ g_{0}, g_{1}} (Exercise). Thus if we can show for some embedding of a nice effective successor structure below a that all Σ_{3}^{A} sets are coded by an exact pair below a then we know that the sets coded in this structure by pairs below a are precisely those which are Σ_{3}^{A}.

3.4. EFFECTIVE SUCCESSOR STRUCTURES 37

Notes: The conditions on (nice) effective successor structures and their use in coding arithmetic come from Shore [1981] as does Proposition 3.4.3.

38 CHAPTER 3. FORCING IN ARITHMETIC AND RECURSION THEORY

The Theories of D and D(≤ 0′)

In the previous section, we talked about embeddability issues. We need to consider more in order to understand the theory of the degrees. We now approach theorems which say that the theories of (i.e. the sets of sentences true in) D and D(≤ 0′) are as complicated as possible. More precisely they are of the same Turing (even 1−1) degree as true second and first order arithmetic, respectively. The method used is interpreting arithmetic in the degree structures.

4.1 Interpreting Arithmetic

We say that we can interpret (true first order) arithmetic in a structure S with parameters p̄ if there are formulas φ_{D}(x), φ_{+}(x, y, z), φ_{×}(x, y, z), φ_{<}(x, y) all with parameters p̄ and one φ_{c}(p̄) such that for any p̄ ∈ S such that S ⊨φ_{c}(p̄) the structure M(p̄) with domain D(p̄) = {x ∈ S|S ⊨ φ_{D}(x)} and relations +, × and < defined by φ_{+}(x, y, z), φ_{×}(x, y, z), φ_{<}(x, y), respectively, is isomorphic to true arithmetic, i.e. the natural numbers ℕ with relations given by +, × and < respectively and there is at least one such p̄. (We are writing the operations + and × in relational form +(x, y, z) ⇔ x + y = z and similarly for ×.) In this situation, the theory of true first order arithmetic, T h(ℕ), i.e. the set of sentences of arithmetic in this language true in ℕ, is reducible to T h(S), the set of sentences in the language of S true in S. Indeed, the reduction is a 1 − 1 reduction. More precisely there is a recursive function T taking sentences φ of arithmetic to ones φ^{T} of S such that ℕ ⊨ φ ⇔S ⊨∀p̄(φ_{c}(p̄) → φ^{T}). The definition of T is given by induction. Atomic formulas +(x, y, z), ×(x, y, z) and x < y are taken to φ_{+}(x, y, z), φ_{×}(x, y, z), φ_{<}(x, y), respectively. A formula of the form ∃wψ is taken to ∃w(φ_{D}(w) & ψ^{T}) while ∀wψ is taken to ∀w(φ_{D}(w) → ψ^{T}). It should be clear (and, if not, routine to prove) by induction that if M(p̄) ≅ ℕ then, any sentence φ (of the relational formulation of arithmetic) is true in ℕ if and only if φ^{T} is true in M(p̄). Thus if φ_{c}(p̄) guarantees that M(p̄) ≅ ℕ, we have the desired recursive reduction from T h(ℕ) to T h(S).

40 CHAPTER 4. THE THEORIES OF D AND D(≤ 0′)

A second order structure is a two sorted structure (i.e. one with two sorts of variables say x and X in its language and two domains U and W ⊆ 2^{U} over which the two types of variable range, respectively. This provides the semantics for the quantifiers ∃x, ∀x, ∃X, and ∀X in the obvious way). The language also has relation symbols and relations on the first sort as in a standard first order language and structure. In addition, it has one relation x ∈ X between elements of the first sort and ones of the second sort that is interpreted by true membership. We say that it is a true second order structure if W = 2^{U}, i.e. the second order quantifiers range over all subsets of the domain U of the usual first order structure. It is a model of true second order of arithmetic if U = ℕ, the first order language is that of arithmetic as above and W = 2^{ℕ}. (Note that as with true first order arithmetic there is, up to isomorphism, only one model of true second order of arithmetic.)

We extend our notion of an interpretation of arithmetic to second order structures by adding a formula φ_{S}(x, ȳ) which implies φ_{D}(x). For each tuple of degrees ȳ, we are thinking of φ_{S}(x, ȳ) as defining the set of n ∈ ℕ such that φ_{S}(d_{n}, ȳ) holds for d_{n} the degree corresponding to the nth element of the model in the ordering given by φ_{<}, We then translate the second order quantifiers by replacing each atomic formula x ∈ X by φ_{S}(x, ȳ_{X}), ∃Xψ by ∃ȳ_{X}ψ^{T} and ∀Xψ by ∀ȳ_{X}ψ^{T} where we are thinking of the ȳ_{X} as coding the set X. If, as before, φ_{c}(p̄) guarantees that the associated first order structure is isomorphic to ℕ and, in addition, as ȳ ranges over S^{n} (where n is the length of ȳ) the sets Sȳ = {x|φ_{S}(x, ȳ)} range exactly over all subsets of D(p̄) then it clear (or routine to prove) that, for any second order sentence φ of arithmetic, φ is satisfied in the true second order model of arithmetic if and only if S ⊨ φ_{c}(p̄) → φ^{T}. In this case we again have a recursive reduction: a sentence ψ of second order arithmetic is “true”, i.e. satisfied in the model of true second order of arithmetic if an only if S ⊨∀p̄(φ_{c}(p̄) → ψ^{T}).

Our goals now are to prove that there are interpretations of true second order arithmetic in D and true first order arithmetic in D(≤0′). The first we complete in this chapter. We actually show in the next section that we can code and quantify over all countable relations on D in a first order way by quantifying over elements of D. From this result is routine to get a coding as described here of second order arithmetic in D. The results and analysis need for D(≤ 0′) are mostly contained in this chapter but the proof also requires material from the next chapter as well. In each case, the correctness condition φ_{c}(p̄) includes the translations (via T) of the axioms of a finite axiomatization of arithmetic such as Robinson arithmetic that is strong enough to guarantee that any model of the axioms in which the ordering < on its domain is isomorphic to ω is actually isomorphic to ℕ. The crucial steps are then to prove that there are p̄ such that M(p̄) ≅ ℕ and that there is a formula φĉ which guarantees that the ordering of M(p̄) (given by φ_{<}(p̄)) is isomorphic to ω.

We begin with D and coding countable subsets of pairwise incomparable degrees by using Slaman-Woodin forcing. We then show how to deal with arbitrary countable relations on degrees.

4.2. SLAMAN-WOODIN FORCING AND T H(D) 41

4.2 Slaman-Woodin Forcing and T h(D)

Let S = {c_{i}|i ∈ ℕ} be a countable set of pairwise incomparable degrees. We want to make S definable in D from three parameters c, g_{0} and g_{1}. The definition is that S is the set of minimal degrees x ≤ c such that (x ∨ g_{0}) ∧ (x ∨ g_{1}) ≠ x in the strong sense that there is a d ≤ x ∨ g_{0}, x ∨ g_{1} such that d ≰ x.

Theorem 4.2.1 For any set S = {C_{0}, C_{1}, …, } of pairwise Turing incomparable subsets of ℕ let C = ⊕C_{i}. There are then G_{0}, G_{1} and D_{i} such that, for every i ∈ ℕ and j < 2, D_{i} ≤_{T} C_{i} ⊕ G_{j} while D_{i} ≰_{T} C_{i}. Moreover, the C_{i} are minimal with this property among sets recursive in C in the sense that for any X ≤_{T} C for which there is a D such that D ≤_{T} X ⊕ G_{j} (j < 2) but D ≰_{T} X there is an i such that C_{i} ≤_{T} X. Indeed, there is a notion of forcing P recursive in C such that any 2-generic computes such G_{0} and G_{1}. Thus for c_{i}, c and g_{0}, g_{1} the degrees of C_{i}, C, G_{0} and G_{1} respectively, the set S = {c_{i}|i ∈ ℕ} is definable in D from the three parameters c, g_{0} and g_{1}.

Proof. Without loss of generality we may assume that each C_{i} is recursive in any of its infinite subsets: simply replace C_{i} by the set of binary stings σ such that σ ⊂ C_{i}. The point of this assumption is that to compute C_{i} from some X it suffices to show that X can enumerate an infinite subset of C_{i} as then there is an infinite subset of this set recursive in X and so then is C_{i}.

We build G_{i} as required by forcing in such a way as to uniformly define the D_{i} from G_{0} and C_{i} and such that D_{i} is also recursive in G_{1} ⊕ C_{i} (although not uniformly). We begin with the coding scheme that says how we compute the D_{i}.

Let {c_{i,0}, c_{i,1}, …} list C_{i} in increasing order. Our plan is that D_{i}(n) should be G_{0}(c_{i,n}) and so the D_{i} are uniformly recursive in G_{0} ⊕ C_{i}. We call ⟨i, k⟩ a coding location for C_{i} if k ∈ C_{i}. To make sure that D_{i} ≤_{T} G_{1} ⊕ C_{i} as well, we guarantee that G_{0}^{[i]}(c_{n}) = G_{1}^{[i]}(c_{n}) for all but finitely many n. We now turn to our notion of forcing P.

The forcing conditions p are triples of the form ⟨p_{0}, p_{1}, F_{p}⟩ where p_{0}, p_{1} ∈ 2^{<ω}, |p_{0}| = |p_{1}|, and F_{p} is a finite subset of ω. We let the length of condition p be |p| = |p_{0}| = |p_{1}|. Refinement is defined by

p ≤ q ⇔ p_{0} ⊇ q_{0}, p_{1} ⊇ q_{1}, F_{p} ⊇ F_{q}, and
if i ∈ F_{q} and |q| < ⟨i, c_{i,n}⟩ ≤ |p| then p_{0}(⟨i, c_{i,n}⟩) = p_{1}(⟨i, c_{i,n}⟩).

This is a finite notion of forcing with extension recursive in C. The function V is defined in the obvious way: V (p) = p_{0} ⊕p_{1} so our generic object defined from a filter G is G_{0} ⊕G_{1} where G_{k} = ∪{p_{k}|p ∈ G}. We use G_{k} in our language to mean the k^{th} coordinate the generic object. Note that C ≤_{T} P as well (Exercise) and so n-generic for P means generic for all Σ_{n}^{C} sets.

Note that for any φ ∈ Σ_{1}, if p ⊩ φ then (p_{0}, p_{1}, ∅) ⊩ φ as V (p) = V (⟨p_{0}, p_{1}, ∅⟩. So if q ≤ p and q ⊩ ψ for ψ ∈ Σ_{1} then (q_{0}, q_{1}, F_{P}) ⊩ ψ as well.

Suppose that G is 1-generic for P. It is immediate from the definition of ≤_{P} and the density of the recursive (in P) sets {p|i ∈ F_{p}} that G_{0}^{[i]} and G_{1}^{[i]} differ on at most finitely many n ∈ C_{i}. (If i ∈ F_{p} and p ∈ G then G_{0}^{[i]}(m) = G_{1}^{[i]}(m) for m ∈ C_{i} and m > |p|.) Thus D_{i} ≤_{T} G_{1} ⊕ C_{i} as required.

We next show that D_{i} ≰_{T} C_{i}, that is Φ_{e}^{C_{i}} ≠ D_{i} for each e. Suppose for the sake of a contradiction that D_{i} = Φ_{e}^{C_{i}} for some e (and so in particular Φ_{e}^{C_{i}} is total). Consider the Σ_{1}^{C} set

S_{i,e} = {p : ∃m(p_{0}(⟨i, c_{i,m}⟩) ≠ Φ_{e}^{C_{i}}(m))}.

The S_{i,e} are dense because if p ∈ P and m is such that ⟨i, c_{i,m}⟩ > |p| then we can define q ≤ p by F_{q} = F_{p} and for |p| ≤ j ≤ ⟨i, c_{i,m}⟩ put q_{0}(j) = q_{1}(j) = 1 − Φ_{e}^{C_{i}}(m). So q ∈ S_{i,e} and q ≤ p as desired. Thus, there is a p ∈ G ∩ S_{i,e} for which

D_{i}(m) = G_{0}(⟨i, c_{i,m}⟩) = p_{0}(⟨i, c_{i,m}⟩) ≠ Φ_{e}^{C_{i}}(m),

contradicting D_{i} = Φ_{e}^{C_{i}}.

Now, we have to ensure the minimality of the C_{i}. In other words, we want to prove that if

Φ_{e}^{X⊕G_{0}} = Φ_{i}^{X⊕G_{1}} = D,  X ≤_{T} C  and D ≰_{T} X

then C_{k} ≤_{T} X for some k.

Consider the sentence φ that says that Φ_{e}^{X⊕G_{0}} and Φ_{i}^{X⊕G_{1}} are total and equal. It is Π_{2} in C (because X ≤_{T} C) and true of G = G_{0} ⊕ G_{1}. So, if we now assume that G is 2-generic, there is p ∈ G such that p ⊩ φ. Suppose first that ¬∃n(∃σ ⊇ p_{0})(∃τ ⊇ p_{0})[Φ_{e}^{X⊕σ}(n) ↓≠ Φ_{e}^{X⊕τ}(n) ↓]. Then we claim D is computable from X. To compute D(n) search for any σ ⊇ p_{0} such that Φ_{e}^{X⊕σ}(n) ↓ and output this value as the answer. There is such a σ ⊂ G_{0} by the totality of Φ_{e}^{X⊕G_{0}}. Our assumption that there is no pair of extensions of p_{0} that give two different answers implies that any such σ gives the answer Φ_{e}^{X⊕G_{0}}(n) = D(n).

On the other hand, suppose there is such a splitting for n given by p_{0}ˆ σ, p_{0}ˆ τ. By extending one of σ and τ if necessary, we may assume that |σ| = |τ|. We claim that p_{0}ˆ σ and p_{0}ˆ τ differ at a coding location ⟨k, c_{k,m}⟩ for some k ∈ F_{p}. Let τ′ be such that

Φ_{i}^{X⊕(p_{1}ˆ τˆ τ′)}(n) ↓= Φ_{e}^{X⊕(p_{0}ˆ τˆ τ′)}(n) ↓ .

There must be such a τ′ as (p_{0}ˆ τ, p_{1}ˆ τ, F_{p}) ≤ p and so it has a further extension q = (p_{0}ˆ τˆ ρ_{0}, p_{1}ˆ τˆ ρ_{1}, F_{p}) which forces Φ_{e}^{X⊕G_{0}}(n) ↓= Φ_{i}^{X⊕G_{1}}(n) ↓. Next consider q̂ = (p_{0}ˆ τˆ ρ_{0}, p_{1}ˆ τˆ ρ_{0}, F_{p}) ≤ p. It also has an extension (p_{0}ˆ τˆ ρ_{0}ˆ μ_{0}, p_{1}ˆ τˆ ρ_{0}ˆ μ_{1}, F_{p}) ⊩ Φ_{e}^{X⊕G_{0}}(n) ↓= Φ_{i}^{X⊕G_{1}}(n) ↓. It is now clear that τ′ = ρ_{0}ˆ μ_{1} has the desired property. Next, consider the condition q = (p_{0}ˆ σˆ τ′, p_{1}ˆ τˆ τ′, F_{p}). Notice that q ≰ p because:

1. Φ_{e}^{X⊕(p_{0}ˆ σ)}(n) = Φ_{e}^{X⊕(p_{0}ˆ σˆ τ′)}(n) as p_{0}ˆ σˆ τ′ ⊇ p_{0}ˆ σ.

2. Φ_{i}^{X⊕(p_{1}ˆ τˆ τ′)}(n) = Φ_{e}^{X⊕(p_{0}ˆ τ)}(n) by our choice of τ′, but 3. Φ_{e}^{X⊕(p_{0}ˆ σ)}(n) ≠ Φ_{e}^{X⊕(p_{0}ˆ τ)}(n) because n, p_{0}ˆ σ, p_{0}ˆ τ were chosen to be splitting.

Hence, Φ_{e}^{X⊕(p_{0}ˆ σˆ τ′)}(n) ≠ Φ_{i}^{X⊕(p_{1}ˆ τˆ τ′)}(n) and so q does not extend p. However, p_{0}ˆ σˆ τ′ ⊇ p_{0} and p_{1}ˆ τˆ τ′ ⊇ p_{1}, so it must be that p_{0}ˆ σˆ τ′ and p_{1}ˆ τ ˆ τ′ differ at a coding location above |p|. Therefore, p_{0}ˆ σ and p_{0}ˆ τ differ at a coding location ⟨k, n⟩ with k ∈ F_{p}.

We now show that there must be such p_{0}ˆ σ and p_{0}ˆ τ which differ at only one number (which then must be a coding location ⟨k, n⟩ for some k ∈ F_{p}). Suppose σ, τ are strings as above with |σ| = |τ| = ℓ. Let σ = γ_{0}^{0}, γ_{1}^{0}, …, γ_{z}^{0} = τ be a list of strings in {0, 1}^{ℓ} such that γ_{i}^{0}, γ_{i+1}^{0} differ at only one number for each i. Let β be such that Φ_{e}^{X⊕(p_{0}ˆ γ_{1}^{0}ˆ β)}(n) ↓ (such a β exists by the same argument as before). Set γ_{i}^{1} = γ_{i}^{0}ˆ β for each 0 ≤ i ≤ z.

Repeat this process for each j ≤ z. At step j + 1, let β be such that Φ_{e}^{X⊕(p_{0}ˆ γ_{j+1}^{j}ˆ β)}(n) ↓, and set γ_{i}^{j+1} = γ_{i}^{j}ˆ β for each 0 ≤ i ≤ z. At the end, we have strings γ_{0}^{z}, γ_{1}^{z}, …, γ_{z}^{z} such that Φ_{e}^{X⊕(p_{0}ˆ γ_{i}^{z})}(n) ↓ for each i, and p_{0}ˆ γ_{i}^{z}, p_{0}ˆ γ_{i+1}^{z} differ at only one number for each i. Since

Φ_{e}^{X⊕(p_{0}ˆ γ_{0}^{z})}(n) = Φ_{e}^{X⊕(p_{0}ˆ σ)}(n) ≠ Φ_{e}^{X⊕(p_{0}ˆ τ)}(n) = Φ_{e}^{X⊕(p_{0}ˆ γ_{z}^{z})}(n),

there must be an i for which Φ_{e}^{X⊕(p_{0}ˆ γ_{i}^{z})}(n) ≠ Φ_{e}^{X⊕(p_{0}ˆ γ_{i+1}^{z})}(n). The strings p_{0}ˆ γ_{i}^{z}, p_{0}ˆ γ_{i+1}^{z} differ at only one number and it must be a coding location ⟨k, m⟩ for some k ∈ F_{p} as required.

Next, we show that X can find infinitely many coding locations ⟨k, m⟩ for some fixed k ∈ F_{p}. Suppose we want to find such a location ⟨k, m⟩ with m > M. Search for strings p_{0}ˆ σ and p_{0}ˆ τ that agree on the first M positions, differ at only one position, and satisfy Φ_{e}^{X⊕(p_{0}ˆ σ)}(n) ≠ Φ_{e}^{X⊕(p_{0}ˆ τ)}(n). Such strings must exist because we could have started the above analysis at any condition q ∈ G with q ≤ p (so we can find such strings agreeing on arbitrarily long initial segments). The position at which p_{0}ˆ σ and p_{0}ˆ τ differ must be a coding location bigger than M. Since F_{p} is finite, infinitely many of these coding locations must be for the same k. Given this k, X can find infinitely many coding locations ⟨k, c_{k,m}⟩. Hence, X can enumerate an infinite subset of C_{k} and so can compute C_{k} by our initial assumption on the C_{i}.

As 2-genericity sufficed for the proof of the theorem above , we can get the required G_{j} ≤_{T} C′′ and,indeed with (G_{0} ⊕ G_{1})′′ ≡_{T} C′′. We show below (Theorem 4.3.1 and Exercise 4.3.3) that we can do better.

Now we work toward coding arbitrary countable relations on D.

Proposition 4.2.2 If H is Cohen 1-generic over C, then, for any i, j ∈ ω and X, Y ≤ C, if X ⊕ H^{[i]} ≤ Y ⊕ H^{[j]} then i = j and X ≤ Y.

Proof. Suppose that for some e, X, Y ≤_{T} C, Φ_{e}^{Y ⊕H^{[j]}} = X ⊕ H^{[i]} and consider the set

S_{e} = {σ ∈ 2^{<ω} : ∃n (Φ_{e}^{Y ⊕σ^{[j]}}(n) ↓≠ X ⊕ σ^{[i]}(n))}.

S_{e} ∈ Σ_{1}(C) so either there is σ ∈ S_{e} ∩ H or there is σ ⊂ H no extension of which is in S_{e}. The first alternative clearly violates our assumption that Φ_{e}^{Y ⊕H^{[j]}} = X ⊕ H^{[i]} and so there is a σ ⊂ H such that τ ∉ S_{e} for all τ ⊇ σ. Let n = |σ^{[i]}|. If i ≠ j and there were β ⊇ σ^{[j]} such that Φ_{e}^{Y ⊕β}(2n + 1) ↓, we could extend σ to τ such that τ^{[j]} = β and τ^{[i]}(n) = 1 − Φ_{e}^{Y ⊕β}(2n + 1) (as the value of τ^{[i]}(n) is independent of τ^{[j]}. In this case, we have

Φ_{e}^{Y ⊕τ^{[j]}}(2n + 1) ↓≠ τ^{[i]}(n) = (X ⊕ τ^{[i]})(2n + 1)

and so τ ∈ S_{e}, contradicting our choice of σ. Therefore, there can be no β ⊇ σ^{[j]} making Φ_{e}^{Y ⊕β}(2n + 1) converge while Φ_{e}^{Y ⊕H^{[j]}} is total by assumption and σ^{[j]} ⊂ H^{[j]} for a contradiction. Thus i = j.

Next, we show that X ≤_{T} Y. To compute X(n) from Y, search for a τ ⊇ σ such that Φ_{e}^{Y ⊕τ^{[j]}}(2n) converges (such a τ exists because Φ_{e}^{Y ⊕H^{[i]}} is total and σ^{[j]} ⊂ H^{[j]}). Then, as usual, we claim that Φ_{e}^{Y ⊕τ^{[j]}} = (X ⊕ τ^{[i]})(2n) = X(n) for if not, τ ∈ S_{e} and extends σ for a contradiction.

Theorem 4.2.3 Every countable relation R(x_{0}, …, x_{n−1}) on D is definable from parameters. Indeed, if C is a uniform upper bound on representatives C_{i} of the sets with degrees c_{i} in the domain of R as well as of the ⟨C_{j_{0}}, …, C_{j_{n−1}}⟩ such that R(c_{j_{0}}, …, c_{j_{n−1}}) and H is Cohen 1-generic over C then there is a notion of forcing recursive in C ⊕ H such that any 2-generic computes the required parameters. Moreover, for each n there is a formula φ_{n}(x_{0}, …, x_{n−1}, ȳ) with ȳ of length some k > 0 (depending only on n) which includes the clauses that x_{i} ≤ y_{0} for each i < n such that as p̄ ranges over all k-tuples of degrees, the sets of n-tuples of degrees {ā|D ⊨ φ(ā, p̄)} range over all countable n-ary relations on D.

Proof. We take c = deg(C) to be our first parameter. Let H be Cohen 1-generic over C and h_{i,j} be the degree of H^{[⟨i,j⟩]}. We code R using the following countable sets of pairwise incomparable degrees.

H_{i} = {h_{i,j}|j ∈ ℕ} for i < n

F_{i} = {c_{j} ∨ h_{i,j}|j ∈ ℕ} for i < n
R = {h_{0,j_{0}} ∨ h_{1,j_{1}} ∨ ⋯ ∨ h_{n−1,j_{n−1}} : R(c_{j_{0}}, c_{j_{1}}, …, c_{j_{n−1}})}

Each of these sets consists of pairwise incomparable degrees. The first and third by Proposition 3.2.18 that for a Cohen 1-generic H the sets H^{[k]} form a very independent set. (So, for any finite A and B, ∨{x|x ∈A} ≤ ∨{x|x ∈B} if and only if A ⊆ B.) The elements of each F_{i} are pairwise incomparable by Proposition 4.2.2. Our defining formula φ for R is now

&_{i<n}(x_{i} ≤ c) & (∃y_{i})_{i<n}(y_{i} ∈ H_{i} & &_{i<n}(x_{i} ∨ y_{i}) ∈ F_{i} & ∨ {y_{i}|i < n} ∈ R)

where we understand membership in the sets H_{i}, F_{i} and R as being defined by the appropriate formulas and parameters as given by Theorem 4.2.1. This also supplies the notion of forcing required in our Theorem by taking (the disjoint union of) three versions of the one provided in Theorem 4.2.1 for the three families of pairwise Turing incomparable sets needed for these definitions as they are uniformly recursive in C ⊕ H. The verification that this formula defines the relation is straightforward. If R(x̄) then every element of the sequence x̄ is below c and is therefore equal to an x̃_{j_{i}} (for i < n). The degrees h_{i,j_{i}} ∈ H_{i} then are the witness y_{i} required in φ. In the other direction, if φ holds of any n-tuple then all its elements are below c and we need to consider the situation where φ(x_{j_{0}}, … x_{j_{n−1}}) for some j_{i}, i < n. Let the required witnesses be y_{i}. As

y_{i} ∈ H_{i} and (x_{j_{i}} ∨ y_{i}) ∈ F_{i}, y_{i} = h_{i,j}. Then as ⋁_{i<n} y_{i} ∈ R, R(x_{j_{0}}, x_{j_{1}}, …, x_{j_{n−1}}). The

assertions in the Theorem about the form of the required formulas φ are now immediate from Theorem 4.2.1.

Note that with the above assumptions on c in this proof, Theorem 4.2.1, the remarks immediately following it and Proposition 3.2.10, we can get all the parameters need for this definition of R below c′′. We improve this by one jump in the next section.

We can now precisely characterize the complexity of T h(D) as that of true second order arithmetic.

Theorem 4.2.4 T h(D, ≤) ≡_{1}T h^{2}(ℕ, ≤, +, ×, 0, 1).

Proof. That T h(D, ≤) ≤_{1}T h^{2}(ℕ, ≤, +, ×, 0, 1) is easy. As A ≤_{T} B is definable in arithmetic (indeed as we have seen it is Σ_{3} in A and B) and quantification over all sets gives quantification over all degree, we can recursively translate any sentence about D to an equivalent one of about second order arithmetic. For the other direction we use the formulas φ_{1}, φ_{2} and φ_{3} of Theorem 4.2.3 to give an interpretation of true second order arithmetic in D. We consider sequences of parameters p̄_{D}, p̄_{+}, p̄_{×} and p̄_{<} so that φ_{1}(p̄_{d}) defines a countable set of degrees and plays the role of φ_{D} for our interpretation. Our correctness condition then includes the sentences that say that φ_{3}(p̄_{+}), φ_{3}(p̄_{×}) and φ_{2}(p̄_{<}) (playing the roles of φ_{+}, φ_{×} and φ_{<}, respectively) define relations on the countable set defined by φ_{1}(p̄_{D}) to determine a structure M(p̄) (where p̄ is the concatenation of all the sequences of parameters used here) that satisfies all the axioms of our finite theory of arithmetic. Theorem 4.2.3 then says that there are choices of these parameters such that the structure so defined is isomorphic to ℕ. After all, ℕ is just a countable set with two ternary relations and one binary one. We now use φ_{1}(x, q̄)∧φ_{1}(p̄_{D}) as the φ_{S} required for our interpretation of true second order arithmetic. Again by Theorem 4.2.3, as q̄ ranges over tuples of degrees, the subsets of M(p̄) defined by φ_{s} range over all subsets of M(p̄) as required. All that remains to do is to show that we can extend the list of correctness conditions that guarantee that M(p̄) is a model of our finite axiomatization of arithmetic to also guarantee that it is isomorphic to ℕ. We can do this by adding on the sentence which asserts that every nonempty subset of M(p̄) (as given by φ_{S}(q̄, p̄) for some q̄) has an <_{M} least element, i.e. ∀q̄{∃x(φ_{S}(x, q̄)) → ∃x[φ_{S}(x, q̄, p̄)∧¬∃y(φ_{S}(y, q̄, p̄)∧φ_{<}(y, x, p̄_{<}))]}.

Exercise 4.2.5 If C is a jump ideal of D (i.e. a downward closed subset that is also closed under jump and join), then the theory of C is 1-1 equivalent to that of the model of second order arithmetic where set quantifiers range over the sets with degrees in C.

Notes: Slaman and Woodin forcing was introduced in Slaman and Woodin [1986] where they proved Theorems 4.2.1 and 4.2.3. Theorem 4.2.4 (which as presented here follows easily from these results) is originally due to Simpson [1977] although with a very different proof using then new initial segments results and Theorem 2.2.11. Another version using simpler codings and previously know initial segment results along with Theorem 2.2.11 is in Nerode and Shore [1980]. Exercise 4.2.5 is from Nerode and Shore [1980a].

4.3 T h(D ≤ 0′)

We now want to improve our coding results so that they become applicable below 0′. We begin with the Slaman and Woodin coding of sets of pairwise incomparable degrees.

Theorem 4.3.1 For any set S = {C_{0}, C_{1}, …, } of pairwise Turing incomparable subsets of ℕ let C = ⊕C_{i}. There are then G_{0},G_{1} ≤_{T} C′ and D_{i} such that, for every i ∈ ℕ and j < 2„ D_{i} ≤_{T} C_{i} ⊕ G_{j} while D_{i} ≰_{T} C_{i}. Moreover, the C_{i} are minimal with this property among sets recursive in C in the sense that for any X ≤_{T} C for which there is a D such that D ≤_{T} X ⊕ G_{j} (j < 2) but D ≰_{T} X there is an i such that C_{i} ≤_{T} X.

Proof. We follow the ideas of the proof of Theorem 4.2.1 but replace the uses of 2genericity for extending conditions to make something converge. At various steps we ask if there are appropriate extensions, if so we take them and continue our construction. If not we have a condition that forces some functional to diverge and so can satisfy the relevant requirement in that way.

We build D_{i} ≤_{T} G_{0} ⊕ C_{i}, G_{1} ⊕ C_{i} such that D_{i} ≰_{T} C_{i}. The requirements for diagonalization here are:

P_{e,i} : Φ_{e}^{C_{i}} ≠ D_{i}.

Let X_{j} = Φ_{j}^{C}. We also have requirements for minimality:

R_{e,,j} : Φ_{e}^{G_{0}⊕X_{j}} = Φ_{e}^{G_{1}⊕X_{j}} = D ⇒ D ≤_{T} X_{j} or ∃i(C_{i} ≤_{T} X_{j}).

4.3. T H(D ≤ 0′) 47

Note that we are using the same index for computing from both X ⊕ G_{0} and X ⊕ G_{1} rather than two distinct ones. This is equivalent to our previous use of two indices, say l_{0} and l_{1}. The point is that we know that G_{0} and G_{1} are different. Say G_{0}(x) = 0 while G_{1}(x) = 1 for some x. Given any indices l_{0} and l_{1}, we can find an e such that for any oracle Z, Φ_{e}^{Z} = Φ_{l_{0}}^{Z} if Z(x) = 0 and Φ_{e}^{Z} = Φ_{l_{1}}^{Z} if Z(x) = 1. Using this e for computing from both X ⊕ G_{0} and X ⊕ G_{1} then gives the same results as using l_{0} and l_{1} to compute from X ⊕ G_{0} and X ⊕ G_{1}, respectively. This notational device is known as Posner’s trick (or at least as one variant thereof).

We list all the requirements as Q_{s}. We build G_{0}, G_{1} by finite approximations γ_{0,s}, γ_{1,s} of equal length. As before we let D_{i}(m) = G_{0}(⟨i, c_{i,m}⟩) where {c_{i,m}} is an enumeration of C_{i} in increasing order. So D_{i} ≤_{T} G_{0} ⊕ C_{i}. We guarantee that D_{i} ≤_{T} G_{1} ⊕ C_{i} as before by making sure that, for each i, G_{0}(⟨i, c_{i,m}⟩ ≠ G_{1}(⟨i, c_{i,m}⟩ for at most finitely many m. In particular we institute a rule for the construction that when we act to satisfy requirement Q_{n} at stage s by extending the current values of γ_{k} (k = 0, 1) we require, for i ≤ n, ⟨i, m⟩ ≥ |γ_{0,s}| = |γ_{1,s}| and m ∈ C_{i}, that the extensions γk^{′} are such that γ′_{0}(⟨i, m⟩) = γ′_{1}(⟨i, m⟩). As we act to satisfy any Q_{n} at most once, this rule guarantees that there are at most finitely many relevant differences between G_{0} and G_{1} for each i.

At stage s, if Q_{s} = P_{e,i}, we act to satisfy P_{e,i}. Choose m such that ⟨i, c_{i,m}⟩ ≥ |γ_{0,s}|. Ask if Φ_{e}^{C_{i}}(m) ↓. If not, let γ_{k,s+1} = γ_{k,s} for k = 0, 1. (As usual this satisfies P_{e,i}.) If it does converge, extend each of γ_{0,s}, γ_{1,s} by the same string σ to γ_{0,s+1}, γ_{1,s+1} with γ_{0,s+1}(⟨i, c_{i,m}⟩) ≠ Φ_{e}^{C_{i}}(m). This also satisfies the requirement because D_{i}(m) = G_{0}(⟨i, c_{i,m}⟩) by definition and trivially obeys the rule of the construction.

Note that C′ can decide if Φ_{e}^{C_{i}}(m) ↓, so this action is recursive in C′.

If Q_{s} = R_{e,j}, this stage has a substage for each requirement Q_{n} = R_{e′,j′} with n ≤ s that has not yet been satisfied. For notational convenience we write γ_{k} for γ_{k,s} in the description of our action at stage s. At the end of each substage we define successive extensions γ_{k,l} of γ_{k} satisfying the rule of the construction. We first try to satisfy R_{e,j} (which, of course, we have not attempted to satisfy before). We ask if ∃x∃σ_{k} ⊇ γ_{k} which satisfy the rule of our construction and such that the σ_{k} ⊕ X e-split at x, i.e.

Φ_{e}^{σ_{0}⊕X_{j}}(x) ↓≠ Φ_{e}^{σ_{1}⊕X_{j}}(x) ↓ .

Note that, when we are acting to satisfy any Q_{n}, checking if extensions of the current values of γ_{k} satisfy the rule of the construction is recursive in ⊕{C_{i}|i ≤ n} and so uniformly recursive in C. Thus this question can be answered by C′. There is one subtlety here. We must be careful with what we mean by a computation from X_{j} as there is no list of all the sets recursive in C that is uniformly recursive in C. So what we mean here is that there is a computation of Φ_{j}^{C} providing a long enough initial segment of X_{j} so as to make the desired computations at m converge. This makes the whole question one that is Σ_{1}^{C} and so recursive in C′.

If the answer is yes, choose as usual the first such extensions (in a uniform search recursive in C) as γ_{0,0}, γ_{1,1}. Note that we have now satisfied R_{e,j}. If the answer is no, ask if ∃x∃σ, τ ((γ_{0}ˆ σ ⊕ X_{j})|_{e}(γ_{0}ˆ τ ⊕ X)) (See Definition 2.2.8). This question is also Σ_{1}(C).

• If not, let γ_{k,s,0} = γ_{k,s}. Then, as usual, if Φ_{e}^{G_{0}⊕X_{j}} is total, it is recursive in X as we guarantee that G_{0} ⊇ γ_{0,0}. To calculate it at x, find any σ such that Φ_{e}^{γ_{0}ˆ σ⊕X_{j}}(x) ↓. This computation must give right answer. So in this case we have also satisfied R_{e,j}.

• If so,we can find such σ and τ (recursively in C). We interpolate between σ, τ with strings σ = δ_{0} = δ_{1}, …, δ_{z} = τ which differ successively at exactly one number. Ask if ∃σ_{1} such that Φ_{e}^{γ_{0}ˆ δ_{1}ˆ σ_{1}⊕X_{j}}(x) ↓. If not, let γ_{k,0} = γ_{k}ˆ δ_{1}. Note that this extension satisfies the rule of the construction and that we have satisfied R_{e,j} by guaranteeing that Φ_{e}^{G_{0}⊕X_{j}}(x) ↑. If yes, consider δ_{2}ˆ σ_{1} and ask again if there is a σ_{2} such that Φ_{e}^{δ_{2}ˆ σ_{1}ˆ σ_{2}⊕X_{j}}(x) ↓. If not, let γ_{k,0} = δ_{2}ˆ σ_{1} as before obeying the rule of the construction and satisfying R_{e,j}. If so, we continue on inductively through the δ_{k}.

• Eventually we either define γ_{k,0} and satisfy R_{e,j} or we find σ_{1}, …, σ_{z} such that Φ_{e}^{γ_{0}ˆ δ_{l}ˆ ρ⊕X_{j}}(x) ↓ for every l ≤ z where ρ = σ_{1}ˆ … ˆ σ_{z}. In the second case, we set γ_{k,0} = γ_{k,s}. This action does not satisfy R_{e,i} but it demonstrates that there are σ̂ and τ̂ which differ at exactly one number and for which (γ_{0} ˆ σ̂ ⊕ X)|_{e}(γ_{0} ˆ τ̂ ⊕ X). The point here is that, as Φ_{e}^{γ_{0}ˆ δ_{0}ˆ ρ⊕X_{j}}(x) ↓= Φ_{e}^{γ_{0}ˆ σ⊕X_{j}}(x) ↓≠ Φ_{e}^{γ_{0}ˆ τ⊕X_{j}}(x) ↓= Φ_{e}^{γ_{0}ˆ δ_{z}ˆ ε⊕X_{j}}(x) ↓, there is an l such that Φ_{e}^{γ_{0}ˆ δ_{l}ˆ ρ⊕X_{j}}(x) ↓≠ Φ_{e}^{γ_{0}ˆ δ_{l+1}ˆ ρ⊕X_{j}}(x) ↓ while δ_{l}ˆ ρ and δ_{l+1}ˆ ρ differ at exactly one number. Now consider γ_{1} ˆ σ̂. If there is no μ such that Φ_{e}^{γ_{1} ˆ σ̂ˆ μ⊕X_{j}}(x) ↓ then we can again satisfy R_{e,j} by setting γ_{k,s,0} = γ_{k,s} ˆ σ̂. If there is such a μ, we compare Φ_{e}^{γ_{1} ˆ σ̂ˆ μ⊕X_{j}}(x) ↓ with Φ_{e}^{γ_{0} ˆ σ̂ˆ μ⊕X_{j}}(x) ↓ and Φ_{e}^{γ_{0} ˆ τ̂ˆ μ⊕X_{j}}(x) ↓. As the last two are different one of them must be different from the first. If Φ_{e}^{γ_{1} ˆ σ̂ˆ μ⊕X_{j}}(x) ↓≠ Φ_{e}^{γ_{0} ˆ σ̂ˆ μ⊕X_{j}}(x) ↓, we would contradict our assumption that the answer to our very first question was no as γ_{1} ˆ σ̂ˆ μ and γ_{0} ˆ σ̂ˆ μ certainly satisfy the rule of the construction. If Φ_{e}^{γ_{1} ˆ σ̂ˆ μ⊕X_{j}}(x) ↓≠ Φ_{e}^{γ_{0} ˆ τ̂ˆ μ⊕X_{j}}(x) ↓, the only way we would not have the same contradiction is if the one point at which σ̂ and τ̂ differ is a coding location ⟨k, c_{k,m}⟩ with k < s. Thus the only way our actions at this stage do not satisfy R_{⟨e,j⟩} is if there are σ̂ˆ μ and τ̂ˆ μ which differ at at exactly one point such that (γ_{1} ˆ σ̂ˆ μ ⊕ X_{j})|_{e}γ_{0} ˆ τ̂ˆ μ ⊕ X_{j} and for any such σ̂ and τ̂ the point of difference must be a coding location ⟨k, c_{k,m}⟩ with k < s.

• In this last case we set γ_{0,0} = γ_{0} and γ_{1,0} = γ_{1,s}. In any event, we now proceed to extend γ_{1,0} (and then γ_{1}) in the same way but attempting to satisfy each Q_{n} = R_{e′,j′} with n < s that has not yet been satisfied. After some finite number of such attempts we have tried them all, satisfying some and for the others producing one more example of an x and two strings σ̂ and τ̂ differing at one number only (after |γ_{0}|) such that (γ_{0} ˆ σ̂ ⊕ X_{j′})|_{e}(γ_{1} ˆ τ̂ ⊕ X_{j′}) for each ⟨e′, j′⟩ which we have not yet satisfied and a guarantee that any two such strings differ at a coding location ⟨k, c_{k,m}⟩ with k < n.

• At the end of this process we let γ_{k,s+1} be the final extension of γ_{k} that we have produced.

We now claim that all the requirements are satisfied. It is immediate that P_{e,i} is satisfied when we act for Q_{s} = P_{e,i} at stage s. Consider any R_{e,j} = Q_{s_{0}}. If we ever act so as to satisfy it at some stage s of the construction, it is clearly satisfied and we never act for it again. As we violate the rule of the construction at some ⟨k, c_{k,m}⟩ only when we act to satisfy requirement Q_{n} for n ≤ k and we do so at most once for each n, D_{i} ≤_{T} G_{1} ⊕ C_{i} as required.

Finally, suppose that the first requirement that we never act to satisfy during the construction is Q_{n}. It must be some R_{e,j}. Suppose that all requirements Q_{r} for r < n have been satisfied by stage s_{0} > n. At each stage s > s_{0} with Q_{s} = R_{e′,j′} we attempt to satisfy R_{e,j} at some substage of the construction. As we fail, there are Φ_{e′}^{δ_{0}⊕X_{j′}}(x) ↓≠ Φ_{e′}^{δ_{1}⊕X_{j′}}(x) ↓ with δ_{k} ⊇ γ_{k,s} ⊇ γ_{k,n} which differ at exactly one point and any such pair differ at a coding location ⟨k, c_{m,k}⟩ with k ≤ n. Recursively in X_{j} we can then search for and find infinitely many extensions δ_{k} of γ_{k,n} with this property with the points at which they differ becoming arbitrarily large (as |γ_{k,s}| is clearly going to infinity). As there are only finitely many k ≤ n, there must be one k ≤ n for which infinitely many of these δ_{k} differ at a point of the form ⟨k, z⟩ with infinitely many different z. As every such point is a coding location, recursively in X we can compute an infinite subset of C_{k}, so by our initial assumption that each C_{i} is recursive in everyone of its infinite subsets C_{k} ≤_{T} X_{j} as required for R_{e,j} to be satisfied in the end.

This step-by-step construction is the much the same as the forcing argument we saw before, but grittier, and we gain a quantifier. This helps us determine the true complexity of T h(D, ≤ 0′): T h(D, ≤ 0′) ≡_{m} T h(ℕ, +, ×, ≤).

Exercise 4.3.2 It is easy to show that the G_{i} of Theorem 4.3.1 can be made to have (or already have) jumps below C′.

Exercise 4.3.3 With the notation as in Theorem 4.2.1 show that for any G 1-generic for P, G_{0} and G_{1} have the properties required by the Theorem. So in particular, we can make G′_{0} ≡_{T} 0′ ≡_{T} G1^{′}. This then supplies the analogous result for Theorem 4.2.3, i.e. a notion of forcing recursive in the appropriate C ⊕ H such that any 1-generic computes the parameters necessary to define the given relation. Hint: This is not too easy. A proof can be found in Greenberg and Montalbán [2004].

Theorem 4.3.4 If R is an n-ary relation on D(≤0′) which is uniformly recursive in a low degree c in the sense that there are families of sets {X_{i}} = S and {⟨X_{i_{1}}, …, X_{i_{n}}⟩} = T uniformly recursive in C ∈ c such that {deg(X_{i})|X_{i} ∈ S} is the field of R (i.e. all elements that occur in any n-tuple satisfying R) and {⟨deg X_{i_{1}}, …, deg X_{i_{n}}⟩ | ⟨X_{i_{1}}, … X_{i_{n}}⟩ ∈ T } = R, then there are p̄ < c′ = 0′ which define R by the formula φ_{n} of Theorem 4.2.3.

Proof. We begin with a G which is Cohen 1-generic over C so that (C ⊕ G)′ ≡_{T} C′. The set of degrees R and the finite families of sets of degrees H_{i} and F_{i} of the proof of Theorem 4.2.3 are all now uniformly recursive in C ⊕ G and consist of pairwise Turing incomparable sets so, by Theorem 4.3.1, there are sequences of parameters defining each of them all below (C ⊕ G)′. The proof of Theorem 4.2.3 now shows that they define R as required.

We now explain how we plan to code arithmetic in D(≤0′). The “intended model” starts with an nice effective successor structure determined by parameters q̄: c, b_{0}, b_{1}, e_{0}, e_{1}, d_{0}, f_{0} and f_{1} with c′ = 0′ and c being above all of the other parameters and all the required d̂_{n} as well. Moreover, the d_{n} are all uniformly recursive in c. We can do this by Exercise 3.3.9 or 3.3.10. We then choose, as in the proof of Theorem 4.2.4 parameters p̄_{D}, p̄_{+}, p̄_{×} and p̄_{<} so that φ_{1}(p̄_{d}) defines {d_{n}|n ∈ ℕ} and φ_{3}(p̄_{+}), φ_{3}(p̄_{×}) and φ_{2}(p̄_{<}) (playing the roles of φ_{+}, φ_{×} and φ_{<}, respectively) that define relations on the countable set defined by φ_{1}(p̄_{D}) to determine a structure M(p̄) (where p̄ is the concatenation of all the sequences of parameters used beginning with q̄) that satisfies all the axioms of our finite theory of arithmetic and such that d_{0} is the least element in the ordering of M(p̄) given by φ_{2}(p̄_{<}) and, for each n, d_{n+1} is the immediate successor of d_{n} in this order. We can find such parameters below 0′ by the arguments for the proof Theorem 4.2.3 combined with Theorem 4.3.1 (relativized to c) since the d_{n} and the desired relations on them are uniformly recursive in c and c′ = 0′. Now this model is standard since the d_{n} are ordered in order type ω and constitute the universe of the model.

The problem is that there is no obvious way to definably say that the universe of the model is precisely the d_{n} in terms of just the prescribed parameters (or any other finite list). The issue is that we only have a scheme to generate these degrees not one to define them. We can come fairly close in first order way. In addition to the correctness conditions that guarantee that the defined relations give a model of arithmetic on {x|φ_{D}(x, p̄)}, we can approximate niceness by adding the sentences c ≱ b and ∀d[φ_{D}(d) → d ∨ c ≥ b & ∃d̂(d ∧ d̂= 0 & (∀d^{∗} ≠ d)(φ_{D}(d^{∗}) → (d ∧ d^{∗} = 0) & (d̂≥ d^{∗}))]. We can approximate the desired condition that {d_{n}|n ∈ ω} is the domain of our structure by saying that d_{0} is the least element in the ordering of M(p̄) given by φ_{2}(p̄_{<}) and for every d such that φ_{D}(d, p̄), if d is an even number in M(p̄), then (e_{0} ∨ d) ∧ f_{0} is its immediate successor in the ordering given by φ_{2}(p̄_{<}) while if it is an odd number then its immediate successor is given by (e_{1} ∨ d) ∧ f_{1}. This guarantees that {d_{n}|n ∈ ω} is the standard part of the model M(p̄). Thus if we had a formula φ̂_{S}(x, r̄, p̄) which, as r̄ ranged over n-tuples from D(≤0′), defined a collection of subsets of M(p̄) that include {d_{n}|n ∈ ω}, we could guarantee that M(P̄) was standard by saying that every subset (i.e. picked out by some choice of parameters r̄) of M(p̄) which contains its least element (d_{0}) and is closed under immediate successor is all of M(p̄).

The crucial point now is that the proof of Proposition 3.4.3 shows that, under these conditions, {d_{n}|n ∈ ω} ∈ Σ_{3}^{C} as is the ideal generated by this set. That is, the standard part of any M(p̄) for p̄ satisfying all of these correctness conditions and the ideal it generates are both Σ_{3}^{C}. Our goal now is to prove that for every c < 0′ and every Σ_{3}^{C} ideal in the degrees below c, there are g_{0}, g,_{1} ≤_{T} 0′ which are an exact pair for the given ideal. Proposition 3.4.3 and Remark 3.4.4 then show that we could define the desired set {d_{n}|n ∈ ω} in terms of this exact pair. We now turn to the proof of this result as Theorem 5.2.12. It supplies the final ingredient of our theorem.

Theorem 4.3.5 T h(D ≤0′) ≡_{1−1} T h(ℕ).

Proof. The above argument (together with Theorem5.2.12) shows that we can interpret true first order arithmetic in D(≤0′). Thus T h(ℕ) ≤_{1−1}T h(D ≤0′). The other direction is immediate since we can define the sets recursive in 0′ in arithmetic as well as the ordering of Turing reducibility on them. Thus we have a recursive translation of sentences about D(≤0′) to ones of arithmetic that preserves truth. Of course, this implies that T h(D ≤0′) ≤_{1−1} T h(ℕ).

Notes: Theorem 4.3.1 and a special case of Theorem 4.3.4 are in Slaman and Woodin [1986]. The full version of Theorem 4.3.4 is in Odifreddi and Shore [1991] as is the proof of Theorem 4.3.5 which is originally due to Shore [1981].

52 CHAPTER 4. THE THEORIES OF D AND D(≤ 0′)

Domination Properties

5.1 Introduction

An important topic in the study of the complexity of functions from ℕ to ℕ is the notion of rate of growth and of one function growing faster than another or faster than a whole class of functions. These issues are not only natural but they have important connections with the computational complexity of the functions as measured by Turing and other reducibilities. In this chapter we will study some of these notions and their impact on the structure of the degrees. They will play a crucial role in our analysis of the complexity of D(≤ 0′). We begin with some basic definitions.

Definition 5.1.1 1. The function g dominates the function f (f < g) if, for all but finitely many x, f(x) < g(x).

2. The degree g dominates the function f if some g ∈ g dominates f.

3. The function g dominates the degree f if g dominates every function f ∈ f.

4. The degree g dominates the degree f if for every f ∈ f there is a g ∈ g which dominates f.

We also sometimes express these relations in the passive form saying, for example, that f is g-dominated or f is g-dominated for the first two relations. A function g that dominates the degree 0 is called dominant.

In the literature a degree f that is not 0-dominated (i.e. there is an f ∈ f which is not dominated by any recursive function) is, for historical reasons unrelated to our concerns, called hyperimmune. If f is not hyperimmune, i.e. it is 0-dominated, is also called hyperimmune free. For example, we show later that every 0 < a < 0′ is hyperimmune (Theorem 5.2.3) while the usual minimal degrees constructed below 0′′ are hyperimmune free.

5.2 R.E. and Δ_{2}^{0} degrees

Theorem 5.2.1 If A >_{T} 0 is r.e. then there is a function m ≡_{T} A which is not 0dominated, i.e. it is not dominated by any recursive function. Indeed, any function g which dominates m computes A.

Proof. For A r.e., let A_{s} be the standard approximation to A at stage s. Let m be the least modulus function for this approximation: m(x) = μs(∀t ≥ s)(A_{s} ↾ x = A_{t} ↾ x). For r.e. sets, the approximation changes its mind at most once and is correct in the limit, so m(x) is also the μs(A_{s} ↾ x = A ↾ x) and is clearly of the same degree as A. Moreover, if g(x) ≥ m(x) for almost all x, then A ≤_{T} g as A ↾ x = A_{g(x)} ↾ x for all but finitely many x. Thus, if A >_{T} 0, then m is not dominated by any recursive function and any g that dominates m computes A.

The Shoenfield limit lemma (Lemma 1.1.11) gives us a recursive approximation h(x, s) to any A ∈ Δ_{2}^{0} (or equivalently A ≤_{T} 0′). So the least modulus function m makes sense for such an approximation as well. So does the second version used in the above proof. Here we call it the computation function: f(x) = μ(s > x)(∀y < x)(h(y, s) = A(y)) (for technical reasons, we don’t consider first few stages). It calculates the first stage after x at which the approximation is correct up to x. But, since we are no longer looking at r.e. sets, the approximation might change even after it’s correct and the computation function f need not be the same as the least modulus m. The two functions may not be the same even up to degree.

Exercise 5.2.2 Find an A <_{T} 0′ and an approximation h(x, s) to A for which the least modulus function m computes 0′. On the other hand, the computation function f for h is always of the same degree as A.

We can, nonetheless extend Theorem 5.2.1 to all A ∈ Δ_{2}^{0}.

Theorem 5.2.3 If A is Δ_{2}^{0}, then there is an f ≡_{T} A which is not 0-dominated. Indeed, any function g which dominates f computes a.

Proof. By the Shoenfield limit lemma, there is a recursive h(x, s) such that lim_{s→∞} h(x, s) = A(x). Let f(x) be the computation function for this approximation. Suppose f < g. We claim that even though h(z, s) may change at z < x for s > f(x), we can still compute A from g. Let s_{0} be such that (∀m ≥ s_{0})(f(m) < g(m)). To calculate A(n) for n > s_{0} find an s > n such that h(n, t) is constant for t ∈ [g(s), gg(s)]. Since h(n, t) is eventually constant, such an s exists. Moreover, we can find it recursively in g: compute the intervals [g(n + 1), gg(n + 1)], [g(n + 2), gg(n + 2)], [g(n + 3), gg(n + 3)], … checking to see if h is constant on the intervals. By the clause that makes f(x) > x in the definition of the computation function and our choice of s_{0}, gg(s) > fg(s) > g(s), so the first t > g(s) at which h is correct for all elements below g(s) is in [g(s), gg(s)]. For this t, h(n, t) = A(n). As we chose s so that the value of h(n, t) is constant on this interval, A(n) = h(n, t) for any t ∈ [g(s), gg(s)] and we have computed A recursively in g as required.

5.2. R.E. AND Δ_{2}^{0} DEGREES 55

Exercise 5.2.4 What are the correct relativizations of the previous two theorems?

Exercise 5.2.5 The above results can be extended by iterating the notions of “r.e. in” or more generally “Δ_{2}^{0} in” as long as one includes the lower degrees. We say that A 1-REA if it is r.e. then we define n-REA by induction: A is n + 1-REA if A is of the form B ⊕ W_{e}^{B} where B is n-REA. (REA stands for r.e. in and above.) Prove that any n-REA set A has an f ≡_{T} A such that any g > f computes A. Do the same with Δ_{2}^{0} replacing r.e. These results can be carried into the transfinite. Prove, for example, that 0^{(ω)} has the same property.

Theorem 5.2.6 If A > 0 is r.e. and P is a recursive notion of forcing then there is is 1-generic sequence ⟨p_{s}⟩ ≤_{T} A so that the corresponding 1-generic G is recursive in A as well.

Proof. We build a 1-generic sequence p_{s} recursive in A. Let f ≤_{T} A be the least modulus function for A. The requirements are

R_{e} : for some s, p_{s} ∈ S_{e} or (∀q ≤ p_{s})(q ∉ S_{e}), where S_{e} is eth Σ_{1} set of conditions.

At stage s, we have a condition p_{s}. Note that we are thinking of P as a subset of ℕ and so have the natural ordering ≤ on its members (and all of ℕ) as well as the forcing ordering ≤_{P}. We say that R_{e} has been declared satisfied by stage s if there is a p_{n} with n ≤ s such that p_{n} ∈ S_{e,f(s)}. Find the least e < s such that R_{e} has not yet been declared satisfied and such that (∃q ≤_{P} p_{s})(q ≤ f(s) & q ∈ S_{e,f(s)}). For this e, choose the least such q and put p_{s+1} = q. If there is no such e, let p_{s+1} = p_{s}.

To verify that the construction succeeds, suppose for the sake of a contradiction that e_{0} is least such that

¬∃s(p_{s} ∈ S_{e_{0}} ∨ (∀q ≤_{P} p_{s})(q ∉ S_{e_{0}})).

Choose s_{0} > e_{0} such that ∀i < e_{0} if there is a p_{s} ∈ S_{i} then there is one with s < s_{0} and p_{s} ∈ S_{i,f(s_{0})} (so by this stage we have already declared satisfied all higher priority requirements that are ever so declared). We claim that we can now recursively recover the entire construction and the values of f(s) for s ≥ s_{0}. As this would compute A recursively, we would have our desired contradiction. Consider what happens in the construction at each stage s ≥ s_{0} in turn. Suppose we have p_{s}. At stage s we look for the least e < s such that (∃q ≤_{P} p_{s})(q ≤ f(s) & q ∈ S_{e,f(s)}). There is no such e < e_{0} by our choice of s_{0}. If e_{0} itself were such an e, we would act for it and declare P_{e_{0}} to be satisfied, contrary to our choice of e_{0}. On the other hand, by our choice of e_{0} there is a q ≤_{P} p_{s} with q ∈ S_{e_{0}}. We can find such a q recursively (because we know it exists). We did not find this q in the construction at stage s because either q > f(s) or q ∈ S_{e_{0}} − S_{e_{0},f(s)}. So we can now find a bound t on f(s) by finding the stage at which q enters S_{e_{0}}. Given t ≥ f(s) we can calculate f(s) as the least z such that A_{z} ↾ s = A_{t} ↾ s. Once we have f(s) we can recursively determine what happened at stage s of the construction and in particular the value of p_{s+1}. Thus we can continue our recursive computation of f(s) as claimed.

Relativizing Theorem 5.2.6 to C gives, for any C recursive notion of forcing P, a G ≤_{T} A which is C 1-generic for P for any A >_{T} C which is r.e. in C.

Exercise 5.2.7 The crucial property of the function f used in the above construction was that there is a uniformly recursive function computing f(x) from any number greater than it. Prove that if there is a partial recursive φ(x, s) such that (∀s ≥ f(x))(φ(x, s) = f(x)) then f is of r.e. degree.

Corollary 5.2.8 If a > 0 is r.e. then there is Cohen 1-generic G <_{T} A and so, for example, every countable partial order can be embedded in the degrees below a.

Similarly we have

Corollary 5.2.9 If a is r.e. in b and strictly above it, then every partial lattice recursive in b can be embedded into [b, a).

Corollary 5.2.10 If a is r.e. then every maximal chain in (D(≤ a), ≤_{T}) is infinite. In fact, there is no maximal element less than a in (D(≤ a), ≤_{T}).

Proof. Suppose b < a. Then a is r.e. in and strictly above b. Relativizing Theorem 5.2.6 to a B ∈ b and using Cohen forcing gives us a G ≤_{T} A which is Cohen 1-generic over B. So the degrees of B ⊕ G^{[i]} are in fact all between b and a and even independent.

Exercise 5.2.11 Prove that every recursive lattice L with 0 and 1 can be embedded in D(≤a) preserving 0 and 1 for any r.e. a.

We now apply Theorem 5.2.6 to provide the missing way of identifying the standard parts of effective successor models coded below 0′ that we need to calculate the complexity of T h(D(≤0′)).

Theorem 5.2.12 If A >_{T} C, A is r.e. in C and I is an ideal in D(≤ deg(C)) such that W = {e : deg(Φ_{e}^{C}) ∈ I} ∈ Σ_{3}^{C} then there is an exact pair G_{0}, G_{1} for I below A.

Proof. We provide a C-recursive notion of forcing P such that any 1-generic for P gives an exact pair for I and apply Theorem 5.2.6 relativized to C. The conditions of P are of the form p = ⟨p_{0}, p_{1}, F_{p}, n_{p}⟩ where p_{i} ∈ 2^{<ω}, |p_{0}| = |p_{1}| = |p|, F_{p} ∈ ω^{<ω}, n_{p} ∈ ω such that

(∀i ∈ {0, 1})(∀⟨e, x, y⟩)(∃^{≤1}⟨w, m⟩) (⟨e, x, y, w, m⟩ ∈ p_{i}) .

We define V as expected V (p) = p_{0} ⊕ p_{1}. So for a 1-generic G, we have G_{i} = ∪{p_{i}|p ∈ G}. If e ∈ W, we want Φ_{e}^{C} to be coded into G_{i}. The unusual restriction above on conditions in P suggests how we intend to do this coding. Since W ∈ Σ_{3}^{C} we have a relation R ≤_{T} C such that e ∈ W ⇔ ∃x∀y∃zR(e, x, y, z). We denote the pairs of elements of W and their witnesses by Ŵ = {⟨e, x⟩ : ∀y∃zR(e, x, y, z). To calculate Φ_{e}^{C} for e ∈ W, our plan is to first choose an x such that ⟨e, x⟩ ∈ Ŵ. We then search for ⟨w, m⟩ such that ⟨e, x, y, w, m⟩ ∈ G_{i} and announce that Φ_{e}^{C}(y) = m. The definition of P guarantees that this procedure gives at most one answer. The definition of the partial order ≤_{P} below guarantees that this procedure makes only finitely many mistakes for any 1-generic. Genericity also guarantees that, when ⟨e, x⟩ ∈ Ŵ, it gives a total function.

The number n_{p} in our conditions acts as a bound for how far we have to search to sufficiently verify the Π_{2} assertion that x is a witness that e ∈ W (and so also that Φ_{e}^{C} is total). The set F_{p} tells us for which ⟨e, x⟩ we can make no further mistakes in our coding of Φ_{e}^{C} into G_{i}^{⟨e,x⟩} when we extend p. With this intuition, we define extension in P by q ≤_{P} p iff

q_{i} ⊇ p_{i},  F_{q} ⊇ F_{p},  n_{q} ≥ n_{p},

and

(∀i ∈ {0, 1})(∀⟨e, x, y, w, m⟩ ∈ [|p|, |q|)(⟨e, x⟩ ∈ F_{p} & ⟨e, x, y, w, m⟩ ∈ q_{i}
→ Φ_{e,n_{q}}^{C}(y) = m & ∀y′ ≤ y∃z ≤ n_{q} (R(e, x, y′, z))

Note that P is recursive in C.

Suppose that G_{0}, G_{1} are given by a C-1-generic sequence ⟨p_{s}⟩ ≤_{T} A as in Theorem 5.2.6 relativized to C. We claim that G_{0}, G_{1} are an exact pair for I.

First assume that ⟨e, x⟩ ∈ Ŵ. We show that Φ_{e}^{C} ≤_{T} G_{i}. As the sets {p| ⟨e, x⟩ ∈ F_{p}} are obviously dense in P, there is an s such that ⟨e, x⟩ ∈ F_{p_{s}}. For any ⟨e, x, y, w, m⟩ ∈ p_{t} with t > s, Φ_{e}^{C}(y) = m by definition and so as noted above, the prescribed search procedure which is recursive in G_{i} returns only correct answers for y > |p_{s}|. Next, we claim that for each y > |p_{s}|, i ∈ {0, 1} and m = Φ_{e}^{C}(y) the Σ_{1}^{C} sets S_{e,x,y,m,i} = {r|∃w(⟨e, x, y, w, m⟩ ∈ r_{i}} are dense below p_{s}. This guarantees that ⟨p_{t}⟩ meets each of these sets and so the search procedures are total and correctly compute Φ_{e}^{C}(x) for all but finitely many x. To see that these sets are dense below p_{s}, consider any q ≤ p_{s} with no w such that ⟨e, x, y, w, m⟩ ∈ q_{i}. Choose any w > |q| and define an r ≤_{P} q by making |r| = ⟨e, x, y, w, Φ_{e}^{C}(y)⟩ + 1⟩, r_{i} = q_{i} ∪ {⟨e, x, y, w, Φ_{e}^{C}(y)⟩} (i.e. we let them be 0 at other points below the length), F_{r} = F_{q} and letting n_{r} be the least n ≥ n_{q} such that ∀y′ ≤ y∃z < n(R(e, x, y′, z) & Φ_{e,n}^{C}(y) ↓) (one such exists since we are assuming that ⟨e, x⟩ ∈ Ŵ). Then r≤_{P}q and r ∈ S_{e,x,y,m,i} as desired.

We next want to deal with the minimality conditions associated with the G_{i} being an exact pair for I. Suppose then that Φ_{e}^{G_{0}} = Φ_{e}^{G_{1}} = D is total. We want to prove that D ≤ ⊕{Φ_{e}^{C} : e ∈ F } for some finite F ⊂ W. Consider the Σ_{1} set S_{e} of conditions p:

S_{e} = {p : ∃n (Φ_{e}^{p_{0}}(n) ↓≠ Φ_{e}^{p_{1}}(n)) ↓}

By our assumption there is no p_{s} ∈ S_{e} so we have a p_{s} = p such that ∀q ≤_{P} p(q ∉ S_{e}). We claim that D ≤ ⊕{Φ_{e}^{C} : ⟨e, x⟩ ∈ F_{p} ∩ Ŵ }. For every ⟨e, x⟩ ∈ F_{p} \ Ŵ, let y(e, x) be the least y such that ¬∀y′ ≤ y∃zR(e, x, y′, z) ∨ Φ_{e}^{C}(y) ↑. It is clear that there is no q ≤_{P} p with any ⟨e, x, y, w, m⟩ ∈ q_{i} for ⟨e, x⟩ ∈ F_{p} \ Ŵ and y ≥ y(e, x). Choose q ≤_{P} p in ⟨p_{s}⟩ so that it has the maximal number of y’s with some ⟨e, x, y, w, m⟩ ∈ q_{i} for y < y(e, x) and i ∈ {0, 1}. To compute D(y) for y > |q|, we find a t ∈ P such that t_{i} ⊇ q_{i}, Φ_{e}^{t_{0}}(y) ↓= Φ_{e}^{t_{1}}(y) ↓, no elements not in q_{i} are added into t_{i} in columns ⟨e, x⟩ ∈ F_{p}\Ŵ and for any ⟨e, x, y, w, m⟩ ∈ t_{i} with ⟨e, x⟩ ∈ F_{p} ∩ Ŵ, Φ_{e}^{C}(y) = m. Such an extension exists because Φ_{e}^{G_{0}}(y) ↓= Φ_{e}^{G_{1}}(y) ↓ and by the maximality property of q and the definition of ≤_{P}, G_{i}^{[⟨e,x⟩]} = q_{i}^{[⟨e,x⟩]} for ⟨e, x⟩ ∈ F_{p} \ Ŵ and so there is such a t̂∈ ⟨p_{s}⟩. Finding one such t is clearly recursive in ⊕{Φ_{e}^{C} : ⟨e, x⟩ ∈ F_{p} ∩ Ŵ }. Thus we only need to show that any such t_{i} provide the right answer. If one such gave an answer different than that given by t̂ (and so G_{0} and G_{1}) then ⟨t_{0}, t̂_{1}, F_{p}, n⟩ (where n ≥ n_{q} is large enough so that Φ_{e,n}^{C}(y) ↓ for every ⟨e, x, y, w, m⟩ in t_{0} or t̂_{1} with ⟨e, x⟩ ∈ F_{p} ∩ Ŵ) would be an extension of p in S_{e} for the desired contradiction.

This Theorem completes the proof of Theorem 4.3.5 that the theory of the degrees below 0′ is recursively isomorphic to true arithmetic. We can extend the result to all r.e. degrees.

Exercise 5.2.13 For every r.e. r > 0, T h(D(≤r) ≡_{1−1}T h(ℕ).

Notes: Theorem 5.2.1 is due to Dekker [1954]; Theorem 5.2.3 to Miller and Martin [1968]. We are not sure who first proved Corollary 5.2.8 (presumably using a different method called r.e. permitting). The style of proof based directly on domination properties used here to prove Theorem5.2.6 is attributed to us in Soare [1987, Ch. VI Exercise 3.9] in the case of Cohen forcing. Theorem 5.2.12 is in Shore [1981] which also is the original source of Exercise 5.2.13.

5.3 High and \overline{GL}_{2} degrees

We now look at stronger domination properties and their relation to the jump classes H_{1} and L̄_{2} below 0′ and their generalizations. Recall from Definition 1.1.12 that for a ≤ 0′, a ∈ H_{1} ⇔ a′ = 0′′; a ∈ L_{2} ⇔ a′′ = 0′′. For degrees a not necessarily below 0′, a ∈ GL_{2} ⇔ (a ∨ 0′)′ = a′′; a ∈ GH_{1} ⇔ a′ = (a ∨ 0′)′. It is also common to say that a is high if a′ ≥ 0′′. As it turns out these last are the degrees of dominant functions. Of course, a ∈\overline{GL}_{2} means that a ∉ GL_{2}. We relativize these notions to degrees above b by writing, for example, a ∈\overline{GL}_{2}(b).

5.3. HIGH AND \overline{GL}_{2} DEGREES 59

Let’s begin by showing that there is there a dominant function. In fact, if C is any countable class of functions {f_{i}} then there is function f which dominates all the f_{i}. For example, put f(x) = max{f_{i}(x) : i < x} + 1. This construction requires a uniform list of all the functions f_{i}. For the recursive functions we know that 0′′ can compute such a list: T ot = {e : Φ_{e} total} is clearly Π_{2}^{0} and so recursive in 0′′ by the Hierarchy Theorem (Theorem 1.1.10) and so there is a sequence f_{i} uniformly computable from 0′′ which then computes a dominant function as described. We can do better than this and avoid using totality. If f(x) = max{Φ_{e}(x) : e < x & Φ_{e}(x) ↓} then f ≤_{T} 0′ and is also clearly dominant. We can even do a bit better and get away with functions of high degree.

Theorem 5.3.1 (Martin’s High Domination Theorem) A set A computes a dominant function f if and only if 0′′ ≤_{T} A′.

Proof. Suppose first that 0′′ ≤_{T} A′. By the Shoenfield limit lemma (Theorem 1.1.11) and the fact that T ot ≤_{T} 0′′, there is an h ≤_{T} A with lim_{s→∞} h(e, s) = T ot(e). We want to compute a function f recursively in A such that, for every e for which Φ_{e} is total, f(x) is larger than Φ_{e}(x) for all but finitely many x. Any such f is dominant. To compute f(x) we compute, for each e < x, both Φ_{e,t}(x) and h(e, t) for t ≥ x until either the first one converges, say to y_{e}, or h(e, t) = 0. As, if Φ_{e} is not total, lim h(e, t) = 0, one of these outcomes must happen. We set f(x) to be one more than the maximum of all the y_{e} so computed for e < x. Note that f ≤_{T} h ≤_{T} A. It remains to verify that if Φ_{e} is total then Φ_{e} < f. By our choice of h, ∃s_{0}(∀s ≥ s_{0})(h(e, s) = 1). So for x > s_{0} when we calculate f(x) we always find a t such that Φ_{e,t}(x) ↓= y_{e} and so f(x) > Φ_{e}(x) for all x > s_{0}.

For the other direction, suppose we have a dominant f. As T ot is Π_{2}^{0} and computes 0′′, it suffices to show that it is also Σ_{2}(f) as it would then be Δ_{2}(f) and so recursive in f′. We claim that

∀x∃sΦ_{e,s}(x) ↓ ⇔ ∃c∀xΦ_{e,f(x)+c}(x) ↓ .

Suppose Φ_{e} is total (if not, then of course both conditions fail). Let k(x) = μsΦ_{k,s}(x) ↓. Then k is recursive (because we know that∀xΦ_{e}(x) ↓). By hypothesis, f dominates k. Thus, the right hand side holds. This is a Σ_{2}(f) formula as desired.

Now a look at the definitions shows that for a ≤_{T} 0′, a ∉ L_{2} is equivalent to 0′ not being high relative to a. Relativizing Theorem 5.3.1 to an a ≤_{T} 0′ we see that a ∉ L_{2} if and only if no f ≤_{T} 0′ dominates every (total) function recursive in A. We can then handle \overline{GL}_{2} by relativizing to a ∨ 0′ to prove the following:

Proposition 5.3.2 A set A ≤_{T} 0′ has degree in \overline{L}_{2} if and only if (∀g ≤_{T} 0′)(∃f ≤_{T} A)(f ≮ g). An arbitrary set A has degree in \overline{GL}_{2} if and only if (∀g ≤_{T} A ∨ 0′)(∃f ≤_{T} A)(f ≮ g).

Proof. Exercise.

This says that, while sets that are not high do not compute dominant functions, if they are not too low they compute functions which are not dominated by any recursive function. This suffices for many applications.

Theorem 5.3.3 If A ∉ GL_{2} then for any recursive notion of forcing P there is 1-generic sequence ⟨p_{s}⟩ ≤_{T} A and so the associated 1-generic G is also recursive in A.

Proof. For any g ≤_{T} A ∨ 0′, there is an f ≤_{T} A not dominated by g. Without loss of generality we may take f to be strictly increasing. We first construct the function g that we want and then, using the associated f, we construct a 1-generic sequence p_{s} recursively in f (and so A). We again make use of the natural order ≤ on P ⊆ ℕ.

Let S_{e} list the Σ_{1} subsets of P. As usual, we declare S_{e} to be satisfied at s if (∃n ≤ s)(p_{n} ∈ S_{e,s}). We define g by recursion using 0′. Given g(s), we want to determine g(s+1). For each condition p ≤ g(s)+1, ask 0′ if (∃q ≤_{P} p)(q ∈ S_{e}) for each e ≤ g(s)+1. If such an extension exists, let x_{e} be the least x such that (∃q ≤_{P} p)(q ≤ x & q ∈ S_{e,x}). Put g(s + 1) = max{x_{e}|e ≤ g(s) + 1}.

We cannot use g itself in the construction of the desired 1-generic ⟨p_{s}⟩ because we want ⟨p_{s}⟩ ≤_{T} A. But, since g ≤_{T} A ∨ 0′, we can use an increasing f ≤_{T} A not dominated by g. The construction of G is recursive in f (hence in A). At stage s, we have finite a condition p_{s}. For each e ≤ s not declared satisfied at s, see if (∃q ≤_{P} p_{s})(q < f(s + 1) & q ∈ S_{e,f(s+1)}). If so, take the smallest such q for the least such e and let it be p_{s+1}. If not, p_{s+1} = p_{s}. The construction is recursive in f, hence in A. Thus ⟨p_{s}⟩ ≤_{T} A and the associated G ≤_{T} A as well. Note that p_{s} ≤ f(s) by induction. Indeed p_{s} ≤ g(s) as well because g(s) gives a bound on the witness required in the definition of p_{s}.

To verify that G is 1-generic suppose, for the sake of a contradiction, that there is a least e_{0} such that

¬∃s(p_{s} ∈ S_{e_{0}} ∨ (∀p ≤_{P} p_{s})(p ∉ S_{e_{0}})).

Choose s_{0} such that, (∀i < e_{0})(∃s)(S_{i} is declared satisfied at s), S_{i} is declared satisfied by s_{0}. Consider any s > s_{0} at which f(s+1) > g(s+1). By our choice of e_{0}, there is a q ≤_{P} p_{s} such that q ∈ S_{e_{0}}. Moreover, as p_{s} ≤ g(s), by definition of g there is one ≤ g(s + 1) such that it belongs to S_{e_{0},g(s+1)} as well. By our choice of s, q ≤ g(s + 1) < f(s + 1). Thus at stage s + 1, we would act to extend p_{s} to a p_{s+1} ∈ S_{e_{0}} for the desired contradiction.

As for the r.e. degrees, having a 1-generic below a degree a ∉ GL_{2} provides a lot of information about the degrees below a. For example, as in Corollary 5.2.8, we can embed every countable partial order below any a ∉ GL_{2}. It is tempting to think that we could also prove the analog of Corollary 5.2.10 that every maximal chain in the degrees below a is infinite. This is true for a < 0′ (Exercise 5.3.4) but was a long open question (Lerman [1983]). Cai [2012] has now proven that it is not true. There are a ∉ GL_{2} which are the tops of a maximal chain of length three.

Exercise 5.3.4 Prove that if a ≤ 0′ and a ∉ L_{2} then any maximal chain in the degrees below a is infinite.

On the other hand, we can say quite a bit that is not true of arbitrary r.e. degrees about the degrees above a when a ∉ GL_{2} .

Definition 5.3.5 A degree a has the cupping property if (∀c > a)(∃b < c)(a ∨ b = c).

Theorem 5.3.6 If a ∈\overline{GL}_{2} then a has the cupping property. Indeed, if A ∉ GL_{2} and C >_{T} A then there is G ≱_{T} A such that A ∨ G ≡_{T} C and G is Cohen 1-generic.

Proof. We need to add requirements R_{e} : Φ_{e}^{G} ≠ A to the proof of Theorem 5.3.3 for Cohen forcing (making all the requirements into a single list Q_{e}) and code C into G as well (so as to be recoverable from A ⊕ G). In the definition of g(s + 1) in that proof, for each p ≤ g(s) + 1 look as well for q_{0}, q_{1} ⊇ p and x such that q_{0}|_{e}q_{1}. Then make g(s+1) also bound the least such extensions τ_{0}, τ_{1} for each e, p ≤ g(s)+1 for which such extensions exist.

Again choose f ≤_{T} A strictly increasing and not dominated by g. The construction is done recursively in f ⊕ C. At stage s we have p_{s} and we look for the least e such that Q_{e} has not yet been declared satisfied and for which there is either a q ≤_{P} p with q ≤ f(s + 1) that would satisfy Q_{e} as before if it is an S_{i} or a pair of strings q_{0}, q_{1} ⊇ p_{s} with q_{i} ≤ f(s + 1) such that q_{0}|_{e}q_{1} if Q_{e} = R_{i}. Let e be the least for which there are such extensions. If Q_{e} = S_{i} choose q as before. If it is R_{i} Let q be the q_{j} such that Φ_{e}^{q_{j}}(x) ↓≠ A(x). We then let p_{s+1} = qˆ C(s) and declare Q_{e} to be satisfied. If there is no such e, we let p_{s+1} = p_{s}ˆ C(s). Note that p_{s+1} ≤ f(s + 1) + 1 (the extra 1 comes from appending C(s)).

Since the construction is recursive in f ⊕ C and f ≤_{T} A ≤_{T} C, we have G ≤_{T} C. But, C ≤_{T} ⟨p_{s}⟩ because C(s) = p_{s+1}(|p_{s+1}|). However, ⟨p_{s}⟩ ≤_{T} A ∨ G because f ≤_{T} A tells how to compute each stage from the given p_{s} to the choice of q. Then G tells us the last extra bit at the end of p_{s+1}.

To verify that G has the other required properties suppose e_{0} is least such that Q_{e} fails. Assume that by stage s_{0} we have declared all requirements with e′ < e_{0} which will ever be declared satisfied to be satisfied. Consider a stage s > s_{0} at which f(s + 1) > g(s + 1). If Q_{e} = S_{i} then we argue as in the previous theorem. If Q_{e} = R_{i} and there were any q_{0}, q_{1} ⊇ p_{s} with q_{0}|_{e}q_{1} then would have taken one of them as our q and declared Q_{e} = R_{i} to be satisfied contrary to our choice of e_{0}. On the other hand, if there are no such extensions, then as usual Φ_{e}^{G} is recursive if total and so R_{i} would also succeed contrary to our assumption.

Remark 5.3.7 Not every r.e. degree has the cupping property.

For other results about \overline{GL}_{2} degrees it is often useful to strengthen Theorem 5.3.3 to deal with notions of forcing recursive in A rather than just recursive ones.

Theorem 5.3.8 For A ∈ \overline{GL}_{2}, given an A recursive notion of forcing P and a sequence D_{n} of dense sets uniformly recursive in A∨0′ (or with a density function d(n, p) ≤_{T} A∨0′) there is a generic sequence ⟨p_{s}⟩ ≤_{T} A meeting all the D_{n}. Of course, the generic G associated with the sequence is recursive in A as well.

Proof. Let m_{K} be the least modulus function for K = 0′ and let Ψ_{n}^{A⊕K} = D_{n}, i.e. the Ψ_{n} uniformly compute membership in D_{n}. We define g ≤_{T} A ∨ 0′ by recursion. Given g(s) we find, for each p, n ≤ g(s)+1 the least q such that q ≤_{P} p and q ∈ D_{n} as witnessed by a computations of Ψ_{n,u}^{A⊕K_{u}↾u}(n) = 1 where K_{u} is the same as K on the use from K in this computation. Next we let g(s + 1) be the least number larger than q, u and m_{K}(u) for all of these q and u as well as m_{K}(g(s) + 1). As g ≤_{T} A ∨ 0′ and A ∈ \overline{GL}_{2} there is an increasing f ≤_{T} A not dominated by g.

We construct the sequence ⟨p_{s}⟩ recursively in f ≤_{T} A. At stage s we have p_{s}. Our plan is to satisfy the requirement of meeting D_{n} for the least n for which we do not seem to have done so yet and for which we can find an appropriate extension of p_{s} when we restrict our search to q ≤ f(s + 1) as well as our use of 0′ to what we have at stage f(s + 1). More formally, we determine (recursively in A) for which D_{n} (n ≤ s) there is a t ≤ s such that Ψ_{n}^{(A⊕K_{f(s+1)})↾f(s+1)}(p_{t}) = 1. Among the other n ≤ s, we search (again recursively in A) for one such that (∃q ≤_{P} p_{s})(q ≤ f(s+1) & Ψ_{n}^{(A⊕K_{f(s+1)})↾f(s+1)}(p_{t}) = 1). If there is one we act for the least such n by letting p_{s+1} be the least such q for this n. If not, let p_{s+1} = p_{s}. Note that p_{s+1} ≤ f(s + 1) by the restriction on the search space and p_{s+1} ≤ g(s + 1) as well since g(s + 1) also bounds the least witness by the definition of g.

We now claim that for each n there is a p_{s} ∈ D_{n}. If not, suppose, for the sake of a contradiction, that n is the least counterexample. Choose s_{0} such that for all m < n there is t < s_{0} such that p_{t} ∈ D_{m} and indeed such that Ψ_{m}^{(A⊕K_{s_{0}})↾s_{0}}(p_{t}) = 1 and K_{s_{0}} ↾ u = K ↾ u where u is the use of this computation of Ψ_{m} at p_{t}. Thus, by construction, we never act for m < n after s_{0}. As g does not dominate f we may choose an s > s_{0} with f(s + 1) > g(s + 1). At stage s we have p_{s} and p_{t} ∉ D_{n} for all t ≤ s in the sense required, i.e. Ψ_{n}^{(A⊕K_{f(s+1)})↾f(s+1)}(p_{t}) = 0 since any computation of this form gives the correct answer by our definition of g(s + 1) and the fact that f(s + 1) > g(s + 1). There is a q ≤_{P} p_{s} with q ∈ D_{n} and the least such is less than f(s + 1) and Ψ_{n}^{(A⊕K_{f(s+1)})↾f(s+1)}(q) = 1 with the computation being a correct one from A ⊕ K by the definition of g(s + 1) < f(s + 1). Thus we would take the least such q to be p_{s+1} ∈ D_{n} for the desired contradiction.

We now give a couple of applications that play a crucial role in our global analysis of definability in D( ≤ 0′). The first is a jump inversion theorem that generalizes Shoenfield’s (Corollary 5.3.10).

Theorem 5.3.9 (\overline{GL}_{2} jump inversion) If A ∈ \overline{GL}_{2}, C ≥_{T} A ∨ 0′, and C is r.e. in A, then there is a B ≤_{T} A such that B′ ≡_{T} C.

Proof. Let C_{s} be an enumeration of C recursive in A. We want a notion forcing recursive in A and a collection of dense sets D_{n} such that for any ⟨D_{n}⟩ generic G, G′ ≡_{T} C. This time, our notion of forcing has conditions p ∈ 2^{<ω}. The definition of extension for P is a bit tricky. If q ⊇ p and

⟨e, x⟩ ∈ [|p|, |q|) ⇒ [C_{|p|}(x) = q(⟨e, x⟩) or ∃n ≤ e (Φ_{n}^{p}(n) ↑ & Φ_{n}^{q}(n) ↓)]

we say that q ≤_{1} p. Now this relation is clearly recursive in A since A computes C_{|p|} for each p. However, it need not be transitive (Exercise). We let ≤_{P} be its transitive closure. As, given any r ⊇ p, there are only finitely many q’s with r ⊇ q ⊇ p we can check all possible routes via ≤_{1} from p to r recursively in A and so ≤_{P} is also recursive in A. The plan for coding C into G′ uses the Shoenfield limit lemma 1.1.11 and partially explains the notion of extension. It guarantees that e ∈ C ⇒ G^{[e]} =^{∗} ω while e ∉ C ⇒ G^{[e]} =^{∗} ∅. Thus e ∈ C ⇔ lim_{s} G(⟨e, s⟩ = 1 and so C ≤_{T} G′. Suppose we have a generic sequence ⟨p_{s}⟩ ≤_{T} A for some collection of dense sets as in Theorem 5.3.8. The definition of extension guarantees that coding mistakes can happen in column e only when Φ_{n}^{p_{s}}(n) first converges for some n ≤ e. Thus C ≤_{T} G′.

Our first class of dense sets include the trivial requirements and in addition force the jump of G in the hope of making G′ ≤_{T} C:

D_{m,j} = {p : |p| ≥ j & [Φ_{m}^{p}(m) ↓ or (∀q ⊇ p)(Φ_{m}^{q}(m) ↑
or [(∃e < m)(∃⟨e, x⟩ ∈ [|p|, |q|)(C_{|p|}(e) ≠ q(⟨e, x⟩) but ¬(∃n ≤ e)(Φ_{n}^{p}(n) ↑ & Φ_{n}^{q}(n) ↓)])}

Note that, after we use A to compute C_{|p|}, membership in D_{m,j} is a Π_{1} property and so recursive in 0′. Thus, the D_{m,j} are uniformly recursive in A ∨ 0′. We must argue that they are dense. Consider any p. We can clearly extend it to a q with |q| ≥ j by making q(⟨e, x⟩) = C_{|p|}(e) for ⟨e, x⟩ ∈ [|p|, j). So we may as well assume that |p| ≥ j. If Φ_{m}^{p}(m) ↓ then p ∈ D_{m,j} and we are done. So suppose Φ_{m}^{p}(m) ↑. If there is q ⊇ p such that Φ_{m}^{q}(m) ↓ and (∀e < m)(∀ ⟨e, x⟩ ∈ [|p|, |q|)[C_{|p|}(x) = q(⟨e, x⟩) or ∃n ≤ e (Φ_{n}^{p}(n) ↑ & Φ_{n}^{q}(n) ↓)], q ≤_{P} p by definition (because Φ_{m}^{p}(m) ↑ while Φ_{m}^{q}(m) ↓ so any violation of coding is allowed for e ≥ m) and is in D_{m,j}. If there is no such q then p ∈ D_{m,j} by definition.

Now we verify that G = ∪p_{s} has the desired properties. By Theorem 5.3.8, G ≤_{T} A. To see that C ≤_{T} G′ consider any e. Let s be such that (∀i ≤ e)(Φ_{i}^{G}(i) ↓⇒ Φ_{i}^{p_{s}}(i) ↓ & i ∈ C ⇒ i ∈ C_{|p_{s}|}). It is clear from the definition of ≤_{P} that for any t > s and ⟨i, x⟩ ∈ [|p_{s}|, |p_{t}|) with i ≤ e, ⟨i, x⟩ ∈ p_{t} ⇔ i ∈ C. Thus C(e) = lim_{t} G(⟨e, t⟩ and so C ≤_{T} G′ by the Shoenfield limit lemma. For the other direction we want to compute G′(e) recursively in C. (Of course, A ≤_{T} C and so then is ⟨p_{s}⟩.) Suppose we have, by induction, computed an s as above for e − 1. We can now ask if e ∈ C. If so, we find a u ≥ t ≥ s such that e ∈ C_{|p_{t}|} and p_{u} ∈ D_{e,|p_{t}|}. If Φ_{e}^{p_{u}}(e) ↓, then, of course, e ∈ G′. If Φ_{e}^{p_{u}}(e) ↑ but e ∈ G′, then there would be a v > u such that Φ_{e}^{p_{v}}(e) ↓ and, of course, p_{v} ≤_{P} p_{u}. This would contradict the fact that p_{u} ∈ D_{e,|p_{t}|} by our choice of s and t and the definitions of D_{e,|p_{t}|} and ≤_{P}.

Corollary 5.3.10 (Shoenfield Jump Inversion Theorem) For all C ≥ 0′ there is B < 0′ such that B′ ≡_{T} C if and only if C is r.e. in 0′.

Proof. The “only if” direction is immediate. The “if” direction follows directly from the Theorem by taking A = 0′.

For later applications we now strengthen the above jump inversion theorem to make B <_{T} A.

Theorem 5.3.11 If A ∈ \overline{GL}_{2}, C ≥_{T} A ∨ 0′, and C is r.e. in A, then there is B <_{T} A such that B′ ≡_{T} C.

Proof. In addition to the requirements of Theorem 5.3.9, we need to make sure that Φ_{i}^{G} ≠ A for each i. To do this we modify the definition of extension to also allow violations of the coding requirements for e when we newly satisfy one of these diagonalization requirements for i ≤ e. (As we did above for making Φ_{i}^{G}(i) ↓.) We say q ≤_{1} p if

⟨e, x⟩ ∈ [|p|, |q|) ⇒ [C_{|p|}(x) = q(⟨e, x⟩) or

∃n ≤ e ([Φ_{n}^{p}(n) ↑ & Φ_{n}^{q}(n) ↓] or [∃yΦ_{n}^{q}(y) ↓≠ A(y) & ¬∃yΦ_{n}^{p}(y) ↓≠ A(y)]) .

Again ≤_{P} is defined as the transitive closure of this relation and it is recursive in A ∨ 0′ as before. We then adjust the D_{m,j} accordingly

D_{m,j} = {p : |p| > j & [Φ_{m}^{p}(m) ↓ or (∀q ⊇ p)(Φ_{m}^{q}(m) ↑
or [(∃e < m)(∃⟨e, x⟩ ∈ [|p|, |q|)(C_{|p|}(e) ≠ q(⟨e, x⟩) but
¬(∃n ≤ e)([Φ_{n}^{p}(n) ↑ & Φ_{n}^{q}(n) ↓] & ¬(∃y)[Φ_{n}^{q}(y) ↓≠ A(y) & ¬∃yΦ_{n}^{p}(y) ↓≠ A(y)])]}.

We also need dense sets that guarantee that Φ_{e}^{G} ≠ A:

D_{i} = {p|(∃x)(Φ_{i}^{p}(x) ↓≠ A(x) or
(∀q_{0}, q_{1} ⊇ p)(∀x < |q_{0}|, |q_{1}|)[¬(Φ_{i}^{q_{0}}(x) ↓≠ Φ_{i}^{q_{1}}(x) ↓) or
((∃e < i)(∃⟨e, x⟩ ∈ [|p|, |q|)(∃j ∈ {0, 1})[(C_{|p|}(e) ≠ q_{i}(⟨e, x⟩) but
¬(∃n ≤ i)([Φ_{n}^{p}(n) ↑ & Φ_{n}^{q}(n) ↓] & ¬(∃y)[Φ_{n}^{q}(y) ↓≠ A(y) & ¬∃yΦ_{n}^{p}(y) ↓≠ A(y)])]}.

The proof now proceeds as in the previous Theorem. The arguments for all the verifications are now essentially the same as there and are left as an exercise.

Exercise 5.3.12 Verify that the notion of forcing and classes of dense sets specified in the proof of Theorem 5.3.11 suffice to actually prove it.

Exercise 5.3.13 Prove that if A is r.e. and C ≥_{T} 0′ is r.e. in A then there is a B ≤_{T} A such that B′ ≡_{T} C. Indeed we may also make B <_{T} A.

The next result says that every a ∈ \overline{GL}_{2} is RRE (relatively recursively enumerable), i.e. there is a b < a such that a is r.e. in b and a bit more.

Theorem 5.3.14 If a ∈ \overline{GL}_{2} then there is b < a such that a is r.e. in b and a is in \overline{GL}_{2}(b), i.e. (a ∨ b′)′ < a′′.

Proof. Let a ∈ \overline{GL}_{2}. We’ll use a notion of forcing P with conditions p = ⟨p_{0}, p_{1}, p_{2}⟩, p_{i} ∈ 2^{<ω} such that

1. |p_{0}| = |p_{1}|, p_{0}(d_{n}) = A(n), p_{1}(d_{n}) = 1 − A(n) where d_{n} is nth place where p_{0}, p_{1} differ and

2. (∀e < |p_{0} + p_{1}|)(e ∈ p_{0} ⊕ p_{1} ⇔ ∃x(⟨e, x⟩ ∈ p_{2})).

As expected, our generic set G_{0} ⊕ G_{1} ⊕ G_{2} is given by V (p) = p_{0} ⊕ p_{1} ⊕ p_{2}. The idea here is that if we can force p_{0}, p_{1} to differ at infinitely many places while still making our generic sequence recursive in A, the first clause in the definition of ≤_{P} guarantees that G_{0} ⊕ G_{1} ≡_{T} A. The second clause works towards making G_{0} ⊕ G_{1} r.e. in G_{2} with the intention being that deg(G_{2}) = g_{2} is to be the b required by the theorem. Extension in the notion of forcing is defined in the simplest way as q ≤_{P} p ⇔ q_{i} ⊇ p_{i} but note that this only applies to p and q in P and not all q with q_{i} ⊇ p_{i} are in P even if p ∈ P. The notion of forcing is clearly recursive in A.

We now define the dense sets needed to satisfy the requirements of the Theorem. We begin with D_{2n} = {p : p_{0}, p_{1} differ at at least n points}. These sets are clearly recursive in A. We argue that these are dense by induction on n. Suppose D_{2n} is dense. To show that D_{2n+2} is dense, it suffices, for any given p ∈ D_{2n} − D_{2n+2}, to find a q ≤_{P} p in D_{2n+2}. Let q_{0} = p_{0}ˆ A(n), q_{1} = p_{1}ˆ (1 − A(n)). Choose i ∈ {0, 1} such that q_{i}(|p_{0}|) = 1. Define q_{2} ⊇ p_{2} by choosing x large and setting q_{2}(⟨2|p_{0}| + i, x⟩) = 1 and q_{2}(z) = 0 for all z ∉ dom(p_{2}) and less than ⟨2|p_{0}| + i, x⟩. Now q = ⟨q_{0}, q_{1}, q_{2}⟩ satisfies the requirements to be a condition in P. It obviously extends p and is in D_{2n+2}.

For any generic recursive in A which meets all the D_{2n}, G_{0} ⊕ G_{1} ≡_{T} A and G_{0} ⊕ G_{1} is r.e. in G_{2}.

We also want dense sets similar in flavor to those of the previous theorems to force the jump of G_{2} to make (a ∨ g′_{2})′ < a′′. Let

D_{2n+1} = {p : Φ_{n}^{p_{2}}(n) ↓ or (∀σ ⊇ p_{2})
(Φ_{n}^{σ}(n) ↑ or (∃⟨e, x⟩ ∈ σ)((p_{0} ⊕ p_{1})(e) = 0)}.

For p ∈ P, membership in D_{2n+1} is a 0′ question and so these sets are recursive in A∨0′. We want to prove that they are dense. Suppose have a p ∈ P and so we want a q ≤_{P} p with q ∈ D_{2n+1}. We may suppose that Φ_{n}^{p_{2}}(n) ↑ and that the second clause fails for p as otherwise we would already be done. Thus we have a σ ⊇ p_{2} such that Φ_{n}^{σ}(n) ↓ but ¬(∃⟨e, x⟩ ∈ σ)((p_{0} ⊕p_{1})(e) = 0). We claim that there is a q ≤_{P} p such that q_{2} ⊇ σ and so Φ_{n}^{q_{2}}(n) ↓ and q ∈ D_{2n+1} as required. The only issue is that there may be some ⟨j, y⟩ ∈ σ with j > |p_{0} ⊕ p_{1}|. If so, we must define q_{0} and q_{1} accordingly, i.e. j ∈ q_{0} ⊕ q_{1}. So if j is even, we want \frac{j}{2} ∈ q_{0}; if it is odd, \frac{j−1}{2} ∈ q_{1}. We now define q_{0}, q_{1} at the appropriate element (\frac{j}{2} or \frac{j−1}{2}) to both be 1. Elsewhere we let both q_{0} and q_{1} be 0. Thus we have not added any points at which q_{0} and q_{1} differ beyond those in p_{0}, p_{1}). Now we extend σ to q_{2} by adding ⟨e, y⟩ for some large y if (q_{0} ⊕ q_{1})(e) = 1 and e ≥ |p_{0} ⊕ p_{1}| and wherever not yet defined we let q_{2}(z) = 0. Thus q ∈ P and is the desired extension of p in D_{2n+1} as Φ_{n}^{q_{2}}(n) = Φ_{n}^{σ}(n) ↓.

We now let ⟨p_{s}⟩ ≤_{T} A be a generic sequence meeting every D_{n} as given by Theorem 5.3.8. We have already seen that G_{0} ⊕G_{1} ≡_{T} A and it is r.e. in G_{2} ≤_{T} A. If we can show that (A ⊕ G′_{2})′ <_{T} A′′ then we will be done as this clearly implies that G_{2} <_{T} A. We first claim that G′_{2} ≤_{T} A ∨ 0′. To see if n ∈ G′_{2}, recursively in A ∨ 0′ find an s such that p_{s} ∈ D_{2n+1}. Then we claim that n ∈ G′_{2} ⇔ Φ_{n}^{p_{s,2}}(n) ↓. If Φ_{n}^{p_{2}}(n) ↓, then we are done. If not, then (∀σ ⊇ p_{s,2}) (Φ_{n}^{σ}(n) ↑ or (∃⟨e, x⟩ ∈ σ)((p_{0} ⊕ p_{1})(e) = 0)) and by definition of membership and extension in P, Φ_{n}^{p_{t,2}}(n) ↑ for every p_{t,2} for t ≥ s. Thus Φ_{n}^{G_{2}}(n) ↑ as desired. As G′_{2} ≤_{T} A∨0′, (A⊕G′_{2}) = A∨0′ and so as A ∉ GL_{2}, (A⊕G′_{2})′ = (A∨0′)′ <_{T} A′′ as required.

Exercise 5.3.15 If A >_{T} 0 is r.e. and C ≥_{T} 0′ is r.e. in A then there is a B ≤_{T} A such that B′ ≡_{T} C. Indeed we may also make B <_{T} A. Hint: ....Build β_{s} finite extensions that obey a coding rule for columns for e ≤ c(s) ≤ s (so that we can enumerate C recursively in A) except that can violate the rule to force jump as above; search below m_{A}(s + 1) for extensions forcing jump for e ≤ s that obey rule. Also search for extensions so Φ_{e} giving different answers and allow violations in columns > e when satisfy this requirement by choosing one that gives answer other than A.

We can now deduce a result that plays a major role in our analysis of definability in D(≤0′) (and many other results).

Theorem 5.3.16 If b <_{T} a and a ∈ \overline{GL}_{2}(b) and I is a Σ_{3}^{B} ideal in D(≤b) then there is an exact pair for I below a.

Proof. By Theorem 5.3.14 (relativized to b) there is a c such that b ≤ c < a and a is r.e. in c. So I is also Σ_{3}^{C}. Now, by Theorem 5.2.12, we have the desired exact pair.

Theorem 5.3.17 If A ∈ a ∈\overline{GL}_{2} and S ∈ Σ_{3}^{A} then there is an embedding of a nice effective successor model (with the appropriate partial lattice structure) in the degrees below deg(A) and an exact pair x, y ≤ a for the ideal generated by the d_{n} with n ∈ S. (Remember that the d_{n} are the degrees representing n ∈ ℕ in the effective successor model.

Proof. Given A ∈ \overline{GL}_{2} and S ∈ Σ_{3}^{A} Theorem 5.3.14 gives us a B < A such that A is r.e. in B and A is \overline{GL}_{2}(B). Since A′ ≥ A ∨ 0′ and is r.e. in it, Theorem 5.3.9 relativized to B gives us a B̂ < A (with B ≤_{T} B̂) such that B̂′ ≡ A′ and so ΣB̂ ; 3 = Σ_{3}^{A}, Moreover, A is r.e. in B̂ because it was r.e. in B ≤_{T} B̂. The result now follows by using Theorem 5.2.6 and Exercise 3.3.10 to embed an effective successor model between B̂ and A and then Theorem 5.2.12 to pick out the ideal generated by the associated d_{n} for n ∈ S as the set {e|∃n(ΦB̂ ; e ∈ d_{n})} is itself ΣB̂ ; 3 = Σ_{3}^{A} as is then {e|(∃n ∈ S)(Φ_{e}^{A} ∈ d_{n})}.

Exercise 5.3.18 Prove that every degree has a GL_{2} degree below it.

Exercise 5.3.19 Prove that every recursive lattice L with 0 and 1 can be embedded in D(≤a) preserving 0 and 1 for any a ∈ \overline{GL}_{2}.

5.4. DEFINABILITY AND BIINTERPRETABILITY IN D(≤ 0′) 67

Notes: Theorem 5.3.1 is due to Martin [1966]. Its very useful consequence, Proposition 5.3.2 is from Jockusch and Posner [1978] which also contains a version of Theorem 5.3.3 for Cohen forcing, Exercises 5.3.4 and 5.3.18 as well as Theorem 5.3.9. The version given here of Theorem 5.3.3 and the more general Theorem 5.3.8 as well as 5.3.14 come from Cai and Shore [2012]. Corollary 5.3.10 was originally proved in Shoenfield [1959]. The original direct proof of (a stronger version of) Theorem 5.3.17 is in Shore [2007]. Remark 5.3.7 follows, for example, from Slaman and Steel [1989, Theorem 3.1] or Cooper [1989]. Theorem 5.3.6 is from Jockusch and Posner [1978].

5.4 Definability and Biinterpretability in D(≤ 0′)

We already know that the theory of D(≤0′) is (recursively) equivalent to true first order arithmetic and so as complicated as possible. We now want attack the problem of determining which subsets of, and relations on, D(≤0′) are definable in the structure. The interpretation of D(≤0′) in ℕ gives a necessary condition. Only subsets and relations definable in arithmetic can possibly be definable in D(≤0′). Our goal is to prove that, if they are also invariant under the double jump, then the are, in fact, definable in D(≤0′).

Definition 5.4.1 A relation R(x_{1}, … x_{n}) on degrees is invariant under the double jump if, for all degrees x_{1}, … x_{n} and y_{1}, … y_{n} such that x′′_{i} = y′′_{i} for all i ≤ n, R(x_{1}, … x_{n}) ⇔ R(y_{1}, … y_{n}).

We begin with the subsets of D(≤ 0′) and, in particular, with the basic question of definably determining the double jump of a degree a ≤ 0′. (This would actually suffice to show that all subsets of D(≤0′) invariant under double jump and definable in arithmetic are definable in D(≤0′) but as we prove more later we omit this argument.) The crucial point is that the sets we can code below an r.e. or \overline{GL}_{2} degree a are precisely the ones Σ_{3}^{A}. We use this to determine a′′ via the following characterization of the double jump.

Proposition 5.4.2 For any sets A and B, A′′ ≡_{T} B′′ if and only if Σ_{3}^{A} = Σ_{3}^{B}. Indeed, for any n ≥ 1, A^{(n)} ≡_{T} B^{(n)} if and only if Σ_{n+1}^{A} = Σ_{n+1}^{B}.

Proof. The hierarchy theorem 1.1.10 says that, for any set X and n ≥ 1, Σ_{n+1}^{X} = Σ_{1}^{X^{(n)}}. On the other hand, for any Z and W, Σ_{1}^{Z} = Σ_{1}^{W} iff Z ≡_{T} W since the equality implies that both Z and Z̄ (W and W̄) are Σ_{1}, i.e. r.e., in W (Z) and so each is recursive in the other. Thus if Σ_{n+1}^{A} = Σ_{n+1}^{B} then Σ_{1}^{A^{(n)}} = Σ_{1}^{B^{(n)}} and so A^{(n)} ≡_{T} B^{(n)} as required.

Theorem 5.4.3 The set L_{2} = {x ≤ 0′|x′′ = 0′′} is definable in D(≤0′).

Proof. Our analysis of coding in models of arithmetic in Proposition 3.4.3 and preceding Theorem 4.3.5 (which is really part of the proof of that theorem), shows that we have a way to, definably in D(≤0′), pick out, via correctness conditions, parameters p̄ that define structures M(p̄) isomorphic to ℕ. (The crucial point here is Theorem 5.2.12 which says that there is an exact pair for the Σp̄_{0} 3 ideal generated standard part of the model below 0′ as it is r.e. in and strictly above p̄_{0}.) Also note that, by Proposition 3.4.3, any set S coded in them by a pair g_{0}, g_{1} and a coding formula φ_{S}(x, p̄) is Σ_{3}^{A} as long as the parameters q̄ for the nice effective successor structure determining the domain of the model and g_{0}, g_{1} are recursive in A.

We now claim that x ∈ L_{2} if and only for any such q̄, g_{0}, g_{1} ≤_{T} x the set S coded by g_{0}, g_{1} is Σ_{3}. Moreover, this property is definable in D(≤0′) and so proves the Theorem.

First suppose that x ∈ L_{2}. Then our initial remarks show that S ∈ Σ_{3}^{X} for any X ∈ x. As X′′ ≡_{T} 0′′, Σ_{3}^{X} = Σ_{3} by Proposition 5.4.2. Next, if x ∉ L_{2}, then by Exercise 3.3.10 and Theorem 5.3.3 there are parameters q̄ defining a nice effective successor model with join c < x with c′ = 0′. By Theorem 4.3.4, we can extend these parameters to ones p̄ defining a standard model of arithmetic which, of course, satisfies the definable properties guaranteeing that it is such a model. Now, by Theorem 5.3.16, for any S ∈ Σ_{3}^{X} there are g_{0}, g_{1} ≤_{T} x which code S in this model. Since x′′ > 0′′ there is an S ∈ Σ_{3}^{X} − Σ_{3} again by Proposition 5.4.2 and so a code for such an S below x as required.

Finally, note that as we are working in definable standard models of arithmetic we can definably say that a set is Σ_{3} simply by using the translation into our degree structure of the corresponding sentence of arithmetic.

Theorem 5.4.4 For every h ≥ 0′′ which is r.e. in 0′′, the set {x ≤ 0′|x′′ = h} is definable in D(≤0′).

Proof. The previous theorem handles the case that h = 0′′. For h > 0′′ Let E ∈ e ∈ [0′, 0′′] be such that E′ ∈ h. There is such an E by Corollary 5.3.10 and we can fix a definition of one in arithmetic. Consider the formula which says that for any q, g_{0}, g_{1}< x and p̄ which define a standard model of arithmetic and a set S coded in the model as in the proof of the Theorem, S ∈ Σ_{2}^{E} and for any set Ŝ ∈ Σ_{2}^{E} (again as given by a definition in arithmetic) there are such q, g_{0}, g_{1}< x and p̄ defining Ŝ. Proposition 5.4.2 and calculations already described now show that this guarantees that Σ_{2}^{X′} = Σ_{3}^{X} = Σ_{2}^{E} and so x′′ = e′ = h as required.

Corollary 5.4.5 The jump classes L_{n} (a^{(n)} = 0^{(n)}) and H_{n} (a^{(n)} = 0^{(n+1)}) are definable in D(≤0′) for n ≥ 2.

Proof. In the proof of Theorem 5.4.4, require instead of E′ ∈ h that E^{(n−1)} ≡_{T} 0^{(n)} for L_{n} and E^{(n−1)} ≡_{T} 0^{(n+1)} for H_{n}.

By a separate additional argument that requires results beyond the scope of these lectures we can also get the definability of H_{1}. While we could make such an argument at this point it will be easier later. We do so in Corollary 5.4.11. The definability of L_{1} in D(≤0′) is an important open problem.

If we now wish to deal with arbitrary relations on D(≤0′) rather than simply subsets, we are faced with the problem that our analysis so far has, for each degree a, produced various models of arithmetic in which we code the sets Σ_{3}^{A}. To discuss even binary relations we must have a way to analyze any a and b (or equivalently the sets coded below them as long as we are only working up to invariance under the double jump) in a single model (perhaps with additional correctness conditions). The basic formulation of this issue is given by asking about the biinterpretability of the structure (here D(≤0′)) with arithmetic (here first order). A similar notion applies to other structures (such as the r.e. degrees, R) still with first order arithmetic and to ones such as D but for second order arithmetic.

Definition 5.4.6 A degree structure S is biinterpretable with true second (first) order arithmetic if it is interpretable in second (first) order arithmetic and we have formulas in parameters p̄ (including a correctness condition) as specified in §4.1 and a formula φ_{S}(x, ȳ) which defines sets (coded) in the model given by p̄ as described there which provide an interpretation of true arithmetic in S (i.e. the models M(p̄) satisfying the correctness condition are all standard). For second order arithmetic, we require that the sets defined by φ_{S}(x, ȳ) as ȳ ranges over all parameters in S are all subsets of ℕ. Moreover, for both first and second order arithmetic, there is an additional formula φ_{R}(x, ȳ, p̄) such that S ⊨ ∀x∃ȳφ_{R}(x, ȳ, p̄) and for every a, ḡ ∈ S, S ⊨φ_{R}(a, ḡ, p̄) if and only if the set {n|φ_{S}(d_{n}, ḡ, p̄)} (where d_{n} is the nth element of the model M(p̄) coded by the parameters p̄) is of degree a. These last conditions then say that the set coded in M(p̄) by ḡ is of degree a and that all degrees a in S have codes ḡ for a set of degree a. We say that S is biinterpretable with true first or second order arithmetic up to double jump if we weaken the second condition on φ_{R} so that for every a, b̄ ∈ S, S ⊨φ_{R}(a, b̄, p̄) if and only if the set {n|φ_{S}(d_{n}, b̄, p̄)} has the same double jump as a.

It is not hard to see that, if a degree structure S is biinterpretable with first or second order arithmetic, then we know all there is to know about definability in, and automorphisms of, S.

Theorem 5.4.7 If a degree structure S is biinterpretable with first or second order arithmetic then it is rigid, i.e. it has no automorphisms other than the identity, and a relation on S is definable in S if and only if it is definable in first or second order arithmetic, respectively.

Proof. We first prove rigidity. Let p̄ satisfy all the formulas required for it to determine a standard model of arithmetic via the given formulas. Consider any a ∈S with some ḡ such that S ⊨ φ_{R}(a, ḡ, p̄) and any automorphism Ψ of S. The image Ψ(p̄) = r̄ satisfies all the same formulas as p̄ and so also defines a standard model of arithmetic. The image h̄ of ḡ under Ψ also determines a subset of this model via φ_{S} and it must be the “same” subset in the sense that they correspond to the same subset of ℕ via the isomorphisms among M(p̄), M(r̄) and ℕ. Of course, φ_{R}(b, h̄, r̄) (where b =Ψ(a)) is also true in S since Ψ is an automorphism. Our definition of biinterpretability now says that a = b as required for rigidity.

Now consider any relation Q(x̄) on S. By the assumption that S is interpretable in first or second order arithmetic, we know that Q is definable in those structures. For the other direction, suppose Q is definable by a formula Θ of first or second order arithmetic.

If this is first order arithmetic then we expanded it by a sequence X̄ of second order parameters (of the same length n as x̄) whose intended interpretations are some subsets of the model. If it is second order arithmetic then we simply assume that the formula already contains a sequence X̄ of free second order variables (of the same length as x̄). In any case, Θ defines the property that the sequence of the degrees of X satisfies Q.) Q is then

defined in S by the formula Ψ(z̄) ≡ ∃p̄, ḡ_{0} … ∃ḡ_{n−1}(φ_{c}(p̄) & ⋀_{i<n} φ_{R}(z_{i}, ḡ_{i}, p̄) → Θ^{T} (ḡ_{i}, p̄))

where T is the translation of formulas of second order arithmetic given in §4.1. Here our correctness condition φ_{c} guarantees that the model M(p̄) is standard and we also assume that the requirements of the definition of biinterpretability are satisfied. So the translation of Θ asserts (because of the properties of φ_{R}) that a sequence of sets of degree z_{i} satisfy Θ (in ℕ), i.e. Q holds of z̄.

Our goal now is to prove that D(≤0′) is biinterpretable with arithmetic up to double jump and so every relation on it invariant under the double jump is definable in it if and only if it is definable in first order arithmetic.

Theorem 5.4.8 D(≤0′) is biinterpretable with arithmetic up to double jump.

Theorem 5.4.3 and Theorem 5.4.4 show that we can define the double jump classes of degrees a in D(≤0′) by talking about the sets that are coded (by our usual formula φ_{S}(x, ḡ)) in standard models M(p̄) of arithmetic with q̄, ḡ below a as in the proof of Theorem 5.4.3. The point here is that these sets determine Σ_{3}^{A} and so a′′ by Proposition 5.4.2. If we wish to define the relations needed for biinterpretability up to double jump, we need to be able to talk about the sets that are Σ_{3}^{A} for an arbitrary degree a simultaneously in a single model. Our plan is to provide a scheme defining isomorphisms between two arbitrary standard models satisfying some additional correctness condition. Such isomorphisms would allow us to definably transfer (codes for) sets in different models to ones for the same sets in a single model and so define the required relation φ_{R}. We begin with a lemma that is used to build such isomorphisms by interpolating a sequence of additional models between the two given ones and isomorphisms between each successive pair of models.

Lemma 5.4.9 If c ≤ 0′, c ∈ \overline{L}_{2} , a_{0}, a_{1} ∈ L_{1} and P is a recursive notion of forcing, then there is a G ≤_{T} C which is 1-generic for P and such that A_{0} ⊕ G and A_{1} ⊕ G are both low.

Proof. Let D_{n,2} be the usual dense sets for making G 1-generic for P. They, and the density function for them, are uniformly recursive in 0′. Now consider, for i ∈ {0, 1}, the sets D_{n,i} = {p|Φ_{n}^{A_{i}⊕V (p)}(n) ↓ or (∀q ≤ p)Φ_{n}^{A_{i}⊕V (q)}(n) ↑}. As the A_{i} are low, these sets and their density functions are also uniformly recursive in 0′. Thus, by Theorem 5.3.8, there is a 1-generic sequence ⟨p_{k}⟩ and associated generic set G both recursive in C meeting all these dense sets. Any such G clearly has all the properties required in the theorem. (Follow, for example, the proof of Proposition 3.2.13 using these D_{e,i} in place of D_{1,e}.)

Proof (of Theorem 5.4.8). In addition to the previous correctness conditions for our standard models M(p̄) we require for the rest of this section that p_{0}, the first of the parameters p̄, which bounds the parameters q̄ defining the nice effective successor structure providing the domain d_{n} of the model, is in L̄_{2}. (This condition is definable by Theorem 5.4.3.) Given two such models M(p̄_{0}) and M(p̄_{4}) we want to show that there are additional models M(p̄_{k}) for k ∈ {1, 2, 3} and uniformly definable isomorphisms between the domain of these models taking d_{i,n} to d_{1+1,n} for i < 4. (Given parameters p̄_{k} defining a model M(p̄_{k}) we write d_{k,n} for the degree representing the nth element of this model. Similarly, we write p̄_{k,0} for the first element of p̄_{k} and q̄_{k} for the parameters in p̄_{k} determining the effective successor structure which provides the domain of M(p̄_{k}).) Thus (as we explain below) we produce a single formula θ(x, y, z̄, z̄′) which uniformly defines isomorphisms between any two of our standard models M(p̄_{0}) and M(p̄_{4}) (with z̄ and z̄′ replaced by p̄_{0} and p̄_{4}).

We begin by choosing q̄_{1} < 0′ as given by a 1-generic over p_{0,0} sequence and function for the recursive notion of forcing (Exercise 3.3.10) that embeds a nice effective successor model with q̄_{1,0}, the first element of q̄_{1}, being the bound on all the other required parameters. As p_{0,0} ∈ L_{2}, 0′ is L̄_{2}(p_{0,0}) and so such q̄_{1} exists by Theorem 5.3.3 (relativized to p_{0,0}). Note that q̄_{1} (and so q̄_{1,0}) is in L_{1} by Proposition 3.2.13 as it is associated with a 1-generic sequence recursive in 0′. We may now extend q̄_{1} to p̄_{1} defining a standard model M(p̄_{1}) by Exercise 4.3.3 and Theorem 5.3.3 as 0′ is \overline{GL}_{2}(q̄_{1}). Similarly, we see that there are q̄_{3} and p̄_{3} bearing the same relation to M(p_{4}) as q̄_{1} and p̄_{1} do to M(p_{0}). Now as q̄_{1,0} and q̄_{3,0} are both low we may apply Lemma 5.4.9 to the forcing of Exercise 3.3.10 to get q̄_{2} < 0′ (again as 0′ ∈ L̄_{2}(q̄_{1,0}), L̄_{2}(q̄_{3,0})) such that both q̄_{1,0} ⊕ q̄_{2,0} and q̄_{2,0} ⊕ q̄_{3,0} are in L_{1} and then extend q̄_{2} to p̄_{2} defining M(p̄_{2}) as we did for q̄_{1}.

We now apply Exercise 4.3.3 and Theorem 5.3.3 to get the desired schemes defining our desired isomorphisms: Given any n ∈ ℕ and i < 4, consider the finite sequences of degrees ⟨d_{i,0}, …, d_{i,n}⟩ and ⟨d_{i+1,0}, …, d_{i+1,n}⟩. We want to show that there are parameters r̄_{i} < 0′ such that the formula φ_{2}(x, y, r̄_{i}) (where φ_{2}(x, y, z̄) ranges over binary relations as z̄ varies as in Theorem 4.2.3) defines an isomorphism taking d_{i,k} to d_{i+1,k} for each k ≤ n. By the results just cited it suffices to show that the ⨁_{k<n} d_{i,k} ⊕ ⨁_{k<n} d_{i+1,k} are in L_{2} for each

i < 4. For i = 0, note that q̄_{1} is associated with a 1-generic/p_{0.0} sequence which is recursive in 0′. Thus by Proposition 3.2.13 (suitably relativized) (q̄_{1}⊕p_{0,0})′ = p′_{0,0} and so (q̄_{1,0} ⊕p̄_{0,0})′ = p′_{0,0}. As p_{0,0} ∈ L_{2}, 0′′ = p̄′′_{0,0} = (q̄_{1,0} ⊕p̄_{0,0})′′ as required. The argument for i = 3 is similar. For the other pairs, we have already guaranteed that q̄_{1,0} ⊕ q̄_{2,0} and q̄_{2,0} ⊕ q̄_{3,0} are both L_{1}.

We can now define the desired isomorphism θ(n, m, p̄_{0}, p̄_{4}) between M(p̄_{0}) and M(p̄_{4}). We say that an n in the domain of M(p̄_{0}) (i.e. φ_{D}(n, p̄_{0})) is taken to m in the domain of M(p̄_{4}) if and only if there are degrees p̄_{k} for k ∈ {1, 2, 3} defining models of arithmetic M(p̄_{k}) and ones r̄_{i} for i < 4 as above such that each φ_{2}(x, y, r̄_{i}) defines an isomorphism between initial segments of (the domains of) M(p̄_{i}) and M(p̄_{i+1}) where the initial segment in M(p̄_{0}) is the one with largest element n and that in M(p̄_{1}) has largest element m. Clearly this can all be expressed using the formulas φ_{D}(x, p̄_{k}) and φ_{<}(x, y, p̄_{k}) defining the domains of M(p̄_{k}) and the orderings on them. Note that the definition of this isomorphism is uniform in p̄_{0} and p̄_{4} and that we have shown that for any p̄_{0} and p̄_{4} defining our standard models of arithmetic, there are parameters below 0′ defining all these isomorphisms. In other words, we have described the desired formula θ(x, ȳ, z̄, z̄′).

We now wish to define the formula φ_{R}(x, ȳ, p̄_{0}) required in the definition of biinterpretability up to double jump (for M(p̄_{0}) a model of arithmetic). (We have replaced p̄ in Definition 5.4.6 by p̄_{0} to match our current notation.) First, φ_{R} says that, if x ∈ L_{2} (as defined by Theorem 5.4.3), then ȳ defines (via our standard φ_{S}) the empty set in M(p̄_{0}). In addition, φ_{R} says that, if x ∉ L_{2} and S is the set defined in M(p̄_{0}) by ȳ, then for every set Ŝ ∈ Σ_{3}^{S} (with Ŝ defined by other parameters h̄ in M(p̄_{0}) and Ŝ ∈ Σ_{3}^{S} expressed in the translation of arithmetic into M(p̄_{0})), there are ḡ < x and p̄_{4} with p̄_{4,0} < x such that ḡ codes a set Ŝ_{4} in M(p̄_{4}) and, for every n and m, θ(n, m, p̄_{0}, p̄_{4}) implies that φ_{S}(n, h̄, p̄_{0}) ⇔φ_{S}(m, ḡ, p̄_{4}), i.e. Ŝ = Ŝ_{4}. By all that we have done already, this guarantees that every Ŝ ∈ Σ_{3}^{S} is Σ_{3}^{X}. For the other direction, φ_{R} also says that if ḡ < x and p̄_{4} with p̄_{4,0} < x are such that ḡ codes a set Ŝ_{4} in M(p̄_{4}) then there is a set Ŝ (coded in M(p̄_{0}) by some h̄) which is Σ_{3}^{S} (as expressed in M(p̄_{0})) such that Ŝ = Ŝ_{4} as expressed as above using θ. So again by what we have already done, this guarantees that every Ŝ_{4} ∈ Σ_{3}^{X} is Σ_{3}^{S}. Thus, by Proposition 5.4.2, S has the same double jump as X as required.

Theorem 5.4.10 A relation on D(≤0′) which is invariant under the double jump is definable in D(≤0′) if and only if it is definable in true first order arithmetic.

Proof. Follow the proof of Theorem 5.4.7 but use Theorem 5.4.8 in place of the assumption that the structure is biinterpretable with arithmetic.

Corollary 5.4.11 H_{1} is definable in D(≤0′).

Proof. This follows immediately from the Theorem and fact that x < 0′ is in H_{1} if and only if D(≤0′) ⊨∀z∃y ≤ x(z′′ = y′′). This fact is proven for r.e. x in Nies, Shore and Slaman [1998, Theorem 2.21] but (as indicated there on p. 257) replacing the last use of the Robinson jump interpolation theorem in the proof by Theorem 5.3.9 provides a proof for D(≤0′).

The analogous theorems hold for both D and R, i.e. they are biinterpretable with second or first order arithmetic, respectively, up to double jump. (Moreover, in D the jump is also definable.) Their definable relations which are invariant under the double jump are then characterized in the same way. Indeed, every jump ideal I of D (i.e. an ideal that is also closed under the jump operator) which contains 0^{(ω)} is biinterpretable with second order arithmetic up to double jump if one takes the second order structure to have sets precisely those with degrees in I and the jump is definable in I as well.

By more extensive uses of Theorem 5.3.8 we can prove our biinterpretability and so definability results for D(≤ x) for any x ≤ 0′ in L̄_{2}.

Exercise 5.4.12 For every x ≤ 0′ in L̄_{2}, T h(D(≤x) is biinterpretable with true first order arithmetic and so its theory is 1-1 equivalent to that of true arithmetic. Moreover, for every x ≤ 0′ a relation on D(≤ x) invariant under double jump is definable in D(≤ x) if and only if it is definable in first order arithmetic. (For x ∈ L_{2}, this last result is trivial. Otherwise, it follows from biinterpretability as before.)

The Biinterpretability Conjectures for D(≤0′), R and D assert that these structures are actually biinterpretable with first, first and second order arithmetic, respectively. As we have seen proofs of these conjectures would show that the structures are rigid and would completely characterize their definable relations. These are the major open problems of degree theory.

Notes: The definitions of biinterpretability for different degree structures and the associated conjectures are due to Harrington and Slaman and Woodin (see Slaman [1991] and [2008]). Theorems 5.4.3 and 5.4.4 are originally due to Shore [1988] but for triple jump in place of double jump. The improvement of one jump is essentially an application of Proposition 5.4.2 as pointed out in Nies, Shore and Slaman [1998] where Corollary 5.4.11 also appears. Slaman and Woodin also proved Theorem 5.4.7 (again see Slaman [1991] and [2008]). Plans for proving Theorem 5.4.8 were proposed in both Shore [1988] and more concretely in Nies, Shore and Slaman [1998] but neither actually provided the definitions of the required comparison maps nor the proofs that they exist as we have done here. Thus Theorems 5.4.8, 5.4.10 and the improvement to initial segments of D(≤0′) bounded by any x ∈ L̄_{2} of Exercise 5.4.12 are new. A proof of Exercise 5.4.12 will appear in Shore [2013]. Biinterpretability up to double jump for the r.e. degree R is proven in Nies, Shore and Slaman [1998]. Slaman and Woodin (see Slaman [1991] and [2008]) proved it for D. A very different proof that also gives the results described for jump ideals containing 0^{(ω)} is in Shore [2007]. The definability of the jump is proven in Shore and Slaman [1999] based on the results of Slaman and Woodin. This reliance is removed in Shore [2007] where the jump is also defined in every jump ideals containing 0^{(ω)}.

74 CHAPTER 5. DOMINATION PROPERTIES

Bibliography

Abraham, U. and Shore, R. A. [1986], Initial segments of the Turing degrees of size ℵ_{1}, Israel J. Math. 55, 1-51.

Cai, M. [2012], Array nonrecursiveness and relative recursive enumerability, J. of Symb. Logic, to appear.

Cai, M. and Shore, R. A. [2012], Domination, forcing, array nonrecursiveness and relative recursive enumerability, J. of Symb. Logic, to appear.

Cooper, S. B. [1989], Degrees of unsolvability complementary between recursively enumerable degrees, Ann. Math. Logic 4, 31-73.

Dekker, J. C. E. [1954], A theorem on hypersimple sets, Proc. Am. Math. Soc. 5, 791-796.

Feferman, S. [1965] Some applications of the notions of forcing and generic sets, Fund. Math. 56, 325–345.

Feiner, L. [1970], The strong homogeneity conjecture, J. Symb. Logic 35, 375-377. Greenberg, N. and Montalbán, A. [2004], Embedding and coding below a 1-generic

degree, Notre Dame J. Formal Logic 44, 200-216.

Groszek, M. S. and Slaman, T. A. [1983], Independence results on the global structure of the Turing degrees, Trans. Am. Math. Soc. 277, 579-588.

Hinman, P. G. [1969] Some applications of forcing to hierarchy problems in arithmetic, Z. Math. Logik Grundlagen Math. 15, 341–352.

Jockusch, C. G. jr. [1980], Degrees of generic sets, in Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979), London Math. Soc. Lecture Note Ser., 45, Cambridge Univ. Press, Cambridge-New York, 110–139.

Jockusch, C. G., Jr. and Posner, D. B. [1978], Double jumps of minimal degrees. J. Symbolic Logic 43 , 715–724.

Kleene, S. C. and Post, E. L. [1954] The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379–407.

Lerman, M. [1971], Initial segments of the degrees of unsolvability, Ann. of Math.

(2) 93, 365-389.

Lerman, M. [1983], Degrees of Unsolvability, Springer-Verlag, Berlin.

Martin, D. A. [1966], Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12, 295–310.

Miller, W. and Martin, D. A. [1968], The degrees of hyperimmune sets. Z. Math. Logik Grundlagen Math. 14, 159–166.

Nerode, A. and Shore, R. A. [1980], Second order logic and first order theories of reducibility orderings in The Kleene Symposium, J. Barwise, H. J. Keisler and K. Kunen, eds., North-Holland, Amsterdam, 181-200.

Nerode, A. and Shore, R. A. [1980a], Reducibility orderings: theories, definability and automorphisms, Ann. of Math. Logic 18, 61-89.

Nies, A., Shore, R. A. and Slaman, T. [1998], Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society (3) 77, 241-291.

Odifreddi, P. [1989] and [1999] Classical recursion theory. Vols. I and II. Studies in Logic and the Foundations of Mathematics 125 and 143. North-Holland Publishing Co., Amsterdam.

Odifreddi, P. and Shore, R. A. [1991], Global properties of local degree structures, Bul. U. Mat. Ital. 7, 97-120.

Rogers, H. Jr. [1987], Theory of recursive functions and effective computability. Second edition. MIT Press, Cambridge, MA.

Sacks, G. E. [1961], On suborderings of degrees of recursive unsolvability, Z. Math. Logik Grundlagen Math. 7, 46-56.

Sacks, G. E. [1963], Recursive enumerability and the jump operator, Trans. Am. Math. Soc. 108, 223-239.

Shoenfield, J. R. [1959], On degrees of unsolvability, Ann. Math. (2) 69, 644-653. Shoenfield, J. R. [1960], An uncountable set of incomparable degrees, Proc. Am.

Math. Soc. 11, 61-62.

Shore, R. A. [1981], The theory of the degrees below 0′, J. London Math. Soc. (3) 24 (1981), 1-14.

Shore, R. A. [1982], Finitely generated codings and the degrees r.e. in a degree d, Proc. Am. Math. Soc. 84, 256-263.

Shore, R. A. [1982a], On homogeneity and definability in the first order theory of the Turing degrees, J. Symb. Logic 47, 8-16.

Shore, R. A. [1988], Defining jump classes in the degrees below 0′, Proceedings of the American Mathematical Society 104, 287-292.

Shore, R. A. [2007], Direct and local definitions of the Turing jump, J. of Math. Logic 7, 229-262.

Shore, R. A. [2013], Biinterpretability up to double jump in the degrees below 0′, to appear.

Shore, R. A. and Slaman, T. A. [1999], Defining the Turing jump, Math. Research Letters 6, 711-722

Simpson, S. G. [1977], First order theory of the degrees of recursive unsolvability, Ann. Math. (2), 105, 121-139.

Slaman, T. A. [1991], Degree structures, in Proc. Int. Cong. Math., Kyoto 1990, Springer-Verlag, Tokyo, 303-316.

Slaman, T. A.. [2008], Global properties of the Turing degrees and the Turing jump in Computational prospects of infinity. Part I. Tutorials, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 14, World Sci. Publ., Hackensack, NJ, 83–101.

Slaman, T. A. and Steel, J. R. [1989], J. of Symb. Logic 54, 160-176. Slaman, T. A. and Woodin, H. W. [1986], Definability in the Turing degrees, Illinois

J. Math. 30, 320-334 Soare, R. I. [1987], Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin. Spector, C. [1956], On degrees of recursive unsolvability, Ann. Math. (2) 64, 581-592 Thomason, S. K. [1970], Sublattices and initial segments of the degrees of unsolvabil-

ity, Can. J. Math. 3, 569-581.