This study combines an introduction to recursive function theory (and its applications to metamathematics) with a presentation of new results in the field. The author has particularly borne in mind the needs of the generally mature mathematician with no background in mathematical logic. Our treatment (particularly in Chapters I and II) has been mainly influenced by the elegant methods of Post.

Chapter I commences with a new characterization of “formal mathematical systems” and “recursively enumerable sets and relations”. We introduce the notion of an “elementary formal system” which serves as the basic formalism for the entire study. A very short and simple proof is given of Church's theorem – that there exists no uniform “algorithm” for deciding which sentences are provable in which mathematical systems. The proof is in the spirit of Post, but the normal form theorem for canonical systems is avoided. The study of elementary formal systems is continued in Chapter II, which consists mainly of results of a preliminary nature or the remaining chapters.

In Chapter III we approach the Gödel and Rosser incompleteness theorems and related results on undecidability, from a highly abstract point of view. The usual machinery of mathematical logic (the propositional and first order functional calculi) is not employed. The applications to mathemat1cal logic proper are treated separately in the supplement. The results on undecidability are all deduced from a tiny fragment of recursive function theory developed in #A of Chapter II. Chapter III also extends some well known metamathematical results; these are further extended in Chapter V.

Chapter IV contains a connected presentation of recursive function theory from a viewpoint which combines the theory of elementary formal systems with an extension of Quine’s techniques of concatenation theory. [The reader whose main interest is in recursive functions can read this chapter directly following Chapter II.] Gödel’s program of arithmethtizing syntax is accomplished in a new manner; no appeal is made to primitive recursive function theory, prime factorization, theory of congruences or the Chinese remainder theorem. A by-product of this approach (which was undertaken primarily out of considerations of elegance) is that improved normal form theorems are obtained.

The concluding chapter contains the results of the author's recent research on the theory of' universal sets and double universal pairs. A particularly interesting application, jointly due to Hilary Putnam and the author, is given in the concluding section of the supplement.
Read more at http://ebookee.org/Theory-of-Formal-Systems_604018.html#s4Tm220VlKJz5B7X.99