Linked e-resources
Details
Table of Contents
Intro
Preface
References
Contents
1 First-Order Logic
1.1 First-Order Languages
1.2 Free Variables
1.3 Substitution
1.4 A Deductive Calculus
1.5 Connective Rules
1.6 Quantifier Rules
1.7 Substitutivity of Equivalence
1.8 Equality
2 Completeness
2.1 Interpretations
2.2 Substitution Properties
2.3 Soundness
2.4 Consistency
2.5 Rich Sets
2.6 Completeness Theorem
2.7 Isomorphisms of Interpretations
2.8 Elementary Equivalence
2.9 Definability in an Interpretation
3 First-Order Theories
3.1 Generalities on First-Order Theory
3.2 Extensions of Theories
3.3 Definitional Extensions
4 Primitive Recursive Arithmetic
4.1 Primitive Recursive Functions
4.2 The Theories PRA and PA
4.3 Elementary Properties of PRA
4.4 Developing Arithmetic in PRA
4.5 Bounded Formulas
4.6 Non-Standard Models of PA
5 Encoding
5.1 Encoding of Finite Sequences
5.2 Encoding of Syntax
5.3 RE-Theories
6 Incompleteness
6.1 Traditional Gödel's First Incompleteness Theorem
6.2 Gödel's First Incompleteness Theorem
6.3 Corollaries of Gödel's First Incompleteness Theorem
6.4 Gödel's Second Incompleteness Theorem
6.5 Expressing Consistency
6.6 Rosser's Incompleteness Theorem
6.7 Gödel's Third Incompleteness Theorem
6.8 Reflection Principle
6.9 Löb's Theorem
6.10 Extension to Other First-Order Theories
7 Other Limitative Results
7.1 Tarski's Undefinability Theorems
7.2 Undecidability Theorem
7.3 Church's Theorem
7.4 Extension to Other First-Order Theories
7.5 Decidability of Monadic First-Order Logic
8 Second-Order Logic
8.1 Second-Order Languages
8.2 Free Variables
8.3 Substitution
8.4 A Deductive Calculus
8.5 Quantifier Rules
8.6 Substitutivity of Equivalence
8.7 Equality
8.8 Interpretations
8.9 Substitution Properties
8.10 Soundness
8.11 Consistency
8.12 Negative Results
8.13 Isomorphism of Interpretations
9 Second-Order Arithmetic
9.1 Second-Order Theories
9.2 The Theory PA2
9.3 Primitive Recursive Functions in PA2
9.4 Limitative Results for PA2
9.5 Categoricity of PA2
9.6 Strong Incompleteness Theorem for Second-Order Logic
9.7 Non-recursive Enumerability of Consequences of PA2
Appendix
A.1 Hilbert's Approach
A.2 The Conservation Program
A.3 The Consistency Program
A.4 Equivalence of the Two Programs
A.5 Fall of the Consistency Program
A.6 Fall of the Conservation Program
A.7 Other Shortcomings of Hilbert's Approach
References
Index
Preface
References
Contents
1 First-Order Logic
1.1 First-Order Languages
1.2 Free Variables
1.3 Substitution
1.4 A Deductive Calculus
1.5 Connective Rules
1.6 Quantifier Rules
1.7 Substitutivity of Equivalence
1.8 Equality
2 Completeness
2.1 Interpretations
2.2 Substitution Properties
2.3 Soundness
2.4 Consistency
2.5 Rich Sets
2.6 Completeness Theorem
2.7 Isomorphisms of Interpretations
2.8 Elementary Equivalence
2.9 Definability in an Interpretation
3 First-Order Theories
3.1 Generalities on First-Order Theory
3.2 Extensions of Theories
3.3 Definitional Extensions
4 Primitive Recursive Arithmetic
4.1 Primitive Recursive Functions
4.2 The Theories PRA and PA
4.3 Elementary Properties of PRA
4.4 Developing Arithmetic in PRA
4.5 Bounded Formulas
4.6 Non-Standard Models of PA
5 Encoding
5.1 Encoding of Finite Sequences
5.2 Encoding of Syntax
5.3 RE-Theories
6 Incompleteness
6.1 Traditional Gödel's First Incompleteness Theorem
6.2 Gödel's First Incompleteness Theorem
6.3 Corollaries of Gödel's First Incompleteness Theorem
6.4 Gödel's Second Incompleteness Theorem
6.5 Expressing Consistency
6.6 Rosser's Incompleteness Theorem
6.7 Gödel's Third Incompleteness Theorem
6.8 Reflection Principle
6.9 Löb's Theorem
6.10 Extension to Other First-Order Theories
7 Other Limitative Results
7.1 Tarski's Undefinability Theorems
7.2 Undecidability Theorem
7.3 Church's Theorem
7.4 Extension to Other First-Order Theories
7.5 Decidability of Monadic First-Order Logic
8 Second-Order Logic
8.1 Second-Order Languages
8.2 Free Variables
8.3 Substitution
8.4 A Deductive Calculus
8.5 Quantifier Rules
8.6 Substitutivity of Equivalence
8.7 Equality
8.8 Interpretations
8.9 Substitution Properties
8.10 Soundness
8.11 Consistency
8.12 Negative Results
8.13 Isomorphism of Interpretations
9 Second-Order Arithmetic
9.1 Second-Order Theories
9.2 The Theory PA2
9.3 Primitive Recursive Functions in PA2
9.4 Limitative Results for PA2
9.5 Categoricity of PA2
9.6 Strong Incompleteness Theorem for Second-Order Logic
9.7 Non-recursive Enumerability of Consequences of PA2
Appendix
A.1 Hilbert's Approach
A.2 The Conservation Program
A.3 The Consistency Program
A.4 Equivalence of the Two Programs
A.5 Fall of the Consistency Program
A.6 Fall of the Conservation Program
A.7 Other Shortcomings of Hilbert's Approach
References
Index