Contents
Preface
1. Background
1.1 Overview of Mathematical Logic
1.2 Induction
1.3 Formal Systems
1.4 Set Theory, Functions, and Relations
1.5 Countable and Uncountable Sets
1.6 Axiom Systems
1.7 Decidability and Computability
1.8 Recersive Functions and Recursive Relations
2. Language and Semantics of Propositional Logic
2.1 Language of Propositional Logic
2.2 Tautological Consequence
2.3 Adequate Sets of Connectives
3. Propositional Logic
3.1 The Formal System P
3.2 Soundness Theorem
3.3 Deduction Theorem
3.4 Model Existence Theorem and Adequacy Theorem
3.5 Hilbert-style Proof Systems for Propositional Logic
3.7 Gentzen-style Proof Systems for Propositional Logic
4. First-Order Languages
4.1 A Language for Arithmetic
4.2 First-Order Languages, Interpretation and Models
4.3 Tarski's Definition of Truth
4.4 Agreement Theorem and Substitution for Free Variables
5. First-Order Logic
5.1 The Formal System FOL
5.2 Soundness Theorem
5.3 The Deduction Theorem and Equality Theorem
5.4 The Model Existence Theorem
5.5 Gödel Completeness Theorems: Decidability
5.6 Replacement Theorem and Prenex Form
6. Mathematics and Logic
6.1 First-Order Theories and Hibert's Program
6.2 The Löwenheim-Skolem Theorem and Compactness Theorem
6.3 Decidable Theories
6.4 Zermelo-Frankel Set Theory
7. Incomleteness, Undecidability, and Indefinability
7.1 Overview of the Theorems of Gödel, Church, and Tarski
7.2 Coding and Expressibility
7.3 Recursive Relation ==> Expressible Relation
7.4 Gödel's Incompleteness Theorems
7.5 Church's Theorem
7.6 Definability and Tarski's Theorem
8. Recursive Functions
8.1 Recursive Functions
8.2 Recursive Relations
8.3 Recursive Coding Functions
8.4 Primitive Recursion
8.5 RE Relations
8.6 THMΓ is not Recursive and TR is not Definable
8.7 THMΓ is RE
9. Computability Theory
9.1 Register Machines and RM-Computable Functions
9.2 Recursive ==> RM-Computable
9.3 Kleene Computation Relation Tn
9.4 Partial Recursive Functions
9.5 Parameter Theorem and Recursion Theorem
9.6 Semi-Thue System and Word Problems
10. Hibert's Tenth Problem
10.1 Overview of Hibert's Tenth Problem
10.2 Diophantine Relations and Functions
10.3 RE Relations ==> Diophantine Relation (Assuming Bounded ∀-Rule)
10.4 The Exponential Function is Diophantine
10.5 Bounded ∀-Rule
10.6 Application of the Main Theorem
Appendix: Number Theory
Reference and Recommended Readings
· · · · · · (收起)