Computability-theoretic categoricity and Scott families (Q1740457)

A computable structure \(A\) is computably categorical if for every computable structure \(B\) isomorphic to \(A\), there exists a computable isomorphism from \(A\) onto \(B\). A computable structure \(A\) is \(\Delta^0_\alpha\)-categorical, where \(\alpha\) be a computable ordinal, if for every computable structure \(B\) isomorphic to \(A\), there exists a \(\Delta^0_\alpha\) isomorphism. \(A\) is relatively \(\Delta^0_n\)-categorical if and only if \(A\) has a computably enumerable Scott family of computable (infinitary) \(\Sigma_n\) formulas. Relative \(\Delta^0_n\)-categoricity implies \(\Delta^0_n\)-categoricity, but not vice versa. The age of a structure \(M\) is the class of all finitely generated structures \(\mathcal K\) that can be embedded in \(M\). A structure \(A\) is ultrahomogeneous if every isomorphism between finitely generated substructures of \(A\) extends to an automorphism of \(A\). A structure \(A\) is a Fraisse limit of a class of finitely generated structures \(\mathcal K\) if \(A\) is countable, ultrahomogeneous, and has age \(\mathcal K\). The authors present an example of a computable Fraisse limit that is computably categorical (that is, \(\Delta^0_1\)-categorical) but not relatively computably categorical and examples of \(\Delta^0_2\)-categorical but not relatively \(\Delta^0_2\)-categorical structures in natural classes such as trees of finite and infinite heights, and homogeneous, completely decomposable, abelian groups. It is known that for structures from these classes computable categoricity and relative computable categoricity coincide. The categoricity spectrum of a computable structure \(M\) is the set of all Turing degrees \(\mathbf d\) such that \(M\) is \(\mathbf d\)-computably categorical. The degree of categoricity of \(M\) is the least degree in the categoricity spectrum of \(M\), if such a degree exists. It provides the exact level of categoricity of the structure. Theorem 1. Let \(A\) be a computable structure, which is a Fraisse limit. Then \(A\) is relatively \(\Delta^0_2\)-categorical. Theorem 2. There is a 1-decidable structure F that is a Fraisse limit and computably categorical, but not relatively computably categorical. Moreover, the language for such F can be finite or it can be relational. Theorem 3. There is a computable \(\Delta^0_2\)-categorical tree of finite height, which is not relatively \(\Delta^0_2\)-categorical. Theorem 4. There is a computable \(\Delta^0_2\)-categorical tree of infinite height, which is not relatively \(\Delta^0_2\)-categorical. Theorem 5. A computable, homogeneous, completely decomposable, abelian group of infinite rank \(G\) is relatively \(\Delta^0_2\)-categorical if and only if it is isomorphic to \(\bigoplus_\omega Q(P)\), where \(P\) is a computable set of primes. Corollary 1. There is a computable, homogeneous, completely decomposable, abelian group, which is \(\Delta^0_2\)-categorical but not relatively \(\Delta^0_2\)-categorical. Theorem 6. The categoricity degrees of computable relatively \(\Delta^0_2\)-categorical abelian p-groups can only be \(\mathbf 0\) and \(\mathbf 0^\prime\). Theorem 7. The degrees of categoricity of relatively \(\Delta^0_3\)-categorical Boolean algebras can only be \(\mathbf 0\), \(\mathbf 0^\prime\) and \(\mathbf 0^{\prime\prime}\).