An extended Lachlan splitting theorem
If \(a,b\) are r.e. degrees, then the inf of \(a,b\) is (if it exists) an r.e. degree \(c\) such that (1) \(c \leq_Ta\), (2) \(c \leq_Tb\), and (3) for all \(d\), if \(d \leq_Ta\) and \(d \leq_Tb\) then \(d \leq_Tc\). A minimal pair of r.e. degrees is a pair with \(\inf \emptyset\). An r.e. degree \(d\) is the top of a 1-diamond if there exists a minimal pair \(a,b\) such that \(d = a \oplus b\). An r.e. degree \(d\) is the top of an \(n\)-diamond if there exists a minimal pair \(a,b\) such that the inf of \(a,b\) exists and is an \(n-1\) diamond. Lachlan and Yates showed that minimal pairs exist. This paper shows that every top of a 1-diamond is also the top of an \(n\)-diamond for every \(n>1\). The proof uses a priority construction on a tree.
- A minimal pair of recursively enumerable degrees
- An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
- Decomposition of Recursively Enumerable Degrees
- Highness and bounding minimal pairs
- Lower Bounds for Pairs of Recursively Enumerable Degrees
- The weak truth table degrees of recursively enumerable sets
- Wtt-degrees and T-degrees of r.e. sets
- A parametric version of Forstnerič's splitting lemma
- A splitting theorem for blocks
- A generalization of the Lorentzian splitting theorem
- scientific article; zbMATH DE number 3845570 (Why is no real title available?)
- On Zimmermann-Huisgen's Splitting Theorem
- scientific article; zbMATH DE number 1101532 (Why is no real title available?)
- New Computational Paradigms
This page was built for publication: An extended Lachlan splitting theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1919538)
