Finite generation of recursively enumerable sets
Julia Robinson · Proceedings of the American Mathematical Society · 1968
Suppose we wish to build up the class of recursively enumerable sets by starting with the set DI of natural numbers and constructing new sets from those already obtained using as little auxiliary machinery as possible. One way would be to start with a finite number of functions F1, * * *, Fk (of one variable, from and to 9t) such that every recursively enumerable set can be obtained from t by constructing new sets Fj [3 I where 5 is a previously obtained set. We can think of F1, * * *, Fk as unary operations on sets of natural numbers. Any set 8 obtained in this way is the range of a function F obtained by composition from F1, **, Fk. If we consider the values of F1, * * *, Fk as given, then the number of steps needed to compute Fn does not depend on n. Hence for all xe8, there exists a proof that xCS of bounded length in terms of F1, * * *, Fk (just as there is a one-step proof that a composite number is composite in terms of multiplication). We say a set of natural numbers is generated by F1, * * *, Fk if it is the range of a function obtained by composition from F1, * * * , Fk. Also a class e of sets is generated by F1, * * *, Fk if every nonempty set of e is generated by F1, l * , Fk and every set generated by Fl, @ , Fk is in e. EXAMPLE. Let Go, G1, * * * be the primitive recursive functions listed systematically so that the function G given by