Affiliations: Department of Mathematics, Hofstra University, Room 306, Roosevelt Hall, Hempstead, NY 11549-0114, USA. email@example.com, http://people.hofstra.edu/Johanna_N_Franklin/ | Department of Mathematics, University of Connecticut, 196 Auditorium Road, Unit 3009, Storrs, CT 06269-3009, USA. firstname.lastname@example.org, 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