Degrees that Are Low for Isomorphism

Article type: Research Article

Authors: Franklin, Johanna N.Y. | Solomon, Reed

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