Simultaneous Cupping and Continuity
in Bounded Turing Degrees
Wu Guohua

Nanyang Technological University, Singapore

CiE 2023, Batumi

Assumed:
I

Computable (decidable) sets, Computably enumerable (semi-decidable)
sets

I

Turing reduction, no constraint to query to oracles

I

Bounded Turing reduction, i.e., weak-truth-table reduction,
query to oracles are recursively boundedI

Turing degrees, Bounded Turing degrees

Ic.e. degrees, a upper-semi-latticea ∨ b always exists, but not for a ∧ bFriedberg-Muchinik theorem, Sacks’s theorems: splitting and density,
Lachlan’s nonsplitting theorem
I High/Low hierachy, Cups and Caps
I Model-theoretic properties of degree structures

IIIc.e. bT-degrees, , also a upper-semi-latticeII

Ladner and Sasso’s splitting theorem
Contiguous degrees and characterizations

Shoenfield’s Conjecture
As an upper-semi lattice, the structure of c.e. degrees is countably categorical.
If the conjecture is true, the theory of this structure is decidable.
Lachlan and Yates first proved the existence of minimal pairs, refuting
Shoenfield’s Conjecture.
00rra
JJJJJJJJJJJr0br

Embedding of M3 and N5 into c.e. degrees
Lachlan’s embeddings
Two nondistributive lattices, M3 and N5 , can be embedded into c.e. degrees.
IThe construction of M3 in c.e. degrees is fairly complicated, as we need tohandle with sequences of traces, which changes a lot.

I

M3 and N5 cannot be embedded into c.e. bT-degrees, as c.e. bT-degrees
form a distributive upper-semilattice.

Lachlan-Soare’s example of nonembedding
The nondistributive lattice, S8 , cannot be embedded into c.e. degrees. So,ITop elements of any M3 in c.e. degrees are nonbranching.

ITop elements of N5 can be branching (Ambos-Spies, Fejer).

The structure of c.e. bT-degrees admits nice algebraic properties, but notmodel-theoretic properties.

Contiguous Degrees
Many complicated constructions in c.e. degrees cannot be done in c.e.
bT-degrees, due to the constraints on the queries.
I

Lachlan’s nonslitting theorem cannot be done in c.e. bT-degrees (Ladnerand Sasso)
That is, for any c.e. bT-degrees a > b, there are c.e. bT-degrees a1 , a2
above b, incomparable, with a1 ∨ a2 = a.
As a consequence, a c.e. degree either contains exactly one c.e.
bT-degree, or infinitely many c.e. bT-degrees.

Definition:
A c.e. degree a is contiguous if a contains exactly one c.e. bT-degree. A c.e.
degree is noncontiguous if it is not contiguous.
I

Array computable degrees are contiguous and contiguous degrees are low2 .

I

Nonlow2 c.e. degrees are noncontiguous.

Theorem:Contiguous degrees, and also noncontiguous degrees, are downward dense inr.e. degrees.

A direct construction of contiguous degree
Note that 0 is contiguous.
Construct a c.e. set A, not computable, satisfying the following requirements:
Pe : A 6= Wee
Re : If A = ΦW
and We = ΨAe , then there are wtt-reductions Γe and ∆e suchethateA = ΓW
and We = ∆Ae .
eHere, a wtt-reduction, Γ say, is a partial computable functional, with arecursive function bounding the queries.

Techniques:
IDumping and Confirmation

ITree argument

Downey’s Theorem:There is a contiguous nonbranching degree.

Characterizations of contiguous degrees
As c.e. bT-degrees form a distributive upper semi-lattice, contiguous degrees
cannot be top elements of either M3 or N5 in c.e. degrees.

Theorem (Downey and Lempp (1997); Ambos-Spies and Fejer (2001)):
The following are equivalent for a c.e. degree a:
1. a is contiguous;
2. a is locally distributive;
3. a is locally modular;
4. a cannot be the top of any N5 .

Here,
I

a is locally distributive if for any b ≤ a and a1 , a2 with a1 ∨ a2 = a, thereare b1 , b2 with b1 ∨ b2 = b and b1 ≤ a1 , b2 ≤ a2 .

Ia is locally modular if for any b ≤ a and any a1 , a2 with a1 ∨ a2 = a anda1 ≤ b, there are b1 , b2 with b1 ∨ b2 = b and b1 ≤ a1 , b2 ≤ a2 .

