An edition of Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction (Springer Monographs in Mathematics)
(2013)
Logical Foundations of Mathematics and Computational Complexity: ()
A Gentle Introduction
by Pavel Pudlák
- 1 Currently reading
Share
×Close
This work doesn't have a description yet. Can you add one?
Check nearby libraries
Buy this book
| Edition | Availability |
|---|---|
1
Logical Foundations of Mathematics and Computational Complexity: (): A Gentle Introduction
Apr 22, 2013, Springer
3319001191 9783319001197
|
aaaa
|
Book Details
Table of Contents
.
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
.
Edition Notes
Classifications
Edition Identifiers
Work Identifiers
Community Reviews (0)
Lists
See All
| March 18, 2024 | Edited by meot | adding lccn 2013936799, content, series (from title), subtitle (from title) + link to publisher |
| November 2, 2021 | Edited by ImportBot | import existing book |
| July 5, 2019 | Edited by MARC Bot | import existing book |
| February 23, 2019 | Created by MARC Bot | import new book |