We give various examples of automorphism bases for the recursively enumerable (r.e.) degrees. In particular, we show that any nontrivial initial segment of the r.e. degrees is an automorphism base.
K.Ambos-Spies, Automorphism bases for the r.e. degrees (abstract), in: Extended Abstracts of Short Talks of the 1982 Summer Institute on Recursion Theory Held at Cornell University, Special Publication of Recursive Function Theory Newsletter, I.Kalantari, ed., 1982, pp. 3–4.
2.
K.Ambos-Spies, Contiguous r.e. degrees, in: Computation and Proof Theory, Aachen, 1983, Lecture Notes in Math., Vol. 1104, Springer, Berlin, 1984, pp. 1–37. doi:10.1007/BFb0099477.
3.
K.Ambos-Spies, On pairs of recursively enumerable degrees, Trans. Amer. Math. Soc.283 (1984), 507–531. doi:10.1090/S0002-9947-1984-0737882-5.
4.
K.Ambos-Spies, Generators of the recursively enumerable degrees, in: Recursion Theory Week (Oberwolfach 1984), Lecture Notes in Math., Vol. 1141, Springer, Berlin, 1985, pp. 1–28. doi:10.1007/BFb0076212.
5.
K.Ambos-Spies and D.Ding, Discontinuity of cappings in the recursively enumerable degrees and strongly nonbranching degrees, Mathematical Logic Quarterly40 (1994), 287–317. doi:10.1002/malq.19940400302.
6.
K.Ambos-Spies and P.A.Fejer, Degrees of Unsolvability. Computational Logic, Handb. Hist. Log., Vol. 9, Elsevier/North-Holland, Amsterdam, 2014, pp. 443–494.
7.
K.Ambos-Spies, D.Hirschfeldt and R.A.Shore, Undecidability and 1-types in intervals of the computably enumerable degrees, Annals of Pure and Applied Logic106 (2000), 1–47. doi:10.1016/S0168-0072(99)00011-1.
8.
K.Ambos-Spies, C.G.JockuschJr., R.A.Shore and R.I.Soare, An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc.281 (1984), 109–128. doi:10.1090/S0002-9947-1984-0719661-8.
9.
K.Ambos-Spies and R.A.Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic63 (1993), 3–37. doi:10.1016/0168-0072(93)90206-S.
10.
P.Cholak, R.Downey and S.Walk, Maximal contiguous degrees, J. Symbolic Logic67 (2002), 409–437. doi:10.2178/jsl/1190150052.
11.
P.J.Cohen, Weak truth-table reducibility and the pointwise ordering of 1–1 recursive functions, Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1975.
12.
S.B.Cooper, Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic39 (1974), 655–660. doi:10.2307/2272849.
13.
S.B.Cooper, Beyond Goedel’s theorem: The failure to capture information content, in: Complexity, Logic and Recursion Theory, A.Sorbi, ed., Lecture Notes in Pure and Appl. Math., Vol. 187, Marcel Dekker, 1997, pp. 93–122.
14.
S.B.Cooper, The Turing Universe Is Not Rigid, University of Leeds Pure Mathematics Preprint Series, no. 16, 1997, revised February 1998.
D.Ding, Every p-generic degree r.e. degree is meet-inaccesible (Chinese), Chin. Ann. Math., Ser. A14 (1993), 542–547.
17.
R.Downey, Notes on the 0′′′ priority method with special attention to density results, in: Recursion Theory Week, Lecture Notes in Math., Vol. 1432, Springer, 1990, pp. 111–140. doi:10.1007/BFb0086115.
18.
R.Downey and S.Lempp, Contiguity and distributivity in the enumerable Turing degrees, J. Symbolic Logic62 (1997), 1215–1240. doi:10.2307/2275639.
19.
R.Downey and J.Mourad, Superbranching degrees, in: Recursion Theory Week, Lecture Notes in Math., Vol. 1432, Springer, 1990, pp. 175–186. doi:10.1007/BFb0086117.
P.A.Fejer, The density of the nonbranching degrees, Annals of Pure and Applied Logic24 (1983), 113–130. doi:10.1016/0168-0072(83)90028-3.
22.
P.A.Fejer and R.I.Soare, The plus-cupping theorem for the recursively enumerable degrees, in: Logic Year 1979–80: University of Connecticut, M.Lerman, J.H.Schmerl and R.I.Soare, eds, Lecture Notes in Mathematics, Vol. 859, Springer, 1981, pp. 49–62. doi:10.1007/BFb0090938.
23.
M.Ingrassia, p-genericity for recursively enumerable sets, Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1981.
24.
C.G.JockuschJr., Genericity for recursively enumerable sets, in: Recursion Theory Week, H.D.Ebbinghaus, G.H.Müller and G.E.Sacks, eds, Springer, 1985, pp. 203–232. doi:10.1007/BFb0076222.
25.
C.G.JockuschJr. and D.Posner, Automorphism bases for degrees of unsolvability, Israel J. Math.40 (1981), 150–164. doi:10.1007/BF02761906.
26.
A.H.Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc.16 (1966), 537–569. doi:10.1112/plms/s3-16.1.537.
27.
A.H.Lachlan, Bounding minimal pairs, J. Symbolic Logic44 (1979), 626–642. doi:10.2307/2273300.
28.
S.Lempp, Review of “Upper cones as automorphism bases” by S. B. Cooper [Siberian Adv. Math.9 (1999), 17–77. MR 1796986], 2002.
29.
M.Lerman, Automorphism bases for the semilattice of recursively enumerable degrees, Notices Amer. Math. Soc.24 (1977), A-251, Abstract # 77T-E10.
30.
W.Maass, R.A.Shore and M.Stob, Splitting properties and jump classes, Israel J. Math.39 (1981), 210–224. doi:10.1007/BF02760850.
31.
D.Miller, High recursively enumerable degrees and the anti cupping property, in: Logic Year 1979–80: University of Connecticut, M.Lerman, J.H.Schmerl and R.I.Soare, eds, Lecture Notes in Mathematics, Vol. 859, Springer, 1981, pp. 230–245. doi:10.1007/BFb0090950.
32.
A.Nies, Global properties of degree structures, in: In the Scope of Logic, Methodology and Philosophy of Science. Volume One of the 11th International Congress of Logic, Methodology and Philosophy of Science, Cracow, August 1999, P.Gärdenfors, J.Wolenski and K.Kijania-Place, eds, Kluwer Academic Publishers, Netherlands, 2002, pp. 65–80.
33.
A.Nies, Parameter definability in the recursively enumerable degrees, J. Math. Log.3 (2003), 37–65. doi:10.1142/S0219061303000236.
34.
A.Nies, R.A.Shore and T.A.Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc.77 (1998), 241–291. doi:10.1112/S002461159800046X.
35.
R.W.Robinson, Interpolation and embedding in the recursively enumerable degrees, Annals of Math.93 (1971), 285–314. doi:10.2307/1970776.
36.
R.W.Robinson, Jump restricted interpolation in the recursively enumerable degrees, Annals of Math.93 (1971), 586–596. doi:10.2307/1970889.
37.
G.E.Sacks, Degrees of unsolvability, Rev. Ed. in: Annals of Math. Studies, Vol. 55, Princeton University Press, 1966.
38.
R.A.Shore, Biinterpretability up to double jump in the degrees below , Proc. Amer. Math. Soc.142 (2014), 351–360. doi:10.1090/S0002-9939-2013-11719-3.
39.
R.A.Shore and T.A.Slaman, Working below a high recursively enumerable degree, J. Symbolic Logic58 (1993), 824–859. doi:10.2307/2275099.
40.
T.A.Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic52 (1991), 155–179. doi:10.1016/0168-0072(91)90044-M.
41.
T.A.Slaman, Degree structures, in: Proc. Int. Congr. Math., Kyoto, Vol. 1990, 1991, pp. 303–316.
42.
T.A.Slaman, Global properties of the Turing degrees and the Turing jump, in: Computational Prospects of Infinity. Part I. Tutorials, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., Vol. 14, World Sci. Publ., Hackensack, NJ, 2008, pp. 83–101. doi:10.1142/9789812794055_0002.
43.
T.A.Slaman and M.I.Soskova, The Turing degrees: Automorphisms and definability, Trans. Amer. Math. Soc.370 (2018), 1351–1375. doi:10.1090/tran/7187.
44.
T.A.Slaman and W.H.Woodin, Definability in degree structures, Preprint, 2005.
45.
R.I.Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer, 1987.
46.
C.E.M.Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic31 (1966), 159–168. doi:10.2307/2269807.
47.
Q.Zhang, The density of the meet-inaccessible r.e. degrees, J. Symbolic Logic57 (1992), 585–596. doi:10.2307/2275294.
