Manin Yu. I. A Course in Mathematical Logic

New York: Springer Science+Business Media. 1977. 296 p. ISBN: 978-1-4757-4387-6 ISBN: 978-1-4757-4385-2 (eBook)This book is a text of mathematical logic on a sophisticated level, presenting the reader with several of the most significant discoveries of the last 10 to 15 years, including the independence of the continuum hypothesis, the Diophantine nature of enumerable sets and the impossibility of finding an algorithmic solution for certain problems. The book contains the first textbook presentation of Matijasevic's result. The central notions are provability and computability; the emphasis of the presentation is on aspects of the theory which are of interest to the working mathematician. Many of the approaches and topics covered are not standard parts of logic courses; they include a discussion of the logic of quantum mechanics, Goedel's constructible sets as a sub-class of von Neumann's universe, the Kolmogorov theory of complexity. Feferman's theorem on Goedel formulas as axioms and Highman's theorem on groups defined by enumerable sets of generators and relations. A number of informal digressions concerned with psychology, linguistics, and common sense logic should interest students of the philosophy of science or the humanities.ProvabilityIntroduction to formal languagesGeneral information
First order languages
Digression: names
Beginners' course in translation
Digression: syntaxTruth and deducibilityUnique reading lemma
Interpretation: truth, definability
Syntactic properties of truth
Digression: natural lope
Deducibility
Digression: proof
Tautologies and Boolean algebras
Digression: Kennings
Gbdel's completeness theorem
Countable nunlels and Skolcm's paradox
Language extensions
Undefinabiliiy of truth: the language SELF
SmullyaiTs language of arithmetic
Undefinability of truth: Tarski's theorem
Digression: self-reference
Quantum logic
Appendix. The von Neumann UniverseThe continuum problem and forcingThe problem: results, ideas
A language of real analysis
The continuum hypothesis is not deducible in L; Real
Boolean-valued universes
The axiom of extensionality is "true"
The axioms of pairing, union, power set. and regularity arc "true"
The axioms of infinity, replacement, and choice are "true"
The continuum hypothesis is "false" for suitable B
ForcingThe continuum problem and constructible setsGodel's constructible universe
Definability and absoluteness
The constructible universe as a model for set theory
The generalized continuum hypothesis is Z,-true
Constructibility formula
Remarks on formalization
What is the cardinality of the continuum?ComputabilityRecursive functions and Church's thesisIntroduction. Intuitive computability
Partial recursive functions
Basic examples of recursiveness
Enumerable and decidable sets
Elements of recursive geometryDiophantine sets and algorithmic undecidabilityThe basic result
Plan of proof
Enumerable sets are Z>-sets
The reduction
Construction of a special Diophantine set
The graph of the exponential is Diophantine
The graphs of the factorial and the binomial coefficients are DiophantineProvability and computabilityGodel's incompleteness theoremArithmetic of syntax
Incompleteness principles
Nonenumerability of true formulas
Syntactic analysis
Enumerabilily of deducible formulas
The arithmetical hierarchy
Productivity of arithmetical truth
On the length of proofsRecursive groupsBasic result and its corollaries
Free products and HNN-extensions
Embeddings in groups with two generators
Benign subgroups
Bounded systems of generators
End of the proof