The central themes of this study are diagonalization, self-reference and fixed-point properties in the context of Gödel’s incompleteness proofs, recursion theory, combinatory logic, semantics and metamathematics.
The book is divided into four parts and twenty chapters. The first introductory part defines the subject of self-reference via quotation (Chapter 1), deals with different kinds of fixed-point arguments on an abstract level (Chapter 2), considers some abstract versions of halting problems (Chapter 3) and certain general versions of the incompleteness proofs (Chapter 4). Self-reference in first-order arithmetic is studied in Chapter 5, and a generalization of Cantor’s famous construction (by which a set cannot be put into a one-to-one correspondence with its power set) is presented. An introduction to recursion theory, by means of elementary formal systems, as defined in the author’s book: Theory of formal systems (1961; Zbl 0097.245), is given in Chapters 6 and 7, and continued in Chapter 8 of the second part of the book concerning systems with effective properties. It is described, quite explicitly, how from an elementary formal system for an incomplete axiomatizable theory, an undecidable sentence can be found (Chapter 9), and then it is shown how to apply this method in order to obtain an undecidable sentence of Peano arithmetic. Chapters 10 and 11 deal with effective representation systems, as well as with indexed relational systems and double indexing, generalizing some classical results of recursion theory and making the proofs simpler and more elegant.
The third part, entitled “Fixed point theorem in a general setting”, starts with the study of abstract structures called sequential systems, each fixed-point theorem of which simultaneously yields a fixed-point theorem for recursion theory, one for combinatory logic, and one for metamathematics (Chapter 12). Chapter 13 is devoted to the recursion property, the Myhill property and some related “strong” fixed-point properties, while Chapter 14 deals with multiple fixed-point properties arising in recursion theory, combinatory logic and metamathematics. In Chapter 15, a totally different approach to double and multiple fixed- point properties is presented, based on the original form of the double recursion theorem given in the author’s book cited above. Some further relations between fixed-point properties are considered in Chapter 16.
The fourth part of the book presents an introduction to combinatory logic (Chapters 17 and 18), with special emphasis on fixed-point properties and various ways of constructing fixed-point combinators and related entities. A generalization and extensions of a result in combinatory logic known as the “second fixed-point theorem”, based on methods of naming combinators within combinatory logic itself, are given in Chapter 19. The final chapter (Chapter 20) is devoted to a variety of fixed-point theorems that simultaneously generalize the fixed-point theorems of the preceding chapter and earlier fixed-point theorems for sequential systems.
The book is self-contained and even no prior knowledge of mathematical logic is presupposed (except a little familiarity with the logical connectives and quantifiers for Chapters 5 and 9 only). Like the previous books by the same author, this one is characterized by a very precise, nice and approachable style. Undoubtedly, this will be one more pearl in the string of brilliant fundamental books in logic written by R. M. Smullyan.