Every Incomplete Computably Enumerable Truth-Table Degree Is Branching^{∗}

Peter A. Fejer

University of Massachusetts at Boston Richard A. Shore^{∗∗} Cornell University

January 21, 1999

Abstract

If r is a reducibility between sets of numbers, a natural question to ask about the structure C_{r} of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing that every ttincomplete computably enumerable truth-table degree a is branching in C_{tt}. The fact that every Turing-incomplete computably enumerable truth-table degree is branching can be shown using a technique of Ambos-Spies. Although this result has been known for some time, it has not appeared in the literature, and we give a proof here. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof.

∗The authors thank André Nies for helpful conversations.

∗∗Partially supported by NSF Grants DMS-9503503 and DMS-9802843 and as a Visiting Scholar by M.I.T. and Harvard University.

1 Introduction

If r is one of the reducibilities between sets of natural numbers studied in computability theory, one can form the structures D_{r}, D_{r}(≤ 0′_{r}) and C_{r} consisting of all the r-degrees, the r-degrees of sets r-reducible to the 1-complete computably enumerable set K = {e|{e}(e)↓}, and the r-degrees containing computably enumerable sets, respectively. (We write 0′_{r} for the r-degree of K.) These structures are always partially ordered sets and are usually upper semi-lattices. Among the many algebraic questions one might ask about these structures, a basic one is whether every element not equal to the greatest element is branching, where we call a degree branching if it is meet-reducible, i.e., it is the meet of two degrees strictly above it. In the case of C_{r} and the most commonly studied reducibilities r (namely, many-one (m), truth-table (tt), weak truth-table (wtt) and Turing (T)) we have the following results. Every incomplete c.e. m-degree is branching. This can be seen as follows. Given a c.e. m-degree, c < 0′_{m}, by a result of Denisov [2], there is a c.e. mdegree a with c < a < 0′_{m}. Now, by a result of Ershov and Lavrov [3], there is a strong minimal cover b of c in the c.e. m-degrees (that is, c < b and for all c.e. m-degrees d, if d < b, then d ≤ c) such that b is incomparable with a. The two degrees a and b now have meet c. (See Odifreddi [8], Exercise X.5.5 for a direct proof of the fact that every c.e. m-degree is branching.) Every incomplete c.e. wtt-degree is branching by a result of Cohen [1]. (See Odifreddi [8], Exercise X.6.8.) In the case of Turing reducibility, the situation is a bit more complicated. There are nonzero branching c.e. T-degrees and 0 is also branching, but there are also incomplete c.e. T-degrees that are not branching (Lachlan [6]). In fact, both the branching (Slaman [9]) and nonbranching (Fejer [4]) c.e. T-degrees are dense in C_{T}. Thus, among these problems, only the truth-table case has been unresolved. In this paper, we show that every incomplete c.e. truth-table degree is branching.

An unpublished argument using a technique due to Ambos-Spies shows that every Turing-incomplete c.e. truth-table degree is branching. (We call a c.e. truth-table degree Turing-complete if its members belong to deg_{T} (K).) Ambos-Spies’ technique was used by Nies and Shore [7] in showing a related result. We begin this paper by showing how the result in [7] can be strengthened slightly in order to get a result that has as a corollary the fact that every Turing-incomplete c.e. truth-table degree is branching. Then, in the main part of the paper, we show (Theorem 4) that every Turing-complete, tt-incomplete truth-table degree is branching. In combination with the result on Turing-incomplete c.e. degrees, this gives the result of the title of this paper. We conclude the paper by mentioning some related open problems.

Our notation is for the most part standard. (See for example Soare[10].) Our notation for truth-table reductions is from [5]. In particular, if {e}(x)↓, then [e](x) denotes the truth-table with Gödel number {e}(x) and |[e](x)| denotes the length of this truth table. (Here, as in [5], we take this length to be one more than the largest number asked about in the truth table.) For any set A, [e]^{A}(x) is 1 or 0 according to whether or not A satisfies [e](x). We then have that for any two sets A and B, A ≤_{tt} B if and only if there is an e with {e} total such that for all x, [e]^{B}(x) = A(x). Also, we let F_{k} denote the finite set with canonical index k.

