.

0 (hodnocen0 x )

BK

2nd ed.

New York : Springer, c2010

xvii, 384 s. ; 25 cm

ISBN 978-1-4419-0614-4 (váz.)

Graduate texts in mathematics ; 53

ruština

Některé kapitoly přeloženyz ruštiny

Obsahuje bibliografii na s. [379]-380 a rejstřík

000177654

Contents // Preface to the Second Edition... vii // Preface to the First Edition... xi // I PROVABILITY // I Introduction to Formal Languages... 3 // 1 General Information... 3 // 2 First-Order Languages... 5 // Digression: Names... 9 // 3 Beginners’ Course in Translation... 9 // Digression: Syntax... 15 // II Truth and Deducibility... 19 // 1 Unique Reading Lemma... 19 // 2 Interpretation: Truth, Definability... 23 // 3 Syntactic Properties of Truth... 28 // Digression: Natural Logic... 33 // 4 Deducibility... 36 // Digression: Proof... 45 // 5 Tautologies and Boolean Algebras... 49 // Digression: Kennings... 53 // 6 Godel’s Completeness Theorem ... 55 // 7 Countable Models and Skolem’s Paradox... 61 // 8 Language Extensions... 66 // 9 Undefinability of Truth: The Language SELF... 69 // 10 Smullyan’s Language of Arithmetic... 71 // 11 Undefinability of Truth: Tarski’s Theorem ... 74 // Digression: Self-Reference... 77 // 12 Quantum Logic... 78 // Appendix: The Von Neumann Universe... 89 // The Last Digression. Truth as Value and Duty: Lessons of // Mathematics... 96 // III The Continuum Problem and Forcing...105 // 1 The Problem: Results, Ideas...105 // 2 A Language of Real Analysis...110 // 3 The Continuum Hypothesis Is Not Deducible in L2 Real...114 // xvi // Contents // 4 Boolean-Valued Universes...120 // 5 The Axiom of Extensionality Is "True”...124 // 6 The Axioms of Pairing, Union, Power Set, and // Regularity Are "True” ...127

7 The Axioms of Infinity, Replacement,, and // Choice Are "True”...132 // 8 The Continuum Hypothesis Is "False” for Suitable B...140 // 9 Forcing...145 // IV The Continuum Problem and Constructible Sets ...151 // 1 Godel’s Constructible Universe...151 // 2 Definability and Absoluteness...155 // 3 The Constructible Universe as a Model for Set Theory...158 // 4 The Generalized Continuum Hypothesis Is L-True...161 // 5 Constructibility Formula...164 // 6 Remarks on Formalization...171 // 7 What Is the Cardinality of the Continuum?...172 // II COMPUTABILITY // V Recursive Functions and Church’s Thesis...179 // 1 Introduction. Intuitive Computability...179 // 2 Partial Recursive Functions...183 // 3 Basic Examples of Recursiveness...187 // 4 Enumerable and Decidable Sets...191 // 5 Elements of Recursive Geometry...201 // VI Diophantine Sets and Algorithmic Undecidability...207 // 1 The Basic Result...207 // 2 Plan of Proof...209 // 3 Enumerable Sets Are ...211 // 4 The Reduction...214 // 5 Construction of a Special Diophantine Set...217 // 6 The Graph of the Exponential Is Diophantine...221 // 7 The Factorial and Binomial Coefficient Graphs // Are Diophantine ...221 // 8 Versal Families...223 // 9 Kolmogorov Complexity...226 // III PROVABILITY AND COMPUTABILITY // VII Godel’s Incompleteness Theorem...235 // 1 Arithmetic of Syntax ...235 // 2 Incompleteness Principles...240 // 3 Nonenumerability of True Formulas...241 // Contents xvii // 4 Syntactic

Analysis...243 // 5 Enumerability of Deducible Formulas...249 // 6 The Arithmetical Hierarchy...252 // 7 Productivity of Arithmetical Truth...255 // 8 On the Length of Proofs...258 // VIII Recursive Groups...263 // 1 Basic Result and Its Corollaries...263 // 2 Free Products and HNN-Extensions...266 // 3 Embeddings in Groups with Two Generators...270 // 4 Benign Subgroups...271 // 5 Bounded Systems of Generators...275 // 6 End of the Proof...280 // IX Constructive Universe and Computation...285 // 1 Introduction: A Categorical View of Computation...285 // 2 Expanding Constructive Universe: Generalities...289 // 3 Expanding Constructive Universe: Morphisms...293 // 4 Operads and PROPs...296 // 5 The World of Graphs as a Topological Language...298 // 6 Models of Computation and Complexity...307 // 7 Basics of Quantum Computation I: Quantum Entanglement .. 315 // 8 Selected Quantum Subroutines...319 // 9 Shor’s Factoring Algorithm...322 // 10 Kolmogorov Complexity and Growth of Recursive Functions .. 325 // IV MODEL THEORY // X Model Theory...331 // 1 Languages and Structures...331 // 2 The Compactness Theorem...334 // 3 Basic Methods and Constructions ...342 // 4 Completeness and Quantifier Elimination in Some Theories . .. 350 // 5 Classification Theory ...359 // 6 Geometric Stability Theory...364 // 7 Other Languages and Nonelementary Model Theory.374 // Suggestions for Further Reading...379 // Index...381