Definability via Kalimullin pairs in the structure of the enumeration degrees
HTML articles powered by AMS MathViewer
- by Hristo A. Ganchev and Mariya I. Soskova PDF
- Trans. Amer. Math. Soc. 367 (2015), 4873-4893 Request permission
Abstract:
We give an alternative definition of the enumeration jump operator. We prove that the class of total enumeration degrees and the class of low enumeration degrees are first order definable in the local substructure of the enumeration degree, consisting of the elements bounded by ${\mathbf {0}_e}’$.References
- M. M. Arslanov, I. Sh. Kalimullin, and S. B. Kuper, Splitting properties of total enumeration degrees, Algebra Logika 42 (2003), no. 1, 3–25, 125 (Russian, with Russian summary); English transl., Algebra Logic 42 (2003), no. 1, 1–13. MR 1988020, DOI 10.1023/A:1022660222520
- 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
- S. Barry Cooper, Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion theory week (Oberwolfach, 1989) Lecture Notes in Math., vol. 1432, Springer, Berlin, 1990, pp. 57–110. MR 1071514, DOI 10.1007/BFb0086114
- Kevin McEvoy and S. Barry Cooper, On minimal pairs of enumeration degrees, J. Symbolic Logic 50 (1985), no. 4, 983–1001 (1986). MR 820127, DOI 10.2307/2273985
- Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117–125. MR 112831, DOI 10.1002/malq.19590050703
- Hristo Ganchev and Mariya I. Soskova, Cupping and definability in the local structure of the enumeration degrees, J. Symbolic Logic 77 (2012), no. 1, 133–158. MR 2951634, DOI 10.2178/jsl/1327068696
- Hristo Ganchev and Mariya Soskova, The high/low hierarchy in the local structure of the $\omega$-enumeration degrees, Ann. Pure Appl. Logic 163 (2012), no. 5, 547–566. MR 2880272, DOI 10.1016/j.apal.2010.10.004
- Hristo Ganchev and Mariya Soskova, Interpreting true arithmetic in the local structure of the enumeration degrees, J. Symbolic Logic 77 (2012), no. 4, 1184–1194. MR 3051620, DOI 10.2178/jsl.7704070
- Matthew Giorgi, Andrea Sorbi, and Yue Yang, Properly $\Sigma _2^0$ enumeration degrees and the high/low hierarchy, J. Symbolic Logic 71 (2006), no. 4, 1125–1144. MR 2275852, DOI 10.2178/jsl/1164060448
- Carl G. Jockusch Jr. and James C. Owings Jr., Weakly semirecursive sets, J. Symbolic Logic 55 (1990), no. 2, 637–644. MR 1056377, DOI 10.2307/2274653
- Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. MR 220595, DOI 10.1090/S0002-9947-1968-0220595-7
- 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
- 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
- Kevin McEvoy, Jumps of quasiminimal enumeration degrees, J. Symbolic Logic 50 (1985), no. 3, 839–848. MR 805690, DOI 10.2307/2274335
- André Nies, Richard A. Shore, and Theodore A. Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77 (1998), no. 2, 241–291. MR 1635141, DOI 10.1112/S002461159800046X
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- M. Rozinas, The semilattice of e-degrees, Recursive functions (Russian), Ivanov. Gos. Univ., Ivanovo, 1978, pp. 71–84 (Russian). MR 604944
- Richard A. Shore, Biinterpretability up to double jump in the degrees below $0’$, Proc. Amer. Math. Soc. 142 (2014), no. 1, 351–360. MR 3119208, DOI 10.1090/S0002-9939-2013-11719-3
- Richard A. Shore, Degree structures: local and global investigations, Bull. Symbolic Logic 12 (2006), no. 3, 369–389. MR 2248589, DOI 10.2178/bsl/1154698739
- Richard A. Shore and Theodore A. Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), no. 5-6, 711–722. MR 1739227, DOI 10.4310/MRL.1999.v6.n6.a10
- Theodore A. Slaman, Global properties of the Turing degrees and the Turing jump, Computational prospects of infinity. Part I. Tutorials, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 14, World Sci. Publ., Hackensack, NJ, 2008, pp. 83–101. MR 2449478, DOI 10.1142/9789812794055_{0}002
- Andrea Sorbi, The enumeration degrees of the $\Sigma ^0_2$ sets, Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., vol. 187, Dekker, New York, 1997, pp. 303–330. MR 1455141
- I. N. Soskov, A jump inversion theorem for the enumeration jump, Arch. Math. Logic 39 (2000), no. 6, 417–437. MR 1773778, DOI 10.1007/s001530050156
Additional Information
- Hristo A. Ganchev
- Affiliation: Faculty of Mathematics and Informatics, Sofia University, 1164 Sofia, Bulgaria
- MR Author ID: 873534
- Email: ganchev@fmi.uni-sofia.bg
- Mariya I. Soskova
- Affiliation: Department of Mathematics, University of California Berkeley, Berkeley, California 94720
- Address at time of publication: Faculty of Mathematics and Informatics, Sofia University, 1164 Sofia, Bulgaria
- MR Author ID: 802392
- Email: msoskova@fmi.uni-sofia.bg
- Received by editor(s): November 12, 2012
- Received by editor(s) in revised form: April 10, 2013
- Published electronically: November 24, 2014
- Additional Notes: This research was supported by a BNSF grant No. DMU 03/07/12.12.2011 and by Sofia University SF grant No. 131/09.05.2012
The second author was supported by a Marie Curie international outgoing fellowship STRIDE (298471) within the 7th European Community Framework Programme and the Isaac Newton Institute for Mathematical Sciences in the programme ‘Semantics and Syntax’ - © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 367 (2015), 4873-4893
- MSC (2010): Primary 03D30
- DOI: https://doi.org/10.1090/S0002-9947-2014-06157-6
- MathSciNet review: 3335403