2 Turing Incomplete Truth-Table Degrees

In this section, we present a slight strengthening of a result from [7] which will allow us to conclude that every Turing incomplete c.e. truth-table degree is branching. We first give a slightly modified version of Lemma 3.3 of [7].

Lemma 1 Let (D_{n})_{n∈ω} be a uniformly c.e. sequence of sets and let

D = {⟨x, n⟩|x ∈ D_{n}}.

Suppose that, for each e, the set D^{[≤e]} is T -incomplete. Then, there exist c.e. sets B, C such that

(∀n)[D_{n} ≤_{tt} B, C]  (1)
(∀n)[B, C ≰_{tt} D_{n}]  (2)
(∀Z)[Z ≤_{tt} B, C ⇒ (∃e)[Z ≤_{tt} D^{[≤e]}]]  (3)

We say that B, C form an exact pair for the sequence (D_{n}).

Proof: The difference between this result and Lemma 3.3 of [7] is the addition of equation (2). We will not give a complete proof here, but instead will just describe the modifications that need to be made to the proof of Lemma 3.3 of [7]. We have the requirements P_{n} and Q_{e} of [7]. To make (2) hold, we introduce requirements

R_{e,n}^{X} : X ≠ [e]^{D^{[n]}} (X = B, C)

for e, n ∈ ω. We let (R_{i})_{i∈ω} be an effective listing of the R_{e,n}^{X}. For each γ in the tree ω^{<ω}, there are strategies P_{γ}, Q_{γ}, R_{γ} for P_{i}, Q_{i}, R_{i}, respectively, where i = |γ|. Strategies P_{γ} and Q_{γ} work as in [7], except that P_{γ} tries to code D^{[i]} into X^{[2n(γ)]} for X = B, C, instead of into X^{[n(γ)]}, where n(γ) is the code number assigned to γ.

The strategy for R_{γ} is Sacks coding; that is, if R_{|γ|} is R_{e,n}^{X}, then R_{γ} codes K into X (more exactly into X^{[2n(γ)+1]}) until a difference between X and [e]^{D^{[n]}} occurs. (This must happen since D^{[n]} is tt-incomplete.) Because the reduction being diagonalized against is a truth-table reduction, the action of R_{γ} is finite.

To measure the length of agreement for the R_{i} requirements, we define

l′(i, s) = max{x|(∀y < x)[X(y) = [e]^{D^{[n]}}(y)[s]]},

where R_{i} = R_{e,n}^{X}. The construction is the same as in [7] except for the following changes. 1) In Step 1, we consider numbers x = ⟨z, 2n(β)⟩ instead of x = ⟨z, n(β)⟩. 2) We add a Step 1.5 (where R_{β} codes K) given by

For each x < s, if l′(e, s) ≥ x ≥ R(β, [s, e]) and x = ⟨z, 2n(β)+1⟩ for z ∈ K_{s}, then enumerate x into X, where R_{e} is R_{i,n}^{X}.

3) In Step 3, replace equation (5.9) by

F ∩ (ω^{[2n(γ)]} ∪ ω^{[2n(γ)+1]}) = ∅ for each γ < β ∗ m.

In the verification, Lemma 5.1 of [7] is modified by changing X^{[γ]} and ⟨z, n(γ)⟩ in Part (iv) to X^{[2n(γ)]} and ⟨z, 2n(γ)⟩, respectively, and by adding a Part (v) which states

(v) If γ ⊆ α, i = |γ|, and R_{i} is R_{e,n}^{X}, then X ≠ [e]^{D^{[n]}} and X^{[2n(γ)+1]} is finite.

The proof of the new Part (v) of the lemma goes as follows. By the inductive hypothesis, it is only necessary to prove (v) for γ = α. Let R_{e+1} be R_{i,n}^{X} and let s_{α} be as in the statement of the lemma. By the argument for Part (iv) of the lemma given in [7], no Q_{β} puts a number into X^{[2n(α)+1]} after stage s_{α}. Suppose that X = [i]^{D^{[n]}}. Then, lim_{s} l′(e + 1, s) = ∞. We claim that

