Deficiency sets and bounded information reducibilities
Leonard P. Sasso · Transactions of the American Mathematical Society · 1974
For recursively enumerable sets $A$ and $H$ of natural numbers $H$ is a deficiency set of $A$ if there is a one-one, recursive function $f$ with $A = \operatorname {Rng} (f)$ and $H = \{ i:(\exists j)[i < j \& f(j) < f(i)]\}$. The relation between recursively enumerable sets and their deficiency sets under bounded information reducibilities (i.e. weak truth table, truth table, bounded truth table, many-one, and one-one reducibility) is investigated.