The computably enumerable degrees are locally non-cappable (Q1879005)

From MaRDI portal
Revision as of 20:22, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
The computably enumerable degrees are locally non-cappable
scientific article

    Statements

    The computably enumerable degrees are locally non-cappable (English)
    0 references
    0 references
    22 September 2004
    0 references
    The bulk of this paper is devoted to a proof that every non-computable incomplete computably enumerable degree is locally non-cappable. Seetapun proved this in his thesis, but the new proof given here is a priority argument patterned after \textit{R. Soare}'s link/list proof of the Lachlan non-bounding theorem [Recursively enumerable sets and degrees, Berlin: Springer-Verlag (1987; Zbl 0667.03030)]. An immediate corollary is that there is no maximal non-bounding computably enumerable degree.
    0 references
    0 references
    computably enumerable degree
    0 references
    maximal
    0 references
    non-bounding
    0 references
    cappable
    0 references
    link/list
    0 references
    0 references