X^{[2n(α)+1]} = X_{s_{α}}^{[2n(α)+1]} ∪{⟨z, 2n(α)+1⟩|⟨z, 2n(α)+1⟩ ≥ R(α)∧z ∈ K}. (4)

To see the right-to-left inclusion of (4), suppose that x = ⟨z, 2n(α)+1⟩ ≥ R(α) and z ∈ K. Take s ≥ s_{α} such that s is an α-stage, z ∈ K_{s}, s > x and l′(e+1, s) ≥ x. Since R(α, [s, e+1]) = R(α), x is enumerated into X at stage [s, e + 2]. For the other inclusion, suppose that x ∈ X^{[2n(α)+1]} − X_{s_{α}}^{[2n(α)+1]}. Then, x did not enter X through the action of any Q_{β}, so x entered X at Step 1.5 of Stage [s, e+2], where s is an α-stage > s_{α}. Since R(α, [s, e+1]) = R(α), x ∈ {⟨z, 2n(α) + 1⟩|⟨z, 2n(α) + 1⟩ ≥ R(α) ∧ z ∈ K}.

From (4), we now get K ≤_{tt} X^{[2n(α)+1]} ≤_{tt} X ≤_{tt} D^{[n]}, contradicting assumption that D^{[n]} is Turing-incomplete.

Thus, X ≠ [i]^{D^{[n]}}, so l′(e + 1, s) is bounded as s → ∞. This implies that the set of elements put into X^{[2n(α)+1]} by R_{α} is finite. As already mentioned, the set of elements put into X^{[2n(α)+1]} by Q_{β} requirements is finite. Thus, X^{[2n(α)+1]} is finite. This completes the proof of Part (v).

There are a few other modifications to the proof of Lemma 3.3 of [7] which are necessary to prove this lemma, but they are routine and are left to the reader.

An ideal I of C_{tt} is called Σ_{3}^{0} if {i|deg_{tt}(W_{i}) ∈ I} is Σ_{3}^{0}.

Theorem 2 Let I be a Σ_{3}^{0}-ideal of C_{tt} consisting of only Turing-incomplete truth-table degrees. Then, I has an exact pair b, c such that neither of b and c belongs to I.

Proof: This theorem follows from Lemma 1 as Theorem 3.2 follows from Lemma 3.3 in [7].

Theorem 3 If a is a Turing-incomplete c.e. tt-degree, then a is branching.

Proof: Let a be a Turing-incomplete c.e. truth-table degree and define I = {d ∈ C_{tt}|d ≤ a}. Fix a c.e. set A ∈ a. We have

deg_{tt}(W_{i}) ∈ I ⇔ (∃e)(∀x)(∀t)(∃s ≥ t)[{e}_{s}(x)↓ ∧W_{i,s}(x) = [e]^{A_{s}}(x)],

so I is a Σ_{3}^{0}-ideal. All the members of I are Turing-incomplete. Thus, by Theorem 2, there is an exact pair b, c for I such that neither b nor c belongs to I. It follows that a < b, c and that a is the meet of b and c in C_{tt}, so a is branching.

3 Turing Complete Truth-Table Degrees

In this section, we present the main result of the paper, namely, that every Turing-complete tt-incomplete c.e. degree is branching.

Theorem 4 If b is a Turing-complete, tt-incomplete c.e. tt-degree, then b is branching in C_{tt}.

Proof: Let B be a c.e. set in b. We want to construct c.e. sets A_{0}, A_{1} such that A_{i} ≰_{tt} B for i = 0, 1 and such that deg_{tt}(A_{0} ⊕ B) and deg_{tt}(A_{1} ⊕ B) have meet b in C_{tt}. We will actually meet the following requirements R_{e,i} for e ∈ ω and i = 0, 1:

R_{e,i} : [e]^{A_{i}⊕B} ≠ A_{1−i}.

These requirements certainly imply A_{i} ≰_{tt} B for i = 0, 1 and the meet requirements will hold automatically due to the way we achieve the R_{e,i} requirements.

