With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is (...) intrinsically r.e. if and only if a natural recursive-syntactic condition is satisfied. We show that, while a recursive non-intrinsically r.e. relation may have a two element degree spectrum, a non-intrinsically r.e. relation which satisfies the Ash–Nerode decidability condition has an infinite degree spectrum. We also study several related decidability conditions and their effects on the degree spectra, including some conditions which are sufficient to obtain every r.e. degree in a spectrum. (shrink)

Hird, G.R., Recursive properties of relations on models, Annals of Pure and Applied Logic 63 241–269. We prove general existence theorems for recursive models on which various relations have specified recursive properties. These capture common features of results in the literature for particular algebraic structures. For a useful class of models with new relations R, S, where S is r.e., we characterize those for which there is a recursive model isomorphic to on which the relation corresponding to S remains r.e., (...) while that corresponding to R is not r.e.; immune; hyperimmune. The results are applied to vector spaces, Boolean algebras and abelian groups. In the case of vector spaces, this leads to a new kind supermaximal subspace of V∞. (shrink)

Let be a recursive structure, and let R be a recursive relation on . Harizanov isolated a syntactical condition which is necessary and sufficient for to have recursive copies in which the image of R is r.e. of arbitrary r.e. degree. We had conjectured that a certain extension of Harizanov's syntactical condition would be necessary and sufficient for to have recursive copies in which the image of R is ∑α0 of arbitrary ∑α0 degree, but this is not the case. Here (...) we give examples illustrating some restrictions on the possible ∑α0 degrees. In these examples, the image of R cannot be ∑α0 of degree d unless d possesses an “α-table”. (shrink)