We restrict attention to computably enumerable degrees. Degree \(\mathbf a\) is a major sub-degree of degree \(\mathbf b>\mathbf a\) if \(\mathbf a\) and \(\mathbf b\) join to \(\mathbf 0'\) with exactly the same degrees, i.e., \(\mathbf b \lor\mathbf x = \mathbf 0'\) iff \(\mathbf a \lor \mathbf x = \mathbf 0'\). In 1967 Lachlan asked which degrees, if any, have major sub-degrees. This paper caps a series of partial results by proving that every degree lying properly between \(\mathbf 0\) and \(\mathbf 0'\) has a major sub-degree. The lengthy solution is uniform and effective, providing a computable function \(f\) such that for every \(e\), if \(W_e\) is neither recursive nor of degree \(\mathbf 0'\), the degree of \(W_{f(e)}\) is a major sub-degree of the degree of \(W_e\). In 1974 Yates established the existence of noncuppable degrees, nonzero degrees that join to \(\mathbf 0'\) only with \(\mathbf 0'\) itself. Any nonzero degree less than a noncuppable degree is a major sub-degree of it, answering part of Lachlan's question. In 1983 Jockusch and Shore proved the existence of cuppable degrees that have major sub-degrees, in fact high cuppable degrees with major sub-degrees that are low. In 1991 Seetapun showed that every nonzero low\(_2\) degree has a major sub-degree. Sharpening a discovery of Lachlan, Harrington proved in 1980 that there is a degree other than \(\mathbf 0'\) with the property that whenever a pair of degrees above it joins to \(\mathbf 0'\), one of them must be \(\mathbf 0'\). An immediate corollary of the present paper's result is that no degree is minimal among those with this property.
- A minimal pair of recursively enumerable degrees
- A recursively enumerable degree which will not split over all lesser ones
- Algebraic aspects of the computably enumerable degrees.
- Bounding minimal pairs
- scientific article; zbMATH DE number 3117565 (Why is no real title available?)
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 1955470 (Why is no real title available?)
- scientific article; zbMATH DE number 218585 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3304986 (Why is no real title available?)
- scientific article; zbMATH DE number 3404227 (Why is no real title available?)
- Interpolation and embedding in the recursively enumerable degrees
- Lower Bounds for Pairs of Recursively Enumerable Degrees
- Minimal pairs and high recursively enumerable degrees
- On the degrees less than 0'
- On the Lattice of Recursively Enumerable Sets
- Pseudo Jump Operators. I: The R. E. Case
- Recursively enumerable sets of positive integers and their decision problems
- Splitting and nonsplitting, II: A low2 c.e. degree above which 0′ is not splittable
- The continuity of cupping to \(\text \textbf{0}'\)
- The recursively enumerable degrees are dense
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- Working below a \(low_ 2\) recursively enumerable degree
This page was built for publication: On Lachlan's major sub-degree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q943340)
