E-book
Logical Foundations of Mathematics and Computational Complexity [electronic resource] : A Gentle Introduction / by Pavel Pudlák.
Record details
- ISBN: 9783319001197
- Physical Description: XIV, 695 p. 49 illus., 4 illus. in color. online resource.
- Publisher: Heidelberg : Springer International Publishing : 2013.
Search for related items by subject
Search for related items by series
Electronic resources
| . | ||
| Contents | ||
| 1 Mathematicianâs World . . . . . . . . . . . . . . . . . . . . . . . . . 1 | ||
| 1.1 Mathematical Structures . . . . . . . . . . . . . . . . . . . . . . . 2 | ||
| 1.2 Everything Is a Set . . . . . . . . . . . . . . . . . . . . . . . . . . 25 | ||
| 1.3 Antinomies of Set Theory . . . . . . . . . . . . . . . . . . . . . . 36 | ||
| 1.4 The Axiomatic Method . . . . . . . . . . . . . . . . . . . . . . . 43 | ||
| 1.5 The Necessity of Using Abstract Concepts . . . . . . . . . . . . . 54 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 64 | ||
| 2 Language, Logic and Computations . . . . . . . . . . . . . . . . . . 65 | ||
| 2.1 The Language of Mathematics . . . . . . . . . . . . . . . . . . . . 66 | ||
| 2.2 Truth and Models . . . . . . . . . . . . . . . . . . . . . . . . . . 80 | ||
| 2.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 | ||
| 2.4 Programs and Computations . . . . . . . . . . . . . . . . . . . . . 123 | ||
| 2.5 The Lambda Calculus . . . . . . . . . . . . . . . . . . . . . . . . 146 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 155 | ||
| 3 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 | ||
| 3.1 The Axioms of Set Theory . . . . . . . . . . . . . . . . . . . . . . 159 | ||
| 3.2 The Arithmetic of Infinity . . . . . . . . . . . . . . . . . . . . . . 176 | ||
| 3.3 What Is the Largest Number? . . . . . . . . . . . . . . . . . . . . 196 | ||
| 3.4 Controversial Axioms . . . . . . . . . . . . . . . . . . . . . . . . 215 | ||
| 3.5 Alternative Set-Theoretical Foundations . . . . . . . . . . . . . . 231 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 253 | ||
| 4 Proofs of Impossibility . . . . . . . . . . . . . . . . . . . . . . . . . . 255 | ||
| 4.1 Impossibility Proofs in Geometry and Algebra . . . . . . . . . . . 256 | ||
| 4.2 The Incompleteness Theorems . . . . . . . . . . . . . . . . . . . 272 | ||
| 4.3 Algorithmically Unsolvable Problems . . . . . . . . . . . . . . . . 300 | ||
| 4.4 Concrete Independence . . . . . . . . . . . . . . . . . . . . . . . 319 | ||
| 4.5 The Independent Sentences of Set Theory . . . . . . . . . . . . . . 340 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 364 | ||
| xiii | ||
| - | ||
| xiv ... | ||
| 5 The Complexity of Computations . . . . . . . . . . . . . . . . . . . . 365 | ||
| 5.1 What Is Complexity? . . . . . . . . . . . . . . . . . . . . . . . . 366 | ||
| 5.2 Randomness, Interaction and Cryptography . . . . . . . . . . . . . 410 | ||
| 5.3 Parallel Computations . . . . . . . . . . . . . . . . . . . . . . . . 437 | ||
| 5.4 Quantum Computations . . . . . . . . . . . . . . . . . . . . . . . 448 | ||
| 5.5 Descriptional Complexity . . . . . . . . . . . . . . . . . . . . . . 479 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 493 | ||
| 6 Proof Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 | ||
| 6.1 Proof Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496 | ||
| 6.2 Theories and Complexity Classes . . . . . . . . . . . . . . . . . . 523 | ||
| 6.3 Propositional Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 540 | ||
| 6.4 Feasible Incompleteness . . . . . . . . . . . . . . . . . . . . . . . 562 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 580 | ||
| 7 Consistency, Truth and Existence . . . . . . . . . . . . . . . . . . . . 583 | ||
| 7.1 Consistency and Existence . . . . . . . . . . . . . . . . . . . . . . 584 | ||
| 7.2 The Attributes of Reality . . . . . . . . . . . . . . . . . . . . . . 609 | ||
| 7.3 Finitism and Physical Reality . . . . . . . . . . . . . . . . . . . . 646 | ||
| Main Points of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . 664 | ||
| Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 667 | ||
| References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 | ||
| Name Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683 | ||
| Subject Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687 | ||
| Symbols and Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . 695 | ||
| . |
