## Computability and LogicNow 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 - GoodreadsSimple, yet complete, presentation of the underlying theories of Computability; beautifully explained. Read full review

#### Review: Computability and Logic

User Review - Lane Wilkinson - GoodreadsA vast improvement over the fourth edition. Still the best introduction to advanced logic and metatheory. Read full review

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

349 | |

### Common terms and phrases

arguments arithmetically definable atomic formulas atomic sentence axioms blank block called chapter Church's thesis closed term code number compactness theorem conjunction consider consistent constant contains Corollary deducible definition denotation derivation diagonal lemma disjunction domain effectively computable elements entry Example existential quantification finite set finite subset first-order first-order logic flow chart follows formal function symbols given Godel hence identity implies infinite isomorphic language of arithmetic Lemma Lowenheim-Skolem theorem monadic logic natural numbers negation nonenumerable nonlogical symbols nonstandard model normal form notation notion obtained one-place pairs positive integers preceding problem primitive recursive function Proposition provable prove Ramsey's theorem rational numbers real numbers recursive relation recursive set recursive total function result right number satisfiable second-order logic semirecursive set of sentences sets of natural Skolem standard interpretation strokes subformula Suppose tape theory true Turing computable Turing machine universal quantification unsatisfiable variables write zero