DOUBLE JUMP INVERSIONS AND STRONG MINIMAL COVERS IN THE TURING DEGREES

A Dissertation

Presented to the Faculty of the Graduate School

of Cornell University

in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

by Yuval Gabay August 2004

\begin{matrix}c \\ ◯ \end{matrix} 2004 Yuval Gabay ALL RIGHTS RESERVED DOUBLE JUMP INVERSIONS AND STRONG MINIMAL COVERS IN THE TURING DEGREES Yuval Gabay, Ph.D. Cornell University 2004

Decidability problems for (fragments of) the theory of the structure D of Turing degrees, form a wide and interesting class, much of which is yet unsolved. Lachlan showed in 1968 that the first order theory of D with the Turing reducibility relation is undecidable. Later results concerned the decidability (or undecidability) of fragments of this theory, and of other theories obtained by extending the language (e.g. with 0 or with the Turing jump operator). Proofs of these results often hinge on the ability to embed certain classes of structures (lattices, jump-hierarchies, etc.) in certain ways, into the structure of Turing degrees. The first part of the dissertation presents two results which concern embeddings onto initial segments of D with known double jumps, in other words a double jump inversion of certain degree structures onto initial segments. These results may prove to be useful tools in uncovering decidability results for (fragments of) the theory of the Turing degrees in languages containing the double jump operator.

The second part of the dissertation relates to the problem of characterizing the Turing degrees which have a strong minimal cover, an issue first raised by Spector in 1956. Ishmukhametov solved the problem for the recursively enumerable degrees, by showing that those which have a strong minimal cover are exactly the r.e. weakly recursive degrees. Here we show that this characterization fails outside the r.e. degrees, and also construct a minimal degree below 0′ which is not weakly recursive, thereby answering a question from Ishmukhametov’s paper.

BIOGRAPHICAL SKETCH

Yuval Gabay was born in the third person in Jerusalem, Israel. After graduating from the Hebrew University High School in 1992, he served in the Israeli Defense Forces for three years. He then attended the Hebrew University of Jerusalem, graduating with honors in 1998 with a B.Sc. in Mathematics and a B.Sc. in Computer Science. In 2002 he received an M.Sc. in Computer Science from Cornell University. He accepted a post-doctoral offer from the Mathematics Department at the Ben-Gurion University of the Negev in Beer-Sheva, Israel, starting October 2004. He firmly believes that eggplants were never meant to be food.

In memory of my mother.

iv

ACKNOWLEDGMENTS

One could argue that it is impossible to thank, or even list, all those who have made it possible, indeed inevitable, that I go down the road which has led me to a successful completion of this dissertation. One could say that such a list would have to include every person whom I ever had any contact with, as well as every person whom they ever had any contact with (prior to the time of their contact with me), and so on. Had any of these contacts failed to exist in the way that it did, one could explain, the chain of influences may have been irreparably broken. Thus for example, Chapter 4 could be attributed to the police officer who once caught me speeding, Chapter 5 may be claimed by the aunt of my high school janitor, and her cat’s veterinarian could be responsible for the Introduction. This paragraph, however, is unmistakably and entirely my fault.

I thank my parents above all. My father infected me with an insatiable curiosity about the inner workings of the universe. My numerous and fascinating childhood visits to his labs at the Hebrew University have made the pleasant grounds of the Givat Ram campus a second home to me. My mother, a philosopher at heart, exposed me to the tremendous joy of thinking. She is responsible for the eagerness with which I have developed my skill of clear and unconstrained thought, a bare necessity of mathematical research. It saddens me that she did not live to see this document and to celebrate her significant part in its authorship. I thank both my sisters for their love and care, and for not letting my being their family get in the way of their being my friends.

I thank my advisor, Richard Shore, whom I cannot thank enough. Infinitely patient, Richard has guided me with calm and confidence through the precarious labyrinth of being a graduate student, having faith in my abilities even when I did not. Richard has been an inspiring teacher, both on the professional level and on the personal one. At this point I still do not know if I want to be a mathematician, but because of Richard I know that I can.

I thank Dexter Kozen and Anil Nerode, members of my special committee. It has been a pleasure to know them and to get a taste of their mathematical interests and abilities. I only wish I had spent more of my time at Cornell interacting with both of them. I thank Juris Hartmanis, whose Complexity Theory course I thoroughly enjoyed first as a student and then (not as thoroughly) as a teaching assistant. The brief conversations we have had were positive and helpful, and I consider his acquaintance a privilege.

Finally, I thank my friends, whom there is no need to name. For you were there, and are still, every step of the way, willing to listen to my ramblings concerning mathematics, my love for it and my frequent frustration with it (your personal preference notwithstanding). Of all mentioned here, you are the only ones of whom I ask to continue performing your seemingly ungratifying role. If not for others, this work would surely have not been written. If not for you it may have been written, but surely not by me.

Table Of Contents

1 Introduction 1 1.1 Double Jump Inversion . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Strong Minimal Covers . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Basic Definitions and Notation 6 2.1 Recursion Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Strings and Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Finite Distributive Lattices 12 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 The Main Construction . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 The Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Countable Linear Orders 26 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 The Main Construction . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 The Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5 Degrees r.e.a. in 0′′ 36 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 The Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6 A Non-Weakly Recursive Minimal With a Strong Minimal Cover 42

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2 The Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7 A Non-Weakly Recursive Minimal Below 0′ 50 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.2 The Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

8 Very Weakly Recursive Degrees 55 9 Constructing a Non-Join 60 Bibliography 64

Chapter 1

Introduction

The most significant part of Recursion Theory has always been the study of the structure D of Turing Degrees. This study has two main interests. One is of algebraic nature, asking local and global questions about the existence of certain formations of degrees. The second interest is logical, concentrating on computable complexity results for the theory (or sub-theories) of D (or substructures of it), in various languages. These two interests are strongly related. Most decidability results are based on algebraic findings, usually the existence of embeddings of certain structures into D. The earliest such result was Lachlan’s proof of the undecidability of Th(D, ≤) [Lac68], which is based on the embeddability of any countable distributive lattice as an initial segment of D (the embeddability of finite distributive lattices suffices, see [Ler83, VI.4.6]). It was shown independently by Shore [Sho78] and Lerman (see [Ler83, VII.4.4]) that Th_{∀∃}(D, ≤) is decidable. This result is based on the embeddability of any finite lattice as an initial segment of D and extension of embedding results. Later results concern the decidability of fragments of the theory of D with added operators, such as lattice operators and the Turing jump (as the jump operator has been recently shown to be definable in Th(D, ≤) [SS99], these language expansions affect only the complexity of theory fragments, not that of the whole theory).

This dissertation deals with two issues of the algebraic kind. The first, with an eye toward decidability results for fragments of the theory of D with languages containing the double jump operator, concerns the embeddability of certain structures as initial segments of D with prespecified double jumps. The second issue dealt with is the problem of characterizing the Turing degrees which have strong minimal covers.

1.1 Double Jump Inversion

While there is relatively little work concerning the inversion specifically of the double jump, much has been said about single jump inversion. The most basic jump inversion theorem is due to Friedberg.

Theorem 1.1.1. [Fri57] a ≥ 0′ iff there exists a degree c such that c′ = a.

Later results, such as the Sacks Inversion [Sac63] or the Cooper Inversion [Coo73] put further requirements on the given degree and on the produced, inverted degree (see Theorems 5.1.1 and 5.1.2). However, the proofs of these theorems are very elaborate, and other similar problems are still in need of a solution. For instance, finite partial orders of degrees above 0′ can be jump inverted [Sho88, 1.8], but there is no known general method for inverting lattices (or even upper semi-lattices). The results we bring here attempt to suggest that double jump inversion is much more natural and flexible than its single jump counterpart.

In Chapter 3 we show that certain finite lattices of degrees (distributive ones in particular) above 0′′ can be double jump inverted to initial segments of D. In Chapter 4 we show a similar result for countable linear orderings recursive in 0′′ (Simpson [Sim77] has proven this for orders of type ω).

In Chapter 5 we directly (double jump) invert any degree r.e. in and above 0′′ to a minimal degree below 0′′. From this it follows that the degrees r.e. in and above 0′′ are exactly the jumps of minimal degrees below 0′. To contrast, not all degrees r.e. in and above 0′ are jumps of minimal degrees below 0′, as all such jumps must be low over 0′ (that is, having 0′′ as their jump). Moreover, even the degrees r.e. in and low over 0′ cannot all be inverted to minimal degrees below 0′ [DLS96].

We conclude this part by showing, as a corollary of Shore’s Non-Inversion Theorem [Sho88, 1.2], that this inversion result for degrees r.e. in and above 0′′ cannot be extended for even the simplest lattices.

1.2 Strong Minimal Covers

A degree b is a strong minimal cover of a degree a below it, if every degree < b is ≤ a. In 1956 Spector constructed a minimal degree, which is by nature a strong minimal cover of 0, and raised the issue of characterizing those degrees which possess a strong minimal cover [Spe56]. One should note that relativizing the minimal degree construction to D(≥ a) gives only a minimal cover of a (i.e. a degree b > a with no degrees strictly between the two).

Several constructions of degrees with strong minimal covers were presented over the years. The first serious stab at a characterization was made by Downey, Jockush and Stob. In [DJS96a] they defined the notion of r.e. array non-recursive degrees, and later extended it to D in general [DJS96b].

Definition 1.2.1. A degree a is array non-recursive if for each f ≤_{wtt} K there is a function g recursive in a such that g(n) ≥ f(n) for infinitely many n.

In other words, a is a.n.r. if no function weak-truth-table recursive in 0′ dominates all g ≤_{T} a. This clearly implies that the class of a.n.r. degrees is upward closed. This definition has other interesting equivalents which we will not go into here.

Theorem 1.2.2. [DJS96b] Let a be array non-recursive.

(i) a is the supremum of two 1-generic a.n.r. degrees which form a minimal pair.

(ii) If c > a then there is a degree b < c such that a ∨ b = c.

By (i), a.n.r. degrees cannot be strong minimal covers. By (ii), they cannot have strong minimal covers (alternatively, one could argue that a strong minimal cover of an a.n.r. degree would be a.n.r. by upward closure, thereby contradicting (i)).

The second half of the characterization came, for the r.e. degrees, in a 1999 paper by Ishmukhametov [Ish99]. He defined the class of weakly recursive degrees (see Definition 6.1.2), argued that it is complementary to the class of a.n.r. degrees in the r.e. degrees, and then proved that all weakly recursive degrees possess strong minimal covers, concluding

Theorem 1.2.3. If a is recursively enumerable, it has a strong minimal cover iff it is weakly recursive.

In Chapter 6 we construct a minimal degree which is not weakly recursive, but has a strong minimal cover, showing that the characterization in Theorem 1.2.3 does not hold outside the realm of r.e. degrees. This is also done independently in [KHNS] (where the weakly recursive degrees are called r.e.-traceable).

In Chapter 7 we construct a minimal degree below 0′ which is not weakly recursive, thereby showing that the a.n.r. and weakly recursive classes are not complementary in the degrees below 0′ (note that a minimal degree is not a.n.r. by 1.2.2(i)). This answers an open question in [Ish99].

In Chapter 8 we define the seemingly broader class of very weakly recursive degrees, and show that those possess a strong minimal cover as well, by a slight modification of Ishmukhametov’s argument. At this time we do not know if there are very weakly recursive degrees which are not weakly recursive.

Chapter 9 has no new results. It describes a direct construction of a degree a for which the statement 1.2.2(ii) does not hold. This is a product of a failed attempt to produce a counterpart to Theorem 6.2.1, by constructing a degree which is not a.n.r., yet does not have a strong minimal cover. Nonetheless, we have chosen to include it, since we feel it may prove useful in the future, either in this or in other research routes, such as the characterization of the class of cuppable degrees (i.e. degrees for which 1.2.2(ii) does hold).

Basic Definitions and Notation

2.1 Recursion Theory

The e-th partial recursive function with oracle A ⊆ ω will be denoted φ_{e}^{A}. The same function, computed for only s steps, will be denoted φ_{e,s}^{A}. We write φ_{e}^{A}(x)↓ or φ_{e}^{A}(x)↑ to mean the function is defined or undefined on an input x ∈ ω, respectively (and similarly for φ_{e,s}^{A}).

We write φ_{e}^{A} ≃ φ_{i}^{A} to mean

∀x ∈ ω φ_{e}^{A}(x)↓= φ_{i}^{A}(x) ∨ (φ_{e}^{A}(x)↑ ∧φ_{i}^{A}(x)↑).

We write φ_{e}^{A} = B to mean that for all x ∈ ω, (x ∉ B → φ_{e}^{A}(x) ↓= 0) ∧ (x ∈ B → φ_{e}^{A}(x)↓= 1).

Definition 2.1.1. A is (Turing) computable from B if φ_{e}^{A} = B for some e ∈ ω. In this case we write A ≤_{T} B.

The relation A ≡_{T} B defined as A ≤_{T} B ∧ B ≤_{T} A is an equivalence relation on 2^{ω}, which divides it into countable equivalence classes, the Turing degrees. The set of Turing degrees is denoted by D, and individual degrees by boldface letters (a, b, …). The Turing degree of a set A is denoted deg(A). The least degree is the set of all recursive subsets of ω, denoted 0. We write A <_{T} B to mean that A is computable from B and they are of distinct Turing degrees. Definition 2.1.2. For A ⊆ ω, the Turing jump of A is the set

A′ = {e : φ_{e}^{A}(e)↓}

A <_{T} A′ and if A ≤_{T} B then A′ ≤_{T} B′. Consequently the Turing jump is well defined on Turing degrees, which allows us to define the jump of a Turing degree a = deg(A) as a′ = deg(A′).

The following facts will be used throughout the text, sometimes implicitly. Theorem 2.1.3. [Ler83, III.2.6] For A ⊆ ω we have

• A ∈ Σ_{n+1}^{0} iff A is recursively enumerable in 0^{(n)}.

• A ∈ Δ_{n+1}^{0} iff A is recursive in 0^{(n)}.

Hence, if A is definable by a formula ψ(x) in normal form with n quantifiers, it is computable from 0^{(n)}. Lemma 2.1.4. [Ler83, IV.3.2] The totality set of A,

Tot(A) = {e : φ_{e}^{A} is total},

is Turing equivalent to A′′. Lemma 2.1.5. [Ler83, IV.3.6] Any degree a in a finite initial segment of D is in GL_{2}, that is a′′ = (a ∨ 0′)′.

We denote by ⟨·, ·⟩ a fixed recursive bijection between ω × ω and ω. ⟨x, y, z⟩ is used to mean ⟨x, ⟨y, z⟩⟩, and so on.

The set-join of A, B ∈ ω is the set

A ⊕ B = {⟨i, x⟩ : (i = 0 ∧ x ∈ A) ∨ (i = 1 ∧ x ∈ B)}

If A ≤_{T} C and B ≤_{T} D then A ⊕ B ≤_{T} C ⊕ D. This allows us to define the join of two Turing degrees a = deg(A) and b = deg(B) as a ∨ b = deg(A ⊕ B). This is the least upper bound of the degrees a and b.

2.2 Strings and Trees

Let B be a non-empty at most countable set. Definition 2.2.1. A B-string is a member of B^{≤ω}. For a finite B-string σ and a B-string τ we define:

(i) The length of τ is |τ|. We identify elements of B and strings of length 1. (ii) If σ ⊆ τ (as functions), we say that σ is an initial segment of τ. (iii) The concatenation σ ⌢τ is the string ρ of length |σ| + |τ| defined by

ρ(n) = \begin{cases}σ(n) & n < |σ| \\ τ(n − |σ|) & |σ| ≤ n < |σ| + |τ| \end{cases}

(iv) If σ ⊆ τ let τ − σ denote the unique ρ such that σ ⌢ρ = τ.

(v) If σ ⊆ τ and |ρ| = |σ|, we denote ρ⌢(τ −σ) by the special notation τ[σ → ρ]. We naturally identify a binary string (i.e. a {0, 1}-string) A with the set A^{−1}(1).

Definition 2.2.2. Let A be a B-string and let X ⊆ ω be infinite and enumerated by m_{0}, m_{1}, m_{2}, … in increasing order. X(A) is the B-string C such that C(n) = A(m_{n}) for all n for which this is defined. If X(A_{1}) is compatible with X(A_{2}), we say that A_{1} and A_{2} agree on X.

Note that X(A) is infinite iff A is. Also, if A is infinite, X, Y are recursive and X ⊆^{∗} Y (that is, X \ Y is finite) then X(A) ≤_{T} Y (A). In particular, X(A) ≤_{T} ω(A) = A for all X. Definition 2.2.3. Let σ, τ be (finite or infinite) B^{k}-strings (for k > 0), and i < k.

(i) σ^{[i]} is the B-string given by σ^{[i]}(n) = σ(n)(i).

(ii) σ and τ are equivalent mod i (σ ≡_{i} τ) if σ^{[i]} = τ^{[i]}. Definition 2.2.4. (i) A B-tree is an injective function T : B^{<ω} → B^{<ω} such

that

σ ⊆ τ ↔ T (σ) ⊆ T (τ)

(ii) Given a B-tree T and an infinite B-string A, we can define the infinite Bstring P = ⋃_{σ⊂A} T (σ). P is called a path on T, and is sometimes denoted by T (A) (slightly abusing notation). The set of paths on T is denoted by [T].

(iii) A B-tree T is said to force a property P of infinite B-strings if every path on T satisfies P. A finite string σ ∈ rg(T) forces P if every path extending σ on T satisfies P.

Definition 2.2.5. For B-trees S and T, S is a subtree of T (S ⊆ T) if the range of S is contained in the range of T. Note that in this case [S] ⊆ [T] as well.

Let S, T be B-trees. The composition R = T ∘ S is injective, and for all σ, τ ∈ B^{<ω} we have

σ ⊆ τ ⟺ S(σ) ⊆ S(τ) ⟺ R(σ) = T (S(σ)) ⊆ T (S(τ)) = R(τ).

Hence R is a B-tree, and is called the product of T and S (denoted T · S or simply T S).

If S ⊆ T, the composition R = T^{−1} ∘ S is well defined and injective, and for all σ, τ ∈ B^{<ω} we have

σ ⊆ τ ⟺ T (R(σ)) = S(σ) ⊆ S(τ) = T (R(τ)) ⟺ R(σ) ⊆ R(τ).

Hence R is a B-tree, and is called the quotient of S by T (denoted S/T).

Proposition 2.2.6. Let R, S, T be B-trees. T_{id} denotes the identity B-tree.

(i) T · (S · R) = (T · S) · R.

(ii) T/T = T_{id} and T/T_{id} = T_{id} · T = T · T_{id} = T.

(iii) If S ⊆ T then T · (S/T) = S.

(iv) If S ⊆ T then S · R ⊆ T, and (S · R)/T = (S/T) · R.

(v) If T ⊆ R · S then T ⊆ R, T/R ⊆ S and (T/R)/S = T/(R · S).

(vi) If S ⊆ T then R · S ⊆ R · T and (R · S)/(R · T) = S/T.

Proof. Immediate from the definitions.

For a finite B-string σ, let E_{σ} be the tree defined by E_{σ}(τ) = σ ⌢ τ. If T is a B-tree then T · E_{σ} is an extension subtree of T (denoted Ext(T, σ) in Lerman).

Since B is at most countable, we allow ourselves to identify B-strings with their codes (in some fixed Gödel numbering). In this light, a tree T is a numerical function, and has a Turing degree.

Furthermore, when we talk about operators on recursive trees, we implicitly (and sometimes explicitly) refer to corresponding functions on recursive indices of trees (even though these are not unique). For example, there is a (recursive!) function f_{·}(s, t) which maps a pair of recursive indices for trees S, T to a recursive index for S · T. We will frequently write S · T to mean f_{·}(s, t).

Finally we address an important application of these tree operations.

Definition 2.2.7. Two B-tree extensions T′ ⊆ T and S′ ⊆ S are equivalent if T′/T = S′/S.

Informally speaking, the extensions are equivalent if T′(σ) is on the same place on T as S′(σ) is on S (for all strings σ). The tree operations let us construct equivalent extensions with ease.

Proposition 2.2.8. If T′ ⊆ T is a B-tree extension and S is a B-tree, then the tree

S′ = S · (T′/T)

is an extension of S, equivalent to T′ ⊆ T.

Proof. By Proposition 2.2.6 (v) we have that S′ ⊆ S and

(S′/S)/(T′/T) = S′/(S · (T′/T)) = S′/S′ = T_{id}.

Finite Distributive Lattices

In this chapter we focus on embedding certain lattices as initial segments with given double jumps. Most of the introductory material is taken from Chapter IV of [Ler83]. In section 2 we present the main construction, and in section 3 we prove the results that are based on it.

3.1 Introduction

In the following, L = (L, ≤, ∨, ∧) is a finite lattice, where L = {u_{0}, …, u_{n}}, and the distinct bottom and top elements of L are u_{0} and u_{n}, respectively. Also, h : L → D is an u.s.l. homomorphism (i.e. a map preserving the lattice weak order relation and the join function).

Definition 3.1.1. A finite homogeneous lattice table for L is a set Θ of functions from {0, …, n} to ω, such that

(i) ∀α, β ∈ Θ(α ≡_{0} β) (equivalence mod 0 of Θ-strings of length 1)

(ii) ∀i, j ≤ n(u_{i} ≤ u_{j} ↔ ∀α, β ∈ Θ(α ≡_{j} β → α ≡_{i} β))

(iii) ∀i, j, k ≤ n(u_{i} ∨ u_{j} = u_{k} ↔ ∀α, β ∈ Θ(α ≡_{k} β ↔ α ≡_{i} β ∧ α ≡_{j} β))

(iv) ∀i, j, k ≤ n(u_{i} ∧ u_{j} = u_{k} ↔ ∀α, β ∈ Θ(α ≡_{k} β ↔

∃s ∈ ω ∃γ_{0}, …, γ_{s} ∈ Θ(α = γ_{0} ≡_{i} γ_{1} ≡_{j} γ_{2} ≡_{i} ⋯ ≡_{j} γ_{s} = β)))

(v) For all α_{0}, α_{1}, β_{0}, β_{1} ∈ Θ, if ∀i ≤ n(α_{0} ≡_{i} α_{1} → β_{0} ≡_{i} β_{1}), then there is a function f : Θ → Θ such that f(α_{0}) = β_{0}, f(α_{1}) = β_{1}, and for all α, β ∈ Θ, ∀i ≤ n(α ≡_{i} β → f(α) ≡_{i} f(β)).

We are concerned here only with finite lattices which have a finite homogeneous lattice table. In the following, assume that Θ is such a table for L. Embeddings of L into D will be given by infinite Θ-strings. Definition 3.1.2. An infinite Θ-string A codes a map g : L → D if for all i ≤ n

g(u_{i}) = deg(A^{[i]}) ∨ g(u_{0}).

A map g : L → D is Θ-representable if there exists a Θ-string that codes it.

Every Θ-string codes a u.s.l. homomorphism g with g(u_{0}) = 0 (this is essentially the Homomorphism Lemma, [Ler83, IV.1.4]). In order to make g an embedding onto an initial segment, we construct the string as a path on uniform Θ-trees forcing certain conditions. Definition 3.1.3. A Θ-tree T is uniform if

(i) |σ| = |τ| ↔ |T (σ)| = |T (τ)| (ii) σ ≡_{i} τ ↔ T (σ) ≡_{i} T (τ) (iii) |σ| = |τ| → ∀α ∈ Θ T (σ ⌢α) − T (σ) = T (τ ⌢α) − T (τ)

Note that condition (iii) implies (iii’) |σ| = |τ| → ∀ρ ∈ Θ^{<ω} T (σ ⌢ρ) − T (σ) = T (τ ⌢ρ) − T (τ) by induction on the length of ρ. Also note that if S, T are recursive uniform trees then so are S · T and S/T (when defined).

Definition 3.1.4. Let e ∈ ω, i, j ≤ n and let T be a Θ-tree.

(i) T decides e-totality if either φ_{e}^{P} is total for all P ∈ [T] or φ_{e}^{P} is not total for all P ∈ [T]. T forces e-totality, e-partiality in the first, resp. second, case.

(ii) T is ⟨e, i, j⟩-differentiating if for all P ∈ [T], φ_{e}^{P^{[j]}} ≠ P^{[i]}.

(iii) T is e-splitting if there exists i ≤ n such that for all P ∈ [T] with φ_{e}^{P} total, we have φ_{e}^{P} ≡_{T} P^{[i]}.

Clause (iii) differs from the definition of e-splitting in [Ler83], but is shown to follow from it by the Computation Lemma [Ler83, IV.3.3]. Hence, the justification of the following Lemma is not affected.

Lemma 3.1.5. There is a total function f : ω × ω → ω, computable in 0′′, such that if T is (a recursive index for) a uniform Θ-tree then

(i) if r = ⟨1, e⟩ then f(r, T) is (a recursive index for) a uniform subtree of T which decides e-totality;

(ii) if u_{i} ≰ u_{j} and r = ⟨2, e, i, j⟩ then f(r, T) is a uniform subtree of T which is ⟨e, i, j⟩-differentiating;

(iii) if r = ⟨3, e⟩ then f(r, T) is a uniform subtree of T which is e-splitting;

(iv) for all other values of r, f(r, T) = T.

Proof. The constructions needed to define f are described in the proofs of Lemmas 2.13, 2.15 and 3.12 in [Ler83, IV]. One should note that the constructions are uniform in 0′′, as the different cases in each are defined by two quantifier statements.

3.2 The Main Construction

In order to get an embedding of L onto an initial segment of D, Lerman applies f of Lemma 3.1.5 repeatedly to force all of the totality, differentiating and minimality requirements. The goal in this chapter is to code certain degrees into this construction, in a way which would make these degrees the double jumps of the degrees in the initial segment. Rather than explicitly coding any given degrees, we perform every possible coding simultaneously, by branching into separate forcing extensions after each application of f. This creates a tree of trees, as stated by the following Lemma.

Lemma 3.2.1. There is a uniform Θ-tree T̂, computable in 0′′, such that every P ∈ [T̂] codes an embedding of L onto an initial segment of D. Furthermore, for any such path P = T̂(A) and any i ≤ n

P^{[i]}′′ ≡_{T} P^{[i]} ∨ 0′′ ≡_{T} A^{[i]} ∨ 0′′

Proof. Let f be as in Lemma 3.1.5. We define recursive uniform Θ-trees T_{σ} for every finite Θ-string σ, such that

(i) T_{σ⌢α} ⊆ T_{σ}E_{α}

(ii) T_{σ⌢α} ⊆ f(|σ|, T) for some recursive tree T

(iii) if |σ_{1}| = |σ_{2}| and |ρ_{1}| = |ρ_{2}| then the strings χ_{d} = T_{σ_{d}}(ρ_{d}) (d = 1, 2) are of equal length, and for all i ≤ n

χ_{1} ≡_{i} χ_{2} ⟺ σ_{1} ⌢ρ_{1} ≡_{i} σ_{2} ⌢ρ_{2}

(iv) if |σ_{1}| = |σ_{2}| then T_{σ_{1}}(ρ⌢ρ′) − T_{σ_{1}}(ρ) = T_{σ_{2}}(ρ⌢ρ′) − T_{σ_{2}}(ρ).

Each tree T_{σ} is the forcing condition which is obtained by coding σ into Lerman’s original construction. Property (i) ensures that these conditions are distinct, while property (ii) ensures that the next application of f has taken place. Conditions (iii) and (iv) provide a kind of uniformity for T̂, which will make the coding work.

Let T_{∅} = T_{id}. Suppose T_{σ} has been defined for all σ of length k. Let {τ_{j}}_{j=1}^{m} list all Θ-strings of length k + 1, and let τ_{j} = σ_{j} ⌢ α_{j} with |σ_{j}| = k and α_{j} ∈ Θ. Let T′_{τ_{j}} = T_{σ_{j}}E_{α_{j}}. We go by subinduction on j:

T_{τ_{1}}^{∗} = f(k, T′_{τ_{1}}), T_{τ_{j+1}}^{∗} = f(k, T′_{τ_{j+1}}(T_{τ_{j}}^{∗}/T′_{τ_{j}})).

