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.

Let K be a computable field. Let F be a collection of recursive functions over K, possibly including field operations. We investigate the following question. Given an r.e. degree a, is there an injective map j: K $\longrightarrow \mathbb{N}$ such that j(K) is of degree a and all the functions in F are translated by restrictions of total recursive functions.

In this paper, we state a metatheorem for constructions involving coding. Using the metatheorem, we obtain results on coding a family of sets into a family of relations, or into a single relation. For a concrete example, we show that the set of limit points in a recursive ordering of type ω 2 can have arbitrary 2-REA degree.

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)