Recursively enumerable sets and degrees

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 Gdel [Gl], 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].