An extended Lachlan splitting theorem (Q1919538)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An extended Lachlan splitting theorem |
scientific article |
Statements
An extended Lachlan splitting theorem (English)
0 references
23 July 1996
0 references
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.
0 references
recursively enumerable degrees
0 references
priority argument
0 references
top of an \(n\)-diamond
0 references
minimal pair
0 references
top of a 1-diamond
0 references