A set with barely degree

From MaRDI portal





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\).











This page was built for publication: A set with barely degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4948537)