- Introduction
- An Example from Group Theory
- An Example from the Theory of Equivalence Relations
- A Preliminary Analysis
- Preview
- Syntax of First-Order Languages
- Alphabets
- The Alphabet of a First-Order Language
- Terms and Formulas in First-Order Language
- Induction in the Calculi of Terms and of Formulas
- Free Variables and Sentences
- Semantics of First-Order Languages
- Structures and Interpretations
- Standardization of Connectives
- The Satisfaction Relation
- The Consequence Relation
- Two Lemmas on the Satisfaction Relation
- Some Simple Formalizations
- Some Remarks on Formalizability
- Substitution
- A Sequent Calculus
- Sequent Rules
- Structural Rules and Connective Rules
- Derivable Connective Rules
- Quantifier and Equality Rules
- Further Derivable Rules
- Summary and Example
- Consistency
- The Completeness Theorem
- Henkin's Theorem
- Satisfiability of Consistent Sets of Formulas (the Countable Case)
- Satisfiability of Consistent Sets of Formulas (the General Case)
- The Completeness Theorem
- The Löwenheim-Skolem and the Compactness Theorem
- The Löwenheim-Skolem Theorem
- The Compactness Theorem
- Elementary Classes
- Elementarily Equivalent Structures
- The Scope of First-Order Logic
- The Notion of Formal Proof
- Mathematics Within the Framework of First-Order Logic
- The Zermelo-Fraenkel Axioms for Set Theory
- Set Theory as a Basis for Mathematics
- Syntactic Interpretations and Normal Forms
- Term-Reduced Formulas and Relational Symbol Sets
- Syntactic Interpretations
- Extensions by Definitions
- Normal Forms
- Extensions of First-Order Logic
- Second-Order Logic
- The System Lw1w
- The System LQ
- Computability and Its Limitations
- Decidability and Enumerability
- Register Machines
- The Halting Problem for Register Machines
- The Undecidability of First-Order Logic
- Trakhtenbrot's Theorem and the Incompleteness of Second-Order Logic
- Theories and Decidability
- Self-Referential Statements and Gödel's Incompleteness Theorems
- Decidability of Presburger Arithmetic
- Decidability of Weak Monadic Successor Arithmetic
- Free Models and Logic Programming
- Herbrand's Theorem
- Free Models and Universal Horn Formulas
- Herbrand Structures
- Propositional Logic
- Propositional Resolution
- First-Order Resolution (without Unification)
- Logic Programming
- An Algebraic Characterization of Elementary Equivalence
- Finite and Partial Isomorphisms
- Fraïssé's Theorem
- Proof of Fraïssé's Theorem
- Ehrenfeucht Games
- Lindström's Theorems
- Logical Systems
- Compact Regular Logical Systems
- Lindström's First Theorem
- Lindström's Second Theorem
- References
- List of Symbols
- Subject Index

- A
- I Introduction
- II Syntax of First-Order Languages
- III Semantics of First-Order Languages
- IV A Sequent Calculus
- V The Completeness Theorem
- VI The Löwenheim-Skolem and the Compactness Theorem
- VII The Scope of First-Order Logic
- VIII Syntactic Interpretations and Normal Forms
- B
- IX Extensions of First-Order Logic
- X Computability and Its Limitations
- XI Free Models and Logic Programming
- XII An Algebraic Characterization of Elementary Equivalence
- XIII Lindström's Theorems
- References
- List of Symbols
- Subject Index

This introduction to first-order logic clearly works out the role of first-order logic in the foundations of mathematics, particularly the two basic questions of the range of the axiomatic method and of theorem-proving by machines. It covers several advanced topics not commonly treated in introductory texts, such as Fraisse's characterization of elementary equivalence, Lindstroem's theorem on the maximality of first-order logic, and the fundamentals of logic programming.

(source: Nielsen Book Data)
This junior/senior level text is devoted to a study of first-order logic and its role in the foundations of mathematics: What is a proof? How can a proof be justified? To what extent can a proof be made a purely mechanical procedure? How much faith can we have in a proof that is so complex that no one can follow it through in a lifetime? The first substantial answers to these questions have only been obtained in this century. The most striking results are contained in Goedells work: First, it is possible to give a simple set of rules that suffice to carry out all mathematical proofs; but, second, these rules are necessarily incomplete - it is impossible, for example, to prove all true statements of arithmetic. The book begins with an introduction to first-order logic, Goedel's theorem, and model theory. A second part covers extensions of first-order logic and limitations of the formal methods. The book covers several advanced topics, not commonly treated in introductory texts, such as Trachtenbrot's undecidability theorem. Fraisse's elementary equivalence, and Lindstroem's theorem on the maximality of first-order logic.

(source: Nielsen Book Data)