Classes bounded by incomplete sets (Q1602854)

From MaRDI portal
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