We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\rm ss} B}$$\end{document} (respectively, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\overline{\rm s}} B}$$\end{document}): here \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm (...) s}}}$$\end{document} is the finite-branch version of s-reducibility, ≤ss is the computably bounded version of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm s}}}$$\end{document}, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}}$$\end{document} is the complement of the halting set. Restriction to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} sets provides a similar characterization of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} hyperhyperimmune sets in terms of s-reducibility. We also show that no \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \geq_{\overline{\rm s}}\overline{K}}$$\end{document} is hyperhyperimmune. As a consequence, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\deg_{\rm s}(\overline{K})}$$\end{document} is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed. (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 investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, (...) we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (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 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)

In this paper, we study the lattice of r.e. subspaces of a recursively presented vector space V ∞ with regard to the various complexity-theoretic speed-up properties such as speedable, effectively speedable, levelable, and effectively levelable introduced by Blum and Marques. In particular, we study the interplay between an r.e. basis A for a subspace V of V ∞ and V with regard to these properties. We show for example that if A or V is speedable , then V is levelable (...) . We also show that if A is an r.e. subset of a recursive basis for V ∞ , then A is levelable iff V is speedable while it is not the case that A is levelable iff V is speedable. We also provide several contrasts between the lattice of r.e. subspaces and the lattice of r.e. sets with respect to these speed-up properties. For example, every maximal set is levelable but we show that there exist supermaximal spaces which are nonspeedable in all possible r.e. degrees as well as supermaximal spaces which are levelable in all r.e. degrees which contain levelable sets. (shrink)