An Introduction to Metalogic is a uniquely accessible introduction to the metatheory of first-order predicate logic. No background knowledge of logic is presupposed, as the book is entirely self-contained and clearly defines all of the technical terms it employs. Yaqub begins with an introduction to predicate logic and ends with detailed outlines of the proofs of the incompleteness, undecidability, and indefinability theorems, covering many related topics in between.
Comments
“This is an excellent text in intermediate logic that should be warmly received by students. The well-paced exposition is remarkably clear. The choice of material, including remarks on the philosophical significance of the principal theorems and welcome sections on Second-Order logic, seems just right. And the ample exercises at the end of each chapter, which range from easy to difficult, not only test the reader’s understanding, but move the subject forward. Highly recommended.” — David Keyt, Research Professor, University of Arizona; Professor Emeritus, University of Washington
“An Introduction to Metalogic provides extensive coverage of the usual meta-theoretic results concerning the standard logical systems. It covers the completeness theorems, compactness, the Löwenheim-Skolem theorems, and the incompleteness of arithmetic. There is also a good sketch of more advanced topics, giving the enthusiastic reader and student incentive to keep studying the field. As with Professor Yaqub’s earlier logic text, An Introduction to Logical Theory, the presentation is clear and straightforward.” — Stewart Shapiro, Ohio State University
“Yaqub has produced a pedagogically sensitive, yet completely rigorous tour of the introductory metalogical terrain. His textbook will be welcomed by instructors in philosophy, mathematics, computer science and linguistics who endeavor to offer their students something more substantial than standard introductory logic.” — Kai Wehmeier, University of California, Irvine
Introduction
Chapter One: First-Order Predicate Logic (PL)
1.1 The Syntax of PL
- The basic vocabulary of PL
- PL terms
- PL formulas
- Bound and free variables and PL sentences
1.2 The Semantics of PL
- PL interpretations
- Examples of PL interpretations
- Objectual and substitutional quantification
- The size of a PL interpretation
- The truth conditions of PL sentences
- Possible objections to substitutional quantification and replies
1.3 Logical Concepts in PL
- Definition of a PL argument
- Validity and logical consequence
- Definition of a valid argument
- Definition of an invalid argument
- Definition of a valid sentence
- Definition of a contradictory sentence
- Definition of a contingent sentence
- Definition of logically equivalent sentences
- Definition of a satisfiable set
- Definition of an unsatisfiable set
- Decidable and semidecidable concepts
1.4 PL Proof Theory
- The notion of formal derivation
- The statements of the Soundness and Completeness Theorems for PL
- Corollaries of the Soundness and Completeness Theorems
- The structure and application of inference rules
- The Natural Deduction System (NDS)
- A justification for the rule Explosion
- The Gentzen Deduction System (GDS)
1.5 Exercises
- Solutions to the Starred Exercises
Chapter Two: Resources of the Metatheory
2.1 Linguistic and Logical Resources
- The metatheory of PL
- The language of the metatheory
- Logical resources
2.2 Arithmetical Resources
- The structure of the natural numbers
- The Principle of Mathematical Induction
2.3 Set-Theoretic Resources
- Basic concepts and principles
- Russell’s Paradox
- Relations and functions
- Cardinalities of sets
- Cantor’s Diagonal Argument
2.4 An Economical Version of PL
- Expressive completeness
- The Mini Deduction System (MDS)
2.5 Exercises
- Solutions to the Starred Exercises
Chapter Three: The Soundness and Completeness Theorems
3.1 The Soundness Theorem
3.2 The Completeness Theorem
- An equivalent formulation of the Completeness Theorem
- Lindenbaum’s Lemma
- Henkin sets
- Henkin interpretations of Henkin sets without the identity predicate
- Henkin interpretations of Henkin sets with the identity predicate
3.3 The Compactness Theorem
- The Compactness Theorem
- The Finite-Satisfiability Theorem
3.4 Elementary Equivalence and Isomorphism
3.5 Properties of PL Sets
- PL theories
- Axiomatizable PL theories
- Complete and categorical PL sets
3.6 The Löwenheim-Skolem Theorem
- A proof of the theorem
- Skolem’s Paradox
3.7 Exercises
- Solutions to the Starred Exercises
Chapter Four: Computability
4.1 Effective Procedures and Computable Functions
4.2 Turing Computability
- Turing machines
- An example
- Instruction lines and diagrams of Turing machines
- The zero, successor, and addition functions
- Turing-computable functions and Church’s Thesis
- Decidable and semidecidable sets
4.3 The Halting Problem
4.4 Partial Recursive Functions
4.5 Exercises
- Solutions to the Starred Exercises
Chapter Five: The Incompleteness Theorems
5.1 Peano Arithmetic
5.2 Representability in Peano Arithmetic
5.3 Arithmetization of the Metatheory
5.4 Diagonalization and the First Incompleteness Theorem
- The Diagonalization Lemma
- Gödel’s First Incompleteness Theorem
5.5 Consequences of Diagonalization and Incompleteness
- The undecidability of consistent extensions of Peano Arithmetic
- Tarski’s Indefinability Theorem
- Church’s Undecidability Theorem
5.6 The Incompleteness of Second-Order Predicate Logic
- Second-Order Predicate Logic (PL²)
- Second-Order Peano Arithmetic
- PL2 and the Compactness Theorem
- The incompleteness of PL²
5.7 Gödel’s Second Incompleteness Theorem
- Hilbert’s Program
- The Provability Conditions
5.8 Exercises
- Solutions to the Starred Exercises
Index
Aladdin M. Yaqub is Professor of Philosophy at Lehigh University and the author of
An Introduction to Logical Theory, The Liar Speaks the Truth, and a new translation of Al-Ghazali’s Moderation in Belief.
The instructor site includes solutions to the book’s exercises. An access code to the website is included with all examination copies.
An expanded, comprehensive version of the book’s index is also available to all readers here.
