Jumps of Σ_{2}^{0}-high e-degrees and properly Σ_{2}^{0} e-degrees

Richard Shore^{∗} Andrea Sorbi^{†}

Abstract

We show that the Σ_{2}^{0} high e-degrees coincide with the high edegrees. We also show that not every properly Σ_{2}^{0} e-degree is high.

1 Introduction

Enumeration reducibility is the notion of relative enumerability of sets: a set A is enumeration reducible (or simply e-reducible) to a set B, in symbols, A ≤_{e} B, if there is an effective procedure for enumerating A given any enumeration of B. Formally, we define A ≤_{e} B if there is some computably enumerable set Φ (called in this context an enumeration operator or simply an e-operator) such that

A = {x : (∃ finite D)[⟨x, D⟩ ∈ Φ & D ⊆ B]}

(throughout the paper we identify finite sets with their canonical indices). We denote by ≡_{e} the equivalence relation generated by the preordering relation ≤_{e} and deg_{e}(A) denotes the equivalence class (or the e-degree) of A. The partially ordered structure of the e-degrees is denoted by 𝔇_{e}; its partial ordering is denoted by ≤. 𝔇_{e} is, in fact, an upper semilattice with least element 0_{e}.

One of the most interesting features of the e-degrees is that they extend the structure 𝔇_{T} of the Turing degrees ([Med55] and [Rog67]). Indeed if we define ι : 𝔇_{T} → 𝔇_{e} by ι(deg_{T} (A)) = deg_{e}(χ_{A}) (where deg_{T} (A) is the Turing degree of the set A and χ_{A} denotes the characteristic function of A) then ι is the desired embedding. (In fact, it preserves joins and least element.) The verification that ι is well defined relies on the following lemma:

∗Department of Mathematics, Cornell University, Ithaca NY 14853, USA. The frist authro was partially supported by NSF Grant DMS-9503503 and a CNR visiting professorship at the University of Turin.

†Department of Mathematics, University of Siena, Italy. The second author was partially supported by the HC&M research network Complexity, Logic and Recursion Theory (COLORET ), contract no. ERBCHRXCT930415; MURST 60%, and CNR-GNSAGA.

During the preparation of part of this paper the second author was visiting at the University of Wisconsin, Madison.

Lemma 1.1 For every total function f and g, we have

f ≤_{T} g ⇔ f ≤_{e} g.

Proof. See e.g. [Rog67, p. 153]. □

One can define (see below) a jump operation ′ on the e-degrees, and therefore introduce the notions of a low e-degree (i.e. an element of the class L_{1} = {a ≤ 0′_{e} : a′ = 0′_{e}}); and that of a high e-degree (i.e. an element of H_{1} = {a ≤ 0′_{e} : a′ = 0e^{′′}}). Moreover, since ι preserves jump, we have that low Turing degrees are mapped to low e-degrees and high Turing degrees are mapped to high e-degrees.

A nice, useful characterization of the class L_{1} of the low e-degrees is given in [MC85]: a ∈ L_{1} if and only if a contains a set A such that, for every B ≤_{e} A, B ∈ Δ_{2}^{0} . Thus a and all the e-degrees below a consist entirely of Δ_{2}^{0} sets. In this paper, we characterize the class H_{1} of high e-degrees by a result analogous to the one characterizing the high Turing degrees as those containing a set with an approximation whose associated computation function dominates every total recursive function (Theorem 2.1). The relevant definitions of a Σ_{2}^{0} approximation and a computation function are given below. The e-degrees of sets with such approximations are known as the Σ_{2}^{0}- high e-degrees (Definition 1.7). This characterization answers Question 7.3 of [Coo90].

Since the e-degrees below 0′_{e} are exactly the e-degrees consisting of Σ_{2}^{0} sets, in view of the above cited characterization of the low e-degrees, a natural question to ask is where an e-degree a ≤ 0′_{e} which contains no Δ_{2}^{0} set (such an e-degree is called a properly Σ_{2}^{0} e-degree) lies in the low/high hierarchy. A natural conjecture might be that the properly Σ_{2}^{0} e-degrees are all in H_{1}. Cooper and Copestake ([CC88]) show that there exist properly Σ_{2}^{0} e-degrees that are Σ_{2}^{0}-high, and thus lie in H_{1} by Theorem 2.1. However, in Theorem 3.1 we show that the properly Σ_{2}^{0} e-degrees are not contained in H_{1}.

Our notations and terminology are mostly based on [Soa87]. The reader is referred to [Coo90] for an introduction and extensive bibliography on enumeration reducibility. We will be mostly working with Σ_{2}^{0} sets. We recall that a Σ_{2}^{0} approximation to a Σ_{2}^{0} set A is computable sequence of computable sets {A^{s} : s ∈ A^{s}} such that A = {x : (∃t)(∀s ≥ t)[x ∈ A^{s}]}. See [LS92] for an introduction to Σ_{2}^{0} approximations, and for a proof that every Σ_{2}^{0} set has a good Σ_{2}^{0} approximation {A^{s} : s ∈ A^{s}}, i.e. a computable sequence of computable (in fact, finite) sets such that {s : A^{s} ⊆ A} is infinite.

Let X be any set of natural numbers; if x is a number, then X^{[x]} = {z ∈ X : (∃y)[z = ⟨x, y⟩]}, and X ↾ x = {y ∈ X : y < x}. If σ is a string and x < |σ| (where |σ| denotes the length of σ), then σ ↾ x denotes the initial segment of σ having length x; likewise, if f is a function, then f ↾ x denotes the initial segment of f having length x.

Let {φ_{i}}_{i∈ω} be the standard enumeration of all partial computable functions with corresponding enumerations {W_{i}}_{i∈ω} and {Φ_{i}}_{i∈ω} of the computably enumerable sets and the enumeration operators, respectively. Let us fix, as in [Soa87, p. 16], computable approximations {φ_{i,s}}_{i,s∈ω} to the partial computable functions. Without loss of generality, we may assume that if φ_{i,s}(x) ↓ then φ_{i,s}(x) < s. Correspondingly, we get computable finite approximations {W_{i,s}}_{i,s∈ω} and {Φ_{i,s}}_{i,s∈ω} to the computably enumerable sets and the enumeration operators, respectively.

