Finite final segments of the d.c.e. Turing degrees beyond the distributive case: join-semidistributive and interval-dismantlable lattices, and the general characterization

The d.c.e. Turing degrees — degrees of differences of two computably enumerable sets, the second level of the Ershov hierarchy — form an upper semilattice below the halting problem degree. A finite final segment with a least element is exactly a finite interval, hence a finite lattice. After the 1991 nondensity theorem realized the two-element chain this way, Lempp, Liu, Liu, Ng, Peng and Wu (arXiv:2403.04254, 2024) proved that every finite distributive lattice occurs as such a final segment, and deduced undecidability of the ∃∀∃-theory of the d.c.e. degrees in the partial-order language. They conjecture the theorem extends to much wider classes — the finite join-semidistributive lattices and the interval-dismantlable lattices — and pose the general problem of determining exactly which finite lattices occur as finite final segments of the d.c.e. degrees, noting that extension to all finite lattices appears out of reach but not impossible. As of August 2026, no extension, partial result, or refutation is known. The conjecture and the characterization problem remain open: no finite non-distributive lattice is known to occur as a final segment, and none is known not to.

Background

The d.c.e. (difference of computably enumerable) sets form the second level of the Ershov hierarchy: a set is c.e. if it has a computable enumeration, d.c.e. if it is the difference of two c.e. sets, and more generally ω-c.e. if each membership value stabilizes after a computably bounded number of mind changes. A Turing degree is an equivalence class of sets under computability relative to an oracle, and the d.c.e. degrees, written $\mathbf{D}_2$ , form an upper semilattice between $\mathbf{0}$ and $\mathbf{0}'$ (the degree of the halting problem): joins exist, but meets (greatest lower bounds) need not, so $\mathbf{D}_2$ is not a lattice.

