# Book:George S. Boolos/Computability and Logic/Third Edition

Jump to navigation
Jump to search
## George S. Boolos and Richard C. Jeffrey:

## 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