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
17 December 2000
0 references
relative computabilty
0 references
relative enumerability
0 references
computably enumerable sets
0 references
0.87539333
0 references
0.84958315
0 references
0.8454157
0 references
0 references
0.8256673
0 references
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