Final Segments of Difference-C.E. Degrees

Definitions and mathematical statement

A set $A\subseteq{\mathbb{N}}$ is difference computably enumerable (d.c.e.) if $A=U\setminus V$ for computably enumerable sets $U,V\subseteq{\mathbb{N}}$. Under the conventional interpretation of "degrees" as Turing degrees, write $A\leq_T B$ when membership in $A$ is computable with oracle $B$, and write $A\equiv_T B$ when both reductions hold. Let \[ \mathcal D_{\mathrm{d.c.e.}}=\{\deg_T(A):A\subseteq{\mathbb{N}}\text{ is d.c.e.}\}, \] ordered by Turing reducibility. Its greatest element is $\mathbf 0'$, the Turing degree of the halting set.

For $\mathbf a\in\mathcal D_{\mathrm{d.c.e.}}$, define the principal final segment, including both endpoints, by \[ F_{\mathbf a}=\{\mathbf b\in\mathcal D_{\mathrm{d.c.e.}}:\mathbf a\leq_T\mathbf b\leq_T\mathbf 0'\}. \] Under the interpretation that the source asks about principal final segments, the classification problem is: characterize exactly the finite nonempty partially ordered sets $(P,\preceq)$ for which there exist $\mathbf a\in\mathcal D_{\mathrm{d.c.e.}}$ and a bijection $f:P\to F_{\mathbf a}$ satisfying \[ \forall x,y\in P,\qquad x\preceq y\ \Longleftrightarrow\ f(x)\leq_T f(y). \] Thus finiteness concerns the entire final segment in the ambient d.c.e. degrees.

The supplied question is: "Which finite final segments occur in the degrees of d.c.e. sets?" It does not explicitly specify the reducibility or whether final segments must be principal. A general final segment could instead mean a nonempty upward closed subset $F\subseteq\mathcal D_{\mathrm{d.c.e.}}$, satisfying \[ \forall\mathbf b,\mathbf c\in\mathcal D_{\mathrm{d.c.e.}},\qquad (\mathbf b\in F\ \land\ \mathbf b\leq_T\mathbf c)\ \Longrightarrow\ \mathbf c\in F. \] Such a set need not have a least element. If this broader meaning is intended, the target is the order-isomorphism types of all finite such $F$, without a principality requirement. The intended convention requires source confirmation.

The supplied dated curation labels the problem partially solved and reports that Lempp and collaborators proved realization of every finite distributive lattice as a final segment, while the complete classification remains unresolved. These are supplied literature assessments, not independently verified claims in this draft.

Short English statement

Classify the finite ordered structures that occur as final segments of the Turing degrees containing d.c.e. sets. The source leaves implicit whether a final segment must have a least degree; the principal-segment formulation above is conditional on that convention. The supplied partially solved status and distributive-lattice realization claim require independent review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003689$, title "Final Segments of Difference-C.E. Degrees," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2018.
• Supplied source citation: Computability Theory (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/1, pp. 5--41. https://doi.org/10.4171/owr/2018/1. The record describes these reports as documenting mathematical workshops and their open-problem discussions. The relationship between the citation's 2019 designation and the recorded 2018 year requires bibliographic review.
• Supplied literature reference: Lempp et al., "Finite final segments." https://arxiv.org/abs/2403.04254. The record supplies no complete author list or more detailed bibliographic information.
• Supplied literature reference: "Oberwolfach report." https://doi.org/10.4171/owr/2018/1.
• Literature assessment checked at 2026-08-21: supplied dated curation, not independently verified. It reports that every finite distributive lattice occurs as a final segment and that the full classification remains unresolved. The background explicitly describes this as dated literature triage derived from supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports manual semantic, typographic, and LaTeX review. This is supplied verification metadata, not independent mathematical or source verification by this draft.