Kurt G\u00f6del and the Foundations of Mathematics: Horizons of Truth

Mentions Aquinas and Gödel's Anselm-like ontological proof * * * An edited volume that commemorates the life, work, and foundational views of Kurt Godel by exploring the impact of his work on current research and its future implications. Cover 1 Half-title 3 Title 5 Copyright 6 Contents 9 Contributors 13 Foreword 15 Preface 17 Acknowledgments 19 Short Biography of Kurt G ̈odel 21 Part One Historical Context: Godel's Contributions and Accomplishments: G ̈odel’s Historical, Philosophical, and Scientific Work 27 Chapter 1 The Impact of Godel's Incompleteness Theorems on Mathematics 29 1.1 His Contemporaries in Logic 30 1.2 The Mathematical Evolution of the Ideas 31 1.3 How the Number Theorists React to the Godel Phenomenon 32 1.4 Group Theory 36 1.5 Geometry and Dynamical Systems 37 1.6 Set Theory 37 1.7 Logical Form 39 1.8 Ramsey Independence 39 1.9 ``Topologie Moderee'' 39 1.10 Conclusion 40 Appendix: Modularity, Fermat's Last Theorem, and PA 40 A1 Flavors of Incompleteness 41 A2 Finite Approximations 41 A3 Galois Theory 42 A4 The p-adic Fields 42 A5 Some of the Number-Theoretic Notions and Their Logical Aspects 43 A6 L-Series 44 A7 Serre Conjecture 45 A8 A Special Representation Coming from a Counterexample to FLT 45 A9 Modular Forms 46 A10 More on the Conductor 46 A11 Equivalences 47 A12 Wiles’ Proof 48 A13 Deformation Theory 48 A14 Conclusion 49 References 49 Chapter 2 Logical Hygiene, Foundations, and Abstractions 53 2.1 Logical Hygiene: Asymmetric Items in Logical Dress 54 2.2 Logical Foundations: A (Here) Suitable Sense 56 2.3 Logical Abstractions 57 Personal Acknowledgment 60 Endnotes 60 Chapter 3 The Reception of Godel’s 1931 Incompletability Theorems by Mathematicians, and Some Logicians, to the Early 1960s 83 3.1 The Significance of Godel's Theorems: Four Main Aspects 84 3.2 The Reception by Some Logicians 84 3.2.1 Hans Hahn 85 3.2.2 W. V. Quine 85 3.2.3 Saunders MacLane 86 3.2.4 Bertrand Russell 86 3.3 The Reception among Mathematicians: The Technical Literature 87 3.4 The Reception among Mathematicians: The General Literature 89 3.4.1 Reactions to 1940 89 3.4.2 The Key Role of Newman 90 3.5 Reception in Some Other Countries 91 3.5.1 France 91 3.5.2 Other Countries 92 3.6 Concluding Remarks 93 General References 99 Chapter 4 ``Dozent Godel Will Not Lecture'' 101 4.1 part 1: a place in history 102 4.2 Part 2: Psychiatric Clinics and Ivory Towers 107 4.3 Part 3: Escape from the Reich 111 References 117 Chapter 5 Godel's Thesis: An Appreciation 121 Introduction 121 5.1 The Introduction to G ̈odel’s Thesis: Different Notions of Consistency 121 5.2 Categoricity and the Separation of Firstand Higher-Order Logic 126 5.3 The Incompleteness Theorem 129 5.3.1 The Timing of the Incompleteness Theorem 131 5.4 Back to Godel's Thesis 133 5.5 Conclusion 133 References 134 Chapter 6 Lieber Herr Bernays! Lieber Herr Godel! Godel on Finitism, Constructivity, and Hilbert’s Program 137 6.1 Godel, Bernays, and Hilbert 137 6.2 The Year 1931: The Incompleteness Theorems and Hilbert’s ω-Rule 140 6.3 The year 1933: the cambridge lecture 142 6.4 Transitions: 1934--1941 145 6.5 The Dialectica Interpretation 148 6.6 What, Really, Were Godel's Views on Finitism and the Consistency Program? 151 Acknowledgments 154 Endnotes 154 References 157 Chapter 7 Computation and Intractability: Echoes of Kurt Godel 163 7.1 The Two Foundations Quests 164 7.2 The Dawn of Computation 166 7.3 Johnny-Come-Lately: Von Neumann, Godel,and the Computer 167 7.4 Hilbert's Last Stand: Godel's Letter and P versus NP 169 7.5 On Negative Results and Godel's Influence 170 7.6 Latter-Day Arithmetization: Equilibria in Games 172 7.7 Epilogue 174 Acknowledgments 175 References 175 Chapter 8 From the Entscheidungsproblem to the Personal Computer- and Beyond 177 8.1 Turing and the Entscheidungsproblem 178 8.2 Early Days 179 8.3 Colossus: The First Large-Scale Electronic Computer 182 8.4 Next: The Stored Program 190 8.5 Epilogue: The Computer and the Mind 202 References 205 Chapter 9 Godel, Einstein, Mach, Gamow, and Lanczos: Godel’s Remarkable Excursion into Cosmology 211 9.1 First Look at Godel's Model 212 9.2 How the Model Came into Being 214 9.3 Godel's Newtonian Rotating Universe 217 9.4 Stationary Metrics in General and the Formof Godel's Metric in Particular 219 9.5 Do the Field Equations Permit a Godel Universe? 222 9.6 Light Cones, Time Travel, and Geodesics in Godel's Universe 225 9.7 Stability 233 9.8 Comments 233 9.9 Epilogue: Lanczos' Model Universe of 1924 235 Acknowledgments 236 References 236 Chapter 10 Physical Unknowables 239 10.1 Rise and Fall of Determinism 239 10.1.1 Toward Explanation and Feasibility 240 10.1.2 Rise of Indeterminism 242 10.2 Provable Physical Unknowables 243 10.2.1 Intrinsic Self-Referential Observers 244 10.2.2 Unpredictability 246 10.2.3 The Busy Beaver Function as the Maximal Recurrence Time 247 10.2.4 Undecidability of the Induction Problem 248 10.2.5 Impossibility 248 10.2.6 Results in Classical Recursion Theory with Implications for Theoretical Physics 249 10.3 Deterministic Chaos 250 10.3.1 Instabilities in Classical Motion 250 10.3.2 Rate of Convergence 252 10.4 Quantum Unknowables 253 10.4.1 Random Individual Events 254 10.4.2 Complementarity 256 10.4.3 Value Indefiniteness versus Omniscience 258 10.5 Miracles Due to Gaps in Causal Description 262 10.6 Concluding Thoughts 263 10.6.1 Metaphysical Status of (In)determinism 263 10.6.2 Harnessing Unknowables and Indeterminism 264 10.6.3 Personal Remarks 264 Acknowledgements 265 Bibliography 266 Part Two A Wider Vision:The Interdisciplinary, Philosophical, and Theological Implications of Godel's Work: On the Unknowables 279 Chapter 11 Godel and Physics 281 11.1 Some Historical Background 281 11.1.1 Physical Impossibilities 281 11.1.2 Mathematical Impossibilities 282 11.1.3 Axiomatics 282 11.1.4 Hilbert’s Program 283 11.2 Some Mathematical Jujitsu 285 11.2.1 The Optimists and the Pessimists 285 11.2.2 Drawing the Line between Completeness and Incompleteness 287 11.3 Laws versus Outcomes 292 11.3.1 Symmetry Breaking 292 11.3.2 Undecidable Outcomes 293 11.4 Godel and Space-Time Structure 295 11.4.1 Space-Time in a Spin 295 11.4.2 Supertasks 296 Acknowledgments 299 References 299 Chapter 12 Godel, Thomas Aquinas, and the Unknowability of God 303 12.1 Incompleteness, Arithmetical and Theological 303 12.2 The Variables of Unknowability 305 12.3 Systematic Indeterminacy 309 12.3.1 Gregory of Nyssa 309 12.3.2 Immanuel Kant 311 12.4 Theology as Essentially Uncompletable 312 12.5 Thomas Aquinas, Unknowability,and Proof of Unknowability 314 12.6 The Failure of Godels' Ontological Argument 316 12.7 Aquinas on Proof of God's Existence 318 12.8 Arithmetical and Theological Incompleteness: Are They the Same? 320 References 321 Chapter 13 Godel's Mathematics of Philosophy 325 13.1 The Arithmetization Method (1931) 325 13.2 The Incompleteness Theorem (1931) 326 13.3 The Double-Negation Translation (1933) 327 13.4 Sets and Classes (1940) 327 13.5 Cosmological Models (1949) 328 13.6 The Ontological Proof (1970) 328 13.7 Conclusion 329 References 329 Chapter 14 Godel's Ontological Proof and Its Variants 333 14.1 The Logic Used 334 14.2 Godel's Proof 336 14.3 Anderson's Variant and Its Variants 338 14.4 Oppy's Criticism 340 14.5 Miscellanea 343 14.6 What Do We Learn about Godel? 344 14.7 Meaning for Religion? 344 14.8 Conclusion 345 Acknowledgments 346 References 346 Chapter 15 The Godel Theorem and Human Nature 351 15.1 Noam Chomsky, Scientific Competence,and Turing Machines 352 15.2 Godel’s Incompleteness Theorems 352 15.3 Thinking about Chomsky’s Conjecture in a Rigorous Godelian Way 352 15.4 Lucas and Penrose 355 15.5 A Caution against a Widespread But Naive Argument for Algorithms in the Brain 358 Appendix 360 References 362 Chapter 16 Godel, the Mind, and the Laws of Physics 365 16.1 Three Worlds and the Mysteries That Connect Them 365 16.2 The Godel-Turing Argument 369 16.3 The Noncomputability of Mathematical Conviction 372 16.4 Mistakes, Vague Arguments, and Idealizations 376 16.5 Computability in the Laws of Physics 378 16.6 Possible Role in Brain Function 381 Acknowledgments 382 References 383 Part Three New Frontiers: Beyond Godel's Work in Mathematics and Symbolic Logic: Extending Godel’s Work 349 Chapter 17 Godel’s Functional Interpretation and Its Use in Current Mathematics 387 17.1 Introduction: General Remarks on Proof Interpretations 387 17.2 Functional Interpretation 391 17.3 From Consistency Proofs to the Unwinding of Proofs 396 17.4 A Comparison of Interpretations of ... 399 17.4.1 Kleene Realizability of ... 400 17.4.2 Modified Realizability Interpretation of ... 400 17.4.3 Functional Interpretation of ... 401 17.4.4 Negative Translation Followed by Kleene Realizability Resp. Modified Realizability of ... 402 17.4.5 Negative Translation Followed by Functional Interpretation of 403 17.4.6 Negative Translation Followed by A-Translation and Modified Realizability of 404 17.4.7 Discussion of the Results of the Comparison 405 17.4.7.1 Comparison between (A )D and Other (Classical) ... 405 17.5 Extraction of Effective Uniform Bounds in Analysis 408 17.6 Concluding Remarks 418 17.6.1 Foundational Reductions Revisited 418 17.6.2 Enrichment of Data Revisited 419 Acknowledgments 419 References 420 Chapter 18 My Forty Years on His Shoulders 425 18.1 The Completeness Theorem 427 18.2 The First Incompleteness Theorem 428 18.3 The Second Incompleteness Theorem 432 18.4 Lengths of Proofs 436 18.5 The Negative Interpretation 439 18.6 The Axiom of Choice and the Continuum Hypothesis 441 18.7 Wqo Theory 443 18.8 Borel Selection 445 18.9 Boolean Relation Theory 446 18.10 Finite Incompleteness 448 18.11 Incompleteness in the Future 449 Acknowledgments 452 References 452 Chapter 19 My Interaction with Kurt Godel: The Man and His Work 461 19.1 Background 461 19.2 Meeting Godel 464 19.3 High School: My Earliest Interest in Logic 464 19.4 Graduate School: The Continued Pull of Logic 465 19.5 The Beginnings of My Research Career 466 19.6 The Quest for Consistency 466 References 468 Additional Reading 469 Chapter 20 The Transfinite Universe 475 20.1 The Examples 476 20.1.1 The First Example: Infinitary Combinatorics 476 20.1.2 The Second Example: Infinite Games 477 20.1.3 Three Problems and Three Formal Theories 478 20.2 A Prediction and a Challenge for the Skeptic 478 20.3 The Cumulative Hierarchy of Sets 479 20.4 Probing the Universe of Sets: The Inner Model Program 483 20.5 The Building Blocks for Inner Models: Extenders 484 20.6 The Inner Model Program and the Core Model Program and the Skeptic’s Retreat 487 20.7 Supercompact Cardinals and Beyond 489 20.8 Summary 495 References 496 Chapter 21 The Godel Phenomenon in Mathematics: A Modern View 501 21.1 Overview 501 21.1.1 Decision Problems and Finite Algorithms 502 21.2 Godel's Letter to von Neumann 504 21.2.1 The Letter 504 21.2.2 Time Complexity and G ̈odel’s Foresight 506 21.3 Complexity Classes, Reductions, and Completeness 509 21.3.1 Efficient Computation and the Class ... 509 21.3.1.1 Why Polynomial? 509 21.3.2 Efficient Verification and the Class NP 511 21.3.3 The P versus NP Question: Its Meaning and Importance 512 21.3.4 The NP versus co NP Question: Its Meaning and Importance 513 21.3.5 Reductions: A Partial Order of Computational Difficulty 515 21.3.6 Completeness 516 21.3.7 NP-Completeness 516 21.3.8 The Nature and Impact of NP-Completeness 517 21.3.9 Some NP-Complete Problems in Mathematics 518 21.4 Lower Bounds and Attacks on P versus NP 520 21.4.1 Diagonalization and Relativization 520 21.4.2 Boolean Circuits 521 21.4.2.1 Basic Results and Questions 522 21.4.2.2 Why Is It Hard to Prove Circuit Lower Bounds? 523 21.5 Proof Complexity 524 21.5.1 The Pigeonhole Principle: A Motivating Example 525 21.5.2 Propositional Proof Systems andNP versus co NP 526 21.5.3 Concrete Proof Systems 528 21.5.3.1 Algebraic Proof Systems 528 21.5.3.2 Geometric Proof Systems 529 21.5.3.3 Logical Proof Systems 530 21.5.4 Proof Complexity versus Circuit Complexity 531 Acknowledgments 532 References 532 Index 535 0521761441,9780521761444 Cambridge University Press,2011 This Volume Commemorates The Life, Work, And Foundational Views Of Kurt Gödel (1906-1978), Most Famous For His Hallmark Works On The Completeness Of First-order Logic, The Incompleteness Of Number Theory, And The Consistency - With The Other Widely Accepted Axioms Of Set Theory - Of The Axiom Of Choice And Of The Generalized Continuum Hypothesis. It Explores Current Research, Advances, And Ideas For Future Directions Not Only In The Foundations Of Mathematics And Logic, But Also In The Fields Of Computer Science, Artificial Intelligence, Physics, Cosmology, Philosophy, Theology, And The History Of Science. The Discussion Is Supplemented By Personal Reflections From Several Scholars Who Knew Gödel Personally, Providing Some Interesting Insights Into His Life. By Putting His Ideas And Life's Work Into The Context Of Current Thinking And Perceptions, This Book Will Extend The Impact Of Gödel's Fundamental Work In Mathematics, Logic, Philosophy, And Other Disciplines For Future Generations Of Researchers-- I. Historical Context: Gödel's Contributions And Accomplishments: Gödel's Historical, Philosophical, And Scientific Work: 1. The Impact Of Gödel's Incompleteness Theorems On Mathematics / Angus Macintyre; 2. Logical Hygiene, Foundations, And Abstractions: Diversity Among Aspects And Options / Georg Kreisel; Gödel's Legacy: A Historical Perspective: 3. The Reception Of Gödel's 1931 Incompletabilty Theorems By Mathematicians, And Some Logicians, To The Early 1960s/ Ivor Grattan-guinness; 4.dt 'dozent Gödel Will Not Lecture' / Karl Sigmund; 5. Gödel's Thesis: An Appreciation / Juliette Kennedy; 6. Lieber Herr Bernays!, Lieber Herr Gödel! Gödel On Finitism, Constructivity, And Hilbert's Program / Solomon Feferman; The Past And Future Of Computation: 7. Computation And Intractability: Echoes Of Kurt Gödel / Christos H. Papadimitriou; 8. From The Entscheidungsproblem To The Personal Computer -- And Beyond / B. Jack Copeland; Gödelian Cosmology: 9. Gödel, Einstein, Mach, Gamow, And Lanczos: Gödel's Remarkable Excursion Into Cosmology / Wolfgang Rindler; 10. Physical Unknowables / Karl Svozil -- Ii. A Wider Vision: The Interdisciplinary, Philosophical, And Theological Implications Of Gödel's Work: On The Unknowables: 11. Gödel And Physics / John D. Barrow; 12. Gödel, Thomas Aquinas, And The Unknowability Of God / Denys A. Turner; Gödel And The Mathematics Of Philosophy: 13. Gödel's Mathematics Of Philosophy / Piergiorgio Odifreddi; Gödel And Philosophical Theology: 14. Gödel's Ontological Proof And Its Variants / Petr Hájek; Gödel And The Human Mind: 15. The Gödel Theorem And Human Nature / Hilary W. Putnam; 16. Gödel, The Mind, And The Laws Of Physics / Roger Penrose -- Iii. New Frontiers: Beyond Gödel's Work In Mathematics And Symbolic Logic: Extending Gödel's Work: 17. Gödel's Functional Interpretation And Its Use In Current Mathematics / Ulrich Kohlenbach; 18. My Forty Years On His Shoulders / Harvey M. Friedman; The Realm Of Set Theory: 19. My Interaction With Kurt Gödel: The Man And His Work / Paul J. Cohen; Gödel And The Higher Infinite: 20. The Transfinite Universe / W. Hugh Woodin; Gödel And Computer Science: 21. The Gödel Phenomena In Mathematics: A Modern View / Avi Wigderson. Edited By Matthias Baaz ... [et Al.]. Includes Bibliographical References And Index. Machine generated contents note: Part I. Historical Context - Gödel's Contributions and Accomplishments: 1. The impact of Gödel's incompleteness theorems on mathematics Angus Macintyre; 2. Logical hygiene, foundations, and abstractions: diversity among aspects and options Georg Kreisel; 3. The reception of Gödel's 1931 incompletabilty theorems by mathematicians, and some logicians, to the early 1960s Ivor Grattan-Guinness; 4. 'Dozent Gödel will not lecture' Karl Sigmund; 5. Gödel's thesis: an appreciation Juliette C. Kennedy; 6. Lieber Herr Bernays!, Lieber Herr Gödel! Gödel on finitism, constructivity, and Hilbert's program Solomon Feferman; 7. Computation and intractability: echoes of Kurt Gödel Christos H. Papadimitriou; 8. From the entscheidungsproblem to the personal computer - and beyond B. Jack Copeland; 9. Gödel, Einstein, Mach, Gamow, and Lanczos: Gödel's remarkable excursion into cosmology Wolfgang Rindler; 10. Physical unknowables Karl Svozil; Part II. A Wider Vision - The Interdisciplinary, Philosophical, And Theological Implications of Gödel's Work: 11. Gödel and physics John D. Barrow; 12. Gödel, Thomas Aquinas, and the unknowability of God Denys A. Turner; 13. Gödel's mathematics of philosophy Piergiorgio Odifreddi; 14. Gödel's ontological proof and its variants Petr Hájek; 15. The Gödel theorem and human nature Hilary Putnam; 16. Gödel, the mind, and the laws of physics Roger Penrose; Part III. New Frontiers - Beyond Gödel's Work in Mathematics and Symbolic Logic: 17. Gödel's functional interpretation and its use in current mathematics Ulrich Kohlenbach; 18. My forty years on his shoulders Harvey M. Friedman; 19. My interaction with Kurt Gödel: the man and his work Paul J. Cohen; 20. The transfinite universe W. Hugh Woodin; 21. The Gödel phenomena in mathematics: a modern view Avi Wigderson.