Definability via Kalimullin pairs in the structure of the enumeration degrees

Ganchev, Hristo; Soskova, Mariya

doi:10.1090/S0002-9947-2014-06157-6

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