Let

K^{A} = {x : x ∈ Φ_{x}^{A}}.

Lemma 1.2 [McE85] Let A, B be sets; then

A ≤_{e} B ⇔ A ≤_{1} K^{B} ⇔ K^{A} ≤_{1} K^{B}.

Define the jump of a set A ([McE85]) to be the set J_{e}(A) = χ_{K^{A}}. (Note that we identify functions with their graphs.) Clearly J_{e}(A) ≡_{e} K^{A} ⊕ \overline{K^{A}}. If a is an e-degree, then we can define a′ as deg_{e}(J_{e}(A)) for any A ∈ a since, by the previous lemma,

A ≡_{e} B ⇒ K^{A} ⊕ \overline{K^{A}} ≡_{e} K^{B} ⊕ \overline{K^{B}}

this gives a well defined unary operation on the e-degrees. Moreover, a < a′ for every e-degree a.

The following lemma records two important properties of the jump operation.

Lemma 1.3 [McE85] For every set A,

1. ι((deg_{T} (A))′) = (deg_{e}(A))′;

2. if A is total (i.e. the graph of some total function), then J_{e}(A) ≡_{e} \overline{K^{A}}.

Definition 1.4 A set A is called e-high if A ∈ Σ_{2}^{0} and J_{e}^{(2)}(∅) ≤_{e} J_{e}(A). An e-degree a is called high, if a contains an e-high set (hence a′ = 0′′_{e}).

By Lemma 1.3, the embedding ι preserves highness, i.e. it maps high T-degrees to high e-degrees.

The following is a useful characterization of the e-high sets.

Lemma 1.5 For every set A,

A is e-high ⇔ T ot ≤_{e} J_{e}(A) ⇔ T ot ≤_{T} K^{A}.

Proof. First notice that, by Lemma 1.3, A is e-high if and only if \overline{K\overline{K}} ≤_{e} J_{e}(A). Moreover, A is e-high if and only if, by Lemma 1.3, χ_{K\overline{K}} ≤_{e} χ_{K^{A}}, if and only if, by Lemma 1.1, \overline{K\overline{K}} ≤_{T} K^{A}. On the other hand, \overline{K\overline{K}} ≡_{1} T ot. Indeed, \overline{K\overline{K}} ≤_{1} T ot follows from the fact that T ot is Π_{2}^{0}-complete. To show that T ot ≤_{1} \overline{K\overline{K}} simply observe that \overline{T ot} ∈ Σ_{2}^{0}, hence \overline{T ot} ≤_{e} \overline{K}, and thus, by Lemma 1.2, \overline{T ot} ≤_{1} K\overline{K}.

It follows that A is e-high if and only if T ot ≤_{e} J_{e}(A) if and only if T ot ≤_{T} K^{A}. □

Finally notice the following:

Lemma 1.6 For every total function f, J_{e}(f) ≡_{T} f′.

Proof. Since K^{f} is computably enumerable in f, we have K^{f} ≤_{1} f′, and so \overline{K^{f}} ≤_{T} f′. On the other hand, f′ is computably enumerable in f, hence, by the totality of f, f′ ≤_{e} f, and thus f′ ≤_{1} K^{f}, by Lemma 1.2, which shows that f′ ≤_{1} J_{e}(f).

Hence we conclude that J_{e}(f) ≡_{T} f′. □

McEvoy ([McE85]) defines the notion of a Σ_{2}^{0}-high e-degree:

Definition 1.7 A Σ_{2}^{0}-high approximation {A^{s}}_{s∈ω} to a set A is a Σ_{2}^{0} approximation such that the function

c(x) = μs(s > x & A^{s} ↾x ⊆ A)

(called the computation function for A relative to the given approximation) is total and dominates every computable function. A set A is called Σ_{2}^{0}-high, if it has a Σ_{2}^{0}-high approximation. Finally an e-degree is said to be Σ_{2}^{0}-high, if it contains a Σ_{2}^{0}-high set.

Using Lemma 1.3 (1), it is shown in [McE85] that if a ≤ 0′_{e} is total (hence a degree of the form ι(b), for some Turing degree b ≤_{T} 0′_{T}), and a is high, then a is Σ_{2}^{0}-high. On the other hand, the class of Σ_{2}^{0}-high e-degrees properly extends the class of all high total e-degrees (in fact, there exist quasi-minimal Σ_{2}^{0}-high e-degrees, [McE85]).

In the next section we show that the high e-degrees and the Σ_{2}^{0}-high edegrees coincide. This answers Question 7.3 of [Coo90].

2 The Σ_{2}^{0}-high e-degrees coincide with the high e-degrees

Theorem 2.1 An e-degree a is Σ_{2}^{0}-high if and only if a is high.

Proof. (⇒) Let A be Σ_{2}^{0}-high; let {A^{s}}_{s∈ω} be a Σ_{2}^{0}-high approximation to A, and let c be the computation function for A relative to this approximation.

By Lemma 1.5 it is enough to show that T ot ≤_{e} J_{e}(A). We claim that, for every i,

i ∈ T ot ⇔ (∀y)[φ_{i}(y) ↓]
⇔ (∃x)(∃s)[(∀y < x)φ_{i,s}(y) ↓ &
(∀y ≥ x)(∀t > y)[A^{t} ↾ y ⊆ A ⇒ φ_{i,t}(y) ↓]].

Indeed, if φ_{i} is total, then the function

φ̂_{i}(x) = μs( φ_{i,s}(x) ↓)

is a total computable function, and thus dominated by c. Let x be such that c(y) > φ̂_{i}(y) for every y ≥ x; then

(∀y ≥ x)(∀t > y)[A^{t} ↾ y ⊆ A ⇒ φ_{i,t}(y) ↓].

This establishes the left-to-right implication in the claimed equivalence. The right-to-left implication is trivial.

Now let

