- •Contents
- •Preface to the Fifth Edition
- •1 Enumerability
- •1.1 Enumerability
- •1.2 Enumerable Sets
- •Problems
- •2 Diagonalization
- •Problems
- •3 Turing Computability
- •Problems
- •4 Uncomputability
- •4.1 The Halting Problem
- •4.2* The Productivity Function
- •Problems
- •5 Abacus Computability
- •5.1 Abacus Machines
- •5.2 Simulating Abacus Machines by Turing Machines
- •5.3 The Scope of Abacus Computability
- •Problems
- •6 Recursive Functions
- •6.1 Primitive Recursive Functions
- •6.2 Minimization
- •Problems
- •7 Recursive Sets and Relations
- •7.1 Recursive Relations
- •7.2 Semirecursive Relations
- •7.3* Further Examples
- •Problems
- •8.1 Coding Turing Computations
- •8.2 Universal Turing Machines
- •8.3∗ Recursively Enumerable Sets
- •Problems
- •9.1 First-Order Logic
- •9.2 Syntax
- •Problems
- •10.1 Semantics
- •10.2 Metalogical Notions
- •Problems
- •11 The Undecidability of First-Order Logic
- •11.1 Logic and Turing Machines
- •11.2 Logic and Primitive Recursive Functions
- •11.3 Lemma
- •Problems
- •12 Models
- •12.1 The Size and Number of Models
- •12.2 Equivalence Relations
- •Problems
- •13 The Existence of Models
- •13.1 Outline of the Proof
- •13.2 The First Stage of the Proof
- •13.3 The Second Stage of the Proof
- •13.4 The Third Stage of the Proof
- •13.5* Nonenumerable Languages
- •Problems
- •14 Proofs and Completeness
- •14.1 Sequent Calculus
- •14.2 Soundness and Completeness
- •14.3* Other Proof Procedures and Hilbert’s Thesis
- •Problems
- •15 Arithmetization
- •15.1 Arithmetization of Syntax
- •Problems
- •16 Representability of Recursive Functions
- •16.2 Minimal Arithmetic and Representability
- •16.3 Mathematical Induction
- •16.4* Robinson Arithmetic
- •Problems
- •17.1 The Diagonal Lemma and the Limitative Theorems
- •17.2 Undecidable Sentences
- •17.3* Undecidable Sentences without the Diagonal Lemma
- •Problems
- •18 The Unprovability of Consistency
- •Historical Remarks
- •19 Normal Forms
- •19.1 Disjunctive and Prenex Normal Forms
- •19.2 Skolem Normal Form
- •19.3 Herbrand’s Theorem
- •19.4 Eliminating Function Symbols and Identity
- •Problems
- •20 The Craig Interpolation Theorem
- •20.1 Craig’s Theorem and Its Proof
- •20.2 Robinson’s Joint Consistency Theorem
- •20.3 Beth’s Definability Theorem
- •Problems
- •21 Monadic and Dyadic Logic
- •21.1 Solvable and Unsolvable Decision Problems
- •21.2 Monadic Logic
- •21.3 Dyadic Logic
- •Problems
- •22 Second-Order Logic
- •Problems
- •23.2 Arithmetical Definability and Forcing
- •Problems
- •24 Decidability of Arithmetic without Multiplication
- •Problems
- •25 Nonstandard Models
- •25.1 Order in Nonstandard Models
- •25.2 Operations in Nonstandard Models
- •25.3 Nonstandard Models of Analysis
- •Problems
- •26 Ramsey’s Theorem
- •Problems
- •27 Modal Logic and Provability
- •27.1 Modal Logic
- •27.2 The Logic of Provability
- •27.3 The Fixed Point and Normal Form Theorems
- •Problems
- •Annotated Bibliography
- •General Reference Works
- •Textbooks and Monographs
- •By the Authors
- •Index
Annotated Bibliography
General Reference Works
BARWISE, JON (1977) (ed.), Handbook of Mathematical Logic (Amsterdam: North Holland). A collection of survey articles with references to further specialist literature, the last article being an exposition of the Paris–Harrington theorem.
GABBAY, DOV, and GUENTHNER, FRANZ (1983) (eds.), Handbook of Philosophical Logic (4 vols.) (Dordrecht: Reidel). A collection of survey articles covering classical logic, modal logic and allied subjects, and the relation of logical theory to natural language. Successive volumes of an openended, much-expanded second edition have been appearing since 2001.
VAN HEIJENOORT, JEAN (1967) (ed.), From Frege to Godel:¨ A Source Book in Mathematical Logic, 1879–1931 (Cambridge, Massachusetts: Harvard University Press). A collection of classic papers showing the development of the subject from the origins of truly modern logic through the incompleteness theorems.
Textbooks and Monographs
ENDERTON, HERBERT (2001), A Mathematical Introduction to Logic, 2nd ed. (New York: Harcourt/ Academic Press). An undergraduate textbook directed especially to students of mathematics and allied fields.
KLEENE, STEVEN COLE (1950), Introduction to Metamathematics (Princeton: D. van Nostrand). The text from which many of the older generation first learned the subject, containing many results still not readily found elsewhere.
SHOENFIELD, JOSEPH R. (1967), Mathematical Logic (Reading, Massachusetts: Addison-Wesley). The standard graduate-level text in the field.
TARSKI, ALFRED, MOSTOWSKI, ANDRZEJ, and ROBINSON, RAPHAEL (1953), Undecidable Theories
(Amsterdam: North Holland). A treatment putting Godel’s¨ first incompleteness theorem in its most general formulation.
By the Authors
BOOLOS, GEORGE S. (1993), The Logic of Provability (Cambridge, U.K.: Cambridge University Press). A detailed account of work on the modal approach to provability and unprovability introduced in the last chapter of this book.
JEFFREY, RICHARD C. (1991), Formal Logic: Its Scope and Limits, 4th ed. (Indianapolis: Hackett). An introductory textbook, supplying more than enough background for this book.
341