A classification of jump operators

Publisher Website
Google Scholar
Abstract
The structure (D, ≤) of the Turing degrees under Turing reducibility is quite complicated. This is true even if we restrict our attention to the substructure (R, ≤) of r.e. degrees. However, the theorems which imply that these structures are complicated all involve ad hoc constructions of sets having the desired reducibility relations. The complexity disappears when we turn to degrees occurring in nature. Of the degrees in R, only 0 and 0′ seem natural. In D, only 0, 0′, 0″, …, 0ω, 0ω+1, … (and on into the transfinite) seem natural. Thus the natural degrees appear to be wellordered, with successors given by Turing jump.If this is true, one would like to prove it. Of course the first problem is to make the concept of naturalness more precise. The following requirements seem plausible: a natural degree should be definable, its definition should relativise to an arbitrary degree, and this relativisation should preserve reducibility relations among natural degrees. Thus to each natural degree c is associated a definable fc: D → D so that fc(0) = c and ∀d(d ≤ fc(d)). Moreover, b ≤ c iff ∀d(fb(d) ≤, fc(d)). To be specific, let us take the definability of fc to mean that fc ∈ L(R).If P is a property of degrees, we say P holds almost everywhere (a.e.) iff ∃c∀d ≥: c P(d). For f, g: D → D, let f ≤mg iff f(d) ≤ g(d) a.e. Define f′ by f′(d) = f{d)′, and let M = {f: D → D/f ∈ L(R) ∧ d ≤ f(d) a.e.}. The following conjecture is due to D. A. Martin:Conjecture. M is prewellordered by ≤m. If f ∈ M has rank α in ≤m, then f′ has rank α + 1.

This publication has 7 references indexed in Scilit: