Computability and Logic

by George S. Boolos , John P. Burgess , Richard C. Jeffrey

• ISBN13: 9780521877527
• ISBN10: 0521877520
• Edition: 5th
• Format: Hardcover
• Copyright: 2007-09-17
• Publisher: Cambridge University Press

Summary

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. This fifth edition has been thoroughly revised by John Burgess. 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. This new edition is also accompanied by a website as well as an instructor's manual.

Table of Contents

Preface to the Fifth Edition	p. xi
Computability Theory
Enumerability	p. 3
Enumerability	p. 3
Enumerable Sets	p. 7
Diagonalization	p. 16
Turing Computability	p. 23
Uncomputability	p. 35
The Halting Problem	p. 35
The Productivity Function	p. 40
Abacus Computability	p. 45
Abacus Machines	p. 45
Simulating Abacus Machines by Turing Machines	p. 51
The Scope of Abacus Computability	p. 57
Recursive Functions	p. 63
Primitive Recursive Functions	p. 63
Minimization	p. 70
Recursive Sets and Relations	p. 73
Recursive Relations	p. 73
Semirecursive Relations	p. 80
Further Examples	p. 83
Equivalent Definitions of Computability	p. 88
Coding Turing Computations	p. 88
Universal Turing Machines	p. 94
Recursively Enumerable Sets	p. 96
Basic Metalogic
A Precis of First-Order Logic: Syntax	p. 101
First-Order Logic	p. 101
Syntax	p. 106
A Precis of First-Order Logic: Semantics	p. 114
Semantics	p. 114
Metalogical Notions	p. 119
The Undecidability of First-Order Logic	p. 126
Logic and Turing Machines	p. 126
Logic and Primitive Recursive Functions	p. 132
Models	p. 137
The Size and Number of Models	p. 137
Equivalence Relations	p. 142
The Lowenheim-Skolem and Compactness Theorems	p. 146
The Existence of Models	p. 153
Outline of the Proof	p. 153
The First Stage of the Proof	p. 156
The Second Stage of the Proof	p. 157
The Third Stage of the Proof	p. 160
Nonenumerable Languages	p. 162
Proofs and Completeness	p. 166
Sequent Calculus	p. 166
Soundness and Completeness	p. 174
Other Proof Procedures and Hilbert's Thesis	p. 179
Arithmetization	p. 187
Arithmetization of Syntax	p. 187
Godel Numbers	p. 192
More Godel Numbers	p. 196
Representability of Recursive Functions	p. 199
Arithmetical Definability	p. 199
Minimal Arithmetic and Representability	p. 207
Mathematical Induction	p. 212
Robinson Arithmetic	p. 216
Indefinability, Undecidability, Incompleteness	p. 220
The Diagonal Lemma and the Limitative Theorems	p. 220
Undecidable Sentences	p. 224
Undecidable Sentences without the Diagonal Lemma	p. 226
The Unprovability of Consistency	p. 232
Further Topics
Normal Forms	p. 243
Disjunctive and Prenex Normal Forms	p. 243
Skolem Normal Form	p. 247
Herbrand's Theorem	p. 253
Eliminating Function Symbols and Identity	p. 255
The Craig Interpolation Theorem	p. 260
Craig's Theorem and Its Proof	p. 260
Robinson's Joint Consistency Theorem	p. 264
Beth's Definability Theorem	p. 265
Monadic and Dyadic Logic	p. 270
Solvable and Unsolvable Decision Problems	p. 270
Monadic Logic	p. 273
Dyadic Logic	p. 275
Second-Order Logic	p. 279
Arithmetical Definability	p. 286
Arithmetical Definability and Truth	p. 286
Arithmetical Definability and Forcing	p. 289
Decidability of Arithmetic without Multiplication	p. 295
Nonstandard Models	p. 302
Order in Nonstandard Models	p. 302
Operations in Nonstandard Models	p. 306
Nonstandard Models of Analysis	p. 312
Ramsey's Theorem	p. 319
Ramsey's Theorem: Finitary and Infinitary	p. 319
Konig's Lemma	p. 322
Modal Logic and Provability	p. 327
Modal Logic	p. 327
The Logic of Provability	p. 334
The Fixed Point and Normal Form Theorems	p. 337
Annotated Bibliography	p. 341
Index	p. 343
Table of Contents provided by Ingram. All Rights Reserved.