B = {⟨i, x⟩ : (∃y ≥ x)(∃t > y)[A^{t} ↾ y ⊆ A & φ_{i,t}(y) ↑].

Clearly B ≤_{e} A. Hence, by Lemma 1.2, B ≤_{1} K^{A}, via, say, the computable function h.

Then

i ∈ T ot ⇔ (∃x)(∃s)[(∀y < x)φ_{i,s}(y) ↓ & ⟨i, x⟩ ∉ B]
⇔ (∃x)(∃s)[(∀y < x)φ_{i,s}(y) ↓ & h(⟨i, x⟩) ∈ \overline{K^{A}}].

It follows that T ot ≤_{e} \overline{K^{A}}, hence T ot ≤_{e} J_{e}(A), as desired.

(⇐) Assume that A is e-high. Then, by Lemma 1.5, we have that T ot ≤_{T} K^{A}. Let Z = K^{A} and let {Z^{s}}_{s∈ω} be a good Σ_{2}^{0}-approximation to K^{A}. Let ψ be some Turing functional such that T ot = ψ^{Z}.

We now define an enumeration operator Θ by stages, and show that Θ^{Z} is Σ_{2}^{0}-high. Since the Σ_{2}^{0}-high e-degrees are closed upwards in Σ_{2}^{0}-e-degrees (see [BCS97]), it follows that deg_{e}(A) is Σ_{2}^{0}-high as well. Construction:

Stage 0: Let Θ_{0} = ∅.

Stage s + 1: For every i ≤ s, we distinguish the following two cases:

(a) if ψ_{s}^{Z^{s}}(i) = 0, then for every x ≤ s, we enumerate the axiom

⟨⟨i, x⟩, Z^{s}⟩ ∈ Θ_{s+1};

(b) otherwise, do nothing.

Let Θ^{s+1} consist of Θ^{s} plus all the axioms enumerated at stage s + 1 and let Θ = ⋃_{s∈ω} Θ_{s}. We now prove that Θ is the desired enumeration operator by verifying a series of claims.

Verifications: Claim 1 For every number i,

i ∈ T ot ⇒ (Θ^{Z})^{[i]} finite;

i ∉ T ot ⇒ (Θ^{Z})^{[i]} = ω^{[i]}.

Proof. If i ∈ T ot then at all sufficiently large good stages of the approximation {Z^{s}}_{s∈ω} we do nothing on behalf of i (i.e. case (b) of the definition of Θ applies to i). To see this, assume that i ∈ T ot, and let σ ⊂ χ_{Z} be such that ψ^{σ}(i) = 1. Let t_{0} be such that

(∀x < |σ|)[σ = 1 ⇒ (∀s ≥ t_{0})[x ∈ Z^{s}]].

Then

(∀s ≥ t_{0})[s is good ⇒ ψ_{s}^{Z^{s}}(i) = 1].

It follows that at stages s ≥ t_{0}, if (a) holds then s is not good, hence Θ_{s}^{Z^{s}} ⊈ Θ^{Z}. Therefore (Θ^{Z})^{[i]} is finite.

If i ∉ T ot, then at all sufficiently large good stages, case (a) of the definition of Θ applies to i. Indeed, if i ∉ T ot, then ψ^{Z}(i) = 0. One thus argues as in the preceding case, but starting with a string σ ⊂ χ_{Z} such that ψ^{σ}(i) = 0.

Since Θ_{s}^{Z_{s}} ⊆ Θ^{Z}, for all good stages s, it follows in this case that (Θ^{Z})^{[i]} = ω^{[i]}. □

Now let Y = Θ^{Z}. We want to show that Y has a Σ_{2}^{0}-high approximation {Ŷ^{s}}_{s∈ω}. Let {Y^{s}}_{s∈ω} be any good Σ_{2}^{0}-approximation to Y. Given a partial function φ and a number u, define φ ↾ u ↓, if φ(v) ↓ for all v < u.

Define

⟨i, x⟩ ∈ Ŷ^{s} ⇔ [⟨i, x⟩ ∈ Y^{s} ∨ φ_{i,s} ↾ ⟨i, x + 1⟩ ↑].

Claim 2 {Ŷ^{s}}_{s∈ω} is a Σ_{2}^{0}-approximation to Y. Proof. Let Ŷ = {y : (∃t)(∀s ≥ t)[y ∈ Ŷ^{s}]}. If i ∉ T ot then Y^{[i]} = ω^{[i]} = Ŷ^{[i]}. On the other hand, assume that i ∈ T ot. If ⟨i, x⟩ ∈ Y, then clearly ⟨i, x⟩ ∈ Ŷ. If ⟨i, x⟩ ∉ Y, then at all sufficiently large stages φ_{i,s} ↾ ⟨i, x + 1⟩ ↓ and so when ⟨i, x⟩ ∉ Y^{s}, we have that ⟨i, x⟩ ∉ Ŷ^{s}. □

Next, let c be the computation function for Y relative to the Σ_{2}^{0} approximation {Ŷ^{s}}_{s∈ω}. The following claim completes the proof of the Theorem.

Claim 3 The function c is total and dominates all total computable functions. Proof. Let us first show that c is total. To this end, let z ∈ ω be given. Let t > z be a stage such that

(∀⟨i, x⟩ < z)[φ_{i} ↾ ⟨i, x + 1⟩ ↓⇔ φ_{i,t} ↾ ⟨i, x + 1⟩ ↓].

Then if s ≥ t is a good stage of the enumeration {Y^{s}}_{s∈ω}, we have that Ŷ^{s} ↾ z ⊆ Y. Therefore c(z) is defined.

Now consider any total φ_{i}. Let x be such that ⟨i, y⟩ ∉ Y, for every y ≥ x. Let z ≥ ⟨i, x⟩, and let y be the least number such that ⟨i, y⟩ ≤ z < ⟨i, y + 1⟩. Let s be the least stage such that φ_{i,s}(z) ↓, hence φ_{i,t} ↾ ⟨i, y + 1⟩ ↑ for every t < s. Then ⟨i, y⟩ ∈ Ŷ^{t}, for every t < s. Therefore φ_{i}(z) < s ≤ c(z). □

3 Jumps of properly Σ_{2}^{0} e-degrees

A Σ_{2}^{0} e-degree a is called properly Σ_{2}^{0} ([CC88]) if a contains no Δ_{2}^{0} set. Copestake and Cooper, [CC88, Theorem 1], show that there exist e-degrees that are properly Σ_{2}^{0} and Σ_{2}^{0}-high. Since every high computably enumerable Turing degree corresponds, under the embedding ι, to a high e-degree, it follows that not every Σ_{2}^{0}-high e-degree is properly Σ_{2}^{0}-high. (A trivial counterexample is 0′_{e} = deg_{e}(\overline{K})). It is shown in [MC85] that deg_{e}(A) is low if and only if B ∈ Δ_{2}^{0}, for every B ≤_{e} A. This characterization of the low e-degrees seems to suggest the possibility that the properly Σ_{2}^{0} e-degrees are all high. We show in this section that this is not the case.

Theorem 3.1 Let C be such that C is computably enumerable in ∅′, ∅′ ≤_{T} C <_{T} ∅′′ and C′ ≡_{T} ∅′′′. Then there exists a set A of properly Σ_{2}^{0} e-degree, such that J_{e}(A) ≤_{e} χ_{C}.

Corollary 3.2 There exist properly Σ_{2}^{0} e-degrees that are not high.

Proof. Let C and A be as in the previous theorem. If A were e-high, then J_{e}^{(2)}(∅) ≤_{e} χ_{C}, from which, by totality, J_{e}^{(2)}(∅) ≤_{T} χ_{C}; but J_{e}^{(2)}(∅) ≡_{T} ∅′′, by Lemma 1.6. Hence ∅′′ ≤_{T} C, contradiction. □

3.1 Proof of Theorem 3.1

Let C satisfy the hypotheses of the theorem; let C = W^{K}, for some computably enumerable set W. For every t, let κ_{t} = χ_{K^{t}} ↾ k(t), where k is some 1 − 1 computable function such that K = range(k) and K^{t} = {k(s)|s ≤ t}. Define a Σ_{2}^{0} approximation {C^{t}}_{t∈ω} to C by letting

C^{t} = W_{t}^{κ_{t}},

As C′ ≡_{T} K′′, there is an f ≤_{T} C that dominates all Δ_{2}^{0} total functions (see e.g. [Ler83, p. 85]). Let f = Ψ^{C}, for some Turing functional Ψ, be such a function.

We need the following lemma:

Lemma 3.3 There exists a computable sequence {B_{i}^{s}}_{i,s∈ω} of finite sets such that, if

B_{i} = {x : (∃t)(∀s ≥ t)[x ∈ B_{i}^{s}]}

then

1. for every B ∈ Δ_{2}^{0}, there is an i such that B =^{∗} B_{i} and, for almost all x, lim_{s} B_{i}^{s}(x) exists;

2. the relation x ∈ B_{i} (as one of x and i) is computable in C.

Proof. Given u and X, with X = K, or X = K^{v} for some v ≥ u, we say that u is X-true if κ_{u} ⊆ χ_{X}. We will use the fact that for every B ∈ Δ_{2}^{0} there exists some i such that χ_{B} = φ_{i}^{K}. Roughly speaking, we will have x ∈ B_{i}^{s} if there exists some K^{s}-true stage t < w, with φ_{i,t}^{κ_{t}}(x) = 1, where w is the least K^{s}-true stage such that Ψ_{w}^{σ}(x) ↓, for some σ ⊂ χ_{C}. Then we use the fact that Ψ^{C} dominates all Δ_{2}^{0} functions to verify that, for all but finitely many x, there exists a K-true stage t such that φ_{i,t}^{κ_{t}}(x) = 1 and t < Ψ^{C}(x) < w. The main difficulty here is that one can not find, in a computable way, the right w at s. For every i, x, s, we will therefore define the values of a finite set B_{i}^{s} ⊆ ω, a finite set L(x, s) ⊆ ω × 2^{<ω} and a linear ordering <_{x,s} on L(x, s). We “assign preconditions” to elements of ω × 2^{<ω} subject to the following rules: L(x, s) may contain only pairs ⟨r, ρ⟩ with preconditions which have been satisfied at some stage u ≤ s. At stage s, we will choose the <_{x,s}-first element ⟨r, ρ⟩ of L(x, s). We will argue that infinitely many times we choose the correct ⟨w, σ⟩ and we eventually choose only pairs ⟨r, ρ⟩ with r ≥ w.

Let i, x be given. The formal definitions are given by induction on s.

Stage 0: Define B_{i}^{0} = ∅ and L(x, 0) =<_{x,0}= ∅. No ⟨r, ρ⟩ has a precondition at 0.

Stage s + 1: If x ≥ s + 1 then x ∉ B_{i}^{s+1}; otherwise, we distinguish two cases:

• if L(x, s) = ∅, then

x ∈ B_{i}^{s+1} ⇔ x ∈ B_{i}^{s};

• otherwise, let ⟨w, σ⟩ be the <_{x,s}-least element of L(x, s). Then,

(a) if there is no t < w such that t is K^{s+1}-true, then x ∉ B_{i}^{s+1};

(b) otherwise, for the least such t, x ∈ B_{i}^{s+1} if and only if φ_{i,t}^{κ_{t}}(x) = 1.

In the latter case, i.e. when L(x, s) ≠ ∅, we extract ⟨w, σ⟩ from L(x, s+1) and cancel the related precondition. Hence ⟨w, σ⟩ has no precondition at any stage v ≥ s + 1 prior to the smallest stage v′ > s + 1 (if any) at which we again assign a precondition to ⟨w, σ⟩.

We assign a precondition to each pair ⟨r, ρ⟩ such that

1. r is K^{s+1}-true;

2. Ψ_{r}^{ρ}(x) ↓;

3. ρ ⊆ χ_{C^{r}};

4. ρ of minimal length, satisfying 2. and 3. (i.e. if Ψ_{r}^{ρ′}(x) ↓ and ρ′ ⊆ χ_{C^{r}} then ρ ⊆ ρ′; notice that |ρ′| < r, for each such ρ′, by the definition of the use function as in [Soa87, p. 49]);

5. ⟨r, ρ⟩ does not have a precondition at s + 1.

At any v > s + 1, we say that this precondition becomes satisfied at v if

(∀i < |ρ|)[ρ(i) = 0 ⇒ (∃t)[s + 1 ≤ t ≤ v & i ∉ C^{t}]].

Let

L(x, s + 1) = (L(x, s) − {⟨w, σ⟩}) ∪ {⟨r, ρ⟩ : ⟨r, ρ⟩ has a precondition that becomes satisfied at s + 1}.

Finally, we order L(x, s + 1) as follows: if ⟨r, ρ⟩, ⟨r′, ρ′⟩ ∈ L(x, s + 1), then let ⟨r, ρ⟩ <_{x,s+1} ⟨r′, ρ′⟩ if either

1. ⟨r, ρ⟩, ⟨r′, ρ′⟩ ∈ L(x, s) and ⟨r, ρ⟩ <_{x,s} ⟨r′, ρ′⟩, or

2. ⟨r, ρ⟩ ∈ L(x, s) and ⟨r′, ρ′⟩ ∉ L(x, s), or

3. ⟨r, ρ⟩, ⟨r′, ρ′⟩ ∉ L(x, s) and r < r′.

We now check that the sequence B_{i}^{s} has the desired properties. Claim Let x be given, let σ be the least string such that σ ⊂ χ_{C} and Ψ^{σ}(x) ↓. Let w be the least K-true stage such that Ψ_{w}^{σ}(x) ↓. Then 1. at infinitely many stages s we extract ⟨w, σ⟩ from L(x, s);

2. there exists a stage t_{0} such that we do not extract any pair ⟨r, ρ⟩ with r < w from L(x, s) at any stage s ≥ t_{0}.

Proof. Since σ ⊂ χ_{C}, it is clear that there are infinitely many stages at which the requirements (1-4) for assigning a precondition to ⟨w, σ⟩ are fulfilled. Moreover, once assigned at a stage s_{0}, there exists a stage s_{1} > s_{0} such that the precondition becomes satisfied at s_{1} and so is then in L(x, s) until extracted. As there are only finitely many elements of L(x, s_{1}) before ⟨w, σ⟩ in the ordering and no new ones can later be inserted before it ⟨w, σ⟩ is eventually extracted. Hence, there exist infinitely many stages s such that ⟨w, σ⟩ ∈ L(x, s) and we extract ⟨w, σ⟩ from L(x, s) at infinitely many stages.

Let t < w, and assume for a contradiction that at infinitely many stages s, we extract ⟨t, ρ_{s}⟩, for some string ρ_{s}. Thus |ρ_{s}| < t by the definition of the use function, since Ψ_{t}^{ρ_{s}}(x) ↓. Then there exist a ρ, with |ρ| < t, and infinitely many stages u_{s} at which we assign a precondition to ⟨t, ρ⟩ which becomes satisfied at some stage v_{s} ≤ s and ⟨t, ρ⟩ ∈ L(x, v) for every v such that v_{s} ≤ v ≤ s. Then t is K-true. Let t_{0} be a stage such that

(∀s ≥ t_{0})(∀i < t)[i ∈ C ⇒ i ∈ C^{s}].

By the minimality of σ and w, and since C^{t} ⊆ C and t is K-true, it follows that there exists some i < |ρ| < t such that i ∈ C and ρ(i) = 0. But no pair ⟨r, ρ⟩ with ρ(i) = 0, for some i < |ρ| such that χ_{C}(i) = 1, can have a precondition assigned to ⟨r, ρ⟩ at some stage u ≥ t_{0} which becomes later satisfied. □

We now conclude the proof of the lemma. Let B ∈ Δ_{2}^{0}, and let i be such that χ_{B} = φ_{i}^{K}. Let

t(x) = min{t : t is K-true and φ_{i,t}^{κ_{t}}(x) ↓}.

Then t is total and so a Δ_{2}^{0} function. It follows that there exists some number x_{0} such that f(x) > t(x), for all x ≥ x_{0}.

Given x ≥ x_{0}, let w and σ be as in the previous claim (for x). Then t(x) < f(x) < w (since f(x) = Ψ_{w}^{σ}(x)). Moreover, if t_{0} is as in the proof of the previous claim, then, for every pair ⟨r, ρ⟩ such that ⟨r, ρ⟩ is extracted from L(x, s) at any stage s ≥ t_{0}, we have t(x) ≤ r. Hence for all x ≥ x_{0}, χ_{B_{i}}(x) = φ_{i}^{K}(x).

Since f(x), ψ(x), and w can be computed by C, we easily conclude that the relation x ∈ B_{i} is computable in C. □

Remark 3.4 Note that if t(x) ≥ w, then lim_{s} B_{i}^{s}(x) need not exist, but, in any case, x ∉ B_{i}, since at every large enough stage at which we extract ⟨w, σ⟩ from L(x, s) we have x ∉ B_{i}^{s}.

We now go back to the proof of the theorem. We will build a Σ_{2}^{0} set A such that, for every Δ_{2}^{0} set B, A ≢_{e} B, and K^{A} ≤_{T} C. This implies that deg_{e}(A) is properly Σ_{2}^{0} and, by Lemma 1.1, J_{e}(A) ≤_{e} χ_{C}.

3.2 The strategies

The properly Σ_{2}^{0}-strategy. Let {Φ_{e}, Ψ_{e}}_{e∈ω} be some effective listing of all pairs of e-operators. To make A of properly Σ_{2}^{0} e-degree, it is enough to satisfy the following requirements, for every e, i ∈ ω:

P_{e,i} : A = Φ_{e}^{B_{i}} & B_{i} = Ψ_{e}^{A} ⇒ (∃^{∞}x)[lim_{s} B_{i}^{s}(x) ↑]

where {B_{i}}_{i∈ω} and {B_{i}^{s}}_{i,s∈ω} are as given in Lemma 3.3.

Indeed, if we satisfy these requirements for every e, i, then deg_{e}(A) is properly Σ_{2}^{0}. Suppose, for the sake of a contradiction, that A ≡_{e} B and B ∈ Δ_{2}^{0}. Then, by the previous lemma, A = Φ_{e}^{B_{i}} and B_{i} = Ψ_{e}^{A} for some e, i, with B =^{∗} B_{i} and so lim_{s} B_{i}^{s}(x) does not exist for infinitely many x for the desired contradiction, since lim_{s} B_{i}^{s}(x) exists for almost all x.

The strategy to meet P_{e,i} is a slight modification of the canonical properly Σ_{2}^{0} strategy as given in [CC88], and described as follows:

(a) appoint a witness x and let x ∈ A;

(w_{1}) wait for finite sets D, E such that x ∈ Φ_{e}^{D} and D ⊆ Ψ_{e}^{E};

(b) fix E − {x} ⊆ A;

(w_{2}) wait for D ⊆ B_{i};

(w_{3}) let x ∉ A, wait for D ⊈ B_{i};

(ℓ) let x ∈ A; go back to (w_{2}).

A triple x, D, E as above is called a follower of P_{e,i}.

As described in [CC88, Theorem 1], for a given follower x, D, E this strategy may have the following outcomes: (w_{1}) yields x ∈ A−Φ_{e}^{B_{i}} or y ∈ B_{i} −Ψ_{e}^{A} for some y; (w_{2}) corresponds to the case D ⊆ Ψ^{A}, D ⊈ B_{i}; (w_{3}) corresponds to the case x ∈ Φ^{B_{i}}−A; finally, the infinitary outcome ℓ entails that lim_{s} B_{i}^{s}(y) does not exist for some y ∈ D.

The subrequirements P_{e,i,j}. It follows by the analysis of the outcomes of the previous strategy that if B_{i}^{s}(x) does have limit on every x ∈ D, then A ≠ Φ_{e}^{B_{i}} or B_{i} ≠ Ψ_{e}^{A}. The only complication here (see Remark 3.4) is that there might exist finitely many numbers x such that lim_{s} B_{i}^{s}(x) does not exist, thus, for some y ∈ D, lim_{s} B_{i}^{s}(y) need not exist. We cope with this difficulty by attacking P_{e,i} through infinitely many subrequirements P_{e,i,j}, with j ∈ ω. The strategy for P_{e,i,j} consists in looking for a follower x, D, E such that D ↾ j = B_{i} ↾ j : thus, for almost all j, if we appoint a follower x, D, E as before, we are bound to conclude that B_{i}^{s}(y) exists on every y ∈ D. Thus P_{e,i} is satisfied through some subrequirement P_{e,i,j} (in fact cofinitely many such subrequirements). Before acting, the subrequirement P_{e,i,j} must therefore be provided with some knowledge of what numbers x < j are in fact in B_{i}. This information is coded in the first component, h(σ, s), of the outcome of the node corresponding to P_{e,i,j} in the tree of outcomes.

The strategy for K^{A} ≤_{T} C. For every i, we will look for a finite set D such that i ∈ Φ_{i}^{D}. If such a D exists then we let D ⊆ A. Notice that we can determine computably in ∅′ and, thus, in C, whether or not such a finite set exists.

3.3 The tree of outcomes

For notation and terminology for strings and trees, the reader is referred to [Soa87]. The tree of outcomes is the smallest set T of strings σ such that

1. if |σ| is even then σ (h, r) ∈ T, for every h ∈ ω and r ∈ {0, 1};

2. if |σ| is odd then σ r ∈ T, for every r ∈ {0, 1}.

The strings of even length are assigned to the (sub)requirements P_{e,i,j}, according to some fixed priority listing. The first component, h(σ, s), of the outcome of σ at stage s will be an assessment as to which numbers x < j are in fact in B_{i}: at stage s + 1, h(σ, s) will be chosen to be the first element of a list L(σ, s) of numbers. Each element h of the list is the canonical index of a finite subset of {x : x < j}. Its position in the list measures how well the set {x : x < j} − B_{i} is approximated by the finite set D_{h}. Having decided on the first component, h, of the outcome at σ, the strategy for P_{e,i,j} is ready to act at σ^{+} = σ h. The outcome 1 at σ^{+} corresponds to (w_{1}) or (w_{2}); the outcome 0 corresponds to (w_{3}) or (ℓ).

The strings of odd length are devoted to guaranteeing that K^{A} ≤_{T} C: if |σ| = 2i + 1 then we have outcome 0 if there exists (modulo higher priority constraints) some finite set D such that i ∈ Φ_{i}^{D}; otherwise we have outcome 1.

Let T̂ = T ∪ {σ h : |σ| even & h ∈ ω}. For σ ∈ T̂, the parameter α(σ, s) is intended to record some finite set which we want to keep in A for the sake of our actions at σ; the parameter ϵ(σ, s) is meant to record some finite set of elements which we want to keep out of A.

The ordering ⪯ of T is determined in the usual way by the ordering of the outcomes given that we define (h, r) < (h′, r′) if

h > h′ or [h = h′ & r < r′].

We extend ⪯ to T̂ in the obvious way.

Finally, let {ξ_{σ}}_{σ∈T̂} be a computable partition of ω into infinite computable sets.

3.4 The construction

The construction proceeds by stages. At stage s we define a finite set A^{s}, a string δ_{s}, and the values of several parameters. Unless otherwise specified, at each stage each parameter retains the same value as at the preceding stage.

Stage 0: Define δ_{0} = ∅. For every σ ∈ T̂, let

α(σ, 0) = ϵ(σ, 0) = L(σ, 0) = ∅.

Let x(σ, 0) and p(σ, h, 0) be undefined for every x, h ∈ ω. Finally, let A^{0} = ∅.

Stage s + 1: Suppose that we have defined δ_{s+1} ↾ n, where n < s + 1: let σ = δ_{s+1}↾ n. Our aim is to define a string σ^{++} which we will be δ_{s+1} ↾n + 1.

|σ| even. Let P_{e,i,j} be the requirement assigned to σ. For simplicity, drop subscripts, and let Φ_{e} = Φ, Ψ_{e} = Ψ and B_{i} = B.

Our first task is to define the first component, h(σ, s + 1), of the outcome. We define h(σ, s+1) to be the least element of L(σ, s) if L(σ, s) ≠ ∅, otherwise h(σ, s + 1) = 0. Then we cancel the precondition for h(σ, s + 1) by letting p(σ, h(σ, s + 1), s + 1) ↑.

To every h such that max D_{h} < j and h does not have a precondition, we assign the precondition p(σ, h, s + 1) which becomes satisfied at some later stage v > s + 1 if, for every x < j and x ∈ D_{h}, there exists u such that s + 1 ≤ u ≤ v and B^{u}(x) = 0.

Define

L(σ, s + 1) = (L(σ, s) − {h(σ, s + 1)}) ∪ {h : h has a precondition that is satisfied at s + 1}

and order L(σ, s + 1) in the usual way: for every h, h′ ∈ L(σ, s + 1), define h <_{σ,s+1} h′ if either 1. h, h′ ∈ L(σ, s) and h <_{σ,s} h′, or

2. h ∈ L(σ, s) and h′ ∉ L(σ, s), or

3. h, h′ ∉ L(σ, s) and h < h′.

Let σ^{+} = σ h(σ, s + 1).

Now we are ready to activate the strategy for P.

Let x = x(σ^{+}, s + 1) be the least number in ξ_{σ^{+}} such that x ∉ α(ρ, s + 1), for every ρ ≺ σ^{+}. Case 1).

(∃D)(∃E)[x ∈ Φ_{s}^{D} & D ∩ D_{h(σ,s+1)} = ∅ & D ⊆ Ψ_{s}^{E}
& E ∩ ⋃{ϵ(ρ, s + 1) : ρ ⪯ σ} = ∅].

Choose the least such pair D, E.

In this case, let α(σ^{+}, s + 1) = E − {x}:

1. if D ⊆ B^{s}, then let σ^{++} = σ^{+} 0 and ϵ(σ^{++}, s + 1) = {x};
2. otherwise, let σ^{++} = σ^{+} 1 and α(σ^{++}, s + 1) = {x}.

Case 2). Otherwise, let σ^{++} = σ^{+} 1 and α(σ^{++}, s + 1) = {x}. |σ| odd. Let |σ| = 2i + 1. We distinguish two cases. Case 1). (∃D)[i ∈ Φ_{i}^{D} & D ∩ ⋃{ϵ(ρ, s + 1) : ρ ⪯ σ} = ∅].

In this case, let σ^{++} = σ 0, and let α(σ, s + 1) = D for the least such D.

Case 2). Otherwise, let σ^{++} = σ 1.

Definition of A^{s+1}. At the end of stage s + 1, let A^{s+1} = (A^{s} ∪ ⋃{α(ρ, s + 1) : ρ ⪯ δ_{s+1}}) − ⋃{ϵ(ρ, s + 1) : ρ ⪯ δ_{s+1}}.

