The book starts with an elementary introduction to formal languages appealingto the intuition of working mathematicians and unencumbered by philosophical or normative prejudices such as those of constructivism or intuitionism. It proceeds to the Proof Theory and presents several highlights of Mathematical Logic of 20th century: Gödel's and Tarski's Theorems, Cohen's Theorem on the independence of Continuum Hypothesis. Unusual for books on logic is a section dedicated to quantum logic. Then the exposition moves to the Computability Theory,based on the notion of recursive functions and stressing number{theoretic connections. A complete proof of Davis{Putnam{Robinson{Matiyasevich theorem is given, as well as a proof of Higman's theorem on recursive groups. Kolmogorov complexity is treated. The third Part of the book establishes essential equivalence of proof theory and computation theory and gives applications such as Gödel's theorem on the length of proofs. The new Chapter IX, written for the second edition, treats, among other things, categorical approach to the theory of computation, quantum computation, and P/NP problem. The new Chapter X, written for the second edition by Boris Zilber, contains basic results of Model Theoryand its applications to mainstream mathematics. This theory found deep applications in algebraic and Diophantine geometry. Yuri Ivanovich Manin is Professor Emeritus at Max-Planck-Institute for Mathematics in Bonn, Germany, Board of Trustees Professor at the Northwestern University, Evanston, USA, and Principal Researcher at the Steklov Institute of Mathematics, Moscow, Russia. Boris Zilber, Professor of Mathematics at the University of Oxford, has been added to the second edition. Contains a new chapter on categorical approach to theory of computations, quantum computations, and P/NP problem New chapter containing basic results of Model Theory and its applications to mainstream mathematics Presents several highlights of mathematical logic of the 20th century includingGödel's and Tarski's Theorems, Cohen's Theorem on the independence of Continuum Hypothesis Complete proof of Davis-Putnam-Robinson-Matiyasevich theorem Discusses Kolmogorov complexity INDICE: Preface to the Second Edition.- Preface to the First Edition.- Introduction to Formal Languages.- Truth and Deducibility. The Continuum Problem and Forcing.- The Continuum Problem and Constructible Sets.- Recursive Functions and Church's Thesis.- Diophantine Sets and Algorithmic Undecidability.- Gödel's Incompleteness Theorem.- Recursive Groups.- Constructive Universe and Computation.- Model Theory.- Suggestions for Further Reading.- Index.-
- ISBN: 978-1-4419-0614-4
- Editorial: Springer
- Encuadernacion: Cartoné
- Páginas: 384
- Fecha Publicación: 01/10/2009
- Nº Volúmenes: 1
- Idioma: Inglés