Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
An extended Lachlan splitting theorem - MaRDI portal

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