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

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

## Contents

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

## Source work progress

- 1989: George S. Boolos and Richard C. Jeffrey:
*Computability and Logic*(3rd ed.): Not properly started yet. Edition to be resolved.