An intuitive and oversimplified description of how we meet requirement R_{e,i} is the following. Because K ≰_{tt} B, we know that if we make A_{i} look like ω (above higher priority restraint) and we make A_{1−i} look like K (on a row), then there must be an x such that [e]^{A_{i}⊕B}(x) ≠ A_{1−i}(x). Not only is there such an x, but K can find it; that is, there is a function f ≤_{T} K such that if A_{i} looks like ω up to f(e) (above higher priority restraint) and A_{1−i} looks like K on a specified row up to f(e), then [e]^{A_{i}⊕B} ≠ A_{1−i}. Since K ≤_{T} B, there is a j_{0} with {j_{0}}^{B} = f. Then, for all x, {j_{0}}_{s}^{B_{s}}(x)→ f(x) as s→ ∞. At stage s of the construction, we will make A_{i} look like ω up through {j_{0}}_{s}^{B_{s}}(e) and A_{1−i} look like K_{s} through the same number (on a row). In fact, if we get a new computation {j_{0}}_{s}^{B_{s}}(e) at stage s, we make A_{i} look like ω and A_{1−i} look like K up through s. Because of the usual convention that {j_{0}}_{s}^{B_{s}}(e) ≤ s, this suffices to meet R_{e,i}. The reason we put potentially many more numbers than necessary to meet R_{e,i} into A_{i} is to ensure that meet requirements hold.

In outline, the argument that deg_{tt}(A_{0} ⊕ B) and deg_{tt}(A_{1} ⊕ B) have meet deg_{tt}(B) = b in C_{tt} is as follows. It suffices to show that, given e_{0}, e_{1} with {e_{0}}, {e_{1}} total, there is an e′ with {e′} total such that for all x, [e′]^{B}(x) is either [e_{0}]^{A_{0}⊕B}(x) or [e_{1}]^{A_{1}⊕B}(x). Given x, [e′] finds M = max{|[e_{0}](x)|, |[e_{1}](x)|} and then at stage M finds the highest priority R_{e,i} such that {j_{0}}_{M}^{B_{M}} (e) converges by an incorrect computation. Then, at some later stage, every number greater than the current restraint on R_{e,i} and less than M will be dumped into A_{i} and no number smaller than the current restraint will be put in A_{i}. This allows [e′] to correctly compute [e_{i}]^{A_{i}⊕B}(x). We will see that this is in fact a truth-table reduction.

To begin the formal construction, we define

f(⟨e, m, k⟩) = μy[{e}(⟨y, m⟩)↑ ∨[e]^{(ω^{[≥m]}∪F_{k})⊕B}(⟨y, m⟩)↓≠ K(y)].

Since ω^{[≥m]} ∪ F_{k} is recursive and K ≰_{tt} B, f is total. Since B is Turing complete, f ≤_{T} B, say f = {j_{0}}^{B}. The extra parameters in the definition of f, compared to the intuitive discussion just given, are to account for the effect of higher priority requirements. If the requirements of higher priority than R_{e,i} control the first m rows and F_{k} is the set of numbers that the higher priority requirements put into ω^{[<m]}, then ω^{[≥m]} ∪ F_{k} is the value A_{i} would have if R_{e,i} puts every element it can into A_{i}.

We make the following assumptions:

if x = ⟨e, m, k⟩ and {e}(⟨f(x), m⟩) ↓, then
u(B; j_{0}, x) > |[e](⟨f(x), m⟩)| and K(f(x)) =
K_{u(B;j_{0},x)}(f(x));

(5)

{j_{0}}_{0}^{D}(y)↑ for all D, y;  (6)
if  {j_{0}}_{s}^{B_{s}}(x)  ↓
and B_{s} `|u(B_{s}; j_{0}, x, s) ≠ B_{s+1} `|u(B_{s}; j_{0}, x, s), then
{j_{0}}_{s+1}^{B_{s+1}}(x)↑.

(7)

The last of these assumptions is the usual “hat trick”. With these assumptions, we have the following lemma, which summarizes how we will meet the R_{e,i} requirements.

Lemma 5 Let {e} be total and let s be such that {j_{0}}_{s}^{B_{s}}(⟨e, m, k⟩)↓ and

