A set with barely degree
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\).
- A _2⁰ set with no infinite low subset in either it or its complement
- scientific article; zbMATH DE number 1048046
- A characterization of \(\mathbf {\Sigma}_{2}^{1}\) sets
- scientific article; zbMATH DE number 1404665
- Minimal degrees which are Σ₂⁰ but not Δ₂⁰
- \(\Delta^ 1_ 2\)-sets of reals
- Δ-Sets
- The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
- Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
- A zero set for \(A^{\infty}(D)\) of Hausdorff dimension \(2n-1\)
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)