A set with barely degree (Q4948537)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1429782
Language Label Description Also known as
default for all languages
No label defined
    English
    A set with barely degree
    scientific article; zbMATH DE number 1429782

      Statements

      A set with barely degree (English)
      0 references
      0 references
      0 references
      0 references
      17 December 2000
      0 references
      relative computabilty
      0 references
      relative enumerability
      0 references
      computably enumerable sets
      0 references
      The paper is concerned with a fundamental notion of computability theory, namely relative enumerability. The authors study \(\Sigma^0_2\) sets and degrees, and their relations with the computably enumerable sets from which they can be computably enumerated. The situation when a \(\Sigma^0_2\) set \(A\) has \(\Sigma^W_1\) degree for some computably enumerable set \(W\), where \(W\) must be complete, is called in the paper: \(A\) is barely \(\Sigma^0_2\). The authors show the existence of barely \(\Sigma^0_2\) degrees by the main theorem of the paper: There exists a 3-computably enumerable set \(A\) such that for all computably enumerable sets \(W\), \(A\) has \(\Sigma^W_1\) degree if and only if \(W \equiv_T {\emptyset}^\prime\). The above result implies that there is a \(\Delta^0_2\) degree which fails to be computably enumerable in any computably enumerable set strictly below \({\emptyset}^\prime\).
      0 references

      Identifiers