Classes bounded by incomplete sets (Q1602854)

From MaRDI portal
Revision as of 11:10, 4 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Classes bounded by incomplete sets
scientific article

    Statements

    Classes bounded by incomplete sets (English)
    0 references
    0 references
    0 references
    24 June 2002
    0 references
    By the authors' definition, a class \textbf{K} of computably enumerable (c.e.) degrees is bounded if there exists an incomplete c.e. set \(A\) such that every set in \textbf{K} is m-reducible to \(A\). An example of a bounded class is the class of effectively simple sets. An interesting property is proved: the class of c.e. sets Turing reducible to an incomplete c.e. set \(A\) is bounded iff \(A\) is \(\text{low}_2\).
    0 references
    0 references
    computably enumerable degrees
    0 references
    \(m\)-reducible
    0 references
    bounded class
    0 references
    effectively simple sets
    0 references
    Turing reducible
    0 references