A short digression into model theory will help us to analyze the expressive power of the first-order language, and it will turn out that there are certain deficiencies. For example, the first-order language does not allow the formulation of an adequate axiom system for arithmetic or analysis. On the other hand, this di~culty can be overcome---even in the framework of first-order logic--by developing mathematics in set-theoretic terms. We explain the prerequisites from set theory necessary for this purpose and then treat the subtle relation between logic and set theory in a thorough manner.
Godel's incompleteness theorems are presented in connection with several related results (such as Trahtenbrot's theorem) which all exemplify the limitatious of machine-oriented proof methods. The notions of computability theory that are relevant to this discussion are given in detail. The concept of computability is made precise by means of the register machine as a computer model.
Preface
PART A
I Introduction
§1. An Example from Group Theory
§2. An Example from the Theory of Equivalence Relations
§3. A Preliminary Analysis
§4. Preview
II Syntax of First-Order Languages
§1. Alphabets
§2. The Alphabet of a First-Order Language
§3. Terms and Formulas in First-Order Languages
§4. Induction in the Calculus of Terms and in the Calculus of Formulas
§5. Free Variables and Sentences
III Semantics of First-Order Languages
§1. Structures and Interpretations
§2. Standardization of Connectives
§3. The Satisfaction Relation
§4. The Consequence Relation
§5. Two Lemmas on the Satisfaction Relation
§6. Some Simple Formalizations
§7. Some Remarks on Formalizability
§8. Substitution
IV A Sequent Calculus
§1. Sequent Rules
§2. Structural Rules and Connective Rules
§3. Derivable Connective Rules
§4. Quantifier and Equality Rules
§5. Further Derivable Rules and Sequents
§6. Summary and Example
§7. Consistency
V The Completeness Theorem
§1. Henkin's Theorem
§2. Satisfiability of Consistent Sets of Formulas (the Countable Case)
§3. Satisfiability of Consistent Sets of Formulas (the General Case)
§4. The Completeness Theorem
VI The Lowenheim-Skolem and the Compactness Theorem
§1. The L6wenheim-Skolem Theorem
§2. The Compactness Theorem
§3. Elementary Classes
§4. Elementarily Equivalent Structures
VII The Scope of First-Order Logic
§1. The Notion of Formal Proof
§2. Mathematics Within the Framework of First-Order Logic
§3. The Zermelo-Fraenkel Axioms for Set Theory
§4. Set Theory as a Basis for Mathematics
VIII Syntactic Interpretations and Normal Forms
§1. Term-Reduced Formulas and Relational Symbol Sets
§2. Syntactic Interpretations
§3. Extensions by Definitions
§4. Normal Forms
PART B
IX Extensions of First-Order Logic
§1. Second-Order Logic
§2. The System L
§3. The System L
X Limitations of the Formal Method
§1. Decidability and Enumerability
§2. Register Machines
§3. The Halting Problem for Register Machines
§4. The Undecidahility of First-Order Logic
§5. Trahtenbrot's Theorem and the Incompleteness of Second-Order Logic
§6. Theories and Decidability
§7. Self-Referential Statements and GOlel's Incompleteness Theorems
XI Free Models and Logic Programming
§i. Herbrand's Theorem
§2. Free Models and Universal Horn Formulas
§3. Herbrand Structures
§4. Propositional Logic
§5. Propositional Resolution
§6. First-Order Resolution (without Unification)
§7. Logic Programming
XII An Algebraic Characterization of Elementary Equiva- lence
§1. Finite and Partial Isomorphisms
§2. Fraisse's Theorem
§3. Proof of Fraisse's Theorem
§4. Ehrenfeucht Games
XIII Lindstrom's Theorems
§1. Logical Systems
§2. Compact Regular Logical Systems
§3. LindstrSxn's First Theorem
§4. LindstrSm's Second Theorem
References
Symbol Index
Subject Index
