Computability and Logic

George S. Boolos, John P. Burgess, Richard C. Jeffrey0521877520, 9780521877527, 9780521701464, 0521701465

Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel’s incompleteness theorems, but also a large number of optional topics, from Turing’s theory of computability to Ramsey’s theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems.

---

Table of contents :
Cover……Page 1
Half-title……Page 3
Title……Page 5
Copyright……Page 6
Dedication……Page 7
Contents……Page 9
Preface to the Fifth Edition……Page 13
1.1 Enumerability……Page 19
1.2 Enumerable Sets……Page 23
Problems……Page 30
2 Diagonalization……Page 32
Problems……Page 36
3 Turing Computability……Page 39
Problems……Page 50
4.1 The Halting Problem……Page 51
4.2* The Productivity Function……Page 56
Problems……Page 60
5.1 Abacus Machines……Page 61
5.2 Simulating Abacus Machines by Turing Machines……Page 67
5.3 The Scope of Abacus Computability……Page 73
Problems……Page 77
6.1 Primitive Recursive Functions……Page 79
6.2 Minimization……Page 86
Problems……Page 87
7.1 Recursive Relations……Page 89
7.2 Semirecursive Relations……Page 96
7.3* Further Examples……Page 99
Problems……Page 102
8.1 Coding Turing Computations……Page 104
8.2 Universal Turing Machines……Page 110
8.3∗ Recursively Enumerable Sets……Page 112
Problems……Page 113
9.1 First-Order Logic……Page 117
9.2 Syntax……Page 122
Problems……Page 128
10.1 Semantics……Page 130
10.2 Metalogical Notions……Page 135
Problems……Page 139
11.1 Logic and Turing Machines……Page 142
11.2 Logic and Primitive Recursive Functions……Page 148
Problems……Page 150
12.1 The Size and Number of Models……Page 153
12.2 Equivalence Relations……Page 158
12.3 The Lowenheim–Skolem and Compactness Theorems……Page 162
Problems……Page 165
13.1 Outline of the Proof……Page 169
13.2 The First Stage of the Proof……Page 172
13.3 The Second Stage of the Proof……Page 173
13.4 The Third Stage of the Proof……Page 176
13.5* Nonenumerable Languages……Page 178
Problems……Page 180
14.1 Sequent Calculus……Page 182
14.2 Soundness and Completeness……Page 190
14.3* Other Proof Procedures and Hilbert’s Thesis……Page 195
Problems……Page 201
15.1 Arithmetization of Syntax……Page 203
15.2* Godel Numbers……Page 208
15.3* More Godel Numbers……Page 212
Problems……Page 213
16.1 Arithmetical Definability……Page 215
16.2 Minimal Arithmetic and Representability……Page 223
16.3 Mathematical Induction……Page 228
16.4* Robinson Arithmetic……Page 232
Problems……Page 233
17.1 The Diagonal Lemma and the Limitative Theorems……Page 236
17.2 Undecidable Sentences……Page 240
17.3* Undecidable Sentences without the Diagonal Lemma……Page 242
Problems……Page 245
18 The Unprovability of Consistency……Page 248
Historical Remarks……Page 253
19.1 Disjunctive and Prenex Normal Forms……Page 259
19.2 Skolem Normal Form……Page 263
19.3 Herbrand’s Theorem……Page 269
19.4 Eliminating Function Symbols and Identity……Page 271
Problems……Page 274
20.1 Craig’s Theorem and Its Proof……Page 276
20.2 Robinson’s Joint Consistency Theorem……Page 280
20.3 Beth’s Definability Theorem……Page 281
Problems……Page 284
21.1 Solvable and Unsolvable Decision Problems……Page 286
21.2 Monadic Logic……Page 289
21.3 Dyadic Logic……Page 291
Problems……Page 294
22 Second-Order Logic……Page 295
Problems……Page 301
23.1 Arithmetical Definability and Truth……Page 302
23.2 Arithmetical Definability and Forcing……Page 305
Problems……Page 310
24 Decidability of Arithmetic without Multiplication……Page 311
Problems……Page 316
25.1 Order in Nonstandard Models……Page 318
25.2 Operations in Nonstandard Models……Page 322
25.3 Nonstandard Models of Analysis……Page 328
Problems……Page 333
26.1 Ramsey’s Theorem: Finitary and Infinitary……Page 335
26.2 Konig’s Lemma……Page 338
Problems……Page 342
27.1 Modal Logic……Page 343
27.2 The Logic of Provability……Page 350
27.3 The Fixed Point and Normal Form Theorems……Page 353
Problems……Page 356
By the Authors……Page 357
Index……Page 359