Abstract
We show that the Q-degree of a hyperhypersimple set includes an infinite collection of Q 1-degrees linearly ordered under \({\leq_{Q_1}}\) with order type of the integers and consisting entirely of hyperhypersimple sets. Also, we prove that the c.e. Q 1-degrees are not an upper semilattice. The main result of this paper is that the Q 1-degree of a hemimaximal set contains only one c.e. 1-degree. Analogous results are valid for \({\Pi_1^0}\) s 1-degrees.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Downey R.G., Stob M.: Automorphisms of the lattice of recursively enumerable sets: orbits. Adv. Math. 92(2), 237–265 (1992)
Gill J.T. III, Morris P.H.: On subcreative sets and s-reducibility. J. Symbol. Logic 39, 669–677 (1974)
Kobzev, G.N.: The btt-reducibility. Candidate’s Dissertation, Novosibirsk (1975)
Marchenkov, S.S.: One class of partial sets. Mat. Zametki 20, 473–478 (1976) (Russian); Math. Notes 20, 823–825 (1976) (English translation)
Miller D., Remmel J.B.: Effectively nowhere simple sets. J. Symbol. Logic 49(1), 129–136 (1984)
Morozov A.S.: On a class of recursively enumerable sets. Sibirsk. Mat. Zh. 28(2), 124–128 (1987) (Russian)
Omanadze, R. Sh.: The upper semilattice of recursively enumerable Q-degrees. Algebra i Logika 23(2), 175–184 (1984) (Russian); Algebra and Logic 23, 124–130 (1984) (English translation)
Omanadze R.Sh.: Q-reducibility and nowhere simple sets. Soobshch. Akad. Nauk Gruzin. SSR 127(1), 29–32 (1987) (Russian)
Omanadze, R. Sh.: On the upper semilattice of recursively enumerable sQ-degrees. Algebra i Logika 30(4), 405–413 (1991) (Russian); Algebra and Logic 30(4), 265–271 (1991) (English translation)
Omanadze R. Sh., Sorbi A.: Strong enumeration reducibilities. Arch. Math. Logic 45(7), 869–912 (2006)
Omanadze R. Sh., Sorbi A.: Immunity properties of the s-degrees. Georgian Math. J. 17(3), 563–579 (2010)
Rogers H. Jr: Theory of recursive functions and effective computability. 2nd edn. MIT Press, Cambridge (1987)
Shore R.A.: Nowhere simple sets and the lattice of recursively enumerable sets. J. Symbol. Logic 43(2), 322–330 (1978)
Soare R.I.: Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Springer, Berlin (1987)
Yates C.E.M.: On the degrees of index sets. II. Trans. Am. Math. Soc. 135(1), 249–266 (1969)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Omanadze, R.S., Chitaia, I.O. Q 1-degrees of c.e. sets. Arch. Math. Logic 51, 503–515 (2012). https://doi.org/10.1007/s00153-012-0278-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-012-0278-7