In this paper we shall prove three theorems about recursively enumerable sets. The first two answer questions posed by Myhill .
The three proofs are independent and can be presented in any order. Certain notations will be common to all three. We shall denote by “Re ” the set enumerated by the procedure of which e is the Gödel number. In describing the construction for each proof, we shall suppose that a clerk is carrying out the simultaneous enumeration of R 0, R 1, R 2, …, in such a way that at each step only a finite number of sets have begun to be enumerated and only a finite number of the members of any set have been listed. (One plan the clerk can follow is to turn his attention at Step a to the enumeration of Re where e+1 is the number of prime factors of a. Then each Re receives his attention infinitely often.) We shall denote by “Re a ” the set of numbers which, at or before Step a, the clerk has listed as members of Re . Obviously, all the Re a are finite sets, recursive uniformly in e and a. For any a we can determine effectively the highest e for which Re a is not empty, and for any a, e we can effectively find the highest member of Re a , just by scanning what the clerk has done by Step a. Additional notations will be introduced in the proofs to which they pertain.
(Received June 06 1958)