A Course in Mathematical Logic for Mathematicians

✍ Scribed by Yu. I. Manin, B. Zilber

• Publisher: Springer Science & Business Media
• Year: 2009
• Tongue: English
• Leaves: 389
• Series: Graduate Texts in Mathematics
• Edition: 2
• Category: Library

✦ Synopsis

1. The ?rst edition of this book was published in 1977. The text has been well received and is still used, although it has been out of print for some time. In the intervening three decades, a lot of interesting things have happened to mathematical logic: (i) Model theory has shown that insights acquired in the study of formal languages could be used fruitfully in solving old problems of conventional mathematics. (ii) Mathematics has been and is moving with growing acceleration from the set-theoretic language of structures to the language and intuition of (higher) categories, leaving behind old concerns about in?nities: a new view of foundations is now emerging. (iii) Computer science, a no-nonsense child of the abstract computability theory, has been creatively dealing with old challenges and providing new ones, such as the P/NP problem. Planning additional chapters for this second edition, I have decided to focus onmodeltheory,the conspicuousabsenceofwhichinthe ?rsteditionwasnoted in several reviews, and the theory of computation, including its categorical and quantum aspects. The whole Part IV: Model Theory, is new. I am very grateful to Boris I. Zilber, who kindly agreed to write it. It may be read directly after Chapter II. The contents of the ?rst edition are basically reproduced here as Chapters I–VIII. Section IV.7, on the cardinality of the continuum, is completed by Section IV.7.3, discussing H. Woodin’s discovery.

✦ Table of Contents

8739_2_En_BookFrontmatter_OnlinePDF.pdf
A Course in Mathematical Logic for Mathematicians
Preface to the Second Edition
Preface to the First Edition
Contents
8739_2_En_1_Part_OnlinePDF.pdf
PROVABILITY
8739_2_En_1_Chapter_OnlinePDF.pdf
Introduction to Formal Languages
1 General Information
2 First-Order Languages
3 Beginners’ Course in Translation
8739_2_En_2_Chapter_OnlinePDF.pdf
Truth and Deducibility
1 Unique Reading Lemma
2 Interpretation: Truth, Definability
3 Syntactic Properties of Truth
4 Deducibility
5 Tautologies and Boolean Algebras
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
12 Quantum Logic
8739_2_En_3_Chapter_OnlinePDF.pdf
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
8739_2_En_4_Chapter_OnlinePDF.pdf
The Continuum Problem and Constructible Sets
1 Gödel’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?
8739_2_En_2_Part_OnlinePDF.pdf
COMPUTABILITY
8739_2_En_5_Chapter_OnlinePDF.pdf
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
8739_2_En_6_Chapter_OnlinePDF.pdf
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
8739_2_En_3_Part_OnlinePDF.pdf
PROVABILITY ANDCOMPUTABILITY
8739_2_En_7_Chapter_OnlinePDF.pdf
Gödel’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
8739_2_En_8_Chapter_OnlinePDF.pdf
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
8739_2_En_9_Chapter_OnlinePDF.pdf
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 Shor’s Factoring Algorithm
10 Kolmogorov Complexity and Growth of Recursive Functions
8739_2_En_4_Part_OnlinePDF.pdf
MODEL THEORY
8739_2_En_10_Chapter_OnlinePDF.pdf
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
8739_2_En_BookBackmatter_OnlinePDF.pdf
Suggestions for Further Reading
I.–II. Introduction to Formal Languages. Truth and Deducibility
III.–IV. The Continuum Problem and Forcing. The Continuum Problem and Construcitble set
V. Recursive Functions and Church’s Thesis
VI. Diophantine Sets and Algorithmic Undecidability
VII. G¨odel’s Incompleteness Theorem
VIII. Recursive Groups
IX. Constructive Universe and Computation
X. Model Theory
Index