Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Defining totality in the enumeration degrees


Authors: Mingzhong Cai, Hristo A. Ganchev, Steffen Lempp, Joseph S. Miller and Mariya I. Soskova
Journal: J. Amer. Math. Soc. 29 (2016), 1051-1067
MSC (2010): Primary 03D30
DOI: https://doi.org/10.1090/jams/848
Published electronically: November 2, 2015
MathSciNet review: 3522609
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] M. M. Arslanov, S. B. Cooper, and I. Sh. Kalimullin, 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] Mingzhong Cai, Array nonrecursiveness and relative recursive enumerability, J. Symbolic Logic 77 (2012), no. 1, 21-32. MR 2951627
  • [3] 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, https://doi.org/10.2178/jsl/1327068690
  • [4] 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
  • [5] Richard J. Coles, Rod G. Downey, and Theodore A. Slaman, Every set has a least jump enumeration, J. Lond. Math. Soc. (2) 62 (2000), no. 3, 641-649. MR 1794274 (2002a:03081), https://doi.org/10.1112/S0024610700001459
  • [6] 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
  • [7] Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159-160. MR 0098025 (20 #4488)
  • [8] 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)
  • [9] 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
  • [10] 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, https://doi.org/10.1090/S0002-9947-2014-06157-6
  • [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] Stephen Cole Kleene, Introduction to Metamathematics, D. Van Nostrand Co., Inc., New York, N.Y., 1952. MR 0051790 (14,525m)
  • [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] Joseph S. Miller, Degrees of unsolvability of continuous functions, J. Symbolic Logic 69 (2004), no. 2, 555-584. MR 2058189 (2005b:03102), https://doi.org/10.2178/jsl/1082418543
  • [16] Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723-731. MR 641486 (83d:03048), https://doi.org/10.2307/2273222
  • [17] 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 (36 #6286)
  • [18] Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462 (37 #61)
  • [19] Mikhael G. Rozinas, The semi-lattice of $ e$-degrees, Recursive Functions, Ivano. Gos. Univ., New York, Ivanovo, 1978, pp. 71-84. Russian.
  • [20] Dana Scott, Lambda calculus and recursion theory, Proceedings of the Third Scandinavian Logic Symposium (Univ. Uppsala, Uppsala, 1973) North-Holland, Amsterdam, 1975, pp. 154-193. Stud. Logic Found. Math., Vol. 82. MR 0384495 (52 #5372)
  • [21] Alan L. Selman, Arithmetical reducibilities. I, Z. Math. Logik Grundlagen Math. 17 (1971), 335-350. MR 0304150 (46 #3285)
  • [22] Theodore A. Slaman and W. Hugh Woodin, Definability in degree structures (2005). Preprint.
  • [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
  • [24] Ivan N. Soskov, Degree spectra and co-spectra of structures, Annuaire Univ. Sofia Fac. Math. Inform. 96 (2004), 45-68. MR 2068290 (2005a:03087)
  • [25] 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, https://doi.org/10.1007/978-3-642-39053-1_43
  • [26] 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 (2011d:03065), https://doi.org/10.1016/j.apal.2009.01.003
  • [27] Mariya I. Soskova, The automorphism group of the enumeration degrees. To appear in Ann. Pure Appl. Logic.
  • [28] Martin Ziegler, Algebraisch abgeschlossene Gruppen, Word Problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math., vol. 95, North-Holland, Amsterdam-New York, 1980, pp. 449-576 (German, with English summary). MR 579957 (82b:20004)

Similar Articles

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

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


Additional Information

Mingzhong Cai
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755-3551
Email: Mingzhong.Cai@dartmouth.edu

Hristo A. Ganchev
Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
Email: ganchev@fmi.uni-sofia.bg

Steffen Lempp
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
Email: lempp@math.wisc.edu

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
Email: jmiller@math.wisc.edu

Mariya I. Soskova
Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
Email: msoskova@fmi.uni-sofia.bg

DOI: https://doi.org/10.1090/jams/848
Keywords: Enumeration degrees, total enumeration degrees, automorphisms of degree structures
Received by editor(s): January 27, 2014
Received by editor(s) in revised form: May 13, 2015, and August 26, 2015
Published electronically: November 2, 2015
Additional Notes: The first author was partially supported by NSF Grants DMS-1266214 and DMS-1458061.
The second and fifth authors were also partially supported by BNSF Grant No. DMU 03/07/12.12.2011 and by NSF Binational Grant DMS-1101123 from the United States, Russia, Kazakhstan, and Bulgaria.
The third author was partially supported by AMS-Simons Foundation Collaboration Grant 209087.
The fourth author was partially supported by NSF Grant DMS-1001847.
The fifth author was partially supported by a Marie Curie international outgoing fellowship STRIDE (298471) within the 7th European Community Framework Programme.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society