B_{s} `|u(B_{s}; j_{0}, ⟨e, m, k⟩, s) = B `|u(B_{s}; j_{0}, ⟨e, m, k⟩, s).

If

A_{i}^{[≥m]} `|s = ω^{[≥m]} `|s,  (8)
A_{i}^{[<m]} = F_{k}, and  (9)
(∀y ≤ s)(⟨y, m⟩ ∈ A_{1−i}↔ y ∈ K_{s})  (10)

then R_{e,i} is met.

Proof: Let x = ⟨e, m, k⟩ and u = u(B_{s}; j_{0}, x, s). By the usual convention, s ≥ u, f(x) and by the assumption of the lemma, u = u(B; j_{0}, x). Because {e} is total, we have, by definition of f, that [e]^{(ω^{[≥m]}∪F_{k})⊕B}(⟨f(x), m⟩)↓≠ K(f(x)). Thus, the lemma will be proven if we can show that [e]^{A_{i}⊕B}(⟨f(x), m⟩) = [e]^{(ω^{[≥m]}∪F_{k})⊕B}(⟨f(x), m⟩) and that K(f(x)) = A_{1−i}(⟨f(x), m⟩). Towards establishing the first of these equalities, note that by (5), s ≥ u > |[e](⟨f(x), m⟩)|. Thus, (8) and (9) give us the desired equality, since A_{i} equals ω^{[≥m]} ∪ F_{k} up to the length of the appropriate truth table. For the second equality, we have, by (10), A_{1−i}(⟨f(x), m⟩) = K_{s}(f(x)). Since s ≥ u, (5) gives K_{s}(f(x)) = K(f(x)), completing the proof.

Let (R_{n})_{n∈ω} be an effective ordering of the R_{e,i}’s. The construction will be a finite injury one. From time to time during the construction, an attack may be begun on a requirement R_{n}. The attack may later be canceled. At most one attack on a given requirement will be active at a time. When an attack is made on R_{n}, two parameters m_{n} and x_{n} will be defined. If the attack is later canceled, then these values become undefined.

R_{n} = R_{e,i} requires attention at stage s + 1 if either

R_{n} is not under attack at the end of stage s  (11)

or there is an attack on R_{n} at the end of stage s,

{j_{0}}_{s}^{B_{s}}(x_{n,s})↓ and {j_{0}}_{s−1}^{B_{s−1}}(x_{n,s})↑. (12)

Construction:

Stage 0: Do nothing.

Stage s+1: Find the highest priority requirement R_{n} that requires attention. Let R_{n} = R_{e,i}. Proceed according to which case in the definition of requires attention holds.

(11) holds: Begin an attack on R_{n}. Set m_{n} = s and x_{n} = ⟨e, s, k⟩, where F_{k} = A_{i,s}^{[<s]}. Put ⟨y, m_{n}⟩ into A_{i} for all y ≤ s. For all y ∈ K_{s}, put ⟨y, m_{n}⟩ into A_{1−i}.

(12) holds: Put ⟨y, z⟩ into A_{i} for all y, z with m_{n} ≤ z ≤ s and y ≤ s. For all y ∈ K_{s}, put ⟨y, m_{n}⟩ into A_{1−i}.

In either case, cancel all attacks on R_{n′} with n′ > n.

End of Construction

Lemma 6 For each n, R_{n} requires attention only finitely often and an uncanceled attack is made on R_{n}.

Proof: Suppose that the result is true for all n′ < n. Take s_{0} such that no R_{n′} with n′ < n requires attention at a stage > s_{0}. If no attack on R_{n} is in progress at the end of stage s_{0}, one will be made at stage s_{0} + 1, so there is an attack in progress at the end of stage s_{0} + 1. This attack will never be canceled and R_{n} never requires attention via (11) after stage s_{0} + 1. Let x_{n}, m_{n} be the values associated with the final attack and take s_{1} ≥ s_{0}+1 such that {j_{0}}_{s_{1}}^{B_{s_{1}}}(x_{n})↓ and B_{s_{1}} `|u(B_{s_{1}}; j_{0}, x_{n}, s_{1}) = B `|u(B_{s_{1}}; j_{0}, x_{n}, s_{1}). Then, R_{n} does not require attention via (12) after stage s_{1} +1, so R_{n} requires attention only finitely often.

