Complete recursively enumerable sets
A. H. Lachlan · Proceedings of the American Mathematical Society · 1968
The main purpose of this paper is to improve upon the main theorem of Martin [2 ]. Martin gave a sufficient condition for a recursively enumerable (r.e.) set to be complete. By a slight modification we weaken Martin's condition so that it becomes both necessary and sufficient. Next we indicate briefly why Martin's condition for completeness is not a necessary one. Finally, we discuss applications of our theorem and the problem of formulating a notion of effectively maximal set. I am grateful for the referee's suggestions, particularly with regard to the statement of the theorem. Let W0, W1, * * be a standard enumeration of all r.e. sets. Let B00 f91, * * be a standard enumeration of all partial recursive functions of one argument. The representing function KA of a set of natural numbers A is defined by: KA(X) =0 if x is in A, KA(X) = 1 if x is in AT (the complement of A). Let L(x) denote the set of natural numbers <x.