**Preface xiii**

1 Introduction 1
1.1 Completeness 1

1.2 Incompleteness 2

1.3 Computability 3

1.4 Plan 5

**I 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 43

**3 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 85

**II 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 103

**5 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 118

**6 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 169

**III 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 198

**8 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 227

**9 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 250

**10 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 261

**11 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 277

**12 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 311

**IV 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 347

**14 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 377

**15 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 430

**V Appendix 443**

16 Sets, functions, relations 445
16.1 Sets 445

16.1.1 Exercises to Section 16.1 450