Sage Journals: Discover world-class research

Abstract

We show that all levels of the jump hierarchy are first order definable in the local structure of the enumeration degrees.

Keywords

Enumeration degrees definability jump classes

Get full access to this article

View all access options for this article.

References

M.M.

Arslanov,

S.B.

Cooper and

I.S.

Kalimullin, Splitting properties of total enumeration degrees, Algebra Logika42(1) (2003), 3–25, 125. doi:10.1023/A:1022660222520.

Cai,

H.A.

Ganchev,

Lempp,

J.S.

Miller and

M.I.

Soskova, Defining totality in the enumeration degrees, J. Amer. Math. Soc.29 (2016), 1051–1067. doi:10.1090/jams/848.

Cai,

Lempp,

J.S.

Miller and

M.I.

Soskova, On Kalimullin pairs, Computability (2015). doi:10.3233/COM-150046.

J.W.

Case, Enumeration reducibility and partial degrees, PhD thesis, University of Illinois at Urbana-Champaign, 1969.

S.B.

Cooper, Distinguishing the arithmetical hierarchy, Preprint, Berkeley, October 1972.

S.B.

Cooper, Partial degrees and the density problem, J. Symbolic Logic47(4) (1982), 854–859.

S.B.

Cooper, Partial degrees and the density problem. II. The enumeration degrees of the

Σ_{2}

sets are dense, J. Symbolic Logic49(2) (1984), 503–513. doi:10.2307/2274181.

S.B.

Cooper, Enumeration reducibility, nondeterministic computations and relative computability of partial functions, in: Recursion Theory Week, Oberwolfach, 1989, Lecture Notes in Math., Vol. 1432, Springer, Berlin, 1990, pp. 57–110. doi:10.1007/BFb0086114.

S.B.

Cooper, Upper cones as automorphism bases, Siberian Adv. Math.9(3) (1999), 17–77.

10.

S.B.

Cooper and

C.S.

Copestake, Properly

Σ_{2}

enumeration degrees, Z. Math. Logik Grundlag. Math.34(6) (1988), 491–522. doi:10.1002/malq.19880340603.

11.

R.M.

Friedberg and

RogersJr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math.5 (1959), 117–125. doi:10.1002/malq.19590050703.

12.

Ganchev and

Sorbi, Initial segments of the

Σ_{2}^{0}

enumeration degrees, J. Symb. Log.81(1) (2016), 316–325. doi:10.1017/jsl.2014.84.

13.

H.A.

Ganchev and

M.I.

Soskova, Cupping and definability in the local structure of the enumeration degrees, J. Symbolic Logic77(1) (2012), 133–158. doi:10.2178/jsl/1327068696.

14.

H.A.

Ganchev and

M.I.

Soskova, Definability via Kalimullin pairs in the structure of the enumeration degrees, Trans. Amer. Math. Soc.367 (2015), 4873–4893. doi:10.1090/S0002-9947-2014-06157-6.

15.

Gutteridge, Some results on enumeration reducibility, PhD thesis, Simon Fraser University, 1971.

16.

G.C.

JockuschJr. and

R.A.

Shore, Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic49(4) (1984), 1205–1236. doi:10.2307/2274273.

17.

I.S.

Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log.3(2) (2003), 257–267. doi:10.1142/S0219061303000285.

18.

A.H.

Lachlan and

R.A.

Shore, The n-rea enumeration degrees are dense, Arch. Math. Logic31(4) (1992), 277–285. doi:10.1007/BF01794984.

19.

Medvedev, Degrees of difficulty of the mass problem, Dok. Akad. Nauk SSSR104 (1955), 501–504.

20.

Odifreddi, Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1, Studies in Logic and the Foundations of Mathematics, Vol. 125, North Holland, 1992.

21.

M.G.

Rozinas, The semi-lattice of e-degrees, Recursive functions (Ivanovo), Ivano. Gos. Univ. (1978), 71–84 (in Russian).

22.

G.E.

Sacks, Degrees of Unsolvability, Annals of Mathematics Studies, Princeton University Press, 1963.

23.

G.E.

Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc.108 (1963), 223–239. doi:10.1090/S0002-9947-1963-0155747-3.

24.

A.L.

Selman, Arithmetical reducibilities I, Z. Math. Logik Grundlag. Math.17 (1971), 335–350. doi:10.1002/malq.19710170139.

25.

R.A.

Shore, Defining jump classes in the degrees below

0^{'}

, Proc. Amer. Math. Soc.104(1) (1988), 287–292.

26.

R.A.

Shore, Biinterpretability up to double jump in the degrees below

0^{'}

, Proc. Amer. Math. Soc.142(1) (2014), 351–360. doi:10.1090/S0002-9939-2013-11719-3.

27.

R.A.

Shore and

T.A.

Slaman, Defining the Turing jump, Math. Res. Lett.6(5–6) (1999), 711–722. doi:10.4310/MRL.1999.v6.n6.a10.

28.

T.A.

Slaman and

M.I.

Soskova, The

Δ_{2}^{0}

Turing degrees: Automorphisms and definability, Trans. Amer. Math. Soc., to appear.

29.

T.A.

Slaman and

M.I.

Soskova, The enumeration degrees: Local and global structural interactions, In press.

30.

T.A.

Slaman and

W.H.

Woodin, Definability in the Turing degrees, Illinois J. Math.30(2) (1986), 320–334.

31.

T.A.

Slaman and

W.H.

Woodin, Definability in degree structures, Preprint, 2005.

32.

R.I.

Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2)100 (1974), 80–120. doi:10.2307/1970842.

33.

I.N.

Soskov, A jump inversion theorem for the enumeration jump, Arch. Math. Logic39(6) (2000), 417–437. doi:10.1007/s001530050156.

34.

M.I.

Soskova, The automorphism group of the enumeration degrees, Ann. Pure Appl. Logic167(10) (2016), 982–999. doi:10.1016/j.apal.2014.01.007.

The jump hierarchy in the enumeration degrees

Abstract

Keywords

Get full access to this article

References