The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of (...) the minimum element of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family. (shrink)

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 into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...) categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively 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 is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . 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 dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.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 relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

In [7] and [8], it is established that given any abstract countable structure S and a relation R on S, then as long as S has a recursive copy satisfying extra decidability conditions, R will be ∑0α on every recursive copy of S iff R is definable in S by a special type of infinitary formula, a ∑rα() formula. We generalize the typ e of constructions of these papers to produce conditions under which, given two disjoint relations R1 and R2 (...) on S, there is a recursive copy of S in which R1 and R2 are 0α inseparable. We then apply these theorems to specific everyday structures such as linear orderings, boolean algebras andvector spaces. (shrink)

In order to apply known general theorems about the effective properties of recursive structures in a particular recursive structure, it is necessary to verify that certain decidability conditions are satisfied. This requires the determination of when certain relations, called back and forth relations, hold between finite strings of elements from the structure. Here we determine this for recursive reduced abelian p-groups, thus enabling us to apply these theorems.

We extend results of Harizanov and Barker. For a relation R on a recursive structure /oA, we give conditions guaranteeing that the image of R in a recursive copy of /oA can be made to have arbitrary ∑α0 degree over Δα0. We give stronger conditions under which the image of R can be made ∑α0 degree as well. The degrees over Δα0 can be replaced by certain more general classes. We also generalize the Friedberg-Muchnik Theorem, giving conditions on a pair (...) of relations R and S under which the images of R and S can be made ∑α0 and independent over Δα0 in a recursive copy of /oA. (shrink)

We ask when, for a pair of structures $\mathcal {A}_1,\mathcal {A}_2$, there is a uniform effective procedure that, given copies of the two structures, unlabeled, always produces a copy of $\mathcal {A}_1$. We give some conditions guaranteeing that there is such a procedure. The conditions might suggest that for the pair of orderings $\mathcal {A}_1$ of type $\omega _1^{CK}$ and $\mathcal {A}_2$ of Harrison type, there should not be any such procedure, but, in fact, there is one. We construct an (...) example for which there is no such procedure. The construction involves forcing. On the way to constructing our example, we prove a general result on modifying Cohen generics. (shrink)

Hurlburt, K.R., Sufficiency conditions for theories with recursive models, Annals of Pure and Applied Logic 55 305–320. We give conditions under which it is possible to construct recursive models for certain highly non-recursive theories. The main idea is to find an ‘α-friendly family’ of structures corresponding to the given theory and then to construct the desired recursive model by copying appropriate parts of these structures, choosing the part to copy in each structure so as to include important witnesses. All of (...) this is done using the recursive labelling systems designed by C. Ash. An example is given which involves orderings whose elementary first-order theories have degree O. (shrink)

We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal ${\Pi ^{\mathrm {c}}_{3}}$ (...) or ${d\text {-}\Sigma ^{\mathrm {c}}_{3}}$ Scott sentence and give a characterization of those linear orders of rank $1$ with ${\Pi ^{\mathrm {c}}_{3}}$ optimal Scott sentences. At last we show that for all countable $\alpha $ the class of Hausdorff rank $\alpha $ linear orders is $\boldsymbol {\Sigma }_{2\alpha +2}$ complete and obtain analogous results for index sets of computable linear orders. (shrink)

We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically invariant relation whose degree spectrum consists of all nontrivial r-degrees. We extend this construction to show that can be replaced by either or.