Lemma 7 Each R_{n} is met.

Proof: Let R_{n} = R_{e,i}. We may assume that {e} is total, since otherwise the result is immediate. Suppose that the final attack on R_{n} is begun at stage s_{0} + 1. Then, the final values of m_{n} and x_{n} are s_{0} and ⟨e, s_{0}, k⟩ = ⟨e, m_{n}, k⟩, respectively, where F_{k} = A_{i,s_{0}}^{[<s_{0}]}. Let s + 1 ≥ s_{0} + 1 be the last stage at which R_{n} requires attention. We will use Lemma 5 applied with m = m_{n} to show that R_{n} is met. First, we want to show that {j_{0}}_{s}^{B_{s}}(x_{n})↓ and B_{s} `|u(B_{s}; j_{0}, x_{n}, s) = B `|u(B_{s}; j_{0}, x_{n}, s). Suppose not. Let t > s be the first stage at which {j_{0}}_{t}^{B_{t}}(x_{n})↓ by a B-correct computation. Then, by the “hat trick” (7), {j_{0}}_{t−1}^{B_{t−1}}(x_{n})↑, so R_{n} requires attention at stage t + 1 > s + 1, contradicting our assumption.

To show (8), note that if ⟨y, z⟩ ∈ ω^{[≥m_{n}]} `|s, then m_{n} ≤ z ≤ s and y ≤ s. We may have either (11) or (12) holding at stage s+1 (depending on whether s = s_{0} or s > s_{0}), but in either case, ⟨y, z⟩ is put into A_{i} at stage s+1. Thus, A_{i}^{[≥m_{n}]} `|s = ω^{[≥m_{n}]} `|s.

Towards showing the last two facts we need in order to apply Lemma 5, note that by construction, if some R_{n′} puts a number y into A_{0} ∪ A_{1} at stage s′ + 1, then y ∈ ω^{[≥m_{n′,s′}]} ∩ ω^{[≤s′]}. Also, each R_{n′} with n′ > n is canceled at stage s_{0} + 1 and any value assigned to m_{n′} at a later stage will be > s_{0}. Furthermore, no R_{n′} with n′ < n receives attention at a stage ≥ s_{0} + 1. It follows from these facts that F_{k} = A_{i,s_{0}}^{[<s_{0}]} = A_{i}^{[<s_{0}]} = A_{i}^{[<m_{n}]}, so (9) holds.

Finally, to establish (10), suppose that y ∈ K_{s}. Then, ⟨y, m_{n}⟩ ∈ A_{1−i,s} ⊆ A_{1−i} because R_{n} receives attention at stage s + 1. Conversely, if ⟨y, m_{n}⟩ ∈ A_{1−i}, then by the considerations of the previous paragraph, ⟨y, m_{n}⟩ was put into A_{1−i} by R_{n}. Since R_{n} last acts at stage s + 1, if ⟨y, m_{n}⟩ ∈ A_{1−i}, then y ∈ K_{s}. Thus, (10) holds and by Lemma 5, R_{n} is met.

Lemma 8 If {e_{0}} and {e_{1}} are both total, then there is an e′ such that {e′} is total and for all x, either [e′]^{B}(x) = [e_{0}]^{A_{0}⊕B}(x) or [e′]^{B}(x) = [e_{1}]^{A_{1}⊕B}(x). (So, if [e_{0}]^{A_{0}⊕B} = [e_{1}]^{A_{1}⊕B} = g, then [e′]^{B} = g.)

Proof: Given x, we compute the truth table [e′](x) as follows: Find the truth tables [e_{0}](x) and [e_{1}](x) and let M = max{|[e_{0}](x)|, |[e_{1}](x)|}. Carry out the construction through the end of stage s_{0} = M +1. Suppose that at the end of stage s_{0} there are attacks in progress on requirements R_{0}, …, R_{n_{0}}. (Note that by construction, if there is an attack in progress on R_{n} at the end of a stage s and n′ < n, then there is an attack in progress on R_{n′} at the end of stage s.) The truth table [e′](x) will have length M and will query all the numbers 0, …, M−1. Given σ ∈ 2^{M}, find the minimum n ≤ n_{0}, if any, such that either {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↑ or {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↓ and B_{s_{0}−1} `|u(B_{s_{0}−1}; j_{0}, x_{n,s_{0}}, s_{0} − 1) ≠ σ `|u(B_{s_{0}−1}; j_{0}, x_{n,s_{0}}, s_{0} − 1). (Note that if n ≤ n_{0} and {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↓, then u(B_{s_{0}−1}; j_{0}, x_{n,s_{0}}, s_{0} − 1) < s_{0} − 1 = M = |σ|.) If no such n exists, then [e′]^{σ}(x) is [e_{0}]^{A_{0,s_{0}}⊕σ}(x). If such a minimal n exists, then let R_{n} be R_{e,i}. We

define [e′]^{σ}(x) to be [e_{i}]^{(A_{i,s_{0}}^{[<mn,s_{0} ]}∪ω^{[≥mn,s_{0} ]})⊕σ}(x). Then, e′ is certainly a truth table reduction. We have to show that [e′]^{B `|M}(x) is either [e_{0}]^{A_{0}⊕B}(x) or [e_{1}]^{A_{1}⊕B}(x).

