Degrees that Are Low for Isomorphism

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.