zbMATH — the first resource for mathematics

Lowness for isomorphism and degrees of genericity. (English) Zbl 1435.03068
Summary: A Turing degree \(\mathbf{d}\) is said to be low for isomorphism if whenever two computable structures are \(\mathbf{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.

03D28 Other Turing degree structures
03D25 Recursively (computably) enumerable sets and degrees
03D45 Theory of numerations, effectively presented structures
Full Text: DOI