Partial degrees and \(r\)-degrees (Q1239158)

For one partial function to be partial recursive in another requires a partial recursive operator; this relation yields the partial degrees [see \textit{H. Rogers jun.}, Theory of recursive functions and effective computability. Maidenhead, Berksh.: McGraw-Hill Publishing Company, Ltd. (1967; Zbl 0183.01401)]. The stronger requirement of a recursive operator, one defined on all partial functions of one variable, gives the relation of recursive reducibility between partial functions; this yields the \(r\)-degrees, a refinement of the partial degrees. Like the partial degrees, the \(r\)-degrees (under the ordering induced by recursive reducibility) form an upper semilattice that is not a lattice. Some of the paper's results: There are uncountably many (using Zorn's Lemma) pairwise incomparable partial degrees each of which contains only one \(r\)-degree (alternatively, each of which contains more than one \(r\)-degree). Every partial degree with a nonrecursive total function contains more than one \(r\)-degree. Any partial degree has as its minimal \(r\)-degree that one consisting of those partial functions that can be extended to partial recursive functions. With the help of a theorem of Sacks: For any countable partial ordering \(\pi\), there are uncountably many partial degrees \(\underline{d}\) with the property that \(\pi\) is isomorphically embeddable in the \(r\)-degrees in \(\underline{d}\).