3.5 Verification

The verification is based upon the following lemmas.

Lemma 3.5 For every n, σ_{n} = lim inf_{s} δ_{s} ↾n exists.

Proof. Assume by induction that the claim is true of n. The only nontrivial case is when |σ_{n}| is even, where, say, the requirement P_{e,i,j} is assigned to σ_{n}.

Let h be the canonical index of \overline{B_{i}} ↾ j. It is clear that, whenever we assign a precondition to h, then this precondition becomes satisfied at some later stage. Hence, at infinitely many stages s, h ∈ L(σ_{n}, s), and at infinitely many stages t, h = h(σ_{n}, t). On the other hand, it is also clear that for almost all stages s, if h′ ∈ L(σ_{n}, s), then D_{h′} ⊆ D_{h}, hence h′ ≤ h by the usual coding of canonical sets. Therefore it follows that σ_{n+1} = σ_{n} (h, r), for some r ∈ {0, 1}. □

Let f = ⋃_{n∈ω} σ_{n}.

Lemma 3.6 For every τ ∈ T̂, if τ ⊂ f, then α(τ) = lim_{s} α(τ, s), ϵ(τ) = lim_{s} ϵ(τ, s) and x(τ) = lim_{s} x(τ, s) exist. Moreover, if τ = σ_{n} for some n, then the requirement assigned to σ_{n} is satisfied.

