Abstract

The contents of this book, pedagogically sound and intellectually rigorous, live up to the high standards one would expect of its author. A two or three semester course based upon this book will carry the student through all of the requisite foundational material to many of the important contemporary results in recursion theory, nonstandard arithmetic, and other more esoteric areas. The book combines features of a rigorous logic text and a book on the foundations of mathematics and elementary recursion theory. In the first chapter of this latter part, Kleene gives a discussion of such topics as countable sets, Cantor's diagonal method, the paradoxes, axiomatic vs. intuitive thinking in mathematics, metamathematics, formal number theory and various formal systems. The material here parallels that in Part I of the author's previous work, Introduction to Metamathematics, but is more reliant upon logic and less upon informal set theory. The chapter on recursion theory begins with the concept of the Turing machine, and then uses this to develop the incompleteness and undecidability results of Church and Gödel. Additional topics include Gödel's completeness theorem for various types of formal systems, Skolem's paradox and nonstandard arithmetic, Herbrand's theorem and Craig's interpolation theorem. Many results and theorems of the present work bear the same indexical number as the corresponding item in IM, and the book as a whole can serve as a prolegomenon to that more advanced work.—H. P. K.