On the bounded quasi‐degrees of c.e. sets
Roland Sh. Omanadze · Mathematical logic quarterly · 2013
Abstract We study the degree structure of bQ‐reducibility and we prove that for any noncomputable c.e. incomplete bQ‐degree a, there exists a nonspeedable bQ‐degree incomparable with it. The structure \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathcal {D}_{\mbox{bs}}$\end{document} of the \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mbox{bs}$\end{document} ‐degrees is not elementary equivalent neither to the structure of the \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mbox{be}$\end{document} ‐degrees nor to the structure of the \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mbox{e}$\end{document} ‐degrees. If c.e. degrees a and b form a minimal pair in the c.e. bQ‐degrees, then a and b form a minimal pair in the bQ‐degrees. Also, for every simple set S there is a noncomputable nonspeedable set A which is bQ‐incomparable with S and bQ‐degrees of S and A does not form a minimal pair.