目錄
Preface to the Second Edition
Preface to the First Edition
Ⅰ PROVABILITY
Ⅰ Introduction to Formal Languages
1 General Information
2 First-Order Languages
Digression: Names
3 Beginners' Course in Translation
Digression: Syntax
Ⅱ Truth and Deducibility
1 Unique Reading Lemma
2 Interpretation: Truth, Definability
3 Syntactic Properties of Truth
Digression: Natural Logic
4 Deducibility
Digression: Proof
5 Tautologies and Boolean Algebras
Digression: Kennings
6 Godel's Completeness Theorem
7 Countable Models and Skolem's Paradox
8 Language Extensions
9 Undefinability of Truth: The Language SELF
10 Smullyan's Language of Arithmetic
11 Undefinability of Truth: Tarski's Theorem
Digression: Self-Reference
12 Quantum Logic
Appendix: The Von Neumann Universe
The Last Digression. Truth as Value and Duty: Lessons of Mathematics
Ⅲ The Continuum Problem and Forcing
1 The Problem: Results, Ideas
2 A Language of Real Analysis
3 The Continuum Hypothesis Is Not Deducible in L2 Real
4 Boolean-Valued Universes
5 The Axiom of Extensionality Is "True"
6 The Axioms of Pairing, Union, Power Set, and Regularity Are "True"
7 The Axioms of Infinity, Replacement, and Choice Are "True".
8 The Continuum Hypothesis Is "False" for Suitable B
9 Forcing
Ⅳ The Continuum Problem and Constructible Sets
1 Godel's Constructible Universe
2 Definability and Absoluteness
3 The Constructible Universe as a Model for Set Theory
4 The Generalized Continuum Hypothesis Is L-True
5 Constructibility Formula
6 Remarks on Formalization
7 What Is the Cardinality of the Continuum?
Ⅱ COMPUTABILITY
Ⅴ Recursive Functions and Church's Thesis
1 Introduction. Intuitive Computability
2 Partial Recursive Functions
3 Basic Examples of Recursiveness
4 Enumerable and Decidable Sets
5 Elements of Recursive Geometry
Ⅵ Diophantine Sets and Algorithmic Undecidability
1 The Basic Result
2 Plan of Proof
3 Enumerable Sets Are D-Sets
4 The Reduction
5 Construction of a Special Diophantine Set
6 The Graph of the Exponential Is Diophantine
7 The Factorial and Binomial Coefficient Graphs Are Diophantine
8 Versal Families
9 Kolmogorov Complexity
Ⅲ PROVABILITY AND COMPUTABILITY
Ⅶ Godel's Incompleteness Theorem
1 Arithmetic of Syntax
2 Incompleteness Principles
3 Nonenumerability of True Formulas
4 Syntactic Analysis
5 Enumerability of Deducible Formulas
6 The Arithmetical Hierarchy
7 Productivity of Arithmetical Truth
8 On the Length of Proofs
Ⅷ Recursive Groups
1 Basic Result and Its Corollaries
2 Free Products and HNN-Extensions
3 Embeddings in Groups with Two Generators
4 Benign Subgroups
5 Bounded Systems of Generators
6 End of the Proof
Ⅸ Constructive Universe and Computation
1 Introduction: A Categorical View of Computation
2 Expanding Constructive Universe: Generalities
3 Expanding Constructive Universe: Morphisms
4 Operads and PROPs
5 The World of Graphs as a Topological Language
6 Models of Computation and Complexity
7 Basics of Quantum Computation I: Quantum Entanglement
8 Selected Quantum Subroutines
9 Shot's Factoring Algorithm
10 Kolmogorov Complexity and Growth of Recursive Functions
Ⅳ MODEL THEORY
Ⅹ Model Theory
1 Languages and Structures
2 The Compactness Theorem
3 Basic Methods and Constructions
4 Completeness and Quantifier Elimination in Some Theories
5 Classification Theory
6 Geometric Stability Theory
7 Other Languages and Nonelementary Model Theory
Suggestions for Further Reading
Index
[