Lowness for isomorphism and degrees of genericity

Article type: Research Article

Authors: Franklin, Johanna N.Y.^a | Turetsky, Dan^b

Affiliations: [a] Department of Mathematics, Hofstra University, Room 306 Roosevelt Hall, Hempstead, NY 11549-0114, USA. [email protected]; people.hofstra.edu/Johanna_N_Franklin | [b] Department of Mathematics, University of Notre Dame, Rom 208 Hayes-Healy Center, Notre Dame, IN 46556, USA. [email protected]

Abstract: 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.

Keywords: Computability, isomorphism, genericity, lowness

DOI: 10.3233/COM-170078

Journal: Computability, vol. 7, no. 1, pp. 1-6, 2018