Book:Yu.I. Manin/A Course in Mathematical Logic for Mathematicians/Second Edition

Yu.I. Manin and Boris Zilber: A Course in Mathematical Logic (2nd Edition)

Published $\text {2010}$, Springer Verlag

ISBN 978-1441906144

Subject Matter

• Mathematical Logic

Contents

Preface to the Second Edition

Preface to the First Edition

I PROVABILITY

I Introduction to Formal Languages

1 General Information

2 First-Order Languages

Digression: Names

3 Beginner's Course in Translation

Digression: Syntax

II 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

Diression: 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

III The Continuum Problem and Forcing

1 The Problem: Results, Ideas

2 A Language of Real Analysis

3 The Continuum Hypothesis Is Not Deducible in $\mathrm L_2$ 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

IV 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?

II COMPUTABILITY

V 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

VI 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

III PROVABILITY AND COMPUTABILITY

VII 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

VIII 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

IX 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

IV MODEL THEORY

X Model Theory

1 Languages and Structure

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