ProofWiki:Books/George S. Boolos/Computability and Logic

George S. Boolos and Richard C. Jeffrey: Computability and Logic

Published 1974 (3rd Edition 1989), Cambridge University Press.

ISBN 0-521-38923-2

Subject Matter

• Mathematical Logic

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