Raymond Smullyan

Written by a creative master of mathematical logic, this introductory text combines stories of great philosophers, quotations, and riddles with the fundamentals of mathematical logic. Author Raymond Smullyan offers clear, incremental presentations of difficult logic concepts. He highlights each subject with inventive explanations and unique problems. Smullyan's accessible narrative provides memorable examples of concepts related to proofs, propositional logic and first-order logic, incompleteness theorems, and incompleteness proofs. Additional topics include undecidability, combinatoric logic, and recursion theory. Suitable for undergraduate and graduate courses, this book will also amuse and enlighten mathematically minded readers.

At the turn of the century, there appeared two comprehensive mathematical systems, which were indeed so vast that it was taken for granted that all mathematics could be decided on the basis of them. However, in 1931, Kurt Gödel surprised the entire mathematical world with his epoch‐making paper which begins with the following startling words: The development of mathematics in the direction of greater precision has led to large areas of it being formalized, so that proofs can be carried out according to a few mechanical rules. The most comprehensive formal systems to date are, on the one hand, the Principia Mathematica of Whitehead and Russell, and, on the other hand the Zermelo‐Fraenkel system of axiomatic set theory. Both systems are so extensive that all methods of proof used in mathematics today can be formalized in them‐i.e., can be reduced to a few axioms and rules of inference. It would seem reasonable, therefore, to surmise that these axioms and rules of inference are sufficient to decide all mathematical questions which can be formulated in the system concerned. In what follows it will be shown that this is not the case, but rather that, in both of the cited systems, there exist relatively simple problems of the theory of ordinary whole numbers which cannot be decided on the basis of the axioms.

More on propositional and first-order logic -- More on propositional logic -- More on first-order logic -- Recursion theory and metamathematics -- Some special topics -- Elementary formal systems and recursive enumerability -- Some recursion theory -- Doubling up -- Metamathematical applications -- Elements of combinatory logic -- Beginning combinatory logic -- Combinatorics galore -- Sages, oracles, and doublets -- Complete and partial systems -- Combinators, recursion, and the undecidable -- Where to go from here.