Computability and Logic

Front Cover
Cambridge University Press, 2002 - Philosophy - 356 pages
2 Reviews
Now in its fourth edition, this book has become a classic because of its accessibility to students without a mathematical background, and because it covers not only 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. John Burgess has enhanced the book by adding a selection of problems at the end of each chapter.
  

What people are saying - Write a review

Review: Computability and Logic

User Review  - Warunika Ranaweera - Goodreads

Simple, yet complete, presentation of the underlying theories of Computability; beautifully explained. Read full review

Review: Computability and Logic

User Review  - Lane Wilkinson - Goodreads

A vast improvement over the fourth edition. Still the best introduction to advanced logic and metatheory. Read full review

Selected pages

Contents

Enumerability
3
12 Enumerable Sets
7
Diagonalization
16
Turing Computability
23
Uncomputability
35
42 The Productivity Function
40
Abacus Computability
45
52 Simulating Abacus Machines by Turing Machines
51
152 Godel Numbers
192
153 More Godel Numbers
196
Representability of Recursive Functions
199
162 Minimal Arithmetic and Representability
207
163 Mathematical Induction
212
164 Robinson Arithmetic
215
Indefinability Undecidability Incompleteness
221
172 Undecidable Sentences
225

53 The Scope of Abacus Computability
57
Recursive Functions
63
62 Minimization
70
Recursive Sets and Relations
73
72 Semirecursive Relations
80
73 Further Examples
83
Equivalent Definitions of Computability
88
82 Universal luring Machines
94
83 Recursively Enumerable Sets
96
A Precis of FirstOrder Logic Syntax
101
92 Syntax
106
A Precis of FirstOrder Logic Semantics
114
102 Metalogical Notions
119
The Undecidability of FirstOrder Logic
126
112 Logic and Primitive Recursive Functions
132
Models
137
122 Equivalence Relations
142
123 The LowenheimSkolem and Compactness Theorems
146
The Existence of Models
153
132 The First Stage of the Proof
156
133 The Second Stage of the Proof
157
134 The Third Stage of the Proof
160
135 Nonenumerable Languages
162
Proofs and Completeness
166
142 Soundness and Completeness
174
143 Other Proof Procedures and Hilberts Thesis
179
Arithmetization
187
173 Undecidable Sentences without the Diagonal Lemma
227
The Unprovability of Consistency
233
Normal Forms
243
192 Skolem Normal Form
247
193 Herbrands Theorem
253
194 Eliminating Function Symbols and Identity
255
The Craig Interpolation Theorem
260
202 Robinsons Joint Consistency Theorem
264
203 Beths Definability Theorem
265
Monadic and Dyadic Logic
270
212 Monadic Logic
273
213 Dyadic Logic
275
SecondOrder Logic
279
Arithmetical Definability
286
232 Arithmetical Definability and Forcing
289
Decidability of Arithmetic without Multiplication
295
Nonstandard Models
302
252 Operations in Nonstandard Models
306
253 Nonstandard Models of Analysis
312
Ramseys Theorem
319
262 Konigs Lemma
322
Modal Logic and Provability
327
272 The Logic of Provability
334
273 The Fixed Point and Normal Form Theorems
337
Hints for Selected Problems
341
Index
349
Copyright

Common terms and phrases

References to this book

All Book Search results »

About the author (2002)

Boolos was Professor of Philosophy, Massachusetts Institute of Technology

Bibliographic information