Suppose first that there is no n ≤ n_{0} such that either {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↑ or {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↓ and, letting u = u(B_{s_{0}−1}; j_{0}, x_{n,s_{0}}, s_{0} − 1), B_{s_{0}−1} `|u ≠ (B `|M) `|u = B `|u. Then, by induction on s ≥ s_{0} + 1, it follows that at no such stage s does any R_{n} with n ≤ n_{0} receive attention. Thus, A_{0,s_{0}}^{[<s_{0}]} = A_{0,s_{0}}^{[≤M]} = A_{0}^{[≤M]}. It follows that A_{0,s_{0}} `|M = A_{0} `|M and hence [e′]^{B `|M}(x) = [e_{0}]^{A_{0,s_{0}}⊕(B `|M)}(x) = [e_{0}]^{A_{0}⊕B}(x), as desired.

Now suppose that n is minimal such that n ≤ n_{0} and either {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↑ or {j_{0}}_{s_{0}−1}^{B_{s_{0}−1}}(x_{n,s_{0}})↓ and, letting u = u(B_{s_{0}−1}; j_{0}, x_{n,s_{0}}, s_{0} − 1), B_{s_{0}−1} `|u ≠ (B `|M) `|u = B `|u. Then, no R_{n′} with n′ < n requires attention at any stage s ≥ s_{0} + 1, so A_{j,s_{0}}^{[<m_{n,s_{0}}]} = A_{j}^{[<m_{n,s_{0}}]}, for j = 0, 1. Let R_{n} be R_{e,i}. At some stage t ≥ s_{0} + 1, R_{n} will receive attention. At stage t, all numbers ⟨y, z⟩ with y < t and m_{n,s_{0}} ≤ z < t are put into A_{i}. Since t ≥ s_{0} + 1 > M, A_{i}^{[≥m_{n,s_{0}}]} `|M = ω^{[≥m_{n,s_{0}}]} `|M. Thus,

A_{i} `|M = A_{i}^{[<m_{n,s_{0}}]} `|M ∪ A_{i}^{[≥m_{n,s_{0}}]} `|M
= A_{i,s_{0}}^{[<m_{n,s_{0}}]} `|M ∪ ω^{[≥m_{n,s_{0}}]} `|M = (A_{i,s_{0}}^{[<m_{n,s_{0}}]} ∪
ω^{[≥m_{n,s_{0}}]}) `|M.

Hence, [e′]^{B `|M}(x) = [e_{i}]^{(A_{i,s_{0}}^{[<mn,s_{0} ]}∪ω^{[≥mn,s_{0} ]})⊕(B `|M)}(x) = [e_{i}]^{A_{i}⊕B}(x), as desired.