Proof. By induction on n, we show that if τ = σ_{n} or τ = σ_{n}^{+}, where σ_{n+1} = σ_{n}^{+} r for some r ∈ {0, 1} (of course σ_{n}^{+} = σ_{n} if n is odd), then lim_{s} α(τ, s), lim_{s} ϵ(τ, s) and lim_{s} x(τ, s) exist, and the requirement assigned to σ_{n} is satisfied. The case n = 0 is trivial as are the existence of the required limits for all nodes to the left of the true path.

Assume that the claim is true of n. For every τ ∈ T̂ such that τ ⪯ σ_{n}, let α(τ) = lim_{s} α(τ, s), ϵ(τ) = lim_{s} ϵ(τ, s) and x(τ) = lim_{s} x(τ, s); and let t be a stage such that, for every s ≥ t and τ ⪯ σ_{n}, α(τ) = α(τ, s), ϵ(τ) = ϵ(τ, s) and x(τ) = x(τ, s).

Suppose first that |σ_{n}| is even, and let P_{e,i,j} be the requirement assigned to σ_{n}. Let σ_{n+1} = σ_{n} (h, i), and let σ_{n}^{+} = σ_{n} h. Then

x(σ_{n}^{+}) = min x ∈ (ξ_{σ_{n}^{+}} − ⋃_{τ⪯σ_{n}} α(τ)).

