A First Course in Logic

An Introduction to Model Theory, Proof Theory, Computability, and Complexity

Shawn Hedman

cover
Oxford Texts in Logic Volume 1
430 pages - ISBN 0-19-852981-3

Description: A First Course in Logic is a unified introduction to model theory, proof theory, computability, and descriptive complexity. It provides a foundation for further study in any one of these related areas of modern logic. Beginning with the basics, this book takes the reader through many of the landmark results in logic achieved during the past century (including the Löwenhiem-Skolem Theorems, Beth's Definability Theorem, Lindström's Theorem, Trakhtenbrot's Theorem, Fagin's Theorem, and Gödel's Incompleteness Theorems). In addition to classical topics such as quantifier elimination and Herbrand theory, this book contains topics in logic that have recently become prominent such as descriptive complexity and strongly minimal theories. The book stresses the connections between logic and theoretical computer science including such topics as recursive sets, the completeness of resolution, and the P = NP problem.
From the back cover:

Contents

    Preliminaries
  1. Propositional logic
  2. Structures and first-order logic
  3. Proof theory
  4. Properties of first-order logic
  5. First-order theories
  6. Models of countable theories
  7. Computability and complexity
  8. The incompleteness theorems
  9. Beyond first-order logic
  10. Finite model theory
    Bibliography
    Index

Online Excerpts:

To Order: