On cototality and the skip operator in the enumeration degrees

Andrews, Uri; Ganchev, Hristo; Kuyper, Rutger; Lempp, Steffen; Miller, Joseph; Soskova, Alexandra; Soskova, Mariya

doi:10.1090/tran/7604

On cototality and the skip operator in the enumeration degrees
HTML articles powered by AMS MathViewer

by Uri Andrews, Hristo A. Ganchev, Rutger Kuyper, Steffen Lempp, Joseph S. Miller, Alexandra A. Soskova and Mariya I. Soskova PDF

Trans. Amer. Math. Soc. 372 (2019), 1631-1670 Request permission

Abstract:

A set $A\subseteq \omega$ is cototal if it is enumeration reducible to its complement, $\overline {A}$. The skip of $A$ is the uniform upper bound of the complements of all sets enumeration reducible to $A$. These are closely connected: $A$ has cototal degree if and only if it is enumeration reducible to its skip. We study cototality and related properties, using the skip operator as a tool in our investigation. We give many examples of classes of enumeration degrees that either guarantee or prohibit cototality. We also study the skip for its own sake, noting that it has many of the nice properties of the Turing jump, even though the skip of $A$ is not always above $A$ (i.e., not all degrees are cototal). In fact, there is a set that is its own double skip.

References

Seema Ahmad, Some results on the structure of the Sigma(,2) enumeration degrees, ProQuest LLC, Ann Arbor, MI, 1989. Thesis (Ph.D.)–Simon Fraser University (Canada). MR 2687296
Liliana Badillo and Charles M. Harris, An application of 1-genericity in the $\Pi _2^0$ enumeration degrees, Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 7287, Springer, Heidelberg, 2012, pp. 604–620. MR 2979367, DOI 10.1007/978-3-642-29952-0_{5}6
Mingzhong Cai, Hristo A. Ganchev, Steffen Lempp, Joseph S. Miller, and Mariya I. Soskova, Defining totality in the enumeration degrees, J. Amer. Math. Soc. 29 (2016), no. 4, 1051–1067. MR 3522609, DOI 10.1090/jams/848
John William Case, ENUMERATION REDUCIBILITY AND PARTIAL DEGREES, ProQuest LLC, Ann Arbor, MI, 1969. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR 2618471
John Case, Enumeration reducibility and partial degrees, Ann. Math. Logic 2 (1970/71), no. 4, 419–439. MR 282832, DOI 10.1016/0003-4843(71)90003-9
S. B. Cooper, Partial degrees and the density problem. II. The enumeration degrees of the $\Sigma _{2}$ sets are dense, J. Symbolic Logic 49 (1984), no. 2, 503–513. MR 745377, DOI 10.2307/2274181
Hristo Ganchev and Andrea Sorbi, Initial segments of the $\Sigma _2^0$ enumeration degrees, J. Symb. Log. 81 (2016), no. 1, 316–325. MR 3471141, DOI 10.1017/jsl.2014.84
Lance Gutteridge, SOME RESULTS ON ENUMERATION REDUCIBILITY, ProQuest LLC, Ann Arbor, MI, 1971. Thesis (Ph.D.)–Simon Fraser University (Canada). MR 2621884
Charles M. Harris, Goodness in the enumeration and singleton degrees, Arch. Math. Logic 49 (2010), no. 6, 673–691. MR 2660931, DOI 10.1007/s00153-010-0192-9
Emmanuel Jeandel, Enumeration in closure spaces with applications to algebra, CoRR, abs/1505.07578, 2015.
I. Sh. Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log. 3 (2003), no. 2, 257–267. MR 2030087, DOI 10.1142/S0219061303000285
Alexander V. Kuznetsov, Algorithms as operations in algebraic systems, Uspekhi Matematicheskikh Nauk, 13 (1958), 240–241.
Alistair H. Lachlan and Richard A. Shore, The $n$-rea enumeration degrees are dense, Arch. Math. Logic 31 (1992), no. 4, 277–285. MR 1155038, DOI 10.1007/BF01794984
Ethan McCarthy, Cototal enumeration degrees and the Turing degree spectra of minimal subshifts. In press.
Kevin McEvoy, Jumps of quasiminimal enumeration degrees, J. Symbolic Logic 50 (1985), no. 3, 839–848. MR 805690, DOI 10.2307/2274335
Joseph S. Miller, Degrees of unsolvability of continuous functions, J. Symbolic Logic 69 (2004), no. 2, 555–584. MR 2058189, DOI 10.2178/jsl/1082418543
P. G. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland Publishing Co., Amsterdam, 1999. MR 1718169
Andrey V. Pankratov, Some properties of $e$-degrees of cototal sets (Russian), International conference “Logic and applications”, Proceedings, Novosibirsk, 2000.
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
Luis E. Sanchis, Hyperenumeration reducibility, Notre Dame J. Formal Logic 19 (1978), no. 3, 405–415. MR 491102
Alan L. Selman, Arithmetical reducibilities. I, Z. Math. Logik Grundlagen Math. 17 (1971), 335–350. MR 304150, DOI 10.1002/malq.19710170139
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
B. Ya. Solon, Total and co-total enumeration degrees, Izv. Vyssh. Uchebn. Zaved. Mat. 9 (2005), 60–68 (Russian); English transl., Russian Math. (Iz. VUZ) 49 (2005), no. 9, 56–64 (2006). MR 2209448
Boris Ya. Solon, Co-total enumeration degrees, CiE, volume 3988 of Lecture Notes in Computer Science, Springer, 2006, pp. 538–545.
Andrea Sorbi, On quasiminimal e-degrees and total e-degrees, Proc. Amer. Math. Soc. 102 (1988), no. 4, 1005–1008. MR 934883, DOI 10.1090/S0002-9939-1988-0934883-8
Simon Thomas and Jay Williams, The bi-embeddability relation for finitely generated groups II, Arch. Math. Logic 55 (2016), no. 3-4, 385–396. MR 3490909, DOI 10.1007/s00153-015-0455-6