Affiliations: Department of Mathematics, Hofstra University, Room 306, Roosevelt Hall, Hempstead, NY 11549-0114, USA. johanna.n.franklin@hofstra.edu, http://people.hofstra.edu/Johanna_N_Franklin/ | Department of Mathematics, University of Connecticut, 196 Auditorium Road, Unit 3009, Storrs, CT 06269-3009, USA. david.solomon@uconn.edu, http://www.math.uconn.edu/~solomon
Abstract: We say that a degree is low for isomorphism if, whenever it can compute an isomorphism between a pair of computable structures, there is already a computable isomorphism between them. We show that while there is no clear-cut relationship between this property and other properties related to computational weakness, the low-for-isomorphism degrees contain all Cohen 2-generics and are disjoint from the Martin–Löf randoms. We also consider lowness for isomorphism with respect to the class of linear orders.
Keywords: low for isomorphism, computable structure theory, genericity, Martin–Löf random
DOI: 10.3233/COM-140027
Journal: Computability, vol. 3, no. 2, pp. 73-89, 2014
