Defining totality in the enumeration degrees

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

¹ Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755-3551
² Faculty of Mathematics and Computer Science, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
³ Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388

Journal of the American Mathematical Society, Tome 29 (2016) no. 4, pp. 1051-1067

Résumé

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.

Détail

DOI : 10.1090/jams/848

Bibliographie

[1] Arslanov, M. M., Kalimullin, I. Sh., Kuper, S. B. Splitting properties of total enumeration degrees Algebra Logika 2003

[2] Cai, Mingzhong Array nonrecursiveness and relative recursive enumerability J. Symbolic Logic 2012 21 32

[3] Cai, Mingzhong, Shore, Richard A. Domination, forcing, array nonrecursiveness and relative recursive enumerability J. Symbolic Logic 2012 33 48

[4] Cai, Mingzhong, Shore, Richard A. Low level nondefinability results: domination and recursive enumeration J. Symbolic Logic 2013 1005 1024

[5] Coles, Richard J., Downey, Rod G., Slaman, Theodore A. Every set has a least jump enumeration J. London Math. Soc. (2) 2000 641 649

[6] Cooper, S. B. Partial degrees and the density problem. II. The enumeration degrees of the Σ₂ sets are dense J. Symbolic Logic 1984 503 513

[7] Friedberg, Richard A criterion for completeness of degrees of unsolvability J. Symbolic Logic 1957 159 160

[8] Friedberg, Richard M., Rogers, Hartley, Jr. Reducibility and completeness for sets of integers Z. Math. Logik Grundlagen Math. 1959 117 125

[9] Ganchev, Hristo, Soskova, Mariya I. Cupping and definability in the local structure of the enumeration degrees J. Symbolic Logic 2012 133 158

[10] Ganchev, Hristo A., Soskova, Mariya I. Definability via Kalimullin pairs in the structure of the enumeration degrees Trans. Amer. Math. Soc. 2015 4873 4893

[11] Jockusch, Carl G., Jr. Semirecursive sets and positive reducibility Trans. Amer. Math. Soc. 1968 420 436

[12] Kalimullin, I. Sh. Definability of the jump operator in the enumeration degrees J. Math. Log. 2003 257 267

[13] Kleene, Stephen Cole Introduction to metamathematics 1952

[14] Mcevoy, Kevin Jumps of quasiminimal enumeration degrees J. Symbolic Logic 1985 839 848

[15] Miller, Joseph S. Degrees of unsolvability of continuous functions J. Symbolic Logic 2004 555 584

[16] Richter, Linda Jean Degrees of structures J. Symbolic Logic 1981 723 731

[17] Rogers, H., Jr. Some problems of definability in recursive function theory 1967 183 201

[18] Rogers, Hartley, Jr. Theory of recursive functions and effective computability 1967

[19] Rozinas, Mikhael G. The semi-lattice of 𝑒-degrees 1978

[20] Scott, Dana Lamba calculus and recursion theory 1975 154 193

[21] Selman, Alan L. Arithmetical reducibilities. I Z. Math. Logik Grundlagen Math. 1971 335 350

[22] Slaman, Theodore A., Woodin, W. Hugh Definability in degree structures 2005

[23] Soskov, I. N. A jump inversion theorem for the enumeration jump Arch. Math. Logic 2000 417 437

[24] Soskov, Ivan N. Degree spectra and co-spectra of structures Annuaire Univ. Sofia Fac. Math. Inform. 2004 45 68

[25] Soskov, Ivan N. A note on 𝜔-jump inversion of degree spectra of structures 2013 365 370

[26] Ganchev, Hristo, Soskov, Ivan N. The jump operator on the 𝜔-enumeration degrees Ann. Pure Appl. Logic 2009 289 301

[27] Soskova, Mariya I. The automorphism group of the enumeration degrees

[28] Ziegler, Martin Algebraisch abgeschlossene Gruppen 1980 449 576