Finitely Generated Classes of Sets of Natural Numbers
Julia Robinson · Proceedings of the American Mathematical Society · 1969
We say that a set S of natural numbers is generated by a class 5W of functions if S is the range of a function F obtained by composition from the functions of i. Here we consider the identity function I to be obtained by the empty composition. We consider only the case in which 5 consists of functions of one variable on and to the set of natural numbers N. All sets considered are subsets of N. A class C of sets is generated by 5 if every nonempty set of C is generated by 5 and every set generated by 5W is in C. C is finitely generated if there is a finite class of functions 5 which generates C. A function F is compatible with C if F(S) belongs to C for every Sin C. Clearly, if 5W generates C then every F in 5W is compatible with C. Also N belongs to C. Furthermore to show that 5 generates C it is sufficient to prove that every F-5E is compatible with C, NE C, and every nonempty set in C is generated by 5i. In [1] finite sets of relatively simple functions are given which generate the classes of recursively enumerable sets and diophantine sets. Here we ask: What classes of sets can be finitely generated? In particular, we will show that if C is a denumerable field of sets such that all finite sets belong to C and at least one infinite set having an infinite complement belongs to C, then C is finitely generated.