A Turing degree d is said to be low for isomorphism if whenever two computable structures are d-computably isomorphic, then they are actually computably isomorphic. We construct a real that is 1-generic and low for isomorphism but not computable from a 2-generic and thus provide a counterexample to Franklin and Solomon’s conjecture that the properly 1-generic degrees are neither low for isomorphism nor degrees of categoricity.
B.A.Anderson and B.F.Csima, Degrees that are not degrees of categoricity, Notre Dame J. Formal Logic57(3) (2016), 389–398.
2.
B.Csima, Degrees of categoricity and related notions, BIRS Computable Model Theory Workshop (2013).
3.
B.F.Csima, J.N.Y.Franklin and R.A.Shore, Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Formal Logic54(2) (2013), 215–231. doi:10.1215/00294527-1960479.
4.
B.F.Csima and M.Harrison-Trainor, Degrees of categoricity on a cone via η-systems, J. Symbolic Logic82(1) (2017), 325–346. doi:10.1017/jsl.2016.43.
5.
R.G.Downey and D.R.Hirschfeldt, Algorithmic Randomness and Complexity, Springer, Berlin2010.
6.
E.B.Fokina, I.Kalimullin and R.Miller, Degrees of categoricity of computable structures, Arch. Math. Logic49(1) (2010), 51–67. doi:10.1007/s00153-009-0160-4.
7.
J.N.Y.Franklin, Lowness and highness properties for randomness notions, in: Proceedings of the 10th Asian Logic Conference, T.Araiet al., eds, World Scientific, Singapore2010, pp. 124–151.
8.
J.N.Y.Franklin and R.Solomon, Degrees that are low for isomorphism, Computability3(2) (2014), 73–89.
9.
A.Nies, Computability and Randomness, Clarendon Press, Oxford, 2009.
10.
P.Odifreddi, Classical Recursion Theory. Number 125 in Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam1989.
11.
T.A.Slaman and R.M.Solovay, When oracles do not help, in: Fourth Annual Workshop on Computational Learning Theory, Morgan Kaufman., Los Altos, CA, 1991, pp. 379–383.
12.
R.Soare, The Friedberg–Muchnik theorem re-examined, Canadian J. of Math.24 (1972), 1070–1078. doi:10.4153/CJM-1972-110-4.
13.
J.D.Suggs, On Lowness for Isomorphism as Restricted to Classes of Structures, PhD thesis, University of Connecticut, 2015.
