Enumerations in computable structure theory

https://doi.org/10.1016/j.apal.2005.02.001Get rights and content
Under an Elsevier user license
open archive

Abstract

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph G into a structure G such that G has a Δα0 isomorphic copy if and only if G has a computable isomorphic copy.

A computable structure A is Δα0 categorical (relatively Δα0 categorical, respectively) if for all computable (countable, respectively) isomorphic copies B of A, there is an isomorphism from A onto B, which is Δα0 (Δα0 relative to the atomic diagram of B, respectively). We prove that for every computable successor ordinal α, there is a computable, Δα0 categorical structure, which is not relatively Δα0 categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.

An additional relation R on the domain of a computable structure A is intrinsically Σα0 (relatively intrinsically Σα0, respectively) on A if in all computable (countable, respectively) isomorphic copies B of A, the image of R is Σα0 (Σα0 relative to the atomic diagram of B, respectively). We prove that for every computable successor ordinal α, there is an intrinsically Σα0 relation on a computable structure, which not relatively intrinsically Σα0. This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.

The Δα0 dimension of a structure A is the number of computable isomorphic copies, up to Δα0 isomorphisms. We prove that for every computable successor ordinal α and every n1, there is a computable structure with Δα0 dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n1.

Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that Δα0 relative to X is not Δα0. In particular, for every finite n, there is a structure with isomorphic copies in exactly the non-lown Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure A with isomorphic copies in exactly the nonzero Turing degrees.

Cited by (0)