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)

The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question (...) is equivalent to: Given a computer with access to an oracle which will answer membership questions about a setA, can a program be written which will correctly compute the answers to all membership questions about a setB? If the answer is yes, then we say thatBisTuring reducibletoAand writeB≤TA. We say thatB≡TAifB≤TAandA≤TB. ≡Tis an equivalence relation, and ≤Tinduces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called thedegrees of unsolvability, and elements of this poset are calleddegrees.Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. (shrink)

The object of this paper is to explain a certain type of construction which occurs in priority proofs and illustrate it with two examples due to Lachlan and Harrington. The proofs in the examples are essentially the original proofs; our main contribution is to isolate the common part of these proofs. The key ideas in this common part are due to Lachlan; we include several improvements due to Harrington, Soare, Slaman, and the author.Our notation is fairly standard. If X is (...) an r.e. set, Xs is the finite set of elements enumerated in X before step s. if Ф is a recursive functional, Фs is the approximation to Ф at step s; it only queries the oracle about numbers xi and iless-than-or-equals, slantx; and right-pointing angle bracketx0,...,xk−1right-pointing angle bracket is an increasing function of each of its arguments. Sets are sometimes identified with their characteristic functions. Wj isthe jth r.e. set. Xc is the complement of X. (shrink)

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)

The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.

The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of $P^- + B\Sigma_2$. The proof has two components: a lemma that in any model of $P^- + B\Sigma_2$, if $B$ is recursively enumerable and incomplete then $I\Sigma_1$ holds relative to $B$ and an adaptation of Shore's [9] blocking technique in $\alpha$-recursion theory to models of arithmetic.

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)