We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of ; the degree of bi-embeddable categoricity of is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and we show that every degree d.c.e above for α a computable successor ordinal and for λ a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra.
B.A.Anderson and B.F.Csima, Degrees that are not degrees of categoricity, Notre Dame Journal of Formal Logic57(3) (2016), 389–398.
2.
C.Ash and J.Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, Elsevier, Amsterdam, 2000. ISBN 978-0-444-50072-4. doi:10.1016/s0049-237x(00)80006-3.
3.
C.Ash, J.Knight, M.Manasse and T.Slaman, Generic copies of countable structures, Annals of Pure and Applied Logic42(3) (1989), 195–205. doi:10.1016/0168-0072(89)90015-8.
4.
C.J.Ash, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Transactions of the American Mathematical Society298(2) (1986), 497–514. doi:10.1090/S0002-9947-1986-0860377-7.
5.
C.J.Ash and J.F.Knight, Pairs of recursive structures, Annals of Pure and Applied Logic46(3) (1990), 211–234. doi:10.1016/0168-0072(90)90004-L.
6.
N.Bazhenov, Linear orders and categoricity spectra, in: Proceedings of the 14th and 15th Asian Logic Conferences, B.Kim, J.Brendle, G.Lee, F.Liu, R.Ramanujam, S.M.Srivastava, A.Tsuboi and L.Yu, eds, World Scientific, 2019, pp. 35–52.
7.
N.Bazhenov, E.Fokina, D.Rossegger and L.San Mauro, Degrees of bi-embeddable categoricity of equivalence structures, Archive for Mathematical Logic58 (2018), 543–563. doi:10.1007/s00153-018-0650-3.
8.
N.Bazhenov, E.Fokina, D.Rossegger and L.San Mauro, Computable bi-embeddable categoricity, Algebra and Logic57(5) (2018), 392–396. doi:10.1007/s10469-018-9511-8.
9.
N.A.Bazhenov, Degrees of autostability relative to strong constructivizations for Boolean algebras, Algebra and Logic55(2) (2016), 87–102. doi:10.1007/s10469-016-9381-x.
10.
N.A.Bazhenov, Effective categoricity for distributive lattices and Heyting algebras, Lobachevskii Journal of Mathematics38(4) (2017), 600–614. doi:10.1134/S1995080217040035.
11.
J.Chisholm, E.B.Fokina, S.S.Goncharov, V.S.Harizanov, J.F.Knight and S.Quinn, Intrinsic bounds on complexity and definability at limit levels, J. Symb. Logic74(3) (2009), 1047–1060. doi:10.2178/jsl/1245158098.
12.
B.F.Csima, J.N.Franklin and R.A.Shore, Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame Journal of Formal Logic54(2) (2013), 215–231. doi:10.1215/00294527-1960479.
13.
R.G.Downey, A.M.Kach, S.Lempp, A.E.Lewis-Pye, A.Montalbán and D.D.Turetsky, The complexity of computable categoricity, Advances in Mathematics268 (2015), 423–466. doi:10.1016/j.aim.2014.09.022.
14.
E.Fokina, I.Kalimullin and R.Miller, Degrees of categoricity of computable structures, Archive for Mathematical Logic49(1) (2010), 51–67. doi:10.1007/s00153-009-0160-4.
15.
E.Fokina, D.Rossegger and L.San Mauro, Bi-embeddability spectra and bases of spectra, Mathematical Logic Quarterly65(2) (2019), 228–236. doi:10.1002/malq.201800056.
16.
J.N.Y.Franklin and R.Solomon, Degrees that are low for isomorphism, Computability3(2) (2014), 73–89. doi:10.3233/COM-140027.
17.
J.N.Y.Franklin and D.Turetsky, Lowness for isomorphism and degrees of genericity, Computability7(1) (2018), 1–6. doi:10.3233/COM-170078.
18.
S.-D.Friedman and L.Motto Ros, Analytic equivalence relations and bi-embeddability, J. Symb. Logic76(1) (2011), 243–266. doi:10.2178/jsl/1294170999.
19.
A.Fröhlich and J.C.Shepherdson, Effective procedures in field theory, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences248(950) (1956), 407–432. doi:10.1098/rsta.1956.0003.
20.
N.Greenberg and A.Montalbán, Ranked structures and arithmetic transfinite recursion, Transactions of the American Mathematical Society360(3) (2008), 1265–1307. doi:10.1090/S0002-9947-07-04285-7.
21.
C.G.Jockusch and R.I.Soare, classes and degrees of theories, Transactions of the American Mathematical Society173 (1972), 33–56. doi:10.1090/S0002-9947-1972-0316227-0.
22.
A.Louveau and C.Rosendal, Complete analytic equivalence relations, Transactions of the American Mathematical Society357(12) (2005), 4839–4866. doi:10.1090/S0002-9947-05-04005-5.
23.
A.I.Maltsev, On recursive Abelian groups, Soviet Mathematics. Doklady3 (1962). English translation.
24.
R.Miller and A.Shlapentokh, Computable categoricity for algebraic fields with splitting algorithms, Transactions of the American Mathematical Society367(6) (2015), 3955–3980. doi:10.1090/S0002-9947-2014-06093-5.
25.
A.Montalbán, Up to equimorphism, hyperarithmetic is recursive, J. Symb. Logic70(2) (2005), 360–378. doi:10.2178/jsl/1120224717.
26.
D.Rossegger, Elementary bi-embeddability spectra of structures, in: Conference on Computability in Europe, Lecture Notes in Computer Science, Springer, 2018, pp. 349–358.
D.Scott, Algebras of sets binumerable in complete extensions of arithmetic, in: Recursive Function Theory, J.Dekker, ed., Proc. Sympos. Pure Math., Vol. 5, American Mathematical Society, Providence, 1962, pp. 117–121. doi:10.1090/pspum/005/0141595.
29.
S.G.Simpson, Degrees of unsolvability: A survey of results, in: Handbook of Mathematical Logic, J.Barwise, ed., Studies in Logic and the Foundations of Mathematics, Vol. 90, Elsevier, Amsterdam, 1977, pp. 631–652. doi:10.1016/S0049-237X(08)71117-0.
