Subsystems of Second Order Arithmetic: Second Edition (Perspectives in Logic)

Foundations of mathematics is the study of the most basic concepts and logical structure of mathematics, with an eye to the unity of human knowledge. Almost all of the problems studied in this book are motivated by an overriding foundational question: What are the appropriate axioms for mathematics? Through a series of case studies, these axioms are examined to prove particular theorems in core mathematical areas such as algebra, analysis, and topology, focusing on the language of second-order arithmetic, the weakest language rich enough to express and develop the bulk of mathematics. In many cases, if a mathematical theorem is proved from appropriately weak set existence axioms, then the axioms will be logically equivalent to the theorem. Furthermore, only a few specific set existence axioms arise repeatedly in this context, which in turn correspond to classical foundational programs. This is the theme of reverse mathematics, which dominates the first half of the book. The second part focuses on models of these and other subsystems of second-order arithmetic. Additional results are presented in an appendix Contents 9 List of Tables 13 Preface 15 I. Introduction 19 1. The Main Question 19 2. Subsystems of Z_2 20 3. The System ACA_0 24 4. Mathematics within ACA_0 27 5. Π^1_1 - CA_0 and Stronger Systems 34 6. Mathematics within Π^1_1 - CA_0 37 7. The System RCA_0 41 8. Mathematics within RCA_0 45 9. Reverse Mathematics 50 10. The System WKL_0 53 11. The System ATR_0 56 12. The Main Question, Revisited 60 13. Outline of Chapters II through X 61 14. Conclusions 78 Part A. Development of Mathematics within Subsystems of Z_2 79 II. Recursive Comprehension 81 1. The Formal System RCA_0 81 2. Finite Sequences 83 3. Primitive Recursion 87 4. The Number Systems 91 5. Complete Separable Metric Spaces 96 6. Continuous Functions 102 7. More on Complete Separable Metric Spaces 106 8. Mathematical Logic 110 9. Countable Fields 114 10. Separable Banach Spaces 117 11. Conclusions 121 III. Arithmetical Comprehension 123 1. The Formal System ACA_0 123 2. Sequential Compactness 124 3. Strong Algebraic Closure 128 4. Countable Vector Spaces 130 5. Maximal Ideals in Countable Commutative Rings 133 6. Countable Abelian Groups 136 7. König’s Lemma and Ramsey’s Theorem 139 8. Conclusions 143 IV. Weak Konig's Lemma 145 1. The Heine/Borel Covering Lemma 145 2. Properties of Continuous Functions 151 3. The Gödel Completeness Theorem 157 4. Formally Real Fields 159 5. Uniqueness of Algebraic Closure 162 6. Prime Ideals in Countable Commutative Rings 164 7. Fixed Point Theorems 167 8. Ordinary Di»erential Equations 172 9. The Separable Hahn/Banach Theorem 178 10. Conclusions 183 V. Arithmetical Transfinite Recursion 185 1. Countable Well Orderings; Analytic Sets 185 2. The Formal System ATR_0 191 3. Borel Sets 196 4. Perfect Sets; Pseudohierarchies 203 5. Reversals 207 6. Comparability of Countable Well Orderings 213 7. Countable Abelian Groups 217 8. Σ^0_1 and Delta01 Determinacy 221 9. The Σ^0_1 and Δ^0_1 Ramsey Theorems 228 10. Conclusions 233 VI. Π^1_1 Comprehension 235 1. Perfect Kernels 235 2. Coanalytic Uniformization 239 3. Coanalytic Equivalence Relations 243 4. Countable Abelian Groups 248 5. ...Determinacy 250 6. The Δ^0_2 Ramsey Theorem 254 7. Stronger Set Existence Axioms 257 8. Conclusions 258 Part B. Models of Subsystems of Z_2 259 VII. β-Models 261 1. The Minimum β-Model of Π^1_1 - CA_0 262 2. Countable Coded β-Models 266 3. A Set-Theoretic Interpretation of ATR_0 276 4. Constructible Sets and Absoluteness 290 5. Strong Comprehension Schemes 304 6. Strong Choice Schemes 312 7. β-Model Reflection 321 8. Conclusions 325 VIII. ω-Models 327 1. ω-Models of RCA_0 and ACA_0 328 2. Countable Coded ω-Models of WKL_0 332 3. Hyperarithmetical Sets 340 4. ω-Models of Σ_1 Choice 351 5. ω-Model Reflection and Incompleteness 360 6. ω-Models of Strong Systems 366 7. Conclusions 374 IX. Non-ω-Models 377 1. The First Order Parts of RCA_0 and ACA_0 378 2. The First Order Part of WKL_0 383 3. A Conservation Result for Hilbert’s Program 387 4. SaturatedModels 397 5. Gentzen-Style Proof Theory 404 6. Conclusions 406 Appendix 407 X. Additional Results 409 1. Measure Theory 409 2. Separable Banach Spaces 414 3. Countable Combinatorics 417 4. Reverse Mathematics for RCA_0 423 5. Conclusions 425 Bibliography 427 Index 443 "From the point of view of the foundations of mathematics, this definitive work by Simpson is the most anxiously awaited monograph for over a decade. The "subsystems of second order arithmetic" provide the basic formal systems normally used in our current understanding of the logical structure of classical mathematics. Simpson provides an encyclopedic treatment of these systems with an emphasis on *Hilbert's program* (where infinitary mathematics is to be secured or reinterpreted by finitary mathematics), and the emerging *reverse mathematics* (where axioms necessary for providing theorems are determined by deriving axioms from theorems). The classical mathematical topics treated in these axiomatic terms are very diverse, and include standard topics in complete separable metric spaces and Banach spaces, countable groups, rings, fields, and vector spaces, ordinary differential equations, fixed points, infinite games, Ramsey theory, and many others. The material, with its many open problems and detailed references to the literature, is particularly valuable for proof theorists and recursion theorists. The book is both suitable for the beginning graduate student in mathematical logic, and encyclopedic for the expert." Harvey Friedman, Ohio State University. COVER; HALF-TITLE; SERIES-TITLE; TITLE; COPYRIGHT; CONTENTS; LIST OF TABLES; PREFACE; ACKNOWLEDGMENTS; Chapter I INTRODUCTION; I.1. The Main Question; I.2. Subsystems of Z2; I.3. The System ACA0; I.4. Mathematics within ACA0; I.5. Pi11 -CA0 and Stronger Systems; I.6. Mathematics within Pi11 -CA0; I.7. The System RCA0; I.8. Mathematics within RCA0; I.9. Reverse Mathematics; I.10. The System WKL0; I.11. The System ATR0; I.12. The Main Question, Revisited; I.13. Outline of Chapters II through X; I.14. Conclusions; Part A DEVELOPMENT OF MATHEMATICS WITHIN SUBSYSTEMS OF Z2. Chapter II RECURSIVE COMPREHENSIONChapter III ARITHMETICAL COMPREHENSION; Chapter IV WEAK KNIG'S LEMMA; Chapter V ARITHMETICAL TRANSFINITE RECURSION; Chapter VI Pi11 COMPREHENSION; Part B MODELS OF SUBSYSTEMS OF Z2; Chapter VII beta-MODELS; Chapter VIII omega-MODELS; Chapter IX NON-omega-MODELS; APPENDIX; Chapter X ADDITIONAL RESULTS; BIBLIOGRAPHY; INDEX. What are the appropriate axioms for mathematics? Through a series of case studies, this volume examines these axioms to prove particular theorems in core areas including algebra, analysis, and topology, focusing on the language of second-order arithmetic, the weakest language rich enough to express and develop the bulk of mathematics.

through A Series Of Case Studies, This Volume Examines These Axioms To Prove Particular Theorems In Core Mathematical Areas.