An extended Lachlan splitting theorem (Q1919538)

From MaRDI portal





scientific article; zbMATH DE number 908467
Language Label Description Also known as
English
An extended Lachlan splitting theorem
scientific article; zbMATH DE number 908467

    Statements

    An extended Lachlan splitting theorem (English)
    0 references
    0 references
    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

    Identifiers