A final segment of $\mathbf{D}_2$ is an upward-closed set of degrees; a finite final segment with a least element is exactly a finite interval $[\mathbf{a},\mathbf{0}']$ , and any such finite interval is automatically a lattice. Following the source paper, an embedding of a finite lattice $\mathcal{L}$ (with least element $0$ and greatest element $1$ ) into $\mathbf{D}_2$ as a final segment is a map $j\colon\mathcal{L}\to\mathbf{D}_2$ such that: (i) $j(1)=\mathbf{0}'$ ; (ii) $a\le b$ implies $j(a)\le j(b)$ ; (iii) $a\nleq b$ implies $j(a)\nleq j(b)$ ; and (iv) for every d.c.e. degree $\mathbf{u}$ , $\mathbf{u}\cup j(0)=j(a)$ for some $a\in\mathcal{L}$ . Condition (iv) says the image of $j$ is precisely the interval $[j(0),\mathbf{0}']$ : every d.c.e. degree above $j(0)$ lies in the image. In particular, joins in $\mathcal{L}$ are preserved, meets in the image agree with any meets that exist in $\mathbf{D}_2$ , and the top of $\mathcal{L}$ lands on $\mathbf{0}'$ , so realizing $\mathcal{L}$ as a final segment realizes it as a finite interval of $\mathbf{D}_2$ ending at $\mathbf{0}'$ — and any finite interval of $\mathbf{D}_2$ is automatically a lattice, since in a finite poset with all joins the meet of a set is the join of its lower bounds.

The study of $\mathbf{D}_2$ goes back to the Ershov hierarchy in the late 1960s and to the construction of the first properly d.c.e. degree (a d.c.e. degree containing no c.e. set) in the early 1970s. The landmark D.C.E. Nondensity Theorem of Cooper, Harrington, Lachlan, Lempp and Soare (1991; with a 2017 corrigendum) established a maximal incomplete d.c.e. degree — equivalently, the two-element chain occurs as a finite final segment, and the d.c.e. degrees are not densely ordered. This made the isomorphism types of all finite final segments of the d.c.e. degrees a natural question. Before the source paper, the case of finite Boolean algebras had been settled in work of the same collaboration, recorded in Yong Liu's 2017 doctoral thesis. Lempp, Liu, Liu, Ng, Peng and Wu (2024) then proved the general distributive case: every finite distributive lattice is isomorphic to a final segment of $\mathbf{D}_2$ (their Theorem 1.3), with the analogous statement for the ω-c.e. degrees (their Theorem 6.1). The proof is a priority argument on a tree of strategies — the standard technique of computability theory for reconciling countably many conflicting requirements, here at the $\mathbf{0}'''$ level (fourth jump) — building on the Nondensity Theorem machinery and organized through the classical representation of a finite distributive lattice as the lattice of down-closed sets of its join-irreducible elements (elements other than $0$ that are not the join of two strictly smaller elements). As a corollary, the undecidability of the first-order theory of $\mathbf{D}_2$ in the language of partial ordering, due to Cai, Shore and Slaman (2012), was sharpened to its ∃∀∃-fragment (sentences with three alternating quantifier blocks).

The conjectured extension targets the following lattice classes. A lattice is distributive if meet distributes over join; it is join-semidistributive ( $\mathrm{SD}_\vee$ ) if $x\vee y=x\vee z$ implies $x\vee(y\wedge z)=x\vee y$ for all elements $x,y,z$ . Distributivity implies join-semidistributivity and the containment is proper, so the finite join-semidistributive lattices form a strictly larger class than the finite distributive ones. Adaricheva, Hyndman, Lempp and Nation (2018) introduced the interval dismantlable lattices: finite lattices that can be partitioned into an ideal (a downward-closed subset closed under joins) and a filter (the order-dual notion), each of which can again be so partitioned, recursively, until only one-element lattices remain; they gave a quasi-equational basis for this class and showed that infinitely many minimal interval non-dismantlable lattices exist. The source paper conjectures its theorem extends to the join-semidistributive and — "even", in the authors' phrasing, indicating they regard it as the wider target — the interval-dismantlable lattices. For perspective on the limit case, Lachlan and Soare (1980) showed that not every finite lattice embeds into the c.e. degrees, so universality of finite-lattice embeddings is a genuine structural question in each degree structure; no analogous obstruction is known for the d.c.e. degrees.

Problem Statement

The problem, stated by Lempp, Liu, Liu, Ng, Peng and Wu in the introduction of arXiv:2403.04254, has one overarching objective: determine the isomorphism types of the finite final segments of the d.c.e. Turing degrees — that is, characterize exactly which finite lattices $\mathcal{L}$ admit an embedding $j\colon\mathcal{L}\to\mathbf{D}_2$ as a final segment, meaning $j(1)=\mathbf{0}'$ , $j$ preserves and reflects the order, and for every d.c.e. degree $\mathbf{u}$ there is $a\in\mathcal{L}$ with $\mathbf{u}\cup j(0)=j(a)$ (the image is exactly the interval $[j(0),\mathbf{0}']$ ).

The source paper resolves the case where $\mathcal{L}$ is distributive and conjectures, as stepping stones toward the general characterization:

(Join-semidistributive case) Does every finite join-semidistributive lattice embed into the d.c.e. degrees as a final segment?
(Interval-dismantlable case) Does every finite interval-dismantlable lattice in the sense of Adaricheva, Hyndman, Lempp and Nation embed into the d.c.e. degrees as a final segment?
(Limit case) Does every finite lattice embed into the d.c.e. degrees as a final segment — a possibility the authors describe as currently appearing "out of reach but not impossible"? If not every finite lattice occurs, which ones fail, and what structural property of the d.c.e. degrees obstructs them?

These items are successive instances of the single characterization objective: items 1 and 2 are the authors' conjectured positive steps (the join-semidistributive lattices containing all distributive ones, and the interval-dismantlable lattices forming, in the authors' phrasing, an even wider target), and item 3 is the general question. The scientific objective — knowing exactly which finite lattices occur as finite final segments of the d.c.e. degrees — is the same in each case.

References