• If there are no finite sets D, E such that D ∩ D_{h} = ∅, x(σ_{n}^{+}) ∈ Φ_{e}^{D}, E ∩ ⋃_{τ⪯σ_{n}} ϵ(τ) = ∅ and D ⊆ Ψ_{e}^{E}, then σ_{n+1} = σ_{n}^{+} 1,

lim_{s} ϵ(σ_{n}^{+}, s) = lim_{s} ϵ(σ_{n+1}, s) = ∅,

lim_{s} α(σ_{n}^{+}, s) = ∅, lim_{s} α(σ_{n+1}, s) = {x(σ_{n}^{+})} and x(σ_{n}^{+}) ∈ A. Moreover, either x(σ_{n}^{+}) ∈ A−Φ_{e}^{B_{i}}, or x(σ_{n}^{+}) ∈ Φ_{e}^{D}, for some D ⊆ B_{i}, but D ⊈ Ψ_{e}^{A}.

• If D, E exist, then we eventually choose the least such pair D, E, hence α(σ_{n}^{+}) = E − {x(σ_{n}^{+})}, ϵ(σ_{n}^{+}) = ∅, and either (a) or (b) holds:

(a) σ_{n+1} = σ_{n}^{+} 0 and α(σ_{n+1}) = ∅, ϵ(σ_{n+1}) = {x(σ_{n}^{+})};

