第1页 / 共385页
第2页 / 共385页
第3页 / 共385页
第4页 / 共385页
第5页 / 共385页
第6页 / 共385页
第7页 / 共385页
第8页 / 共385页
A.Course.in.Mathematical.Logic.for.Mathematicians.1441906142.pdf
1441906142
A Course in Mathematical Logic for Mathematicians, Second Edition
Preface to the Second Edition
Preface to the First Edition
Contents
Introduction to Formal Languages
1 General Information
2 First-Order Languages
3 Beginners’ Course in Translation
1 Introduction to Formal Languages
2 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
3 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
4 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?
5 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
6 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
7 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
8 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
9 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
10 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
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
Graduate Texts in Mathematics 53
Editorial Board
S. Axler
K.A. Ribet
For other titles in this series, go to
http://www.springer.com/series/136
Yu. I. Manin
A Course in Mathematical Logic
for Mathematicians
Second Edition
Chapters I-VIII translated from the Russian
by Neal Koblitz
With new chapters by Boris Zilber and Yuri I. Manin
Author:
Yu. I. Manin
Max-Planck Institut für Mathematik
53111 Bonn
Germany
manin@mpim-bonn.mpg.de
First Edition Translated by:
Neal Koblitz
Department of Mathematics
University of Washington
Seattle, WA 98195
USA
koblitz@math.washington.edu
Editorial Board:
S. Axler
Mathematics Department
San Francisco State University
San Francisco, CA 94132
USA
axler@sfsu.edu
Contributor:
B. Zilber
Mathematical Institute
University of Oxford
Oxford OX1 3LB
United Kingdom
zilber@maths.ox.ac.uk
K. A. Ribet
Mathematics Department
University of California at Berkeley
Berkeley, CA 94720
USA
ribet@math.berkeley.edu
ISSN 0072-5285
ISBN 978-1-4419-0614-4
DOI 10.1007/978-1-4419-0615-1
Springer New York Dordrecht Heidelberg London
e-ISBN 978-1-4419-0615-1
Library of Congress Control Number: 2009934521
Mathematics Subject Classification (2000): 03-XX, 03-01
© Second edition 2010 by Yu. I. Manin
© First edition 1977 by Springer Verlag, New York, Inc.
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY
10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in
connection with any form of information storage and retrieval, electronic adaptation, computer software,
or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are
not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject
to proprietary rights.
Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)
To Nikita, Fedor and Mitya, with love
Preface to the Second Edition
1. The first 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 infinities: 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
on model theory, the conspicuous absence of which in the first edition was noted
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
Chapters I–VIII. Section IV.7, on the cardinality of the continuum,
completed by Section IV.7.3, discussing H. Woodin’s discovery.
the first edition are basically reproduced here as
is
The new Chapter IX: Constructive Universe and Computation, was written
especially for this edition, and I tried to demonstrate in it some basics of cate-
gorical thinking in the context of mathematical logic. More detailed comments
follow.
I am grateful to Ronald Brown and Noson Yanofsky, who read prelimi-
nary versions of new material and contributed much appreciated criticism and
suggestions.
2. Model theory grew from the same roots as other branches of logic: proof
theory, set theory, and recursion theory. From the start, it focused on language
and formalism. But the attention to the foundations of mathematics in model
viii
Preface to the Second Edition
theory crystallized in an attempt to understand, classify, and study models of
theories of real-life mathematics.
One of the first achievements of model theory was a sequence of local
theorems of algebra proved by A. Maltsev in the late 1930s. They were based on
the compactness theorem established by him for this purpose. The compactness
theorem in many of its disguises remained a key model-theoretic instrument
until the end of the 1950s. We follow these developments in the first two sec-
tions of Chapter X, which culminate with a general discussion of nonstandard
analysis discovered by A. Robinson. The third section introduces basic tools
and concepts of the model theory of the 1960s: types, saturated models, and
modern techniques based on these.
We try to illustrate every new model-theoretic result with an application in
“real” mathematics. In Section 4 we discuss an algebro-geometric theorem first
proved by J. Ax model-theoretically and re-proved by G. Shimura and A. Borel.
Moreover, we explain an application of the Tarski–Seidenberg quantifier elim-
ination for R due to L. H¨ormander. A real gem of model-theoretic techniques
of the 1980s is the calculation by J. Denef of the Poincar´e series counting
p-adic points on a variety based on A. Macintyre’s quantifier elimination
theorem for Qp.
In the last two sections we present a survey of classification theory, which
started with M. Morley’s analysis of theories categorical in uncountable powers
in 1964, and was later expanded by S. Shelah and others to a scale that no one
could have envisaged.
The striking feature of these developments is the depth of the very abstract
“pure” model theory underlying the classification, in combination with the
diversity of mathematical
from algebraic and
Diophantine geometry to real analysis and transcendental number theory.
theories affected by it,
3. The formal languages with which we work in the first, and in most of
the second, edition of this book are exclusively linear in the following sense.
Having chosen an alphabet consisting of letters, we proceed to define classes
of well-formed expressions in this alphabet that are some finite sequences of
letters. At the next level, there appear well-formed sequences of words, such as
deductions and descriptions. Church’s λ-calculus furnishes a good example of
strictures imposed by linearity.
languages have
existed for
Nonlinear
and
composers could not perform without using the languages of drawings, resp.
musical scores; when alchemy became chemistry,
it also evolved its own
two-dimensional language. For a logician, the basic problem about nonlinear
languages is the difficulty of their formalization.
centuries. Geometers
This problem is addressed nowadays by relegating nonlinear languages of
contemporary mathematics to the realm of more conventional mathematical
objects, and then formally describing such languages as one would describe any
other structure, that is, linearly.
Preface to the Second Edition
ix
Such a strategy probably cannot be avoided. But one must be keenly aware
that some basic mathematical structures are “linguistic” at their core. Recog-
nition or otherwise of this fact influences the problems that are chosen, the
questions that are asked, and the answers that are appreciated.
It would be difficult to dispute nowadays that category theory as a language
is replacing set theory in its traditional role as the language of mathematics.
Basic expressions of this language, commutative diagrams, are one-dimensional,
but nonlinear: they are certain decorated graphs, whose topology is that of
1-dimensional triangulated spaces.
When one iterates the philosophy of category theory, replacing sets of
morphisms by objects of a category of the next level, commutative diagrams
become two-dimensional simplicial sets (or cell complexes), and so on. Arguably,
in this way the whole of homotopy topology now develops into the language of
contemporary mathematics, transcending its former role as an important and
active, but reasonably narrow research domain. Much remains to be recognized
and said about this emerging trend in foundations of mathematics.
The first part of Chapter IX in this edition is a very brief and tentative
introduction to this way of thinking, oriented primarily to some reshuffling of
classical computability theory, as was explained in the Part II of the first edition.
4. The second part of the new Chapter IX is dedicated to some theoretical
problems of classical and quantum computing. It introduces the P/NP problem,
classical and quantum Boolean circuits, and presents several celebrated results
of this early stage of theoretical quantum computing, such as Shor’s factoring
and Grover’s search algorithms.
The main reason to include these topics is my conviction that at least some
theoretical achievements of modern computer science must constitute an organic
part of contemporary mathematical logic.
Already in the first edition, the manuscript for which was completed in
some length; cf.
September 1974, “quantum logic” was discussed at
Section II.12.
A Russian version of the Part II of first edition was published as a sepa-
rate book, Computable and Uncomputable, by “Soviet Radio” in 1980. For this
Russian publication, I had written a new introduction, in which, in particular,
I suggested that quantum computers could be potentially much more powerful
than classical ones, if one could use the exponential growth of a quantum phase
space as a function of the number of degrees of freedom of the classical system.
implementation of this idea, massive quantum
parallelism, made possible by quantum entanglement, gradually matured, I
gave a talk at a Bourbaki seminar in June 1999, explaining the basic ideas and
results.
When a mathematical
Chapter IX is a revised and expanded version of this talk.
5. Finally, a few words about the last digression in Chapter II, “Truth as
Value and Duty: Lessons of Mathematics.”
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
