Abstract
An introduction to mathematical logic covering propositional logic, predicate calculus, and foundations of mathematics. Written by one of the great logicians of the twentieth century, the book provides a thorough yet elementary treatment of first-order logic in Part I, followed by deeper material on computability, decidability, and the metamathematics of formal systems in Part II. The text includes detailed treatments of formal number theory, Turing machines, and Gödel’s incompleteness theorems. Kleene’s approach emphasizes both syntactic and semantic methods, making it suitable for undergraduate study while also serving as a reference for more advanced topics.
Outline
Part I: Elementary Mathematical Logic
Chapter 1: The Propositional Calculus
- Linguistic considerations: formulas
- Model theory: truth tables, validity
- Model theory: the substitution rule, collection of valid formulas
- Model theory: implication and equivalence
- Model theory: chains of equivalences
- Proof theory: the formal axiomatic system
- Proof theory: the deduction theorem
- Proof theory: soundness and completeness
- Applications to Boolean algebra
Chapter 2: The Predicate Calculus
- Linguistic considerations: predicate calculus formulas
- Free and bound variables, substitution
- Model theory: structures and interpretations
- Model theory: validity and logical consequence
- Model theory: prenex normal form
- Proof theory: the formal axiomatic system for predicate calculus
- Proof theory: soundness and completeness
- Herbrand’s theorem
- Löwenheim-Skolem theorem
Chapter 3: The Predicate Calculus with Equality
- Equality as a logical notion
- Model theory with equality
- Proof theory with equality axioms
- Applications to mathematical theories
Part II: Mathematical Logic and Foundations of Mathematics
Chapter 4: Foundations of Mathematics
- Informal and formal mathematics
- Axiomatic method
- Formalism, intuitionism, and logicism
- Hilbert’s program
- The concept of metamathematics
- Formal number theory (Peano arithmetic)
Chapter 5: Computability and Decidability
- Recursive functions
- Turing machines
- Church-Turing thesis
- Decidability and undecidability
- The halting problem
- Unsolvable problems in predicate calculus
- Recursively enumerable sets
Chapter 6: The Predicate Calculus (Additional Topics)
- Gödel’s incompleteness theorems
- Arithmetization of syntax
- The first incompleteness theorem
- The second incompleteness theorem
- Undecidability of predicate calculus
- Compactness theorem
- Applications of metamathematical results
Significance
Kleene’s Mathematical Logic serves as an accessible introduction to mathematical logic while maintaining rigorous standards. Though published in 1967, it remains a valuable resource for understanding the foundations of logic, computability theory, and metamathematics. The book’s treatment of recursive functions and Turing machines reflects Kleene’s own fundamental contributions to computability theory. The Dover reprint (2002) has made this classic widely available to students and researchers.
Related Works
This book is intended as an undergraduate-level introduction, in contrast to Kleene’s earlier Introduction to Metamathematics (1952), which was written for graduate students and contains more comprehensive treatments of many topics.