Foundations of Logic: Completeness, Incompleteness, Computability

by Dag Westerståhl

Overview

A comprehensive introduction to logic’s central concepts.

This book provides a concise but detailed account of modern logic's three cornerstones: the completeness of first-order logic, Gödel's Incompleteness Theorems, and Turing's analysis of computability. In addition to the central text, an appendix explains the required technical terminology and facts. The main ideas behind the three cornerstones are explained in a simple, easy-to-grasp manner, and it is possible to select among the chapters and sections so that the reader becomes familiar with these ideas, even if some technicalities are skipped or postponed. A wealth of exercises accompany a wide selection of materials, including the histories and philosophical implications of the three main premises, making it useful as a textbook for undergraduate or graduate courses focusing on any of the three main themes. The material is rigorous and detailed but keeps the main ideas in sight, and there are numerous excursions into more advanced material for curious readers to explore. 

Product Details

ISBN-13:	9781684000005
Publisher:	Center for the Study of Language and Inf
Publication date:	01/05/2024
Pages:	451
Product dimensions:	6.00(w) x 9.00(h) x 1.40(d)

About the Author

Dag Westerståhl is professor emeritus of theoretical philosophy and logic at Stockholm University. His recent research is in the area of generalized quantifiers, formal semantics, and the philosophy of logic.

Table of Contents

