Defining totality in the enumeration degrees

Cai, Mingzhong; Ganchev, Hristo; Lempp, Steffen; Miller, Joseph; Soskova, Mariya

doi:10.1090/jams/848

Defining totality in the enumeration degrees
HTML articles powered by AMS MathViewer

by Mingzhong Cai, Hristo A. Ganchev, Steffen Lempp, Joseph S. Miller and Mariya I. Soskova

J. Amer. Math. Soc. 29 (2016), 1051-1067

DOI: https://doi.org/10.1090/jams/848

Published electronically: November 2, 2015

PDF | Request permission

Abstract:

We show that if $A$ and $B$ form a nontrivial $\mathcal {K}$-pair, then there is a semi-computable set $C$ such that $A\leq _e C$ and $B\leq _e \overline {C}$. As a consequence, we obtain a definition of the total enumeration degrees: a nonzero enumeration degree is total if and only if it is the join of a nontrivial maximal $\mathcal {K}$-pair. This answers a long-standing question of Hartley Rogers, Jr. We also obtain a definition of the “c.e. in” relation for total degrees in the enumeration degrees.

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
Mingzhong Cai, Array nonrecursiveness and relative recursive enumerability, J. Symbolic Logic 77 (2012), no. 1, 21–32. MR 2951627
Mingzhong Cai and Richard A. Shore, Domination, forcing, array nonrecursiveness and relative recursive enumerability, J. Symbolic Logic 77 (2012), no. 1, 33–48. MR 2951628, DOI 10.2178/jsl/1327068690
Mingzhong Cai and Richard A. Shore, Low level nondefinability results: domination and recursive enumeration, J. Symbolic Logic 78 (2013), no. 3, 1005–1024. MR 3135511
Richard J. Coles, Rod G. Downey, and Theodore A. Slaman, Every set has a least jump enumeration, J. London Math. Soc. (2) 62 (2000), no. 3, 641–649. MR 1794274, DOI 10.1112/S0024610700001459
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
Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177
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 A. Ganchev and Mariya I. Soskova, Definability via Kalimullin pairs in the structure of the enumeration degrees, Trans. Amer. Math. Soc. 367 (2015), no. 7, 4873–4893. MR 3335403, DOI 10.1090/S0002-9947-2014-06157-6
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
Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
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
Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
H. Rogers Jr., Some problems of definability in recursive function theory, Sets, Models and Recursion Theory (Proc. Summer School Math. Logic and Tenth Logic Colloq., Leicester, 1965) North-Holland, Amsterdam, 1967, pp. 183–201. MR 0223237
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462
Mikhael G. Rozinas, The semi-lattice of $e$-degrees, Recursive Functions, Ivano. Gos. Univ., New York, Ivanovo, 1978, pp. 71–84. Russian.
Dana Scott, Lamba calculus and recursion theory, Proceedings of the Third Scandinavian Logic Symposium (Univ. Uppsala, Uppsala, 1973) Stud. Logic Found. Math., Vol. 82, North-Holland, Amsterdam, 1975, pp. 154–193. MR 0384495
Alan L. Selman, Arithmetical reducibilities. I, Z. Math. Logik Grundlagen Math. 17 (1971), 335–350. MR 304150, DOI 10.1002/malq.19710170139
Theodore A. Slaman and W. Hugh Woodin, Definability in degree structures (2005). Preprint.
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
Ivan N. Soskov, Degree spectra and co-spectra of structures, Annuaire Univ. Sofia Fac. Math. Inform. 96 (2004), 45–68. MR 2068290
Ivan N. Soskov, A note on $\omega$-jump inversion of degree spectra of structures, The nature of computation, Lecture Notes in Comput. Sci., vol. 7921, Springer, Heidelberg, 2013, pp. 365–370. MR 3102039, DOI 10.1007/978-3-642-39053-1_{4}3
Hristo Ganchev and Ivan N. Soskov, The jump operator on the $\omega$-enumeration degrees, Ann. Pure Appl. Logic 160 (2009), no. 3, 289–301. MR 2555780, DOI 10.1016/j.apal.2009.01.003
Mariya I. Soskova, The automorphism group of the enumeration degrees. To appear in Ann. Pure Appl. Logic.
Martin Ziegler, Algebraisch abgeschlossene Gruppen, Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Studies in Logic and the Foundations of Mathematics, vol. 95, North-Holland, Amsterdam-New York, 1980, pp. 449–576 (German, with English summary). MR 579957