Book:George S. Boolos/Computability and Logic/Third Edition
Jump to navigation
Jump to search
George S. Boolos and Richard C. Jeffrey: Computability and Logic (3rd Edition)
Published $\text {1989}$, Cambridge University Press
- ISBN 0-521-38923-2
Subject Matter
Contents
- Preface
- Preface to the third edition
- $1$ Enumerability
- $2$ Diagonalization
- $3$ Turing machines
- $4$ Uncomputability via the busy beaver problem
- $5$ Uncomputability via diagonalization
- $6$ Abacus computable functions are Turing computable
- $7$ Recursive functions are abacus computable
- $8$ Turing computable functions are recursive
- $9$ First-order logic revisited
- $10$ First-order logic is undecidable
- $11$ First-order logic formalized: derivations and soundness
- $12$ Completeness of the formalization; compactness
- $13$ The Skolem-Löwenheim theorem
- $14$ Representability in $Q$
- $15$ Undecidability, undefinability and incompleteness
- $16$ Provability predicates and the unprovability of consistency
- $17$ Non-standard models of arithmetic
- $18$ Second-order logic
- $19$ On defining arithmetical truth
- $20$ Definability in arithmetic and forcing
- $21$ The decidability of arithmetic with addition, but not multiplication
- $22$ Dyadic logic is undecidable: eliminating names and function symbols
- $23$ The Craig interpolation lemma
- $24$ Two applications of Craig's lemma
- $25$ Monadic versus dyadic logic
- $26$ Ramsey's theorem
- $27$ Provability considered modal-logically
- $28$ Undecidable sentences
- $29$ Non-standard models of $Z$ are not recursive
- Index
Further Editions
- 1974: George S. Boolos and Richard C. Jeffrey: Computability and Logic
- 1980: George S. Boolos and Richard C. Jeffrey: Computability and Logic (2nd ed.)
- 2002: George S. Boolos, Richard C. Jeffrey and John P. Burgess: Computability and Logic (4th ed.)
- 2007: George S. Boolos, John P. Burgess and Richard C. Jeffrey: Computability and Logic (5th ed.)
Source work progress
- 1989: George S. Boolos and Richard C. Jeffrey: Computability and Logic (3rd ed.) ... (previous): $1$ Enumerability
- In-depth discussion about partial functions and enumerations which needs attention