## 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 PDF
- J. Amer. Math. Soc.
**29**(2016), 1051-1067 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, Ont.-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**

## Additional Information

**Mingzhong Cai**- Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755-3551
- MR Author ID: 816369
- Email: Mingzhong.Cai@dartmouth.edu
**Hristo A. Ganchev**- Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
- MR Author ID: 873534
- Email: ganchev@fmi.uni-sofia.bg
**Steffen Lempp**- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
- MR Author ID: 247988
- Email: lempp@math.wisc.edu
**Joseph S. Miller**- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
- MR Author ID: 735102
- Email: jmiller@math.wisc.edu
**Mariya I. Soskova**- Affiliation: Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
- MR Author ID: 802392
- Email: msoskova@fmi.uni-sofia.bg
- 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. - © Copyright 2015 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**29**(2016), 1051-1067 - MSC (2010): Primary 03D30
- DOI: https://doi.org/10.1090/jams/848
- MathSciNet review: 3522609