Logical Foundations of Mathematics and Computational Complexity:  ()
Subtitle: A Gentle Introduction
Series: Springer Monographs in Mathematics
Publisher: Springer
Published: Apr 22, 2013
Number of pages: 699
ISBN-13: 9783319001197
Table of contents: title: .; title: Contents; title: 1 Mathematician’s World . . . . . . . . . . . . . . . . . . . . . . . . . 1; title: 1.1 Mathematical Structures . . . . . . . . . . . . . . . . . . . . . . . 2; title: 1.2 Everything Is a Set . . . . . . . . . . . . . . . . . . . . . . . . . . 25; title: 1.3 Antinomies of Set Theory . . . . . . . . . . . . . . . . . . . . . . 36; title: 1.4 The Axiomatic Method . . . . . . . . . . . . . . . . . . . . . . . 43; title: 1.5 The Necessity of Using Abstract Concepts . . . . . . . . . . . . . 54; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 64; title: 2 Language, Logic and Computations . . . . . . . . . . . . . . . . . . 65; title: 2.1 The Language of Mathematics . . . . . . . . . . . . . . . . . . . . 66; title: 2.2 Truth and Models . . . . . . . . . . . . . . . . . . . . . . . . . . 80; title: 2.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92; title: 2.4 Programs and Computations . . . . . . . . . . . . . . . . . . . . . 123; title: 2.5 The Lambda Calculus . . . . . . . . . . . . . . . . . . . . . . . . 146; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 155; title: 3 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157; title: 3.1 The Axioms of Set Theory . . . . . . . . . . . . . . . . . . . . . . 159; title: 3.2 The Arithmetic of Infinity . . . . . . . . . . . . . . . . . . . . . . 176; title: 3.3 What Is the Largest Number? . . . . . . . . . . . . . . . . . . . . 196; title: 3.4 Controversial Axioms . . . . . . . . . . . . . . . . . . . . . . . . 215; title: 3.5 Alternative Set-Theoretical Foundations . . . . . . . . . . . . . . 231; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 253; title: 4 Proofs of Impossibility . . . . . . . . . . . . . . . . . . . . . . . . . . 255; title: 4.1 Impossibility Proofs in Geometry and Algebra . . . . . . . . . . . 256; title: 4.2 The Incompleteness Theorems . . . . . . . . . . . . . . . . . . . 272; title: 4.3 Algorithmically Unsolvable Problems . . . . . . . . . . . . . . . . 300; title: 4.4 Concrete Independence . . . . . . . . . . . . . . . . . . . . . . . 319; title: 4.5 The Independent Sentences of Set Theory . . . . . . . . . . . . . . 340; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 364; title: xiii; title: -; title: xiv ...; title: 5 The Complexity of Computations . . . . . . . . . . . . . . . . . . . . 365; title: 5.1 What Is Complexity? . . . . . . . . . . . . . . . . . . . . . . . . 366; title: 5.2 Randomness, Interaction and Cryptography . . . . . . . . . . . . . 410; title: 5.3 Parallel Computations . . . . . . . . . . . . . . . . . . . . . . . . 437; title: 5.4 Quantum Computations . . . . . . . . . . . . . . . . . . . . . . . 448; title: 5.5 Descriptional Complexity . . . . . . . . . . . . . . . . . . . . . . 479; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 493; title: 6 Proof Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495; title: 6.1 Proof Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496; title: 6.2 Theories and Complexity Classes . . . . . . . . . . . . . . . . . . 523; title: 6.3 Propositional Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 540; title: 6.4 Feasible Incompleteness . . . . . . . . . . . . . . . . . . . . . . . 562; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 580; title: 7 Consistency, Truth and Existence . . . . . . . . . . . . . . . . . . . . 583; title: 7.1 Consistency and Existence . . . . . . . . . . . . . . . . . . . . . . 584; title: 7.2 The Attributes of Reality . . . . . . . . . . . . . . . . . . . . . . 609; title: 7.3 Finitism and Physical Reality . . . . . . . . . . . . . . . . . . . . 646; title: Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 664; title: Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 667; title: References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671; title: Name Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683; title: Subject Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687; title: Symbols and Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . 695; title: .