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
Additional Information
- Uri Andrews
- Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
- MR Author ID: 924690
- Email: andrews@math.wisc.edu
- Hristo A. Ganchev
- Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
- MR Author ID: 873534
- Email: ganchev@fmi.uni-sofia.bg
- Rutger Kuyper
- Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
- MR Author ID: 1024217
- Email: mail@rutgerkuyper.com
- Steffen Lempp
- Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
- MR Author ID: 247988
- Email: lempp@math.wisc.edu
- Joseph S. Miller
- Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
- MR Author ID: 735102
- Email: jmiller@math.wisc.edu
- Alexandra A. Soskova
- Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
- MR Author ID: 291122
- Email: asoskova@fmi.uni-sofia.bg
- Mariya I. Soskova
- Affiliation: Department of Mathematics, University of Wisconsin–Madison, Madison, Wisconsin 53706
- MR Author ID: 802392
- Email: msoskova@math.wisc.edu
- Received by editor(s): December 2, 2016
- Received by editor(s) in revised form: January 2, 2018, and April 21, 2018
- Published electronically: May 9, 2019
- Additional Notes: The third author was supported by John Templeton Foundation grant 15619: “Mind, Mechanism and Mathematics: Turing Centenary Research Project”.
The fourth author was partially supported by AMS-Simons Foundation Collaboration Grant 209087 and a binational NSF grant DMS-1101123 entitled “Collaboration in Computability”.
This research was carried out while the fourth and fifth authors were visiting the University of Sofia in Summer 2015 and while the last author was visiting the University of Wisconsin–Madison in Fall 2015.
The fifth author was partially supported by grant #358043 from the Simons Foundation.
The last two authors were supported by National Science Fund of Bulgaria grant #02/16 from 19.12.2016. - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 1631-1670
- MSC (2010): Primary 03D30
- DOI: https://doi.org/10.1090/tran/7604
- MathSciNet review: 3976572