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

From ProofWiki
Jump to navigation Jump to search

George S. Boolos and Richard C. Jeffrey: Computability and Logic (3rd Edition)

Published $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