For all 1 ≤ j ≤ m now let

T_{τ_{j}} = T′_{τ_{j}}(T_{τ_{m}}^{∗}/T′_{τ_{m}}).

The idea is simple and rather straightforward. We want to find conditions T_{τ_{j}} which force the current requirement, and are all equivalent extensions (in the sense of Definition 2.2.7) of the conditions T′_{τ_{j}}, respectively. To do this, we apply f to the first one, then find the equivalent extension to the second and apply f again, and so on. Finally, we take the final extension, and set the trees T_{τ_{j}} to be the corresponding extensions equivalent to it.

We now formally prove that these extensions are as required. The trees are all uniform recursive, since this quality is preserved by f and by tree multiplication and division. We now show that the properties above hold by induction, assuming the notation of the construction.

(i) This follows directly from the definition, since for all 1 ≤ j ≤ m we have

T_{σ_{j}⌢α_{j}} = T_{τ_{j}} = T′_{τ_{j}}(T_{τ_{m}}^{∗}/T′_{τ_{m}}) ⊆ T′_{τ_{j}} = T_{σ_{j}}E_{α_{j}}.

(ii) From the definition of f and T_{τ_{j+1}}^{∗} it follows that

T_{τ_{j+1}}^{∗} ⊆ T′_{τ_{j+1}}(T_{τ_{j}}^{∗}/T′_{τ_{j}})

and therefore

T_{τ_{j+1}}^{∗}/T′_{τ_{j+1}} ⊆ T_{τ_{j}}^{∗}/T′_{τ_{j}}.

Hence the quotients T_{τ_{j}}^{∗}/T′_{τ_{j}} form a decreasing chain of trees. For any 1 ≤ j ≤ m we then get

T_{τ_{j}} = T′_{τ_{j}}(T_{τ_{m}}^{∗}/T′_{τ_{m}}) ⊆ T′_{τ_{j}}(T_{τ_{j}}^{∗}/T′_{τ_{j}}) = T_{τ_{j}}^{∗} = f(k, T)

for some recursive T as required.

(iii) Consider strings ρ_{1}, ρ_{2} of equal length, and 1 ≤ j, l ≤ m. If we let R = T_{τ_{m}}^{∗}/T′_{τ_{m}}, then

T_{τ_{j}}(ρ_{1}) = T′_{τ_{j}}R(ρ_{1}) = T_{σ_{j}}E_{α_{j}}R(ρ_{1}) = T_{σ_{j}}(α_{j} ⌢R(ρ_{1}))

and similarly

T_{τ_{l}}(ρ_{2}) = T_{σ_{l}}(α_{l} ⌢R(ρ_{2})).

Since R is uniform, we have

|α_{j} ⌢R(ρ_{1})| = 1 + |R(ρ_{1})| = 1 + |R(ρ_{2})| = |α_{l} ⌢R(ρ_{2})|

⟹ |T_{σ_{j}}(α_{j} ⌢R(ρ_{1}))| = |T_{σ_{l}}(α_{l} ⌢R(ρ_{2}))|

by the induction hypothesis. By a similar reasoning

T_{τ_{j}}(ρ_{1}) ≡_{i} T_{τ_{l}}(ρ_{2}) ⟺ T_{σ_{j}}(α_{j} ⌢R(ρ_{1})) ≡_{i} T_{σ_{l}}(α_{l} ⌢R(ρ_{2}))

⟺ σ_{j} ⌢α_{j} ⌢R(ρ_{1}) ≡_{i} σ_{l} ⌢α_{l} ⌢R(ρ_{2}) ⟺ τ_{j} ⌢ρ_{1} ≡_{i} τ_{l} ⌢ρ_{2}

(since R(ρ_{1}) ≡_{i} R(ρ_{2}) iff ρ_{1} ≡_{i} ρ_{2} by uniformity of R). (iv) Let R, j, l be as above, and set

χ = R(ρ), χ′ = R(ρ⌢ρ′) − R(ρ).

Then

T_{τ_{j}}(ρ⌢ρ′) − T_{τ_{j}}(ρ)

= T_{σ_{j}}(α_{j} ⌢R(ρ⌢ρ′)) − T_{σ_{j}}(α_{j} ⌢R(ρ)) = T_{σ_{j}}(α_{j} ⌢χ⌢χ′) − T_{σ_{j}}(α_{j} ⌢χ) = T_{σ_{j}}(α_{l} ⌢χ⌢χ′) − T_{σ_{j}}(α_{l} ⌢χ) (by uniformity of T_{σ_{j}}, cond. (iii’)) = T_{σ_{l}}(α_{l} ⌢χ⌢χ′) − T_{σ_{l}}(α_{l} ⌢χ) (by induction hypothesis) = T_{τ_{l}}(ρ⌢ρ′) − T_{τ_{l}}(ρ).

Now let T̂(σ) = T_{σ}(∅) for all σ. Property (iii) implies that if |σ| = |τ| then |T̂(σ)| = |T̂(τ)| and for all i ≤ n

T̂(σ) ≡_{i} T̂(τ) ↔ σ ≡_{i} τ.

Property (iv) implies that if |σ| = |τ| and α ∈ Θ then

T̂(σ ⌢α) − T̂(σ) = T_{σ}(α⌢ρ) − T_{σ}(∅) = T_{τ}(α⌢ρ) − T_{τ}(∅) = T̂(τ ⌢α) − T̂(τ)

where ρ = R(∅) with R as above. Therefore T̂ is a uniform tree. It is computed with f as an oracle, hence it is computable in 0′′.

Fix P = T̂(A) ∈ [T̂]. We show that P codes an embedding of L onto an initial segment of D. First, note that P ∈ [T_{σ}] whenever σ ⊂ A. Indeed,

P = ⋃_{σ⊆τ⊂A} T̂(τ) = ⋃_{σ⊆τ⊂A} T_{τ}(∅)

and T_{τ} ⊆ T_{σ} for every τ ⊇ σ (by property (i)).

From property (ii) it now follows that for every k ∈ ω there is a recursive tree T such that P ∈ [f(k, T)]. In particular

(i) If u_{i} ≰ u_{j} then for every e ∈ ω, P lies on a recursive ⟨e, i, j⟩-differentiating tree, and therefore P^{[i]} ≰_{T} P^{[j]}.

(ii) For all e ∈ ω, P lies on a recursive e-splitting tree, and therefore

D(≤ deg(P)) = D(≤ deg(P^{[n]})) ⊆ {P^{[i]} : i ≤ n}.

Thus P codes an embedding of L onto an initial segment of D. It is left to prove the triple equality in the Lemma. Since a′′ ≥_{T} a ∨ 0′′ for any degree a, it suffices to demonstrate that the inequalities

P^{[i]} ∨ 0′′ ≥_{T} A^{[i]} ∨ 0′′ ≥_{T} P^{[i]}′′

hold for every i ≤ n. The first of the two follows from the uniformity of T̂. If σ is a Θ-string of length k, then

σ^{[i]} ⊆ A^{[i]} ⟺ σ ≡_{i} A↾k
⟺ T̂(σ) ≡_{i} T̂(A↾k) ⟺ T̂(σ)^{[i]} ⊆ P^{[i]}.

Hence, to find A^{[i]} ↾k (with the given oracle) look for a string σ of length k which satisfies the last statement, and take σ^{[i]}.

For the second inequality, we show how to compute Tot^{P^{[i]}} using A^{[i]} ∨ 0′′ as an oracle (this suffices by Lemma 2.1.4). Given e ∈ ω, let e^{∗} be such that φ_{e^{∗}}^{P} ≃ φ_{e}^{P^{[i]}} (e^{∗} can be found in a uniformly recursive manner). Let σ be of length k = ⟨1, e^{∗}⟩+1 such that σ^{[i]} ⊂ A^{[i]}. Note that both T_{σ} and T_{A↾k}, decide e^{∗}-totality by property (ii) and the nature of the function f. Now

e ∈ Tot^{P^{[i]}} ⟺ φ_{e}^{P^{[i]}} is total
⟺ φ_{e^{∗}}^{P} is total
⟺ T_{A↾k} forces e^{∗}-totality ⟺ T_{σ} forces e^{∗}-totality

where the last equivalence stems from the equality

{X^{[i]} : X ∈ [T_{A↾k}]} = {X^{[i]} : X ∈ [T_{σ}]}

which is a consequence of property (iv) and the equivalence T_{A↾k} ≡_{i} σ.

3.3 The Results

Each path of T̂ codes an embedding of L onto an initial segment of D. Before we pay attention to the coding in the paths, we mention their cardinality.

Corollary 3.3.1. If L has a finite homogeneous lattice table, then there are 2^{ω} many lattice embeddings of L as an initial segment of D.

Proof. For each path P ∈ [T̂], the function h_{P} : u_{i} ↦ deg(P^{[i]}) is such an embedding. Now

2^{ω} ≥ |{h_{P} : P ∈ [T̂]} ≥ |{deg(P^{[n]}) : P ∈ [T̂]} = |{deg(P) : P ∈ [T̂]}| = 2^{ω}

since |[T̂]| = 2^{ω} and Turing equivalence classes are countable.

Now we turn to the main Theorem of this chapter, in its most general form.

Theorem 3.3.2. Suppose L has a finite homogeneous lattice table Θ, and h : L → D is a Θ-representable u.s.l. homomorphism with h(u_{0}) = 0′′. Then there is an initial segment C of D and a lattice isomorphism g : L → C such that

g(x)′′ = g(x) ∨ 0′′ = h(x) for all x ∈ L.

Proof. Suppose the Θ-string A codes h. Let P = T̂(A), g(u_{i}) = deg(P^{[i]}) and C = rg(g). Then g is an embedding of L onto an initial segment of D, and P codes it. Furthermore, for all i ≤ n

g(u_{i})′′ = g(u_{i}) ∨ 0′′ = deg(A^{[i]}) ∨ 0′′ = deg(A^{[i]}) ∨ h(u_{0}) = h(u_{i}).

Next we show that Theorem 3.3.2 always applies to any finite distributive lattice. We already know ([Ler83, B.1]) that every such lattice has a finite homogeneous lattice table, so it remains to show that any homomorphism from such a lattice is representable with respect to some table. To show this, we follow the construction of the lattice table in [Ler83, B.1], repeated here without the justification. In the following assume that L is distributive. Definition 3.3.3. u_{i} ≠ u_{0} is join-irreducible if u_{i} = u_{j} ∨ u_{k} implies i = j or i = k.

Let {u_{i_{k}}}_{k<r} be the join-irreducible elements of L, and let B = P{a_{0}, …, a_{r−1}} be the boolean algebra with r atoms (with ∧ and ∨ interpreted as set intersection and union, respectively). Define g : L → B by

g(u_{i}) = {a_{k} : u_{i_{k}} ≤ u_{i}}

Lemma 3.3.4. g is a lattice embedding of L in B.

For every A ⊆ {a_{0}, …, a_{r−1}}, define a function α_{A} : B → ω as follows. If C = {a_{i_{1}}, …, a_{i_{|C|}}} with i_{1} < ⋯ < i_{|C|}, then let

α_{A}(C) = ∑{2^{|C|−j} : a_{i_{j}} ∈ A}

Now, for every A as above and i ≤ n, let α_{A}^{∗}(i) = α_{A}(g(u_{i})). Let

Θ = {α_{A}^{∗} : A ⊆ {a_{0}, …, a_{r−1}}}.

Lemma 3.3.5. Θ is a finite homogeneous lattice table for L.

Now we show that all appropriate homomorphisms from L can be coded in Θ. Lemma 3.3.6. Let L be finite distributive, Θ as described above, and suppose h : L → D is a u.s.l. homomorphism, with h(u_{0}) = 0′′. Then h is Θ-representable.

Proof. Pick sets A_{k} ∈ h(u_{i_{k}}) for all k < r, and define (for all x ∈ ω and k < r)

A(rx + k) = \begin{cases}α_{\{a_{k}\}}^{∗} & x ∈ A_{k} \\ α_{∅}^{∗} & x ∉ A_{k} \end{cases}

The reason for this choice of lattice elements is that α_{{a_{k}}}^{∗} ≢_{i_{k}} α_{∅}^{∗}, but α_{{a_{k}}}^{∗} ≡_{j} α_{∅}^{∗} whenever u_{j} ≱ u_{i_{k}}.

Fix k < r. First note that for all x ∈ ω

x ∈ A_{k} ⟺ A(rx + k) ≢_{i_{k}} α_{∅}^{∗}

and therefore A_{k} ≤_{T} A^{[i_{k}]}. To show the converse, note that for all j < r and x ∈ ω

A^{[i_{k}]}(rx + j) = \begin{cases}α_{\{a_{j}\}}^{∗}(i_{k}) & x ∈ A_{j} \\ α_{∅}^{∗}(i_{k}) & x ∉ A_{j} \end{cases}

If u_{i_{j}} ≤ u_{i_{k}} then A_{j} ≤_{T} A_{k}. Given A_{k} we can find whether or not x ∈ A_{j}, then find the required value. If u_{i_{j}} ≰ u_{i_{k}} then α_{{a_{j}}}^{∗} ≡_{i_{k}} α_{∅}^{∗}, and consequently A^{[i_{k}]}(rx + j) = α_{∅}^{∗}(i_{k}).

To complete the proof, fix u_{i} ∈ L with i > 0. Let J = {j : u_{i_{j}} ≤ u_{i}}. Then

h(u_{i}) = ⋁_{j∈J} h(u_{i_{j}}) = ⋁_{j∈J} deg(A_{j}) = ⋁_{j∈J} deg(A^{[i_{j}]}) = deg(A^{[i]}) = deg(A^{[i]}) ∨ h(u_{0}),

and clearly h(u_{0}) = 0′′ = deg(A^{[0]}) ∨ h(u_{0}).

The double-jump inversion of finite distributive lattices now follows.

Theorem 3.3.7. Suppose L is a finite distributive lattice, and h : L → D is an u.s.l. homomorphism, with h(u_{0}) = 0′′. Then there is an initial segment C of D and a lattice isomorphism g : L → C such that

