A First Course in Logic

Preliminaries

Chapter 1: Propositional Logic

1. What is propositional logic?
2. Validity, satisfiability, and contradiction
3. Consequence and equivalence
4. Formal proofs
5. Proofs by induction
   1. Mathematical induction
   2. Induction on the complexity of formulas
6. Normal forms
7. Horn formulas
8. Resolution
   1. Clauses
   2. Resolvents
   3. Completeness of resolution
9. Completeness and compactness

Chapter 2: Structures and first-order logic

1. The language of first-order logic
2. The syntax of first-order logic
3. Semantics and structures
4. Examples of structures
   1. Graphs
   2. Relational databases
   3. Linear orders
   4. Number systems
5. The size of a structure
6. Relations between structures
   1. Embeddings
   2. Substructures
   3. Diagrams
7. Theories and models

Chapter 3: Proof Theory

1. Formal proofs
2. Normal forms
   1. Conjunctive prenex normal form
   2. Skolem normal form
3. Herbrand theory
   1. Herbrand structures
   2. Dealing with equality
   3. The Herbrand method
4. Resolution for first-order logic
   1. Unification
   2. Resolution
5. SLD-resolution
6. Prolog

Chapter 4: Properties of first-order logic

1. The countable case
2. Cardinal knowledge
   1. Ordinal numbers
   2. Cardinal arithmetic
   3. Continuum hypotheses
3. Four theorems of first-order logic
4. Amalgamation of structures
5. Preservation of formulas
   1. Supermodels and submodels
   2. Unions of chains
6. Amalgamation of vocabularies
7. The expressive power of first-order logic

Chapter 5: First-order theories

1. Completeness and decidability
2. Categoricity
3. Countably categorical theories
   1. Dense linear orders
   2. Ryll-Nardewski et al.
4. The random graph and 0-1 laws
5. Quantifier elimination
   1. Finite relational vocabularies
   2. The general case
6. Model-completeness
7. Minimal theories
8. Fields and vector spaces
9. Some algebraic geometry

Chapter 6: Models of countable theories

1. Types
2. Isolated types
3. Small models of small theories
   1. Atomic models
   2. Homogeneity
   3. Prime models
4. Big models of small theories
   1. Countable saturated models
   2. Monster models
5. Theories with many types
6. The number of nonisomorphic models
7. A touch of stability

Chapter 7: Computability and complexity

1. Computable functions and Church's thesis
   1. Primitive recursive functions
   2. The Ackermann function
   3. Recursive functions
2. Computable sets and relations
3. Computing machines
4. Codes
5. Semi-decidable decision problems
6. Undecidable decision problems
   1. Nonrecursive sets
   2. The arithmetic hierarchy
7. Decidable decision problems
   1. Examples
   2. Time and space
   3. Nondeterministic polynomial-time
8. NP-completeness

Chapter 8: The incompleteness theorems

1. Axioms for first-order number theory
2. The expressive power of first-order number theory
3. Gödel's First Incompleteness theorem
4. Gödel's codes
5. Gödel's Second Incompleteness Theorem
6. Goodstein sequences

Chapter 9: Beyond first-order logic

1. Second-order logic
2. Infinitary logics
3. Fixed-point logics
4. Lindström's theorem

Chapter 10: Finite model theory

1. Finite variable logics
2. Classical failures
3. Descriptive complexity
4. Logic and the P=NP problem

Bibliography

Index