We show that for every intermediate \ s-degree there exists an incomparable \ s-degree. As a consequence, for every intermediate \ Q-degree there exists an incomparable \ Q-degree. We also show how these results can be applied to provide proofs or new proofs of upper density results in local structures of s-degrees and Q-degrees.

We prove that if $A$, $B$ are noncomputable c.e. sets, $A<_{sQ_{1}}B$ and [($B$ is not simple and $A\oplus B\leq _{sQ_{1}}B$) or $B\equiv _{sQ_{1}}B\times \omega $], then there exist infinitely many pairwise $sQ_{1}$-incomparable c.e. sets $\{C_{i}\}_{i\in \omega }$ such that $A<_{sQ_{1}}C_{i}<_{sQ_{1}}B$, for all $i\in \omega $. We also show that there exist infinite collections of $sQ_{1}$-degrees $\{\boldsymbol {a_{i}}\}_{i\in \omega }$ and $\{\boldsymbol {b_{i}}\}_{i\in \omega }$ such that for every $i, j,$ (1) $\boldsymbol {a_{i}}<_{sQ_{1}}\boldsymbol {a_{i+1}}$, $\boldsymbol {b_{j+1}}<_{sQ_{1}}\boldsymbol {b_{j}}$ and $\boldsymbol {a_{i}}<_{sQ_{1}}\boldsymbol {b_{j}}$; (...) (2) every c.e set in $\boldsymbol {a_{i}}$ is a maximal set; and (3) every c.e. set in $\boldsymbol {b_{j}}$ is a non-maximal hyperhypersimple set. We prove that a noncomputable c.e. $sQ$-degree contains either only one or infinitely many c.e. $sQ_{1}$-degrees. The $sQ_{1}$-degrees of c.e. cylinders are dense upper semilattice. (shrink)

We show that the _sQ_-degree of a hypersimple set includes an infinite collection of \(sQ_1\) -degrees linearly ordered under \(\le _{sQ_1}\) with order type of the integers and each c.e. set in these _sQ_-degrees is a hypersimple set. Also, we prove that there exist two c.e. sets having no least upper bound on the \(sQ_1\) -reducibility ordering. We show that the c.e. \(sQ_1\) -degrees are not dense and if _a_ is a c.e. \(sQ_1\) -degree such that \(o_{sQ_1}, then there exist (...) infinitely many pairwise _sQ_-incomputable c.e. _sQ_-degrees \(\{c_i\}_{i\in \omega }\) such that \((\forall \,i)\;(a. (shrink)

We show that the Q-degree of a hyperhypersimple set includes an infinite collection of Q1-degrees linearly ordered under \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\leq_{Q_1}}$$\end{document} with order type of the integers and consisting entirely of hyperhypersimple sets. Also, we prove that the c.e. Q1-degrees are not an upper semilattice. The main result of this paper is that the Q1-degree of a hemimaximal set contains only one c.e. 1-degree. Analogous results are valid for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...) \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi_1^0}$$\end{document}s1-degrees. (shrink)

We show that if M is an r‐maximal set, A is a major subset of M, B is an arbitrary set and, then. We prove that the c.e. ‐degrees are not dense. We also show that there exist infinite collections of ‐degrees and such that the following hold: (i) for every i, j,, and,(ii) each consists entirely of r‐maximal sets, and(iii) each consists entirely of non‐r‐maximal hyperhypersimple sets.

We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤be, which is a natural extension of s-reducibility ≤s. We show that ≤s, ≤be, and enumeration reducibility do not coincide on the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} –sets, and the structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that the first order theory (...) of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper (Z Math Logik Grundlag Math 33:537–560, 1987). (shrink)

For any enumeration degree let be the set of s-degrees contained in . We answer an open question of Watson by showing that if is a nontrivial -enumeration degree, then has no least element. We also show that every countable partial order embeds into . Finally, we construct -sets A and B such that B≤eA but for every X≡eB, XsA.

We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}$ and singleton ${({\mathcal D}_{\rm s})}$ degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings ${\iota_s}$ and ${\hat{\iota}_s}$ of, respectively, ${{\mathcal D}_{\rm e}}$ and ${{\mathcal D}_{\rm T}}$ (the Turing degrees) into (...) ${{\mathcal D}_{\rm s}}$ , and we show that the image of ${{\mathcal D}_{\rm T}}$ under ${\hat{\iota}_s}$ is precisely the class of retraceable singleton degrees. We define the notion of a good enumeration, or singleton, degree to be the property of containing the set of good stages of some good approximation, and we show that ${\iota_s}$ preserves the latter, as also other naturally arising properties such as that of totality or of being ${\Gamma^0_n}$ , for ${\Gamma \in \{\Sigma,\Pi,\Delta\}}$ and n > 0. We prove that the good enumeration and singleton degrees are immune and that the good ${\Sigma^0_2}$ singleton degrees are hyperimmune. Finally we show that, for singleton degrees a s < b s such that b s is good, any countable partial order can be embedded in the interval (a s, b s). (shrink)