Deducibility and Decidability

The classic results obtained by Godel, Tarski, Kleene and Church in the early thirties are the finest flowers of symbolic logic. They are of fundamental importance to those investigations of the foundations of mathematics via the concept of a formal system that were inaugurated by Frege, and of obvious significance to the mathematical disciplines, such as computability theory, that developed from them. Derived from courses taught by the author over several years, this new exposition of the results attempts a systematic unification of the theory by choosing as the central notion one grounded in the semantics of the existential quantifier, and takes care to stress the importance in the drama of three things: the mathematically well-understood conversion of implicit to explicit definitions, the philosophically perplexing idea of self-reference, and their surprising disclosure as two aspects of one phenomenon by the Recursion Theorem.