This completes the proof of Theorem 4.

4 Open Problems

We conclude the paper by listing three problems related to the topic of the paper that we are unable to solve using the methods developed here.

Q1) Does every Σ_{3}^{0}-ideal I of C_{tt}, different from C_{tt}, have an exact pair b, c such that neither of b and c belongs to I?

(The restriction in (Q1) that b, c do not belong to I is relevant only when I is a principal ideal. If I is not principal, then neither half of an exact pair for I can belong to I.) Theorem 2 gives an affirmative answer to (Q1) when I does not contain any Turing-complete degrees. Theorem 4 gives an affirmative answer to (Q1) when I is a principal ideal and contains Turing complete degrees. An affirmative answer to (Q1) for arbitrary I would make it possible to obtain our result that every tt-incomplete c.e. truth-table degree is branching in C_{tt} from a more general uniformity of C_{tt}. The method of Section 3 does not appear to give an affirmative answer to (Q1) in the remaining open case, namely, when I is nonprincipal and contains Turing-complete degrees.

A set A is said to be bounded truth-table (btt) reducible to a set B if there are numbers e and k such that A = [e]^{B} and for all x, the truth table [e](x) queries at most k numbers.

Q2) Is every btt-incomplete c.e. bounded truth-table degree branching in C_{btt}?

The method of Section 2, unchanged, shows that every Turing-incomplete c.e. bounded truth-table degree is branching in C_{btt}. However, the proof in Section 3 does not show that every Turing-complete btt-incomplete bounded truth-table degree is branching in C_{btt}. This is because in Lemma 8, the truth-table reduction [e′] is not bounded, even if the reductions [e_{0}] and [e_{1}] are bounded.

So far, when a structural property of C_{tt} has been shown, it has turned out to be possible to show the same result, by a more difficult proof, for D_{tt}(≤ 0′_{tt}) and then for the structure D_{wtt}(≤ 0′_{wtt}), where wtt stand for weak truth-table reducibility (i.e., Turing reducibility with a recursive bound on the use function). In fact, no elementary difference is known between these three structures. In view of the results in this paper, it is natural to ask

Q3) Is every degree in D_{tt}(≤ 0′_{tt}), other than 0′_{tt}, branching in D_{tt}(≤ 0′_{tt})?

A negative answer to this question would be the most interesting, but would be surprising. We believe that the method from Section 3, with additional complications, can be used to give an affirmative answer to (Q3) when the degree is Turing-complete, but the situation for Turing-incomplete degrees is unknown – the exact pair result from Section 2 is not easily adapted to this case.

References

[1] P. F. Cohen, Weak truth-table reducibility and the pointwise ordering of 1-1 recursive functions, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1975.

[2] S. D. Denisov, On m-degrees of recursively enumerable sets, Algebra i Logika 9 (1970), 422–427 (Russian), English transl. in Algebra and Logic 9 (1970) 254–256.

[3] Y. L. Ershov and I. A. Lavrov, The uppersemilattice L(γ), Algebra i Logika 12 (1973), 167–189, 243–244 (Russian), English transl. in Algebra and Logic 12 (1973) 93–106.

[4] Peter A. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983), 113–130.

[5] Peter A. Fejer and Richard A. Shore, A direct construction of a minimal recursively enumerable truth-table degree, Recursion Theory Week (Proceedings of a Conference Held in Oberwolfach, FRG, March 19–25, 1989) (Berlin) (K. Ambos-Spies, G. H. Müller, and G. E. Sacks, eds.), Lecture Notes in Mathematics, Number 1132, Springer-Verlag, 1990, pp. 187–204.

[6] Alistair H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569.

[7] André Nies and Richard A. Shore, Interpreting true arithmetic in the theory of the r.e. truth table degrees, Ann. Pure Appl. Logic 75 (1995), 269–311.

[8] Piergiorgio Odifreddi, Classical Recursion Theory, volume 2, In preparation.

[9] Theodore A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 (1991), 155–179.

[10] Robert I. Soare, Recursively enumerable sets and degrees: The study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Ω-Series, Springer-Verlag, Berlin, 1987.