Cupping computably enumerable degrees simultaneously
Wu Guohua
joint with Hong Hanh Tran

Nanyang Technological University, Singapore

CiE 2023, Batumi

Basics:

I

Computable (decidable) sets,

I

Computably enumerable (semi-decidable) sets

I

Turing reduction and Turing degrees

IA c.e. degree is a Turing degrees containing some c.e. sets

I

C.e. degrees form a upper-semi-lattice: given c.e. degrees
given c.e. degrees a and b, a ∨ b, the supremum of a and b always exists(but not for a ∧ b, the infimum)
I Friedberg-Muchinik theorem, Sacks’ theorems: splitting and density,
Lachlan’s nonsplitting theorem
I High/Low hierachy,
I Cups (to 00 ) and Caps (to 0), Cuppable and CappableISacks’ splitting and Lachlan’s nonsplitting
Sacks’ Splitting Theorem:
There are incomparable c.e. degrees a and b with a ∨ b = 00 .
00

r
@a@r

b

@@rr
0

Sacks’ Density Theorem:
The c.e. degrees are dense.

Lachlan’s nonsplitting Theorem (Harrington versioin):
There is an incomparable c.e. degrees c such that 00 is not splittable above c.

Turing Jump - A0 = {e : ΦAe (e) converges}
IIf A ≡T B, then A0 ≡T B 0 .

IThe jump of 0 is 00 .

I 0 is monotonic.

00

rhighhigh2

low2lowr0Cuppable/Noncuppable
Definition:
A c.e. degree a is cuppable if there is an incomplete c.e. degree c such thata ∨ c = 00 .

Continuity of Cupping (Ambos-Spies, Lachlan and Soare):
Given two incomplete, incomputable c.e. degrees a and b with a ∨ b = 00 ,there exists a c.e. degree c < b such that a ∨ c = 00 .

Definition:
A c.e. degree a is plus-cupping if every nonzero c.e. degree c below a iscuppable.

Theorem (Yates):
There are incomputable c.e. degrees which are noncuppable.

Corollary:Plus-cupping degrees and noncuppable degrees form minimal pairs.
Here nonzero c.e. degrees a and b form a minimal pair if a ∧ b = 0.

Minimal pairs, Cappable/Noncappable
Lachlan and Yates first proved the existence of minimal pairs.
00

rabr
@@r

@@r
0

Continuity of Capping (Harrington and Soare):
Given two incomplete, incomputable c.e. degrees a and b with a ∧ b = 0, there
exists a c.e. degree c > b such that a ∧ c = 0.

Definition:
A c.e. degree c is cappable if c is either 0 or a part of a minimal pair.
We have seen that plus-cupping and noncuppable degrees are cappable.
Equivalent Charaterizations: A c.e. degree a is noncappable if and only if oneof the following is true
I a is low-cuppable
I a is promptly simple

The ideal M of Cappable degrees and the quotient structure R/M

Theorem (Ambos-Spies, Jockusch, Shore and Soare, 1984):
In R, the computably enumerable degrees, cappable degrees form an ideal andnoncappable degrees form a strong filter.
Denote this ideal as M.
Consider the quotient structure R/M.
There are no minimal pairs in this structure, as noncappable degrees form astrong filter in R.

Open: dense?

Note that noncuppable degrees for another ideal in R, denoted as NCup.
Consider the quotient structure R/NCup.

Question:
Are there minimal pairs in R/NCup?

Answer: YES
It was first proved by Li, Wu and Yang around 2006.
But, all nonzero elements are cuppable, in R/NCup, of course.

Theorem (Li, Wu and Yang, 2006):
There are two incomplete cuppable degrees a and b such that no incomplete
degree can cup both a and b to 00 .
That is, a and b themselves are cuppable, but they cannot be cupped to 00
simultaneously.
I[a] and [b] form a minimal pair in R/NCup, as for any [c] below both [a]and [b], if [c] 6= [0], then c is cuppable and we can let e incomplete withe ∨ c = 00 , and this e cups both a and b to 00 , which is impossible by ourchoice of a and b.

Proof idea: Construct c.e. sets (incomplete incomputable) A, B, C , D andpartial computable functionals Γ and ∆ such thatC cups A to ∅0 via Γ: ∅0 = ΓC ⊕AI D cups B to ∅0 via ∆: ∅0 = ∆D⊕BIIee
For any c.e. We , if ΦA⊕W= ΨB⊕W= ∅0 , then there is a partialeee
computable functional Ωe such that ∅0 = ΩWe .

We cannot construct A (via C ) without B (via D) as we are constructing Cincomplete:IC cups A to ∅0 via Γ: ∅0 = ΓC ⊕AIee
For any c.e. We , if ΦA⊕W= ΨB⊕W= ∅0 , then there is a partialeee
computable functional Ωe such that ∅0 = ΩWe .

To make C incomplete, we need to enumerate numbers into A from time toetime, and this can cause the computation ΦA⊕W(x) to change, and before thee0We
next agreement, x may enter ∅ , and lead to Ωe (x) = 0 6= ∅0 (x).
Luckily, we have B-side to help us to record ∅0 , to make sure that after we puta number into A, if ∅0 changes at x, We must have a corresponding change, as
ΨeB⊕We (x) changes and B has no change.
We introduce an auxiliary set L to force changes from We .
IIf ΦeA⊕We = ΨeB⊕We = L ⊕ ∅0 , then there is a partial computable functionaleΩe such that ∅0 = ΩWe .

Theorem (with Tran):
For each n ≥ 1, there are n + 1 c.e. degrees a0 , a1 , · · · , an , such that any nmany of them are simultaneously cuppable, but no incomplete c.e. degree cancup all of them to 00 simultaneously.

In this paper, we provide a detailed proof for n = 2:
There are c.e. degrees a, b, c such that any two of them are simultaneously
cuppable, but no incomplete c.e. degree can cup all of them to 00
simultaneously.

More on R/NCup

We were able to prove that the diamond lattice can be embedded into R/NCuppreserving 0 and 1.
IThe paper will be out soon.

I

Embedding of N5 , and perhaps M3 .

Many algebraic questions are not attacked. Of course, we can consider
model-theoretic properties of this structure.
Almost deep degrees form an ideal of R.

Thanks!