Almost recursively enumerable sets

Abstract:

An injective function on N, the nonnegative integers, taking values in N, is called almost recursive (abbreviated a.r.) if its inverse has a partial recursive extension. The range of an a.r. function f is called an almost recursively enumerable set in general; an almost recursive set if in addition f is strictly increasing. These are natural generalizations of regressive and retraceable sets respectively. We show that an infinite set is almost recursively enumerable iff it is point decomposable in the sense of McLaughlin. This leads us to new characterizations of certain classes of immune sets. Finally, in contrast to the regressive case, we show that a.r. functions and sets are rather badly behaved with respect to recursive equivalence.