A reducibility related to being hyperimmune-free.

Abstract: The main topic of the present work is the relation that a set X is strongly hyperimmune-free relative to Y. Here X is strongly hyperimmune-free relative to Y if and only if for every partial X-recursive function p there is a partial Y-recursive function q such that every a in the domain of p is also in the domain of q and satisfies , that is, p is majorised by q. For X being hyperimmune-free relative to Y, one also says that X is pmaj-reducible to Y . It is shown that between degrees not above the Halting problem the pmaj-reducibility coincides with the Turing reducibility and that therefore only recursive sets have a strongly hyperimmune-free Turing degree while those sets Turing above the Halting problem bound uncountably many sets with respect to the pmaj-relation. So pmaj-reduction is identical with Turing reduction on a class of sets of measure 1. Moreover, every pmaj-degree coincides with the corresponding Turing degree. The pmaj-degree of the Halting problem is definable with the pmaj-relation. [Copyright &y& Elsevier]