g(x)′′ = g(x) ∨ 0′′ = h(x) for all x ∈ L.

Proof. Let Θ be as above. Then h is Θ-representable, and the result follows from Theorem 3.3.2.

Finally, relativization and iteration of the previous two theorems yield the following results, which may be helpful tools in determining the decidability of fragments of Th(D, 0, ≤, ∨,′′). Theorem 3.3.8. Suppose L has a finite homogeneous lattice table Θ, and h : L → D is a Θ-representable u.s.l. homomorphism with h(u_{0}) = 0^{(2n)}. Then there are initial segments C_{i} of D(≥ 0^{(2i)}) and lattice isomorphisms g_{i} : L → C_{i} for i < n such that

g_{i}(x)′′ = g_{i}(x) ∨ 0^{(2i+2)} = g_{i+1}(x)  for all x ∈ L and i < n − 1, and
g_{n−1}(x)′′ = g_{n−1}(x) ∨ 0^{(2n)} = h(x)  for all x ∈ L.

Proof. First relativize Theorem 3.3.2 to 0^{(2n)}, to get g_{n−1} as required. Notice that g_{n−1} is Θ-representable by the nature of the proof of Theorem 3.3.2. This allows relativization to 0^{(2n−2)}. Proceed by induction. Theorem 3.3.9. Suppose L_{i} are finite distributive lattices for i ≤ n, with u.s.l. homomorphisms h_{i} : L_{i} → L_{i+1} for all i < n. Suppose further that g_{n} : L_{n} → D is a u.s.l. isomorphism mapping the bottom element of L_{n} to 0^{(2n)}. Then there are initial segments C_{i} of D(≥ 0^{(2i)}) and lattice isomorphisms g_{i} : L_{i} → C_{i} for i < n such that

g_{i}(x)′′ = g_{i}(x) ∨ 0^{(2i+2)} = g_{i+1}(h_{i}(x)) for all i < n and x ∈ L_{i}.

Proof. This is a fairly straightforward induction on i starting at n − 1, relativizing Theorem 3.3.7 to 0^{(2i+2)} with g_{i+1} ∘ h_{i} : L_{i} → D(≥ 0^{(2i+2)}) as the u.s.l. homomorphism. Lemma 3.3.6 ensures that the produced embedding g_{i} is representable with respect to the appropriate lattice table for L_{i}.

If we could demonstrate a similar guarantee of representability in the general (non-distributive) case, we could generalize this result. This, however, seems more difficult, if at all possible.

Countable Linear Orders

The narrative in this chapter is similar to the one in the previous chapter. The setting here is borrowed from [Eps79, IV-VI]. Section 2 has the main construction and section 3 has the results.

4.1 Introduction

In the following, L = (ω, ≤_{L}) is a countable linear order, computable in 0′′, with bottom element 0 and top element 1. Let L_{n} be L restricted to {0, 1, …, n}.

As forcing conditions, we use recursive uniform binary trees (i.e. {0, 1}-trees). The linear order will be represented by a collection of recursive sets, ordered by inclusion, and the trees will have densely many branchings which differentiate between distinct sets in the representation. The following definitions make these notions precise.

Definition 4.1.1. A binary tree T is uniform if for all finite binary strings σ, τ

(i) |σ| = |τ| ↔ |T (σ)| = |T (τ)|

(ii) |σ| = |τ| → ∀i < 2 T (σ ⌢i) − T (σ) = T (τ ⌢i) − T (τ)

Definition 4.1.2. Let X_{i} ⊆ ω be recursive for i ∈ ω.

(i) The sequence X_{0}, …, X_{n} represents L_{n} if for all i, j ≤ n

i <_{L} j ↔ (X_{i} ⊂^{∗} X_{j} ∧ |X_{j} \ X_{i}| = ω).

(ii) The sequence X_{0}, X_{1}, … represents L if X_{0}, …, X_{n} represents L_{n} for all n ∈ ω.

Definition 4.1.3. Recall Definition 2.2.2.

(i) Let X ⊆ Y ⊆ ω. A uniform binary tree T is special for X (resp. for −Y, for X − Y) if there are infinitely many binary strings σ such that T (σ ⌢0) and T (σ ⌢1) agree on X (resp. disagree on Y, agree on X and disagree on Y).

(ii) Let C_{n} = {X_{0}, …, X_{n}} represent L_{n}. A uniform binary tree T is special for C_{n} if it is special for X_{i} − X_{j} for all i, j ≤ n such that i <_{L} j. Note that in this case T · E_{σ} is special for C_{n} as well, for every σ.

Definition 4.1.4. Let C = {X_{0}, X_{1}, … } be a sequence that represents L. An infinite binary string P codes an embedding of L onto an initial segment of D with respect to C if the map i ↦ deg(X_{i}(P)) is such an embedding.

Note that the map above is necessarily an order homomorphism by the remark following Definition 2.2.2. In order to make it an embedding onto an initial segment, some requirements need to be forced.

Definition 4.1.5. Let e ∈ ω, T be a binary tree, and C_{n} represent L_{n}.

(i) T decides e-totality if either φ_{e}^{P} is total for all P ∈ [T] or φ_{e}^{P} is not total for all P ∈ [T]. T forces e-totality, e-partiality in the first, resp. second case.

(ii) T is e-splitting for C_{n} if there exists i ≤ n such that for all P ∈ [T] with φ_{e}^{P} total, we have φ_{e}^{P} ≡_{T} X_{i}(P).

The definition of e-splitting in [Eps79] is different, but implies this one by the Computation Lemma ([Eps79, IV.C]). If the generic path lies on an e-splitting tree for all e, it will thus code a map onto an initial segment. To make sure that the map does not collapse anywhere, we can force differentiation as we did in Chapter 3. But it is simpler to rely on the general Diagonalization Lemma ([Eps79, IV.C], based on Posner’s argument), which we reword as follows.

Lemma 4.1.6. Suppose that the sequence X_{i} represents L, i <_{L} j, and B is an infinite binary string. Suppose further that the following is true for all but finitely many n: that B lies on a uniform binary tree T which is n-splitting and special for X_{i} − X_{j}. Then X_{j}(B) ≰_{T} X_{i}(B).

Finally we state the lemma concerning the effective density of the properties which we would like to force. As in Chapter 3, it is justified by reviewing the arguments in the source ([Eps79, V.A, VI.B]) and noticing that the different cases are defined by two quantifier statements.

Lemma 4.1.7. There is a total function f : ω × ω × ω → ω, computable in 0′′, such that if C_{n} is (a recursive index for) a sequence representing L_{n} and T is (a recursive index for) a uniform binary tree, special for C_{n} then f(C_{n}, e, T) is (a recursive index for) a uniform subtree of T, special for C_{n} which decides e-totality and is e-splitting for C_{n}.

4.2 The Main Construction

We construct a tree of embeddings, as we did in Chapter 3. Lemma 4.2.1. There is a sequence C representing L and a uniform binary tree T̂, both computable in 0′′, such that every P ∈ [T̂] codes an embedding of L onto an initial segment of D with respect to C. Furthermore, there is a recursive sequence {Y_{i}} of disjoint infinite subsets of ω such that for any path P = T̂(A) and any i ∈ ω

X_{i}(P)′′ ≡_{T} X_{i}(P) ∨ 0′′ ≡_{T} ⊕_{j≤_{L}i}Y_{j}(A) ∨ 0′′

Proof. First we fix the sequence {Y_{i}}. Let l : ω → ω \ {0} be recursive such that (i) l(i) ≤ i + 1 for all i (ii) Y_{i} = l^{−1}(i) is infinite for all i > 0 Let f be as in Lemma 4.1.7. We define in stages the sequence C = {X_{0}, X_{1}, … } and recursive uniform trees T_{σ} for all finite binary strings σ. We use C_{n} to denote the partial sequence X_{0}, …, X_{n}. The trees T_{σ} will satisfy the following properties:

(i) T_{σ} is special for C_{|σ|+1} (ii) If |σ| = j then |T_{σ}(∅)| ≤ min(X_{j+1}) (iii) If |σ| = j then T_{σ}(0) and T_{σ}(1) disagree on X_{l(j)}, and l(j) is the L_{j+1}-least

for which this holds. (iii)^{∗} If |σ| = j then T_{σ⌢0}(∅) and T_{σ⌢1}(∅) disagree on X_{l(j)}, and l(j) is the L_{j+1}-least

for which this holds. (iv) T_{σ⌢d} ⊆ T_{σ}E_{d} (for d = 0, 1)

(v) T_{σ⌢d} ⊆ f(C_{|σ|+1}, |σ|, T) for some recursive tree T

(vi) if |σ_{1}| = |σ_{2}| then |T_{σ_{1}}(∅)| = |T_{σ_{2}}(∅)|

(vii) if |σ_{1}| = |σ_{2}| then

T_{σ_{1}}(ρ⌢ρ′) − T_{σ_{1}}(ρ) = T_{σ_{2}}(ρ⌢ρ′) − T_{σ_{2}}(ρ).

Let X_{0} = ∅ and X_{1} = ω. We let T_{∅} = T_{id}, and note that it is trivially special for C_{1} since any branching agrees on X_{0} but not on X_{1}. Property (iii) is also fulfilled, since l(0) = 1. Suppose T_{σ} has been defined for all σ of length k. Let {τ_{j}}_{j=1}^{m} list all binary strings of length k + 1, and let τ_{j} = σ_{j} ⌢d_{j} with |σ_{j}| = k and d_{j} < 2.Let T′_{τ_{j}} = T_{σ_{j}}E_{d_{j}}. We go by subinduction on j:

T_{τ_{1}}^{∗} = f(C_{k+1}, k, T′_{τ_{1}}), T_{τ_{j+1}}^{∗} = f(C_{k+1}, k, T′_{τ_{j+1}}(T_{τ_{j}}^{∗}/T′_{τ_{j}})).

For all 1 ≤ j ≤ m now let

T̃_{τ_{j}} = T′_{τ_{j}}(T_{τ_{m}}^{∗}/T′_{τ_{m}}).

As in Chapter 3, T̃_{τ_{j}} are uniform recursive and satisfy conditions (iv)-(vii) above (in place of T_{τ_{j}}. Furthermore, it is easily seen that replacing these by T̃_{τ_{j}}E_{σ} for any fixed σ will maintain that.

In order to satisfy property (i), we simply define X_{k+2} in a way which would make the trees T̃_{τ_{j}} special for C_{k+2}. Let a and b be the immediate predecessor and immediate successor (resp.) of k + 2 in L_{k+2}. Now, T̃_{τ_{1}} is special for C_{k+1}, and in particular for X_{a} − X_{b}, so that the set

Z = {m : |σ| = m → T̃_{τ_{1}}(σ ⌢0), T̃_{τ_{1}}(σ ⌢1) agree on X_{a} but not on X_{b}}

is infinite (and clearly recursive). Let m_{0}, m_{1}, … be an increasing enumeration of Z. Let

Z_{0} = {x : x ∈ X_{b} \ X_{a} and |T̃_{τ_{1}}(σ)| ≤ x < |T̃_{τ_{1}}(σ ⌢0)| where |σ| = m_{2t}, t ∈ ω},

an infinite recursive set. Let X̃_{k+2} = X_{a} ∪ Z_{0}. Then X_{a} ⊆^{∗} X̃_{k+2} ⊆^{∗} X_{b} and the differences are infinite. Also, T̃_{τ_{1}} is special for X_{a} − X̃_{k+2} since at any level m_{2t} it branches in a way which agrees on X_{a} and disagrees on X̃_{k+2}. By a similar argument (for levels m_{2t+1}) it is seen to be special for X̃_{k+2} − X_{b}. Now note that for any 1 ≤ j ≤ m and any σ, the tree T̃_{τ_{j}}E_{σ} will be special for X_{a} − X̃_{k+2} and for X̃_{k+2} − X_{b}, because the branchings in all trees T̃_{τ_{j}} are the same (property (vii)) and taking an extension tree will only remove finitely many levels.

For condition (iii), let b = l(k + 1) and a the immediate predecessor of b in L_{k+2}. Let r be the least such that T̃_{τ_{1}}(0^{r}0) and T̃_{τ_{1}}(0^{r}1) agree on X_{a} and not on X_{b}. Such r exists, since the tree is special for X_{a} − X_{b}. Now let T_{τ_{j}} = T̃_{τ_{j}}E_{0^{r}} for all 1 ≤ j ≤ m. This takes care of condition (iii). Condition (iii)^{∗} is fulfilled as well, since for any d < 2

T_{σ_{j}⌢d}(∅) = T̃_{σ_{j}⌢d}(0^{r}) = T′_{σ_{j}⌢d}(T_{τ_{m}}^{∗}/T′_{τ_{m}})(0^{r}) = T_{σ_{j}}E_{d}(ρ) = T_{σ_{j}}(d⌢ρ)

where ρ = (T_{τ_{m}}^{∗}/T′_{τ_{m}})(0^{r}). By condition (vii), T_{σ_{j}}(d ⌢ ρ) − T_{σ_{j}}(d) is the same for both values of d, and thus the disagreement between the strings T_{σ_{j}⌢d}(∅) is the same as between the strings T_{σ_{j}}(d). Condition (iii)^{∗} now follows immediately from condition (iii).

Finally, let X_{k+2} = X̃_{k+2} \ {0, 1, …, |T_{0^{k+1}}(∅)|}. As this is only a finite change, we still have X_{a} ⊆^{∗} X_{k+2} ⊆^{∗} X_{b} with infinite differences, and T_{τ_{j}} is special for X_{a} − X_{k+2} and for X_{k+2} − X_{b}, for all 1 ≤ j ≤ m. Therefore C_{k+2} represents L_{k+2}, and the trees T_{τ_{j}} are special for C_{k+2}. Condition (ii) is now fulfilled by definition of X_{k+2}. This completes the induction on k.

Now let T̂(σ) = T_{σ}(∅). By an argument analogous to that in Chapter 3, T̂ is uniform. The tree, as well as the sequence C = ∪C_{k} which represents L, are recursive in 0′′ since the construction is.

Fix P = T̂(A) ∈ [T̂]. The requirements forced, together with lemma 4.1.6, imply that P codes an embedding of L onto an initial segment of D. It is left to show that

X_{i}(P) ∨ 0′′ ≥_{T} ⊕_{j≤_{L}i}Y_{j}(A) ∨ 0′′ ≥_{T} X_{i}(P)′′

holds for every i ∈ ω.

To establish the first inequality, it suffices to demonstrate that X_{i}(P) ∨ 0′′ ≥_{T} Y_{i}(A) uniformly for all i, since then for all j ≤_{L} i we have

X_{i}(P) ∨ 0′′ ≥_{T} X_{j}(P) ∨ 0′′ ≥_{T} Y_{j}(A).

(The reduction on the left is uniform because the sequence {X_{i}} is uniformly recursive in 0′′.) We compute the value of Y_{i}(A)(n) given X_{i}(P) ∨ 0′′. First let m be the n-th value of Y_{i}, so that Y_{i}(A)(n) = A(m). Note that l(m) = i, and therefore T_{σ⌢0}(∅) and T_{σ⌢1}(∅) disagree on X_{i} whenever |σ| = m, by property (iii)^{∗}. Then A(m) = d such that T (σ ⌢d) agrees with P on X_{i} above |T (σ)|.

Next we show that ⊕_{j≤Li}Y_{j}(A) ∨ 0′′ ≥_{T} X_{i}(P)′′. To find X_{i}(P)′′(n), we need to find whether φ_{n}^{X_{i}(P)} is total or not. First let m > 0 be such that φ_{n}^{X_{i}(P)} ≃ φ_{m}^{P} and φ_{m} depends only on oracle values at members of X_{i} (φ_{m} first applies X_{i} to the oracle, then computes φ_{n} with the new oracle). We find, by induction on j ≤ m, a string σ of length j + 1 such that T_{σ}(∅) agrees with P on X_{i}. Suppose that we have σ up to length j. If T_{0^{j}⌢0}(∅) and T_{0^{j}⌢1}(∅) agree on X_{i}, let σ(j) = 0 (a value of 1 would do just as well, of course). Otherwise, T_{0^{j}⌢0}(∅) and T_{0^{j}⌢1}(∅) disagree on X_{i}. We cannot have i > j + 1, since then by condition (ii)

|T_{0^{j+1}}| ≤ |T_{0^{i−1}}(∅)| ≤ min(X_{i}),

in contradiction to the disagreement. Thus i ∈ L_{j+1}, and by condition (iii)^{∗} we have l(j) ≤_{L} i (since l(j) is the least in L_{j+1} for which there is a disagreement). Y_{l(j)}(A) is then part of our oracle, and we can find A(j) = Y_{l(j)}(A)(k) (the value of k depends on l alone). Set σ(j) = A(j). This must be the branching which agrees with P on X_{i}, since the tree is uniform. This completes the computation of σ.

Now notice that

n ∈ X_{i}(P)′′ ⟺ φ_{n}^{X_{i}(P)} is total
⟺ φ_{m}^{P} is total
⟺ T_{A↾(m+1)} forces m-totality
⟺ T_{σ} forces m-totality,

where the last equivalence stems from the equality

{X_{i}(Q) : Q ∈ [T_{A↾(m+1)}]} = {X_{i}(Q) : Q ∈ [T_{σ}]}

which is a consequence of property (vii) and the agreement of T_{σ}(∅) and P = T̂(A) on X_{i}.

4.3 The Results

As in Chapter 3, we first conclude

Corollary 4.3.1. There are 2^{ω} many lattice embeddings of L as an initial segment of D.

On to the main theorem of this section.

Theorem 4.3.2. Let L = (ω, ≤) be a countable linear order, computable in 0′′, with bottom element 0 and top element 1. Let h : L → D be an order homomorphism, with h(0) = 0′′. There is an initial segment C of D and an order isomorphism g : L → C such that

g(i)′′ = g(i) ∨ 0′′ = h(i) for all i ∈ L.

Proof. In view of Lemma 4.2.1, all we need is to define A in such a way that deg(⊕_{j≤_{L}i}Y_{j}(A)) ∨ 0′′ = h(i) for all i ∈ w. Pick representatives A_{i} ∈ h(i) for i > 0, and let A be such that Y_{i}(A) = A_{i} for all i ∈ ω (such A is unique, since the sets Y_{i} form a partition of ω). Now observe that for all i > 0

h(i) = deg(A_{i}) = deg(Y_{i}(A)) = deg(⊕_{j≤_{L}i}Y_{j}(A)) ∨ 0′′

since h(i) ≥ 0′′ for all i > 0 and A_{i} ≥_{T} A_{j} uniformly for j ≤_{L} i (the uniformity follows from the fact that the sequence {Y_{i}} is uniformly recursive.

Now let P = T̂(A), and set g(i) = deg(X_{i}(P)). The equality in the theorem follows for i > 0 by the above, and for i = 0 trivially.

We can relativize and iterate to obtain

Theorem 4.3.3. Let L = (ω, ≤) be a countable linear order, computable in 0′′, with bottom element 0 and top element 1. Let h : L → D be an order homomorphism, with h(0) = 0^{(2n)}. There are initial segments C_{k} of D(≥ 0^{(2k)}) and order isomorphisms g_{k} : L → C_{k} for k < n such that

g_{k}(i)′′ = g_{k}(i) ∨ 0^{(2k+2)} = g_{k+1}(i)  for all i ∈ ω and k < n − 1, and
g_{n−1}(i)′′ = g_{n−1}(i) ∨ 0^{(2n)} = h(i)  for all i ∈ ω.

Proof. This is straightforward. Since L is recursive in 0′′, it is recursive in 0^{(2k)} for any k > 0.

Degrees r.e.a. in 0′′

Section 1 deduces the main result from known theorems. Section 2 presents a direct construction which produces a slight alteration of it. Section 3 explains why a generalization of the result to non-trivial lattices is problematic.

5.1 Introduction

The following theorem is a relativization of the Sacks Inversion Theorem. The second one is the Cooper Inversion Theorem.

Theorem 5.1.1. [Sac63] If b is r.e. in and above x′ then there exists a degree c r.e. in and above x such that c′ = b.

Theorem 5.1.2. [Coo73] If c ≥ 0′ then there exists a minimal degree a such that a′ = c.

If we take x to be 0′ in Theorem 5.1.1, the two theorems combine to produce

Theorem 5.1.3. If b is r.e. in and above 0′′ then there exists a minimal degree a < 0′′ such that b = a′′.

Proof. We get a < 0′′ since c = a′ is r.e. in 0′, and so computable in 0′′.

Note that the converse also holds: if a < 0′′ is minimal, then a′′ is r.e. in (and trivially above) 0′′, for a′′ = (a ∨ 0′)′ by Theorem 2.1.5, and that is r.e. in a ∨ 0′ ≤ 0′′. This characterizes the degrees r.e. in and above 0′′ as the double jumps of minimal degrees below 0′′. As mentioned in Chapter 1, the corresponding problem for degrees r.e. in and above 0′ is not yet solved, and any solution will not be as simple as in the case of 0′′.

In the following section we directly construct a double jump inversion of a degree r.e. in and above 0′′, in a manner which is considerably simpler than the sum of the proofs of the two theorems above. We build on the standard construction of a minimal through forcing with binary trees (uniformity is not needed here), and we code a set B of degree b as we go along. However, we only have an enumeration of B (since the oracle is 0′′), and as a result we may make wrong coding steps. Going back to fix these mistakes creates finite injury, and the conditions settle down eventually.

It turns out that the degree a produced by this construction is different in a fundamental way from the degree given by the proof of Theorem 5.1.3. For we can reconstruct the set B using a′ and the construction oracle, giving

b = a′ ∨ 0′′,

whereas in Theorem 5.1.3 we have a′ ≤ 0′′, and so a′ ∨ 0′′ = 0′′.

Before presenting the construction, we mention the appropriate density lemma, justified in [Ler83, V.2.7, V.3.2].

Definition 5.1.4. A binary tree T is e-splitting if for all P ∈ [T], whenever φ_{e}^{P} is total it is either recursive or computes P.

Lemma 5.1.5. There is a total function f : ω × ω → ω, computable in 0′′, such that if T is (a recursive index for) a binary tree then f(e, T) is (a recursive index for) a binary tree which

(i) is a subtree of T · E_{i} where i < 2 is such that T (i) is incompatible with φ_{e};

(ii) decides e-totality;

(iii) is e-splitting.

We also define the standard narrow binary tree N_{2} as follows:

N_{2}(d_{0}d_{1} … d_{n}) = d_{0}0d_{1}0 … d_{n}0

for all n ∈ ω, d_{i} < 2. Note that for every binary tree T, the tree T · N_{2} is a narrow subtree of T: for no binary string σ is T · E_{σ} a subtree of T · N_{2}. Moreover, if T is recursive, so is T · N_{2}.

5.2 The Construction

Theorem 5.2.1. If b is r.e. in and above 0′′ then there exists a minimal degree a < 0′′ such that

b = a′′ = a′ ∨ 0′′ = (a ∨ 0′)′.

Proof. Fix a set B ∈ b r.e. in 0′′, and let ⟨b_{i}⟩_{i∈ω} be an enumeration witnessing that. Let B_{s} = {b_{i} : i < s} approximate B. The construction is a finite injury one, with oracle 0′′. At stage s we define a nested sequence of recursive binary trees T_{i}^{s} for i ≤ g(s), and a finite string α_{s} = T_{g(s)}^{s}(∅).

Let g(0) = 0, and let T_{0}^{0} be the identity tree (with α_{0} = ∅). At stage s + 1, if g(s) > b_{s} (injury) let g(s + 1) = b_{s} + 1, otherwise let g(s + 1) = g(s) + 1. For all i < g(s + 1) let T_{i}^{s+1} = T_{i}^{s}. Let n = g(s + 1) − 1. If n ∉ B_{s+1} let T_{g(s+1)}^{s+1} = f(n, T_{n}^{s+1}N_{2}). Otherwise let T_{g(s+1)}^{s+1} = f(n, T_{n}^{s+1}E_{σ}) where σ is the first string of even length m such that σ(m − 1) = 1 and T_{n}^{s+1}(σ) ⊇ α_{s}. In any case, let α_{s+1} = T_{g(s+1)}^{s+1}(∅).

Let A = ∪_{s}α_{s}, a = deg(A). This completes the construction.

Before we proceed with the proof, note that in case of injury (g(s) > b_{s}), T_{b_{s}+1}^{s+1} is defined to be a subtree of T_{b_{s}}^{s}E_{σ} where σ is not on N_{2}, whereas at stage s, T_{b_{s}+1}^{s} ⊆ T_{b_{s}}N_{2}. Consequently, not only are T_{b_{s}+1}^{s} and T_{b_{s}+1}^{s+1} different, but they also have disjoint sets of paths. The importance of this point will be apparent in the proof.

First we show by induction that T_{i} = lim_{s} T_{i}^{s} exists for all i. T_{0}^{s} is never changed, since g(s) > 0 for all s > 0. Let s be a stage at which T_{j}^{s} = T_{j} for all j ≤ i. This implies that no n < i enters B after s. Let t ≥ s be the least such that T_{i+1}^{t} ≠ T_{i+1}^{t+1} (if there is no such, we’re done). It must be that b_{t} = i, and so g(t + 1) = i + 1. Therefore after t + 1 no n ≤ i enters B, g remains above i + 1, and lim_{s} T_{i+1}^{s} = T_{i+1}^{t+1}.

Next, observe that a is a minimal degree, since for every e there is some tree S such that A lies on T_{e+1} = f(e, S). The construction is recursive in 0′′, consequently a < 0′′.

To find Tot^{A}(n) given B, follow the construction (using 0′′ ≤ B) until B_{s} ↾ (n + 1) = B ↾ (n + 1). As above, this means that T_{n+1} = T_{n+1}^{s} = f(n, S) for some S. Since A is a path on T_{n+1}, we have n ∈ Tot^{A} iff T_{n+1}^{s} forces n-totality, and this can be found using 0′′. Hence a′′ ≤ b.

To find B(n) given A′ ∨ 0′′, follow the construction, and at every stage s where T_{n+1}^{s} is redefined, find if A lies on T_{n+1}^{s} (this is recursive in A′). Since A ∈ [T_{n+1}], this will eventually be the case. We claim that n ∈ B iff n ∈ B_{s}, where s is the first such that A ∈ [T_{n+1}^{s}]. Indeed, if n ∈ B_{s}, clearly n ∈ B. Suppose n ∉ B_{s}. Let m = b_{t} be the least with t ≥ s, and suppose that m ≤ n. Then

A ∈ [T_{n+1}^{s}] ⊆ [T_{m+1}^{s}] = [T_{m+1}^{t}] and [T_{m+1}^{t}] ∩ [T_{m+1}^{t+1}] = ∅,

hence A ∉ [T_{m+1}^{t+1}]. But T_{m+1} = T_{m+1}^{t+1} and A does lie on T_{m+1}. The contradiction implies that m > n, and consequently that n never enters B.

Together with the inequality a′ ∨ 0′′ ≤ a′′, this proves the first two equalities in the theorem. The last one follows from Lemma 2.1.5.

5.3 Limitations

It is natural to hope for a generalization of the construction which would allow double-jump inversions of certain lattices (of degrees r.e.a. in 0′′) onto initial segments. As it turns out, even Theorem 5.1.3 is not generalizable to the simplest lattices.

Theorem 5.3.1. There are degrees b_{1} and b_{2}, r.e. in and above 0′′, such that for no four element initial segment {0, a_{1}, a_{2}, a_{1} ∨ a_{2}} below 0′′ do we have a′′_{i} = b_{i} and (a_{1} ∨ a_{2})′′ = b_{1} ∨ b_{2}.

Proof. We relativize Shore’s non-inversion theorem [Sho88, 1.2] to 0′: there are degrees b_{1} and b_{2}, r.e. in and above 0′′, such that for no 0′ ≤ c_{1}, c_{2} ≤ 0′′ do we have c′_{i} = b_{i} and (c_{1} ∨ c_{2})′ = b_{1} ∨ b_{2}. Fix such b_{1} and b_{2}.

Suppose there is an initial segment as in the theorem, and let c_{i} = a_{i} ∨ 0′ for i = 1, 2. Then 0′ ≤ c_{1}, c_{2} ≤ 0′′, and for i = 1, 2 we have

c′_{i} = (a_{i} ∨ 0′)′ = a′′_{i} = b_{i}

since a_{i} is GL_{2} by Lemma 2.1.5. For a contradiction, note that (a_{1} ∨ a_{2}) is GL_{2} as well, and therefore

(c_{1} ∨ c_{2})′ = ((a_{1} ∨ a_{2}) ∨ 0′)′ = (a_{1} ∨ a_{2})′′ = b_{1} ∨ b_{2}.

A Non-Weakly Recursive Minimal With a

Strong Minimal Cover

We enter the second part of the thesis, concerning weakly recursive degrees and strong minimal covers. The introduction to this section covers the basic definitions and gives an overview of the construction, which follows in section 2.

6.1 Introduction

The following definition applies to any partial order. However we restrict our attention to Turing degrees.

Definition 6.1.1. Let b < a be Turing degrees.

(i) a is a minimal cover of b if the interval (b, a) is empty.

(ii) a is a strong minimal cover of b if the intervals [0, b] and [0, a) are equal.

Clearly (ii) implies (i). The following definition and theorem are due to Ishmukhametov.

Definition 6.1.2. A degree a is weakly recursive if there is a recursive function p such that for every function f ≤ a there is a recursive function h such that |W_{h(n)}| ≤ p(n) and f(n) ∈ W_{h(n)} for all n ∈ ω.

Theorem 6.1.3. [Ish99] Every weakly recursive degree has a strong minimal cover.

While the converse is true for r.e. degrees [Ish99], we show that it is not true in general. Indeed, in this chapter we construct a (minimal) degree b which is not weakly recursive but has a strong minimal cover. The 0′′ construction is based on that of a three element linear initial segment [Eps79, III] with uniform trees. In order to make the middle degree non-weakly recursive, we define functions f_{i} ≤ b and diagonalize with f_{i} against p_{i}, h_{j} for all j, where p_{k} = h_{k} is an enumeration of all recursive functions (which our oracle provides).

The diagonalization requires fattening the trees so that the branching exceeds the bounds given by p_{i}. This leads us to abandon binary trees in favor of partial ω-trees. The trees are finitely branching, but all of their paths are infinite (so that their partiality is still limited).

Since the trees diverge from the definition given in Chapter 2, care must be taken when dealing with concepts such as tree division (which is used, but in a limited capacity). Also, we are forced to go into the semi-gory details of splitting trees (which were elegantly skipped in previous chapters).

Recall Definition 2.2.2, and let Od be the set of odd natural numbers.

Definition 6.1.4. (i) Two strings σ, τ form an e-split if φ_{e}^{σ}(x) ↓≠ φ_{e}^{τ}(x) ↓ for some x ∈ ω.

(ii) A tree is e-non-splitting if no pair of strings in its range form an e-split.

(iii) A tree is e-splitting if every pair of non-compatible strings in its range form an e-split.

(iv) A tree T is e-splitting on the odds if every branching pair on T (i.e. two immediate successors of the same node) which disagrees on Od forms an e-split, and no pair of strings on T which agrees on the odds forms an e-split.

The following is a summary of the Computation Lemmas from [Eps79, I.G, III.A]. Lemma 6.1.5. Let A be a path on a tree T, such that C = φ_{e}^{A} is a total function.

(i) If T is e-non-splitting, then C is recursive.

(ii) If T is e-splitting, then C ≥_{T} A.

(iii) If T is e-splitting on the odds, then C ≡_{T} Od(A).

6.2 The Construction

Theorem 6.2.1. There are degrees b < a ≤ 0′′ such that b is minimal and not weakly recursive, and a is a strong minimal cover of b. Proof. We construct, with oracle 0′′, an infinite ω-string A and functions {f_{i}}_{i∈ω} recursive in Od(A) satisfying the following requirements:

R_{s}^{0} :  Od(A) ≠ φ_{s}
R_{s}^{1} :  A ≠ φ_{s}^{Od(A)}
R_{s}^{2} :  s = ⟨i, j⟩ → ∃n (|W_{h_{j}(n)}| > p_{i}(n) ∨ f_{i}(n) ∉ W_{h_{j}(n)})
R_{s}^{3} :  φ_{s}^{A} = C is total → (C ≤_{T} 0 ∨ A ≤_{T} C ∨ C ≡_{T} Od(A))

Where p_{i} = h_{i} is the i-th recursive function (which can be found recursively in 0′′). Clearly, if A satisfies these requirements for all k ∈ ω, then b = deg(Od(A)) is minimal and not weakly recursive, and a = deg(A) is a strong minimal cover of b. The construction will produce a sequence of recursive uniform partial ω-trees such that T_{n+1} ⊆ T_{n} for all n. We use τ ⊏_{i} τ′ to mean that for some string σ and k ∈ ω, τ = T_{i}(σ) and τ′ = T_{i}(σ ⌢k) (in other words, τ′ is an immediate successor of τ on T_{i}). We want the following conditions to hold for all i:

(i) If σ ⌢k ∈ dom(T_{i}) and k′ < k then σ ⌢k′ ∈ dom(T_{i}).

(ii) T_{i} is 2-branching at odd levels, i.e. if σ ∈ dom(T_{i}) is of odd length then T_{i}(σ ⌢0) and T_{i}(σ ⌢1) are the (only) immediate successors of T_{i}(σ) on T_{i}.

(iii) (τ_{1}, τ_{2} ⊐_{i} T_{i}(σ) ∧ τ_{1} ≠ τ_{2}) → (|σ| is odd ↔ Od(τ_{1}) = Od(τ_{2}))

(iv) (τ_{1} ∈ rg(T_{i}) ∧ i′ < i ∧ τ_{1} ⊏_{i′} τ_{2}) → ∃τ_{3} ⊇ τ_{2} (τ_{1} ⊏_{i} τ_{3})

Note that if T_{i} satisfies these conditions and T_{i+1} is an extension subtree T_{i} · E_{σ} with |σ| even, then T_{i+1} satisfies these conditions as well.

A will be the unique path which lies on all T_{i}, and the functions f_{i} are computed from A as follows:

f_{i}(n) = C(2n) where A = T_{5i}(C).

Thus, in order to force the value of f_{i}(n) it suffices to specify which node on level 2n + 1 of T_{5i} is an initial segment of A. Note that by condition (iii), if C_{1}(2n) ≠ C_{2}(2n) then Od(T_{5i}(C_{1})) ≠ Od(T_{5i}(C_{2})), and therefore f_{i} is computable in Od(A) (for all i).

To define T_{0}, let

T_{0}(k_{0}d_{0}k_{1}d_{1}k_{2}d_{2} …) = (0k_{0})⌢(d_{0}0)⌢(0k_{1})⌢(d_{1}0)⌢(0k_{2})⌢(d_{2}0)⌢…

for all k_{n} ≤ max(p_{0}(n), 1) and d_{n} = 0, 1 (the parenthesis are for readability). Note that T_{0} satisfies conditions (i)-(iii), and has > p_{0}(n)-branching at level 2n (for all n). Stages 5s+4 of the construction will ensure that T_{5s} will be > p_{s}(n)-branching at level 2n, for all s > 0 as well (this will be assumed in stages 5s + 2).

Stage 5s: Pick the first σ of length 2 such that Od(T_{5s}(σ)) is incompatible with φ_{s} (this is recursive in 0′). Let T_{5s+1} = T_{5s}E_{σ}. Then T_{5s+1} forces R_{s}^{0}, and conditions (i)-(iv) are maintained as in the remark above.

Stage 5s + 1: Let α_{i} = T_{5s+1}(0 ⌢ i) for i = 0, 1, and let x be the first on which α_{0}, α_{1} disagree (note that Od(α_{0}) = Od(α_{1}), so x is even). If there is an extension of α_{0} on T_{5s+1} which forces φ_{s}^{Od(A)}(x) ↑, let σ to be the first of even length such that T_{5s+1}(σ) is such an extension (this is recursive in 0′′).

Otherwise let σ_{0} be the first of even length such that β_{0} = T_{5s+1}(σ_{0}) = α_{0} ⌢ τ satisfies φ_{s}^{Od(β_{0})}(x)↓. Let β_{1} = α_{1} ⌢τ = T_{5s+1}(σ_{1}) (exists by uniformity). Then

β_{0}(x) ≠ β_{1}(x) and φ_{s}^{Od(β_{0})}(x)↓= φ_{s}^{Od(β_{1})}(x)↓

since Od(β_{0}) = Od(β_{1}). Let i be the first such that φ_{s}^{Od(β_{i})}(x) ≠ β_{i}(x), and let σ = σ_{i}.

In any case, now let T_{5s+2} = T_{5s+1}E_{σ}. Then T_{5s+2} is recursive and forces R_{s}^{1}, and conditions (i)-(iv) are maintained.

Stage 5s + 2: Let i, j be such that s = ⟨i, j⟩. Let τ = T_{5s+2}(∅) = T_{5i}(σ). By conditions (iii) and (iv), σ is of some even length 2n. If |W_{h_{j}(n)}| ≤ p_{i}(n), find t ≤ p_{i}(n) such that t ∉ W_{h_{j}(n)} (given h_{j} and p_{i}, this is computable in 0′), and let T_{5s+3} = T_{5s+2}E_{r⌢0} where T_{5s+2}(r) ⊇ T_{5i}(σ ⌢ t) (such r exists by condition (iv)). Then T_{5s+3} satisfies conditions (i)-(iv) and fixes f_{i}(n) = t, thus forcing R_{s}^{2}.

If |W_{h_{j}(n)}| > p_{i}(n), then R_{s}^{2} is already satisfied. In this case, simply let T_{5s+3} = T_{5s+2}.

Stage 5s + 3:

(i) If there is some x and some τ = T_{5s+3}(σ) which forces φ_{s}^{A}(x)↑, let x, τ, σ be the first such with |σ| even, and let T_{5s+4} = T_{5s+3}E_{σ}. This will force φ_{s}^{A} to not be total.

(ii) Otherwise, if there is some τ = T_{5s+3}(σ) above which there are no s-splits, let τ, σ be the first such with |σ| even, and let T_{5s+4} = T_{5s+3}E_{σ}. This will force φ_{s}^{A} to be recursive by Lemma 6.1.5 (i).

(iii) Otherwise, if there is some τ = T_{5s+3}(σ) above which there are no s-splits which agree on the odds, let τ, σ be the first such with |σ| even. The idea here is to construct a subtree of T_{5s+3}E_{σ} with the branching at every even level being pairwise s-splitting. We replace T_{5s+3}, T_{5s+4} with T, T′, resp., for readability. The construction is by induction on the tree level, starting with T′(∅) = τ. Suppose we have defined level n′ of T′, consisting of strings from level n of T (where n − n′ is even). If n′ is odd, simply copy the successors from level n + 1 of T, that is let

T′(σ ⌢i) = T ((T′/T)(σ)⌢i) for all σ ∈ dom(T′) of length n and i = 0, 1.

Note that this is clearly in accordance with conditions (i)-(iv). If n′ is even, let τ_{i} = T′(σ_{i}) (for 1 ≤ i ≤ r) be the strings on level n′ of T′, and let q be the branching size at level n of T. We go by induction on i ≤ r defining a set of extensions ρ_{i,j} for j < q. First let ρ_{0,j} = T ((T′/T)(σ_{0}) ⌢ j) − τ_{0} (that is, the original q extensions of τ_{1} on T). For the induction step, suppose we have defined ρ_{i−1,j} for all j < q. We define strings ρ_{i,j}^{m} by a subinduction on m running over an ordered list of all pairs ⟨t, t′⟩ ∈ q × q with t < t′. First let ρ_{i,j}^{−1} = ρ_{i−1,j}. Given ρ_{i,j}^{m^{−}}, with the next pair being m = ⟨t, t′⟩, let (χ_{0}, χ_{1}) be the first s-split above τ_{i} ⌢ ρ_{i,t}^{m^{−}} on T, and let x be the first such that φ_{s}^{χ_{0}}(x) ≠ φ_{s}^{χ_{1}}(x). Let χ_{2} be the first extension of τ_{i} ⌢ ρ_{i,t′}^{m^{−}} on T such that φ_{s}^{χ_{2}}(x) ↓. Let ρ_{i,t′}^{m} = χ_{2} − τ_{i}, and let ρ_{i,t} be χ_{k} − τ_{i} where k < 2 is the first such that (τ_{k}, τ_{2}) s-splits. Let ρ_{i,j}^{m} = ρ_{i,j}^{m^{−}} for all other j. This completes the subinduction. Having defined ρ_{i,j}^{m} for the last pair m, let w be the least odd number not less than all levels of T on which the strings τ_{i} ⌢ρ_{i,j}^{m} lie. For all j < q, let ρ_{i,j} be the least extension of ρ_{i,j}^{m} such that τ_{i} ⌢ ρ_{i,j} lies on level w of T. This completes the induction on i. Finally, let T′(σ_{i} ⌢j) = τ_{i} ⌢ρ_{r,j} for all 1 ≤ i ≤ r and j < q. This completes the construction in this case. T′ satisfies conditions (i)-(iv). Furthermore, every branching in T which disagrees on the odds s-splits, while no s-split agrees on the odds. Thus T′ is s-splitting on the odds, and consequently forces φ_{s}^{A} ≡ Od(A) by Lemma 6.1.5 (iii).

(iv) Otherwise, it is necessarily the case that there are s-splits agreeing on the odds above every node on T_{5s+3}. In this case we construct a fully s-splitting tree T_{5s+4} with T_{5s+4}(∅) = T_{5s+3}(∅). At even levels, we apply the same process of erecting splits which was applied in case (iii). At odd levels the process is similar, but with two differences. First, there is no subinduction on m, since there is only one pair (q = 2 here). Second, we need to define the extensions ρ_{i,j} (for j = 0, 1) to agree on the odds. The latter slightly complicates the definition of ρ_{i,j} given ρ_{i−1,j}: Let (χ_{0}, χ_{1}) be the first s-split above τ_{i} ⌢ ρ_{i−1,0} on T, which agrees on the odds, and let x be the first such that φ_{s}^{χ_{0}}(x) ≠ φ_{s}^{χ_{1}}(x). Let χ_{2} be the first extension of χ_{0}[τ_{i} ⌢ ρ_{i−1,0} → τ_{i} ⌢ ρ_{i−1,1}] on T such that φ_{s}^{χ_{2}}(x)↓. Let k < 2 be the least such that (χ_{k}, χ_{2}) is an s-split (which agrees on the odds, note). Now let ρ_{i,0} and ρ_{i,1} be extensions of equal length of ρ_{i,0}^{∗} = χ_{k} − τ_{i} and ρ_{i,1}^{∗} = χ_{2} − τ_{i} (resp.), which agree on the odds, by copying the extension from the longer to the shorter. For instance, if ρ_{i,0}^{∗} is the longer, let ρ_{i,0} = ρ_{i,0}^{∗} and let ρ_{i,1} = ρ_{i,0}^{∗}[(ρ_{i,0}^{∗} ↾|ρ_{i,1}^{∗}|) → ρ_{i,1}^{∗}]. The tree thus created forces A ≤ φ_{s}^{A}, by Lemma 6.1.5 (ii).

In each of these cases we get a uniform subtree T_{5s+4} satisfying conditions (i)- (iv), which forces R_{s}^{3}.

Stage 5s + 4: The goal here is to build a subtree of T_{5s+4}, fat enough so as to have > p_{s+1}(m)-branching at level 2m (for every n).

The tree T′ = T_{5s+5} is constructed by induction on levels. As before, T_{5s+4} is denoted by T. First let T′(∅) = T (∅). Suppose we have defined level n′ of T′, consisting of strings from level n of T (where n − n′ is even). If n′ is odd, copy the successors from level n + 1 of T, as was done in case (iii). If n′ = 2m is even, let τ be a string on level n of T, and let w be the least odd number such that there are q > p_{s+1}(m) successors of τ on level w of T, name them τ ⌢ρ_{j} for j < q. For each σ of length n′ such that T′(σ) ↓, and for each j < q, let T′(σ ⌢ j) = T′(σ) ⌢ ρ_{j}. This ends the construction.

T_{5s+5} satisfies conditions (i)-(iv), and has > p_{s+1}(n)-branching at level 2n, as required by the construction.

A Non-Weakly Recursive Minimal Below 0′

We answer a question raised in [Ish99]. An outline is given in section 1, and the construction itself in section 2.

7.1 Introduction

We want to construct a minimal degree below 0′ which is not weakly recursive. In order to achieve that, we apply the diagonalization method presented in Chapter 6 to the classic construction of a minimal degree below 0′, using partial recursive trees and a finite injury argument [Ler83, IX.2.1].

Since 0′ is the oracle, we do not have the privilege of enumerating the recursive functions. However, if p_{i} (or h_{i}) is not total that fact will be found out eventually, and we can go back and act accordingly, just as we do when we run out of splittings.

As any minimal degree is not a.n.r. (see Theorem 1.2.2(i)), this result tightens the bound on the scope of Ishmukhametov’s characterization. The structure of Δ_{2}^{0} degrees (i.e. D(≤ 0′)) is considered to be the “closest”, in many aspects, to the structure of recursively enumerable Turing degrees. Here we see that, while every r.e. degree is either weakly recursive or array non-recursive, the same does not hold for the Δ_{2}^{0} degrees.

7.2 The Construction

Theorem 7.2.1. There is a minimal degree a < 0′ which is not weakly recursive.

Proof. The requirements here are:

R_{k}^{0} :  A ≠ φ_{k}
R_{k}^{1} :  k = ⟨i, j⟩ ∧ φ_{i}, φ_{j} are total → ∃n (|W_{φ_{j}(n)}| > φ_{i}(n) ∨ f_{i}(n) ∉ W_{φ_{j}(n)})
R_{k}^{2} :  φ_{k}^{A} = C is total → (C ≤_{T} 0 ∨ A ≤_{T} C)

The construction is a finite injury one, with oracle 0′. At stage s we construct partial recursive trees T_{i}^{s} for i ≤ g(s), and a string α_{s} = T_{g(s)}^{s}(∅). Following the notation of Chapter 6, we use τ ⊏_{i}^{s} τ′ to mean that τ′ is an immediate successor of τ on T_{i}^{s}. Since a single degree is being constructed, no uniformity is needed here. We will satisfy the following conditions for all s and i ≤ g(s):

(i) If i = 4k and φ_{k}(n) ↓ then every non-terminal node on the n-th level of T_{i}^{s} has > φ_{k}(n) immediate successors.

(ii) If i = 4k + 1 then T_{i}^{s} forces R_{k}^{0}.

(iii) If i = 4k + 2 then T_{i}^{s} forces R_{k}^{1} (f_{i} are defined below).

(iv) If i = 4k+3 then T_{i}^{s} is either a k-splitting subtree or a non-splitting extension subtree of T_{i−1}^{s}.

(v) If τ_{1} is a non-terminal node on T_{i}^{s} and τ_{1} ⊏_{i′}^{s} τ_{2} for some i′ < i, then there exists some τ_{3} ⊇ τ_{2} such that τ_{1} ⊏_{i}^{s} τ_{3}.

For each i, the trees T_{i}^{s} will approach a partial recursive limit tree T_{i}. The function A = ∪α_{s} is the unique path lying on all of the limit trees. The functions f_{i} are computed as follows:

f_{i}(n) = C(n) where A = T_{4i}(C).

We start with g(0) = 0 and T_{0} being the identity tree with domain {σ : σ(n) ≤ φ_{0}(n)} (we assume wlog that φ_{0} is total).

At stage s + 1, let g(s + 1) = g(s) + 1 (this might be changed if there is an injury). Let T_{i}^{s+1} = T_{i}^{s} for all i ≤ g(s). Let T = T_{g(s)}^{s+1}. We define T′ = T_{g(s)+1}^{s+1} by cases as described below. Before carrying out the appropriate instructions, however, we check for convergence of all computations φ_{i}(x) which are mentioned (only finitely many, so the 0′ oracle suffices). If φ_{i}(x) is found to diverge, φ_{i} is marked non-total.

(i) If g(s + 1) = 4k + 1, let T′ = T · E_{r} where r is the first such that T (r) is incompatible with φ_{k} (this is computable in 0′). This can fail if T (∅) is terminal on T, in which case an injury occurs (see below).

(ii) If g(s + 1) = 4k + 2, let i, j be such that k = ⟨i, j⟩. If either of φ_{i}, φ_{j} has been found to be non-total in a prior stage, there is nothing to be done, so let T′ = T. Otherwise observe that α_{s} = T (∅) = T_{4i}^{s+1}(σ) for some σ, and let n = |σ|. Look for the least p ≤ φ_{i}(n) such that p ∉ W_{φ_{j}(n)} (a 0′ computation). If p is found, find the q such that T (q) ⊇ T_{4i}^{s+1}(σ ⌢ p) (exists by property (v) above), and let T′ = T · E_{q}. If no such p is found then |W_{φ_{j}(n)}| > φ_{i}(n), and the requirement is already fulfilled, so let T′ = T. The same applies to the case where φ_{j}(n) ↑. If, however, T (∅) is terminal on T, an injury occurs (see below). Note that this includes the cases where φ_{i}(n)↑ or α_{s} is terminal on T_{4i}^{s+1}.

(iii) If g(s+1) = 4k+3 let T′(∅) = T (∅), and define T′ to be a k-splitting subtree of T in a manner which preserves property (v): when we have defined T′(σ′) = T (σ) = τ which has m immediate successors on T, we define immediate successors T′(σ′ ⌢ p) ⊇ T (σ ⌢ p) for all p < m, which k-split pairwise. The process is much simpler than in Chapter 6, as we do not need to have uniformity: start with ρ_{p} = T (σ ⌢p) for p < m, then for each pair u < v < m extend ρ_{u} and ρ_{v} to be k-splitting (and still on T). If this process cannot be completed, τ is terminal on T′.

(iv) If g(s + 1) = 4k + 4 let T′(∅) = T (∅), and define T′ to satisfy condition (v). When we have defined T′(σ′) = T (σ) = τ with |σ′| = n, let {τ_{p}}_{p<m} be the first set of pairwise incompatible successors of τ on T such that m > φ_{k+1}(n) and every immediate successor of τ on T is contained in some τ_{p}. Let T′(σ′ ⌢ p) = τ_{p} for p < m. If no such set of successors is found, τ is terminal on T′.

In cases (i) or (ii) above, injury occurs if α_{s} = T (∅) is terminal on T. In this case, let j be the least such that α_{s} is terminal on T_{j}^{s}. Note that j is either 4k + 3 or 4k + 4, since in the other two cases the tree is an extension subtree, and cannot be the first on which α_{s} is terminal. In either case, let g(s + 1) = 4k + 3, and as before let T_{i}^{s+1} = T_{i}^{s} for all i < g(s + 1). If j = 4k + 3 then some string τ ⊇ α_{s} on T_{4k+2}^{s} has no k-splits above it on that tree. On the other hand, if j = 4k + 4, then there are no infinite paths extending α_{s} on T_{4k+3}^{s} (the existence of such path would yield a set of successors as required in case (iv) above). This in turn means that some extension of α_{s} is terminal on T_{4k+3}^{s}, and again the existence of such a string τ is implied. Find the first such τ = T_{4k+2}^{s}(σ) using 0′, and set T_{4k+3}^{s+1} = T_{4k+2}^{s+1} · E_{σ}, a non-splitting extension subtree. This ends the construction.

Now we turn to the proof. The trees reach a limit by the usual argument: once T_{j}^{s} have stabilized for all j < i, T_{i}^{s} can be injured at most once (if i = 4k + 3). The sequence α_{s} is increasing, and so A = ∪α_{s} is a function recursive in 0′, the oracle for the construction. The requirements R_{k}^{0}, R_{k}^{1}, R_{k}^{2} are forced by the trees T_{4k+1}, T_{4k+2}, T_{4k+3} (respectively), and so a = deg(A) is minimal and not weakly recursive (refer to Lemma 6.1.5).

Very Weakly Recursive Degrees

We define very weakly recursive degrees, and modify Ishmukhametov’s original proof to show that this possibly larger class of degrees has the strong minimal cover property as well. At this point we have not been able to determine if there exists a very weakly recursive degree which is not weakly recursive. Definition 8.1. A degree a is very weakly recursive if there is a function p ≤ a such that for every function f ≤ a there is a recursive function h with |W_{h(n)}| ≤ p(n) and f(n) ∈ W_{h(n)} for all n ∈ ω.

Clearly every weakly recursive degree is very weakly recursive. Theorem 8.2. Every very weakly recursive degree a has a strong minimal cover. Proof. Let A ∈ a, and let p be the recursive function given by Definition 8.1.

We construct a set M with M(2n) = A(n), such that the following requirements are satisfied:

N_{e} : φ_{e}^{M} is total → (φ_{e}^{M} ≤_{T} A ∨ M ≤_{T} φ_{e}^{M}),
P_{e} : M ≠ φ_{e}^{A}.

In order to construct M, we will construct a sequence of trees {T_{e}}_{e∈ω} such that for all e ∈ ω:

(i) T_{e} ≤_{T} A is a full binary tree,

(ii) T_{e+1} is a subtree of T_{e}, with T_{e+1}(∅) ⊃ T_{e}(∅),

(iii) T_{e+1} forces both N_{e} and P_{e}.

We will then define M as the unique path which lies on all of the trees T_{e}. M will consequently satisfy all requirements N_{e} and P_{e}, and will thus be a strong minimal cover for A.

We start by defining

T_{0} = {σ : ∀n (σ(2n)↓ → σ(2n) = A(n))}

(that is, the full tree of “A-true” strings). T_{0} clearly satisfies condition (i).

At stage e > 0 the trees T_{k} for k ≤ e have been already defined and satisfy conditions (i)-(iii). There are two cases. Case 1. There are no e-splits on T_{e} above some σ = T_{e}(τ).

In this case let T_{e+1} = T_{e} · E_{τ^{∗}}, where τ^{∗} ⊃ τ is the first such that T_{e}(τ^{∗}) ⊈ φ_{e}^{A}. Conditions (i) and (ii) are clearly satisfied by T_{e+1}. For condition (iii), note that N_{e} is forced since if φ_{e}^{M} is total then it can be computed from the non-e-splitting T_{e+1}. Case 2. e-splits are dense on T_{e}.

In other words, there is an e-split above every σ ∈ rg(T_{e}). Merely taking the splitting subtree as T_{e+1} will not do here, as it will produce a minimal cover which is not necessarily strong.

Therefore, in addition to the tree T_{e+1} we shall also construct a partial tree T : ω^{<ω} → 2^{<ω} for which the following conditions hold:

(a) T is partial recursive (i.e. has a r.e. graph), (b) T is e-splitting (i.e. every branching e-splits),

(c) T_{e+1} ⊆ T.

Given such T and T_{e+1}, it is easy to show that T_{e+1} forces the requirement N_{e}. Indeed, if M is a path on T_{e+1}, and φ_{e}^{M} = C is total, then we can compute M from C by enumerating rg(T) and throwing away all strings σ for which φ_{e}^{σ}(n) is incompatible with C. Condition (b) guarantees that the remaining strings are all compatible, while condition (c) guarantees that they will form the full set M, which has arbitrarily long initial segments in rg(T_{e+1}).

For the purpose of constructing T, we will first introduce some terminology. Definition 8.3. (i) An e-splitting k-fan is a set F = {τ_{0}; τ_{1}, …, τ_{k}} of distinct

strings, such that τ_{i} and τ_{j} form an e-split of τ_{0} for every 1 ≤ i < j ≤ k. τ_{0} is the root of F and τ_{1}, …, τ_{k} are the blades of F.

(ii) Two e-splitting fans F_{0}, F_{1} e-split a string σ if their roots e-split σ.

We now define a function f recursively in A. Let σ^{∗} = T_{e}(τ^{∗}) be the first non-root string incompatible with φ_{e}^{A} (this may not be computable in A, but it is only done once, and no uniformity is claimed). Find two e-splitting p(1)-fans F_{0}^{σ^{∗}}, F_{1}^{σ^{∗}} ⊆ rg(T_{e}) which split σ^{∗}, and let f(0) = [F_{0}^{σ^{∗}} ∪F_{1}^{σ^{∗}}], where [·] here denotes a recursive coding of finite sets of strings (not to be confused with the notation for the set of paths on a tree).

Inductively, suppose we have defined

f(n − 1) = [ ⋃_{i<t_{n}, j<2} F_{j}^{σ_{i}}]

where F_{0}^{σ_{i}}, F_{1}^{σ_{i}} ⊆ rg(T_{e}) are e-splitting p(n)-fans which e-split σ_{i} ∈ rg(T_{e}). Find for each blade τ of every fan F_{j}^{σ_{i}}, two p(n + 1)-fans F_{0}^{τ}, F_{1}^{τ} ⊆ rg(T_{e}) which split τ, and let

f(n) = [⋃_{τ,j} F_{j}^{τ}]

This definition can be carried out with oracle A since both T_{e} and p are computable in A, and splitting fans will always be found because of the density of e-splits on T_{e}.

By Definition 8.1, there is a recursive function h such that

∀n ∈ ω (f(n) ∈ W_{h(n)} ∧ |W_{h(n)}| ≤ p(n)).

Now we construct T. First throw into T all strings in {σ^{∗}} ∪ F_{0}^{σ^{∗}} ∪ F_{1}^{σ^{∗}} (that is, let σ^{∗} be the root of T, the two fan roots its successors, and the all the blades as their successors on level 2 of T). Call F_{0}^{σ^{∗}} and F_{1}^{σ^{∗}} accepted fans of level 0. Now simultaneously enumerate all W_{h(n)} for n > 0, and for each element a^{n} = [U] enumerated in W_{h(n)} do the following:

First validation: Check that U is a union of e-splitting k-fans for some fixed k, and that all strings in U agree on even elements. If not, drop a^{n}.

Second validation: Wait until some a^{n−1} is enumerated in W_{h(n−1)} and passes the first and second validation, such that for each blade of a fan given by a^{n−1} there is a distinct pair of fans given by a^{n} which split it. If this happens, then a^{n} passes the second validation, and is said to be extending a^{n−1}.

Now, label the elements of W_{h(n)} as a_{1}^{n}, …, a_{k_{n}}^{n} in order of enumeration, with k_{n} ≤ p(n). For each accepted fan F of level n − 1, given by some a^{n−1}, with blades τ_{1}, …, τ_{r}, and for each 1 ≤ i ≤ r, if a_{i}^{n} exists and extends a^{n−1}, then enumerate in T the two fans given by a_{i}^{n} which split τ_{i} (setting their roots to be successors of τ_{i} in T), and call them accepted fans of level n. This ends the construction of T.

Properties (a),(b) clearly hold. Next we define T_{e+1} by induction as a subtree of T, to ensure property (c). Note that for all n > 0 the set coded by f(n) will pass both validations. Set T_{e+1}(∅) = σ^{∗} and set T_{e+1}(i) to be the root of F_{i}^{σ^{∗}} (i = 0, 1). Suppose we have defined level n > 0 of T_{e+1}, which consists of roots of accepted fans of level n − 1 given by f(n − 1). Given τ on level n, the root of the accepted fan F, there is a blade τ′ of F such that there are two accepted fans F_{0}^{τ′} and F_{1}^{τ′} given by f(n), which e-split τ′ (and hence τ). This is because F is a “true” fan, which has no more than p(n) blades. Let the roots of the fans F_{i}^{τ′} be the successors of τ on level n + 1.

Now, T_{e+1} is a subtree of T since all roots (as well as all blades) of accepted fans appear on T. It is also a subtree of T_{e}, since all roots (as well as all blades) of “true” fans appear on T_{e}. It was constructed from T with knowledge of f, so it is computable in A. It is clearly e-splitting, hence forces P_{e}. Finally, it forces N_{e} and satisfies condition (ii) by choice of σ^{∗}.

Constructing a Non-Join

We give a direct construction of a non-join, with the hope that it may be built upon to produce interesting results (e.g. concerning the class of cuppable degrees).

Lemma 9.1. There are degrees 0 < b < a ≤ 0′′ such that no degree c < a satisfies b ∨ c = a.

Proof. The requirements which we are trying to satisfy are

R_{s}^{0} :  Od(A) ≠ φ_{s}
R_{s}^{1} :  s = ⟨e_{1}, e_{2}⟩ →

(φ_{e_{1}}^{A} is total ∧ φ_{e_{2}}^{φ_{e_{1}}^{A}⊕Od(A)} is total and equal to A → φ_{e_{1}}^{A} ≥_{T} A)

We construct a sequence of recursive uniform binary trees T_{i} such that for all i ∈ ω and binary strings σ we have T_{i+1} ⊆ T_{i} and

|σ| is odd ↔ Od(T_{i}(σ ⌢0)) = Od(T_{i}(σ ⌢1)).

That is, the levels of each tree alternate between agreeing and disagreeing on the odds.

To define T_{0}, let

T_{0}(d_{0}d_{1}d_{2}d_{3} …) = (0d_{0})⌢(d_{1}0)⌢(0d_{2})⌢(d_{3}0)⌢…

for all d_{i} < 2 (the parenthesis are for readability).

At stage 2s, let σ be the first of length 2 such that Od(T_{2s}(σ)) is incompatible with φ_{s}. Let T_{2s+1} = T_{2s}E_{σ}. This tree is in the required form, and satisfies R_{s}^{0}.

At stage 2s + 1, let T = T_{2s+1}, and let e_{1}, e_{2} be such that s = ⟨e_{1}, e_{2}⟩. We construct T′ = T_{2s+2} as follows.

(i) If there is some σ and x such that T (σ) forces φ_{e_{1}}^{A}(x) ↑ on T, let σ be the first such of even length, and let T′ = T · E_{σ}.

(ii) Otherwise, if there is some σ and x such that T (σ) forces φ_{e_{2}}^{φ_{e_{1}}^{A}⊕Od(A)}(x)↑ on T, let σ be the first such of even length, and let T′ = T · E_{σ}.

(iii) Otherwise, if there is some σ and x such that

φ_{e_{2}}^{φ_{e_{1}}^{T (σ)}⊕Od(T (σ))}(x)↓≠ T (σ)(x)

let σ be the first such of even length, and let T′ = T · E_{σ}.

(iv) Otherwise, we first prove

Proposition 9.2. Every σ has extensions σ_{0}, σ_{1} such that T (σ_{0}), T (σ_{1}) agree on the odds and e_{1}-split.

Proof. Assume wlog that |σ| is odd, and let x be the first on which T (σ ⌢0) and T (σ ⌢1) disagree (note that x is even, since these strings must agree on the odds). Since cases (i),(ii) do not hold, there is some σ_{0} ⊇ σ ⌢0 such that φ_{e_{2}}^{φ_{e_{1}}^{T (σ_{0})}⊕Od(T (σ_{0}))}(x) ↓. Let σ_{1}^{∗} = σ_{0}[σ ⌢ 0 → σ ⌢ 1]. Similarly, there is some σ_{1} ⊇ σ_{1}^{∗} such that φ_{e_{2}}^{φ_{e_{1}}^{T (σ_{1})}⊕Od(T (σ_{1}))}(x)↓. Now, T (σ_{0}) and T (σ_{1}) agree on the odds by uniformity of T and because Od(T (σ ⌢0)) = Od(T (σ ⌢1)). On the other hand, we must have

φ_{e_{2}}^{φ_{e_{1}}^{T (σ_{i})}⊕Od(T (σ_{i}))}(x)↓= T (σ_{i})(x)

for both i = 0, 1, since case (iii) fails. But T (σ_{0})(x) ≠ T (σ_{1})(x) by choice of x, and so the oracles must disagree. Since Od(T (σ_{0})) = Od(T (σ_{0})), it must be that φ_{e_{1}}^{T (σ_{0})} is incompatible with φ_{e_{1}}^{T (σ_{1})}, hence T (σ_{0}) and T (σ_{1}) form an e_{1}-split.

The proposition implies that we can construct an e_{1}-splitting subtree of T in the required form. The construction is by induction on levels, and is similar in nature to the one carried out in case (iv) of the proof of Theorem 6.2.1. Start with T′(∅) = T (∅). Suppose we have defined level n of T′, and let τ_{i} = T′(σ_{i}) be the strings on that level (for 1 ≤ i ≤ r). We define by induction on i ≤ r strings ρ_{0,i}, ρ_{1,i}, starting with ρ_{j,0} = ∅ for j = 0, 1. Having defined ρ_{j,i−1}, find a e_{1}-split χ_{0}, χ_{1} ⊇ τ_{i} ⌢ ρ_{0,i−1} on T, such that Od(χ_{0}) = Od(χ_{1}) (the existence of such is guaranteed by the proposition). Let x be the first such that φ_{e_{1}}^{χ_{0}}(x) ↓≠ φ_{e_{1}}^{χ_{1}}(x) ↓, and let χ_{2} ⊇ χ_{0}[τ_{i} ⌢ ρ_{0,i−1} → τ_{i} ⌢ ρ_{1,i−1}] on T such that φ_{e_{1}}^{χ_{2}}(x) ↓ (guaranteed to exist since case (i) fails). Let k < 2 be the first such that φ_{e_{1}}^{χ_{k}}(x) ≠ φ_{e_{1}}^{χ_{2}}(x). Now let ρ_{i,0} and ρ_{i,1} be extensions of equal length of ρ_{i,0}^{∗} = χ_{k} − τ_{i} and ρ_{i,1}^{∗} = χ_{2} − τ_{i} (resp.), which agree on the odds, by copying the extension from the longer to the shorter. For instance, if ρ_{i,0}^{∗} is the longer, let ρ_{i,0} = ρ_{i,0}^{∗} and let ρ_{i,1} = ρ_{i,0}^{∗}[(ρ_{i,0}^{∗} ↾|ρ_{i,1}^{∗}|) → ρ_{i,1}^{∗}]. Note that Od(ρ_{i,0}) = Od(ρ_{i,1}). This completes the induction on i. Finally, if n is odd, simply let T′(σ_{i} ⌢ k) = τ_{i} ⌢ ρ_{r,k} for all 1 ≤ i ≤ r and k = 0, 1. This is a uniform e_{1}-splitting branching which agrees on the odds. If n is even we need to make the branching disagree on the odds, so let ρ_{0}, ρ_{1} be the first extensions of equal length of ρ_{r,0}, ρ_{r,1} (resp.), which disagree on the odds, such that τ_{1} ⌢ρ_{k} ∈ rg(T) for k < 2 (such exist since the branching on every even level of T disagrees on the odds). Let T′(σ_{i} ⌢ k) = τ_{i} ⌢ ρ_{k} for all 1 ≤ i ≤ r and k < 2. Thus level n + 1 of T′ is constructed, and the induction on n is complete. Note that T_{2s+2} = T′ is an e_{1}-splitting tree, and therefore it forces requirement R_{s}^{1} by Lemma 6.1.5.

In each of the cases, T_{2s+2} is a tree of the required form which forces R_{s}^{1}. Now let A be the unique path lying on all T_{i}, and let B = Od(A). Since the requirements R_{s}^{0} are satisfied, B is not recursive. Since the requirements R_{s}^{1} are satisfied, if X ≤_{T} A and X ⊕ B ≥_{T} A then X ≥_{T} A. It follows that a = deg(A) and b = deg(B) are as stated in the lemma.

Bibliography

[Coo73] S. B. Cooper. Minimal degrees and the jump operator. J. Symbolic Logic, 38:249–271, 1973.

[DJS96a] Rod Downey, Carl G. Jockusch, and Michael Stob. Array nonrecursive degrees and genericity. In Computability, enumerability, unsolvability, volume 224 of London Math. Soc. Lecture Note Ser., pages 93–104. Cambridge Univ. Press, Cambridge, 1996.

[DJS96b] Rod Downey, Carl G. Jockusch, and Michael Stob. Array nonrecursive degrees and genericity. In Computability, enumerability, unsolvability, volume 224 of London Math. Soc. Lecture Note Ser., pages 93–104. Cambridge Univ. Press, Cambridge, 1996.

[DLS96] Rodney G. Downey, Steffen Lempp, and Richard A. Shore. Jumps of minimal degrees below 0′. J. London Math. Soc. (2), 54(3):417–439, 1996.

[Eps79] Richard L. Epstein. Degrees of unsolvability: structure and theory, volume 759 of Lecture Notes in Mathematics. Springer, Berlin, 1979.

[Fri57] Richard Friedberg. A criterion for completeness of degrees of unsolvability. J. Symb. Logic, 22:159–160, 1957.

[Ish99] Shamil Ishmukhametov. Weak recursive degrees and a problem of Spector. In Recursion theory and complexity (Kazan, 1997), volume 2 of de Gruyter Ser. Log. Appl., pages 81–87. de Gruyter, Berlin, 1999.

[KHNS] Bjørn Kjos-Hanssen, André Nies, and Frank Stephan. On a question of Ambos-Spies and Kučera. In preparation.

[Lac68] A. H. Lachlan. Distributive initial segments of the degrees of unsolvability. Z. Math. Logik Grundlagen Math., 14:457–472, 1968.

[Ler83] Manuel Lerman. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. Local and global theory.

[Sac63] Gerald E. Sacks. Recursive enumerability and the jump operator. Trans. Amer. Math. Soc., 108:223–239, 1963.

[Sho78] Richard A. Shore. On the ∀∃-sentences of α-recursion theory. In Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977), volume 94 of Stud. Logic Foundations Math., pages 331–353. North-Holland, Amsterdam, 1978.

[Sho88] Richard A. Shore. A noninversion theorem for the jump operator. Ann. Pure Appl. Logic, 40(3):277–303, 1988.

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

[Spe56] Clifford Spector. On degrees of recursive unsolvability. Ann. of Math. (2), 64:581–592, 1956.

[SS99] Richard A. Shore and Theodore A. Slaman. Defining the Turing jump. Math. Res. Lett., 6(5-6):711–722, 1999.