Computability and Logic Fifth Edition

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

computability And Logic Is A Classic Because Of Its Accessibility To Students Without A Mathematical Background.

booknews

this Intermediate Logic Textbook For Philosophy And Computer Science Students Introduces Gödel's Completeness Theorem, Several Incompleteness Theorems, Their Attendant Lemmas And Corollaries, The Theory Of Turing Machines, Recursive Functions, Definability, And Decidability. The Fourth Edition Adds Problems At The End Of Each Chapter. Annotation C. Book News, Inc., Portland, Or (booknews.com)

This fifth edition of 'Computability and Logic' covers not just the staple topics of an intermediate logic course such as Godel's incompleteness theorems, but also optional topics that include Turing's theory of computability and Ramsey's theorem The third edition has been corrected and contains thoroughly revised versions of the chapters on Ramsey and probability, with new exercises provided for three other chapters. There are also two new chapters dealing with undecidable sentences.