Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Definability via Kalimullin pairs in the structure of the enumeration degrees


Authors: Hristo A. Ganchev and Mariya I. Soskova
Journal: Trans. Amer. Math. Soc. 367 (2015), 4873-4893
MSC (2010): Primary 03D30
DOI: https://doi.org/10.1090/S0002-9947-2014-06157-6
Published electronically: November 24, 2014
MathSciNet review: 3335403
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2004e:03077), https://doi.org/10.1023/A:1022660222520
  • [2] 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 (85j:03068), https://doi.org/10.2307/2274181
  • [3] 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 (91i:03088), https://doi.org/10.1007/BFb0086114
  • [4] S. Barry Cooper and Kevin McEvoy, On minimal pairs of enumeration degrees, J. Symbolic Logic 50 (1985), no. 4, 983-1001 (1986). MR 820127 (87i:03086), https://doi.org/10.2307/2273985
  • [5] Richard M. Friedberg and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117-125. MR 0112831 (22 #3682)
  • [6] 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, https://doi.org/10.2178/jsl/1327068696
  • [7] 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 (2012m:03104), https://doi.org/10.1016/j.apal.2010.10.004
  • [8] 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, https://doi.org/10.2178/jsl.7704070
  • [9] 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 (2007i:03051), https://doi.org/10.2178/jsl/1164060448
  • [10] Carl G. Jockusch Jr. and James C. Owings Jr., Weakly semirecursive sets, J. Symbolic Logic 55 (1990), no. 2, 637-644. MR 1056377 (91g:03086), https://doi.org/10.2307/2274653
  • [11] Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420-436. MR 0220595 (36 #3649)
  • [12] I. Sh. Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log. 3 (2003), no. 2, 257-267. MR 2030087 (2005d:03076), https://doi.org/10.1142/S0219061303000285
  • [13] 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 (93b:03073), https://doi.org/10.1007/BF01794984
  • [14] Kevin McEvoy, Jumps of quasiminimal enumeration degrees, J. Symbolic Logic 50 (1985), no. 3, 839-848. MR 805690 (87m:03060), https://doi.org/10.2307/2274335
  • [15] 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 (99m:03083), https://doi.org/10.1112/S002461159800046X
  • [16] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York, 1967. MR 0224462 (37 #61)
  • [17] M. Rozinas, The semilattice of e-degrees, Recursive functions (Russian), Ivanov. Gos. Univ., Ivanovo, 1978, pp. 71-84 (Russian). MR 604944 (82i:03057)
  • [18] R. A. Shore, Biinterpretability up to double jump in the degrees below $ \mathbf {0}'$, Proc. Amer. Math. Soc. 142 (2014), no. 1, 351-360. MR 3119208
  • [19] Richard A. Shore, Degree structures: local and global investigations, Bull. Symbolic Logic 12 (2006), no. 3, 369-389. MR 2248589 (2007e:03074)
  • [20] Richard A. Shore and Theodore A. Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), no. 5-6, 711-722. MR 1739227 (2000m:03104), https://doi.org/10.4310/MRL.1999.v6.n6.a10
  • [21] 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 (2009k:03065), https://doi.org/10.1142/9789812794055_0002
  • [22] 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 (98g:03107)
  • [23] I. N. Soskov, A jump inversion theorem for the enumeration jump, Arch. Math. Logic 39 (2000), no. 6, 417-437. MR 1773778 (2001g:03078), https://doi.org/10.1007/s001530050156

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D30

Retrieve articles in all journals with MSC (2010): 03D30


Additional Information

Hristo A. Ganchev
Affiliation: Faculty of Mathematics and Informatics, Sofia University, 1164 Sofia, Bulgaria
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
Email: msoskova@fmi.uni-sofia.bg

DOI: https://doi.org/10.1090/S0002-9947-2014-06157-6
Keywords: Enumeration reducibility, first order definability, enumeration jump, total enumeration degrees, low enumeration degrees
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’
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society