The study of recursively invariant properties of sets of integers was initiated, in large part, in the 1944paper of POST [l]. Various notions of reducibility, redefined below, are introduced in that paper ; and a set is called complete with respect to a given reducibility if (i) it is recursively enumerable and (ii) all recursively enumerable sets bear the given reducibility relation to it. In [2] MYHILL gives a characteriziation of sets complete with respect to many-one reducibility. These sets turn out to be exactly the sets called creative by POST. A set is creative if and only if (i) it is recursively enumerable and (ii) its complement is productive; the concept of productive set is studied by DEKKER in [3]. In the present paper we obtain a generalization of MYHILL'S result ; this generalization applies to the other reduciliilities defined by POST and yields appropriate generalized versions of the notions of creative set and of productive set. In addition, we make some further remarks on these reducibilities and on other related forms of reducibility.
1. Definitions
We assume the same background as that assumed by DEKKER in [3]. In particular we confine our attention to the set E of all non-negative integers. ("Integer" and "number" henceforth refer to members of this set.) ois the empty set. "a", "@", . . . denote subsets of E. " x " , "y", . . . denote members of E. "a"' denotes E -a, the complement of a. " f " , "g", . . . denote functions mapping E into E . on is the recursively enumerable set with index n under some standard Gijdel numbering of the recursivelyenumerable sets.
we take 6, to be the finite set { x l , x,, . . ., xk}. n is called the canonical index for this set. We define 6, to be 0 . Canonical 'indices give a one-one correspondence between E and the class of all finite sets. An index for any recursively enumerable set gives an effective method for listing its members, while the canonical index for a finite set gives an effective method for listing its members together with information as to how far the listing procedure need be carried in order to yield the whole set, (see
a is many-one reducible to , 9 ("as, 8") zdf there is a recursive function f such a is one-one reducible to @ ("a 5 /?") =df there is a recursive function f , mapping E that / ( a ) 2 @ and / ( a ' ) 2 @ I .
one-one into E , such that / ( a ) 2,9 and f ( a ' ) gp'. vol. t X (1957), p. 107.