Foundations of Logic

The book is based on lecture courses give at Stockholm University and latterly at Tsinghua University, Beijing, and evidently reflects long teaching experience. The expositional choices are very well-judged, and the balance between motivational chat and worked-through formal details seems just right to me. Many student readers should find this book quite excellent for self-study.

Part I (‘Background’, 78 pp.), introduces propositional and FOL languages, and the idea of interpretations and semantic consequences, and then gives both a natural deduction proof system (Gentzen-style) and a Hilbert proof system. Part II (‘Completeness’, 80 pp.) gives soundness and completeness theorems for propositional logic and FOL, and then there is a chapter on the L-S theorems, compactness, and a smidgin of model theory. Part III (‘Incompleteness’, 134 pp.) discusses primitive recursive functions and their representability, Peano arithmetic, arithmetization, and Gödel’s Theorems. Part IV (‘Computability’, 114 pp.) adds chapters on decidability, undecidability and a modest amount more computability theory. There is an Appendix (34 pp.) on sets and functions, etc., for those that need it.