Lowness for isomorphism and degrees of genericity. (English) Zbl 1435.03068

Franklin, Johanna N. Y.; Turetsky, Dan

Computability 7, No. 1, 1-6 (2018).

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

Keywords:

computability; isomorphism; genericity; lowness