Foundations of Logic: Completeness, Incompleteness, Computability
By Dag Westerståhl
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.
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.
December 2023
- Preface
- 1 Introduction
1.1 Completeness
1.2 Incompleteness
1.3 Computability
1.4 Plan
- Background
- First-order logic
2.1 Object language and metalanguage
2.2 Propositional logic (PL)
2.2.1 PL syntax
2.2.2 PL semantics
2.2.3 Logical consequence
2.3 First-order logic (FOL)
2.3.1 FOL syntax
2.3.2 FOL semantics
2.3.3 Logical consequence (again)
2.3.4 Equivalent formulas
2.4 Exercises to Chapter 2
- 3 Inference
3.1 Natural deduction
3.1.1 Rules for the connectives
3.1.2 Rules for the quantifiers and identity
3.1.3 Exercises to Chapter 3.1
3.2 Interlude: constants as parameters
3.3 A Hilbert system
3.3.1 Axioms and rules
3.3.2 The Deduction Theorem
3.3.3 *H versus ND
3.3.4 Exercises to Chapter 3.3
- II Completeness
- 4 Completeness: PL
4.1 Soundness
4.2 Derivability and consistency
4.3 Maximal consistent sets
4.4 Building the interpretation
4.5 Lindenbaum's Lemma
4.6 Overview
4.7 *Digression: maximal consistent sets as possible worlds
4.8 Exercises to Chapter 4
- 5 Completeness: FOL
5.1 Models
5.2 Structure of the proof
5.3 Model construction and Truth Lemma
5.4 Proof of Lindenbaum's Lemma
5.5 Bringing in identity
5.6 Exercises to Chapter 5
- 6 Model theory
6.1 Expressing numerical claims
6.1.1 Numerical quantifiers
6.2 Order relations
6.3 Equivalence relations
6.4 Isomorphic models
6.4.1 The Isomorphism Lemma
6.4.2 Examples
6.5 *Definability
6.6 Theories
6.6.1 Axiomatizable theories
6.6.2 Categorical theories
6.6.3 Complete theories
6.7 The Compactness Theorem
6.8 The Löwenheim-Skolem Theorem
6.9 Other quantifiers
6.9.1 Generalized quantifiers
6.9.2 Quantifiers and natural language
6.10 Back-and-forth of elementary equivalence
6.10.1 EF-games
6.10.2 Three applications
6.10.3 A formulation without games
6.11 *Lindström's Theorem
6.12 Concluding remarks
6.13 Exercises to Chapter 6
- III Incompleteness
- 7 Incompleteness and undecidability
7.1 Background to Parts III and IV
7.1.1 Incompleteness
7.1.2 Computability
7.1.3 Outline
7.2 Road to incompleteness
7.2.1 First-order theories
7.2.2 Arithmetical theories and truth
7.2.3 The incompleteness theorems
7.2.4 To do
7.3 Exercises to Chapter 7
- 8 Primitive recursive functions & relations
8.1 Basic functions
8.2 Composition
8.3 Primitive recursion
8.4 *(Incredibly) fast growing functions
8.5 Examples of recursive functions and relations
8.5.1 Predecessors, subtraction, sign functions, etc.
8.5.2 Booleans, bounded quantification and -operator, definition by cases
8.6 Division
8.6.1 Remainder and quotient
8.6.2 *Using the integers
8.6.3 *Greatest common divisor
8.6.4 *Congruence classes
8.6.5 Enumerating the prime numbers
8.6.6 *The fundamental theorem of arithmetic
8.6.7 *The Chinese remainder theorem
8.7 Coding with exponentiation and prime numbers
8.7.2 *Coding with the function: 1
8.7.3 *Coding with the function: 2
8.7.4 *Coding by iterating the pairing function
8.8 Course-of-values recursion
8.9 Exercises to Chapter 8
- 9 Peano Arithmetic
9.1 The axioms of PA
9.2 Properties of addition and multiplication
9.3 Digression: 2+2=4
9.4 The order relation in PA
9.5 More on addition, multiplication, order
9.6 Bounded quantification in PA
9.7 Closed terms in PA
9.8 Arithmetical definability
9.9 Representability in arithmetical theories
9.9.1 Representable functions
9.10 Exercises to Chapter 9
- 10 Representability of p. r. functions
10.1 The basic functions are representable
10.2 Composition and representability
10.3 Representability of primitive recursion
10.4 Summary and commitment
10.5 Exercises to Chapter 10
- 11 Arithmetization
11.1 Gödel numbering of PA
11.2 Syntax as number theory
11.3 Terms and formulas
11.4 Sentencs
11.5 Axioms
11.6 *Substitution
11.7 Proofs
11.8 The formula PrfT px; yq
11.9 Exercises to Chapter 11
- 12 Incompleteness
12.1 The Diagonal Lemma
12.2 The first incompleteness theorem
12.3 Rosser sentences
12.4 The second incompleteness theorem
12.4.1 *Reflexive theories
12.4.2 *The sentence ConT
12.5 Löb's theorem
12.6 *More about the provability predicate
12.7 *Provability and modal logic
12.7.1 A modal notation
12.7.2 Basic modal logic
12.7.3 Provability logic
12.8 Incompleteness for other theories
12.8.1 Interpretability
12.8.2 *Interpretability of consistency
12.9 What do Gödel's theorems mean?
12.8.1 Goldbach-like statements
12.9.2 Truth and consistency
12.10 Exercises to Chapter 12
- IV Computability
- 13 Decidability
13.1 Decidability 1: definitions and facts
13.1.1 Turing machines
13.1.2 Recursive functions
13.1.3 Turing computability versus recursivity
13.1.4 Representability of recursive functions
13.1.5 The incompleteness theorems revisited
13.2 *Decidability 2: details
13.2.1 Recursive functions are strongly computable
13.2.2 Computable functions are recursive
13.3 Exercises to Chapter 13
- 14 Undecidability
14.1 Undecidable extensions of PA
14.2 Finitely axiomatizable arithmetical theories
14.3 The undecidability of first-order logic
14.3.1 *Digression: some decidable theories
14.4 Robinsons arithmetic
14.5 Representability by E1 formulas
14.5.1 ∆0 E1 and ∏1 formulas
14.5.2 E1-completeness and its consequences
14.5.3 Complexity of some familiar formulas
14.6 *Weak systems of arithmetic
14.7 Undecidability of the halting problem
14.8 Exercises to Chapter 14
- 15 Computability theory
15.1 Recursively enumerable sets
15.1.1 Basic properties
15.1.2 Craig's Theorem
15.1.3 Sets versus relations
15.2 Post's Lemma
15.3 Representability again
15.4 The arithmetical hierarchy
15.5 *Hilbert's 10th problem
15.6 Universal Turing machines
15.7 The s-m-n theorem
15.8 Enumerating the r.e. sets
15.9 *The Fixed Point Theorem
15.10 m-reducability
15.11 Post's Problem, creative and simple sets
15.12 Taking stock
15.13 Applications to logic
15.13.1 The set of true arithmetical sentences
15.13.2 Creative theories
15.14 Exercises to Chapter 15
- Appendix
- 16 Sets, functions, relations
16.1 Sets
16.1.1 Exercises to Section 16.1
ISBN (paperback): 9781684000005
ISBN (electronic): 9781684000784
|
Distributed by the
University of
Chicago Press
|