Preface xiii
1 Introduction 1
1.1 Completeness 1
1.2 Incompleteness 2
1.3 Computability 3
1.4 Plan 5I Background 7
2 First-order logic 9
2.1 Object language and metalanguage 9
2.2 Propositional logic (PL) 11
2.2.1 PL syntax 11
2.2.2 PL semantics 15
2.2.3 Logical consequence 17
2.3 First-order logic (FOL) 21
2.3.1 FOL syntax 21
2.3.2 FOL semantics 31
2.3.3 Logical consequence (again) 39
2.3.4 Equivalent formulas 41
2.4 Exercises to Chapter 2 433 Inference 52
3.1 Natural deduction 54
3.1.1 Rules for the connectives 55
3.1.2 Rules for the quantifiers and identity 65
3.1.3 Exercises to Chapter 3.1 69
3.2 Interlude: constants as parameters 72
3.3 A Hilbert system 74
3.3.1 Axioms and rules 74
3.3.2 The Deduction Theorem 81
3.3.3 *H versus ND 83
3.3.4 Exercises to Chapter 3.3 85II Completeness 91
4 Completeness: PL 93
4.1 Soundness 94
4.2 Derivability and consistency 95
4.3 Maximal consistent sets 96
4.4 Building the interpretation 98
4.5 Lindenbaum’s Lemma 99
4.6 Overview 101
4.7 *Digression: maximal consistent sets as possible worlds 101
4.8 Exercises to Chapter 4 1035 Completeness: FOL 108
5.1 Models 108
5.2 Structure of the proof 110
5.3 Model construction and Truth Lemma 110
5.4 Proof of Lindenbaum’s Lemma 112
5.5 Bringing in identity 114
5.6 Exercises to Chapter 5 1186 Model theory 121
6.1 Expressing numerical claims 122
6.1.1 Numerical quantifiers 123
6.2 Order relations 124
6.3 Equivalence relations 125
6.4 Isomorphic models 128
6.4.1 The Isomorphism Lemma 129
6.4.2 Examples 131
6.5 *Definability 133
6.6 Theories 136
6.6.1 Axiomatizable theories 141
6.6.2 Categorical theories 142
6.6.3 Complete theories 144
6.7 The Compactness Theorem 146
6.8 The Löwenheim-Skolem Theorem 150
6.9 Other quantifiers 153
6.9.1 Generalized quantifiers 154
6.9.2 Quantifiers and natural language 156
6.10 Back-and-forth of elementary equivalence 159
6.10.1 EF-games 160
6.10.2 Three applications 162
6.10.3 A formulation without games 163
6.11 *Lindström’s Theorem 164
6.12 Concluding remarks 168
6.13 Exercises to Chapter 6 169III Incompleteness 179
7 Incompleteness and undecidability 181
7.1 Background to Parts III and IV 181
7.1.1 Incompleteness 181
7.1.2 Computability 183
7.1.3 Outline 185
7.2 Road to incompleteness 187
7.2.1 First-order theories 188
7.2.2 Arithmetical theories and truth 189
7.2.3 The incompleteness theorems 190
7.2.4 To do 193
7.3 Exercises to Chapter 7 1988 Primitive recursive functions & relations 201
8.1 Basic functions 201
8.2 Composition 202
8.3 Primitive recursion 204
8.4 *(Incredibly) fast growing functions 207
8.5 Examples of recursive functions and relations 209
8.5.1 Predecessors, subtraction, sign functions, etc. 211
8.5.2 Booleans, bounded quantification and -operator, definition by cases 212
8.6 Division 214
8.6.1 Remainder and quotient 214
8.6.2 *Using the integers 215
8.6.3 *Greatest common divisor 215
8.6.4 *Congruence classes 217
8.6.5 Enumerating the prime numbers 218
8.6.6 *The fundamental theorem of arithmetic 218
8.6.7 *The Chinese remainder theorem 219
8.7 Coding finite sequences 221
8.7.1 Coding with exponentiation and prime numbers 221
8.7.2 *Coding with the  function: 1 223
8.7.3 *Coding with the  function: 2 224
8.7.4 *Coding by iterating the pairing function 225
8.8 Course-of-values recursion 226
8.9 Exercises to Chapter 8 2279 Peano Arithmetic 232
9.1 The axioms of PA 232
9.2 Properties of addition and multiplication 234
9.3 Digression: 2+2=4 236
9.4 The order relation in PA 238
9.5 More on addition, multiplication, order 240
9.6 Bounded quantification in PA 241
9.7 Closed terms in PA 243
9.8 Arithmetical definability 244
9.9 Representability in arithmetical theories 245
9.9.1 Representable functions 246
9.9.2 Strongly representable functions 248
9.10 Exercises to Chapter 9 25010 Representability of p. r. functions 255
10.1 The basic functions are representable 255
10.2 Composition and representability 256
10.3 Representability of primitive recursion 257
10.4 Summary and comment 260
10.5 Exercises to Chapter 10 26111 Arithmetization 263
11.1 Gödel numbering of PA 264
11.2 Syntax as number theory 266
11.3 Terms and formulas 266
11.4 Sentences 267
11.5 Axioms 268
11.6 *Substitution 269
11.7 Proofs 274
11.8 The formula PrfT px; yq 275
11.9 Exercises to Chapter 11 27712 Incompleteness 280
12.1 The Diagonal Lemma 282
12.2 The first incompleteness theorem 284
12.3 Rosser sentences 286
12.4 The second incompleteness theorem 288
12.4.1 *Reflexive theories 290
12.4.2 *The sentence ConT 291
12.5 Löb’s theorem 293
12.6 *More about the provability predicate 295
12.7 *Provability and modal logic 297
12.7.1 A modal notation 297
12.7.2 Basic modal logic 299
12.7.3 Provability logic 300
12.8 Incompleteness for other theories 301
12.8.1 Interpretability 302
12.8.2 *Interpretability of consistency 305
12.9 What do Gödel’s theorems mean? 307
12.9.1 Goldbach-like statements 307
12.9.2 Truth and consistency 309
12.10 Exercises to Chapter 12 311IV Computability 321
13 Decidability 323
13.1 Decidability 1: definitions and facts 325
13.1.1 Turing machines 325
13.1.2 Recursive functions 332
13.1.3 Turing computability versus recursivity 335
13.1.4 Representability of recursive functions 337
13.1.5 The incompleteness theorems revisited 338
13.2 *Decidability 2: details 339
13.2.1 Recursive functions are strongly computable 339
13.2.2 Computable functions are recursive 344
13.3 Exercises to Chapter 13 34714 Undecidability 350
14.1 Undecidable extensions of PA 350
14.2 Finitely axiomatizable arithmetical theories 352
14.3 The undecidability of first-order logic 354
14.3.1 *Digression: some decidable theories 355
14.4 Robinson arithmetic 357
14.5 Representability by Ε1 formulas 360
14.5.1 Δ0, Ε1, and Π1 formulas 361
14.5.2 Ε1-completeness and its consequences 364
14.5.3 Complexity of some familiar formulas 368
14.6 *Weak systems of arithmetic 370
14.7 Undecidability of the halting problem 374
14.8 Exercises to Chapter 14 37715 Computability theory 384
15.1 Recursively enumerable sets 386
15.1.1 Basic properties 386
15.1.2 Craig’s Theorem 389
15.1.3 Sets versus relations 390
15.2 Post’s Lemma 391
15.3 Representability again 393
15.4 The arithmetical hierarchy 396
15.5 *Hilbert’s 10th problem 401
15.6 Universal Turing machines 403
15.7 The s-m-n theorem 406
15.8 Enumerating the r.e. sets 407
15.9 *The Fixed Point Theorem 410
15.10 m-reducibility 411
15.11 Post’s Problem, creative and simple sets 419
15.12 Taking stock 424
15.13 Applications to logic 425
15.13.1 The set of true arithmetical sentences 426
15.13.2 Creative theories 429
15.14 Exercises to Chapter 15 430V Appendix 443
16 Sets, functions, relations 445
16.1 Sets 445
16.1.1 Exercises to Section 16.1 450

Editorial Reviews

"The most attractively written book at its level that I have newly encountered for some years. . . . The expositional choices are very well-judged, and the balance between motivational chat and worked-through formal details seems just right to me. Many student readers should find this book quite excellent for self-study."

Logic Matters