Introduction to Mathematical Logic, Fifth Edition

Elliott Mendelson is professor emeritus in the Department of Mathematics at Queens College.

The Propositional Calculus


Propositional Connectives. Truth Tables


Tautologies


Adequate Sets of Connectives


An Axiom System for the Propositional Calculus


Independence. Many-Valued Logics


Other Axiomatizations


First-Order Logic and Model Theory


Quantifiers


First-Order Languages and Their Interpretations. Satisfiability and Truth. Models


First-Order Theories


Properties of First-Order Theories


Additional Metatheorems and Derived Rules


Rule C


Completeness Theorems


First-Order Theories with Equality


Definitions of New Function Letters and Individual Constants


Prenex Normal Forms


Isomorphism of Interpretations. Categoricity of Theories


Generalized First-Order Theories. Completeness and Decidability


Elementary Equivalence. Elementary Extensions


Ultrapowers: Nonstandard Analysis


Semantic Trees


Quantification Theory Allowing Empty Domains


Formal Number Theory


An Axiom System


Number-Theoretic Functions and Relations


Primitive Recursive and Recursive Functions


Arithmetization. Gödel Numbers


The Fixed-Point Theorem. Gödel’s Incompleteness Theorem


Recursive Undecidability. Church’s Theorem


Nonstandard Models


Axiomatic Set Theory


An Axiom System


Ordinal Numbers


Equinumerosity. Finite and Denumerable Sets


Hartogs’ Theorem. Initial Ordinals. Ordinal Arithmetic


The Axiom of Choice. The Axiom of Regularity


Other Axiomatizations of Set Theory


Computability


Algorithms. Turing Machines


Diagrams


Partial Recursive Functions. Unsolvable Problems


The Kleene–Mostowski Hierarchy. Recursively Enumerable Sets


Other Notions of Computability


Decision Problems


Appendix A: Second-Order Logic


Appendix B: First Steps in Modal Propositional Logic


Answers to Selected Exercises


Bibliography


Notation


Index