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