(b) σ_{n+1} = σ_{n}^{+} 1 and α(σ_{n+1}) = {x(σ_{n}^{+})}, ϵ(σ_{n+1}) = ∅.

In case (a) either

(a_{1}) there exist infinitely many stages s such that σ_{n}^{+} 1 ⊆ δ_{s}, in which case, there exists some y ∈ D such that lim_{s} B_{i}^{s}(y) does not exist; or

(a_{2}) D ⊆ B_{i} but x(σ_{n}^{+}) ∉ A, giving x(σ_{n}^{+}) ∈ Φ_{e}^{B_{i}} − A.
In (b) we have D ⊈ B_{i}, but E ⊆ A, hence D ⊆ Ψ_{e}^{A}.

Remark 3.7 Notice that if j is such that lim_{s} B_{i}^{s}(y) exists for every y ≥ j, then (a_{1}) does not occur, by Lemma 3.3.

If |σ_{n}| = 2i + 1 is odd and i ∈ Φ_{i}^{D}, for some finite set D such that D ∩ ⋃_{τ⪯σ_{n}} ϵ(τ) = ∅, then σ_{n+1} = σ_{n} 0 and α(σ_{n+1}) = D, for some such D; otherwise σ_{n+1} = σ_{n} 1 and α(σ_{n+1}) = ∅. In either case ϵ(σ_{n+1}) = ∅.

The proof of the lemma is now complete. □

Lemma 3.8 K^{A} ≤_{T} C.

Proof. We will show that, for every n, one can compute σ_{n} recursively in C.

Now, σ_{0} = ∅. Assume by induction that we can compute σ_{n} and a stage s_{n} such that τ ⊈ δ_{s}, for every s ≥ s_{n} and τ ≺_{L} σ_{n} and each parameter at any τ ⪯ σ_{n} has reached its limit by stage s_{n}. Assume first that |σ_{n}| is even, and let P_{e,i,j} be the requirement assigned to σ_{n}. Since C can compute B_{i} ↾ j, it follows that C can compute the first component, h = lim_{s} h(σ_{n}, s), of the outcome of σ_{n}. Moreover, since ∅′ ≤_{T} C, C can compute the least stage s_{n}^{+} ≥ s_{n} such that τ ⊈ δ_{s}, for every τ ≺_{L} σ_{n} h (since for every x ∈ B_{i} ↾ j and every t, one can compute in ∅′ whether there exists some s ≥ t such that x ∉ B_{i}^{s}). Again, using ∅′ as an oracle, one can compute whether Case 1 or Case 2 of the construction holds, thus computing σ_{n+1} and the corresponding s_{n+1}.

A similar argument applies in the case |σ_{n}| = 2i + 1, for some i, since the oracle ∅′ can compute whether or not there exists some stage s ≥ s_{n} and some finite D such that i ∈ Φ_{i}^{D}, and D ∩ ⋃_{τ⪯σ_{n}} ϵ(τ, s_{n}) = ∅.

It follows that i ∈ K^{A} if and only if σ_{2i+2} = σ_{2i+1} 0, thus K^{A} ≤_{T} C. □

Remark 3.9 We expect that, by combining the above construction of A with a variant of the coding procedure and the associated guessing at outcomes used in the tree proof of the Sacks’ jump inversion theorem, one can actually guarantee that J_{e}(A) ≡_{e} χ_{C}.

References

[BCS97] S. Bereznyuk, R. Coles, and A. Sorbi. The distribution of properly Σ_{2}^{0} enumeration degrees. preprint, 1997.

[CC88] S. B. Cooper and C. S. Copestake. Properly Σ_{2} enumeration degrees. Z. Math. Logik Grundlag. Math., 34:491–522, 1988.

[Coo90] S. B. Cooper. Enumeration reducibility, nondeterministic computations and relative computability of partial functions. In K. Ambos-Spies, G. Müller, and G. E. Sacks, editors, Recursion Theory Week, Oberwolfach 1989, volume 1432 of Lecture Notes in Mathematics, pages 57–110, Heidelberg, 1990. Springer–Verlag.

[Ler83] M. Lerman. Degrees of Unsolvability. Perspectives in Mathematical Logic. Springer–Verlag, Heidelberg, 1983.

[LS92] A. H. Lachlan and R. A. Shore. The n-rea enumeration degrees are dense. Arch. Math. Logic, 31:277–285, 1992.

[MC85] K. McEvoy and S. B. Cooper. On minimal pairs of enumeration degrees. J. Symbolic Logic, 50:839–848, 1985.

[McE85] K. McEvoy. Jumps of quasi–minimal enumeration degrees. J. Symbolic Logic, 50:839–848, 1985.

[Med55] Y. T. Medevdev. Degrees of difficulty of the mass problems. Dokl. Nauk. SSSR, 104:501–504, 1955.

[Rog67] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

[Soa87] R. I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series. Springer–Verlag, Heidelberg, 1987.