Abstract
This book presents computability theory as part of mathematical logic. Its opening part covers the standard first-course material: enumerability, diagonalization, Turing computability, uncomputability, abacus machines, recursive functions, recursive sets and relations, and equivalent characterizations of computability. The later parts connect this material to first-order logic, models, completeness, arithmetization, representability, incompleteness, definability, and provability.
Outline
Part I: Computability Theory
- Enumerability and enumerable sets
- Diagonalization arguments
- Turing computability
- Uncomputability and the Halting Problem
- Abacus computability
- Primitive recursive functions and minimization
- Recursive sets, recursive relations, and semirecursive relations
- Coding computations, universal machines, and recursively enumerable sets
Part II: Basic Metalogic
- Syntax and semantics for first-order logic
- Metalogical notions
- The undecidability of first-order logic
- Models, equivalence relations, and the Loewenheim-Skolem and compactness theorems
- Proof systems, sequent calculus, soundness, and completeness
- Arithmetization of syntax and Godel numbering
- Representability of recursive functions in arithmetic
- Indefinability, undecidability, incompleteness, and the unprovability of consistency
Part III: Further Topics
- Normal forms and Herbrand’s theorem
- Craig interpolation, Beth definability, and joint consistency
- Monadic and dyadic logic
- Second-Order Logic
- Arithmetical definability and forcing
- Decidability of arithmetic without multiplication
- Nonstandard models
- Ramsey’s theorem and Konig’s lemma
- Modal logic and provability
https://www.cambridge.org/core/books/computability-and-logic/440B4178B7CBF1C241694233716AB271