×

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.

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