Abstract: BY ROBERT I. SOARE 1 logic, and recursively enumerable sets form the soul of recursion theory.Although some might challenge these claims, it is clear that recursively enumerable sets have played an important role in logic beginning with the first undecidability results of Gödel [Göl], Church [Ch] and Rosser [Rs].Furthermore, the notion of a recursively enumerable set rather than that of a recursive (i.e, computable) function has proved to be the fundamental concept in attempts to generalize classical recursion theory to more general settings, such as admissible ordinals [Sh4], [Le6], or higher types [Sa9].A subset A of <o (the set of nonnegative integers) is recursive (also called decidable or computable) if there is an algorithm for determining whether a