Subsystems of Second Order Arithmetic

by Stephen G. Simpson

• ISBN13: 9780521884396
• ISBN10: 052188439X
• Edition: 2nd
• Format: Hardcover
• Copyright: 2009-05-29
• Publisher: Cambridge University Press

Summary

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.

Author Biography

Stephen G. Simpson is a mathematician and professor at Pennsylvania State University. The winner of the Grove Award for Interdisciplinary Research Initiation, Simpson specializes in research involving mathematical logic, foundations of mathematics, and combinatorics.

Table of Contents

List of Tables	p. xi
Preface	p. xiii
Acknowledgments	p. xv
Introduction	p. 1
The Main Question	p. 1
Subsystems of Z2	p. 2
The System ACA0	p. 6
Mathematics within ACA0	p. 9
$$-CA0 and Stronger Systems	p. 16
Mathematics within $$-CA0	p. 19
The System RCA0	p. 23
Mathematics within RCA0	p. 27
Reverse Mathematics	p. 32
The System WKL0	p. 35
The System ATR0	p. 38
The Main Question, Revisited	p. 42
Outline of Chapters II through X	p. 43
Conclusions	p. 60
Development of Mathematics within Subsystems of Z2
Recursive Comprehension	p. 63
The Formal System RCA0	p. 63
Finite Sequences	p. 65
Primitive Recursion	p. 69
The Number Systems	p. 73
Complete Separable Metric Spaces	p. 78
Continuous Functions	p. 84
More on Complete Separable Metric Spaces	p. 88
Mathematical Logic	p. 92
Countable Fields	p. 96
Separable Banach Spaces	p. 99
Conclusions	p. 103
Arithmetical Comprehension	p. 105
The Formal System ACA0	p. 105
Sequential Compactness	p. 106
Strong Algebraic Closure	p. 110
Countable Vector Spaces	p. 112
Maximal Ideals in Countable Commutative Rings	p. 115
Countable Abelian Groups	p. 118
Köet;nig's Lemma and Ramsey's Theorem	p. 121
Conclusions	p. 125
Weak Köet;nig's Lemma	p. 127
The Heine/Borel Covering Lemma	p. 127
Properties of Continuous Functions	p. 133
The Göet;del Completeness Theorem	p. 139
Formally Real Fields	p. 141
Uniqueness of Algebraic Closure	p. 144
Prime Ideals in Countable Commutative Rings	p. 146
Fixed Point Theorems	p. 149
Ordinary Differential Equations	p. 154
The Separable Hahn/Banach Theorem	p. 160
Conclusions	p. 165
Arithmetical Transfinite Recursion	p. 167
Countable Well Orderings; Analytic Sets	p. 167
The Formal System ATR0	p. 173
Borel Sets	p. 178
Perfect Sets; Pseudohierarchies	p. 185
Reversals	p. 189
Comparability of Countable Well Orderings	p. 195
Countable Abelian Groups	p. 199
¿01 and ¿01 Determinacy	p. 203
The ¿01 and ¿01 Ramsey Theorems	p. 210
Conclusions	p. 215
$$ Comprehension	p. 217
Perfect Kernels	p. 217
Coanalytic Uniformization	p. 221
Coanalytic Equivalence Relations	p. 225
Countable Abelian Groups	p. 230
¿01 ¿ $$ Determinacy	p. 232
The ¿02 Ramsey Theorem	p. 236
Stronger Set Existence Axioms	p. 239
Conclusions	p. 240
Models of Subsystems of Z2
ß-Models	p. 243
The Minimum ß-Model of $$-CA0	p. 244
Countable Coded ß-Models	p. 248
A Set-Theoretic Interpretation of ATR0	p. 258
Constructible Sets and Absoluteness	p. 272
Strong Comprehension Schemes	p. 286
Strong Choice Schemes	p. 294
ß-Model Reflection	p. 303
Conclusions	p. 307
¿-Models	p. 309
¿-Models of RCA0 and ACA0	p. 310
Countable Coded ¿-Models of WKL0	p. 314
Hyperarithmetical Sets	p. 322
¿-Models of ¿11 Choice	p. 333
¿-Model Reflection and Incompleteness	p. 342
¿-Models of Strong Systems	p. 348
Conclusions	p. 356
Non-¿-Models	p. 359
The First Order Parts of RCA0 and ACA0	p. 360
The First Order Part of WKL0	p. 365
A Conservation Result for Hilbert's Program	p. 369
Saturated Models	p. 379
Gentzen-Style Proof Theory	p. 386
Conclusions	p. 388
Additional Results	p. 391
Measure Theory	p. 391
Separable Banach Spaces	p. 396
Countable Combinatorics	p. 399
Reverse Mathematics for RCA0	p. 405
Conclusions	p. 407
Bibliography	p. 409
Index	p. 425
Table of Contents provided by Ingram. All Rights Reserved.