Locally noncappable degrees
Theorem: (Downey, Stob)
Any nonzero c.e. degree a bounds a nonzero c.e. degree c such that c isnoncappable below a.

Definition: (Seetapun)
A nonzero c.e. degree a is locally noncappable if there is a c.e. degree c above
a such that no nonzero c.e. degree below c can form a minimal pair with a.
c witnesses that a is locally noncappable.

Theorem: (Seetapun, 1991)
Each nonzero incomplete c.e. degree a is locally noncappable.

Corollaries:
I

Dual of the major subdegree problem is true.
This implies the Continuity of capping (Harrington and Soare, 1989)

I

There is no maximal nonbounding degree, as when a is nonbounding, so isc.

Constructions become easier, in RbT

Here are some examples:

Theorem (Brodhead, Li and Li, 2008):
For a given nontrivial c.e. bT-degree c, there is a c.e. bT-degree a > c suchthat for any c.e. bT-degree x, c ∧ x = 0 iff a ∧ x = 0.
The same statement is also true for c.e. degrees, proved by Seetapun in histhesis.

Theorem (Li, Li, Pan and Tang, 2008):
There are nontrivial c.e. bT-degrees a and c such that for any c.e. bT-degreex, c ∨ x = 00 iff x ≥ a.
That is, there are no major-subdegree in c.e. bT-degrees.

A hierarchy of cuppable degrees, with high/low-ness considered
Theorem (Ambos-Spies, Jockusch, Shore and Soare, 1984):
A c.e. degree a is low-cuppable (to 00 ) iff a is noncappable.

Theorem (Li, Wu and Zhang, 2000):
There exists a cappable (and hence cannot be low-cuppable), low2 cuppable
degree c.
I

This gives rise to a hierarchy of cuppable degrees.
L1 CUP ( L2 CUP ⊆ L3 CUP ⊆ · · · ⊆ H-CUP ⊆ CUP.

Theorem (Greenberg, Ng and Wu, 2020):
There exists a cuppable degree a which is only high-cuppable.
Thus,
only high-CUP ⊆ H-CUP ⊆ CUP.
L1 CUP ( L2 CUP ⊆ L3 CUP ⊆ · · · ( H-CUP ⊆ CUP.

Question: true or fals for the following
L2 CUP ( L3 CUP;

L3 CUP =[n≥1Ln CUP.

High/Low hierarchy
IJump operator - A0 = {e : ΦAe (e) converges}.
00r
high
high2

low2
lowr
0

Another view of cuppable degrees
Definition:
A pair of cuppable degrees, a and b is said to be simultaneously noncuppable,
if there is no incomplete c.e. degree x such thata ∨ x = b ∨ x = 00 .

Theorem (Li, Wu and Yang (2006)):
Such simultaneously noncuppable pairs exist. This implies that the diamondlattice can be embedded into the quotient structure R/NCup preserving 0 and1.
Construct c.e. sets A and B such thatI

A and B are both incomplete and cuppable;

IIf W cups both A and B to K , then W is Turing equivalent to K .

Recently, Tran generalizes this idea to n many degrees, a1 , · · · , an , such thatany n − 1 of them are simultaneously noncuppable, but no incomplete c.e.
degree can cup all of them simultaneously to 00 .
We apply the same idea to c.e. bT-degrees.

Filters and Ideals in RbT , RbT /MbT , RbT /NCupbT

Theorem (Ambos-Spies, 1985)
In RbT , NCapbT , a strong filter, and its complement MbT , an ideal, form an
algebraic decomposition.
Ambos-Spies also pointed out that noncappable may not coincide with
low-cuppable in the c.e. bT-degrees. So the ideal NCupbT may not be asubideal of MbT .

Theorem:
Simultaneously noncuppable pairs also exist in RbT . Thus, the diamond lattice
can be embedded into the quotient structure RbT /NCupbT preserving 0 and 1.

Some work in progress:
I

RbT /MbT , no minimal pairs.

I

E/M, E/NCup (with Ng, Sorbi and Yang)

Thanks!

Contributors to c.e. bT-degrees

I

Ambos-Spies, Fejor, Downey, Lachlan, Lempp, Nies, Shore, StobI

Soare’s book, Odifreddis’ Volume II