Lempp, Steffen; Liu, Yiqun; Liu, Yong; Ng, Keng Meng; Peng, Cheng; Wu, Guohua. Finite final segments of the d.c.e. Turing degrees. arXiv:2403.04254 (2024). DOI: 10.48550/arXiv.2403.04254. https://arxiv.org/abs/2403.04254
Adaricheva, Kira V.; Hyndman, Jennifer P.; Lempp, Steffen; Nation, James B. Interval Dismantlable Lattices. Order 35 (2018), no. 1, 133–137. DOI: 10.1007/s11083-017-9422-7. https://doi.org/10.1007/s11083-017-9422-7
Cooper, S. Barry; Harrington, Leo; Lachlan, Alistair H.; Lempp, Steffen; Soare, Robert I. The d.r.e. degrees are not dense. Annals of Pure and Applied Logic 55 (1991), no. 2, 125–151. DOI: 10.1016/0168-0072(91)90005-7. https://doi.org/10.1016/0168-0072(91)90005-7
Cooper, S. Barry; Harrington, Leo; Lachlan, Alistair H.; Lempp, Steffen; Soare, Robert I. Corrigendum to "The d.r.e. degrees are not dense" [Ann. Pure Appl. Logic 55 (1991) 125–151]. Annals of Pure and Applied Logic 168 (2017), no. 12, 2164–2165. DOI: 10.1016/j.apal.2017.07.001. https://doi.org/10.1016/j.apal.2017.07.001
Cai, Mingzhong; Shore, Richard A.; Slaman, Theodore A. The n-r.e. degrees: undecidability and Σ1 substructures. Journal of Mathematical Logic 12 (2012), no. 1, article 1250005. DOI: 10.1142/S0219061312500055. https://doi.org/10.1142/S0219061312500055
Lachlan, A. H.; Soare, R. I. Not every finite lattice is embeddable in the recursively enumerable degrees. Advances in Mathematics 37 (1980), no. 1, 74–82. DOI: 10.1016/0001-8708(80)90027-4. https://doi.org/10.1016/0001-8708(80)90027-4
Andrews, Uri; Kuyper, Rutger; Lempp, Steffen; Soskova, Mariya I.; Yamaleev, Mars M. Nondensity of Double Bubbles in the D.C.E. Degrees. In: Computability and Complexity (essays dedicated to Rodney G. Downey on the occasion of his 60th birthday), Lecture Notes in Computer Science 10010, Springer, 2017, 547–562. DOI: 10.1007/978-3-319-50062-1_33. https://doi.org/10.1007/978-3-319-50062-1_33
Liu, Yiqun; Liu, Yong; Peng, Cheng. Isolated d.c.e. degrees and Σ1 induction. Annals of Pure and Applied Logic 177 (2026), no. 3, article 103678. DOI: 10.1016/j.apal.2025.103678. arXiv:2508.05951. https://doi.org/10.1016/j.apal.2025.103678
Liu, Yong; Peng, Cheng. Bi-Isolated d.c.e. Degrees and Σ_1 Induction. arXiv:2512.03778 (2025). https://arxiv.org/abs/2512.03778
Barmpalias, George; Bazhenov, Nikolay; Chong, Chi Tat; Dai, Wei; Gao, Su; Goh, Jun Le; He, Jialiang; Ng, Keng Meng Selwyn; Nies, Andre; Slaman, Theodore; Thornton, Riley; Wang, Wei; Yu, Jing; Yu, Liang. Open Problems in Computability Theory and Descriptive Set Theory. arXiv:2507.03972 (2025). https://arxiv.org/abs/2507.03972
Liu, Yong. The structure of d.r.e. degrees. Ph.D. thesis, National University of Singapore (2017); cited as [Li17] in arXiv:2403.04254.
Arslanov, Marat M.; Kalimullin, Iskander Sh. A survey of results on the d-c.e. and n-c.e. degrees. In: Computability and Complexity (essays dedicated to Rodney G. Downey on the occasion of his 60th birthday), Lecture Notes in Computer Science 10010, Springer, 2017, 469–478. DOI: 10.1007/978-3-319-50062-1_27. https://doi.org/10.1007/978-3-319-50062-1_27