This book catalogs some of the most recent and interesting results in the field of Reverse Mathematics while emphasizing the field’s connection to Computability Theory and its applications. It serves as both a reference for researchers and a very good introductory text for those with no prior background in the field. The most distinguishing feature of this text, when compared to other advanced treatments like those of Simpson (S. G. Simpson,
Subsystems of Second Order Arithmetic
,
$2^{nd}$
edition, Cambridge University Press, Cambridge, 2009) and Hirschfeldt (D. R. Hirschfeldt,
Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles
, World Scientific, Hackensack, 2014), is its explicit emphasis on the computable relationships (i.e., reductions) between solutions to different mathematical problems. Although generally shared, but not as strongly emphasized by Hirschfeldt, the modern point of view found in this work essentially replaces some of the logical formalism found in the traditional literature with computable intuition. The roots of this viewpoint stretch back to a handful of mathematicians in the 1990s who began a fruitful in-depth study of computability-theoretic aspects of various combinatorial principles related to Ramsey’s Theorem for pairs. More recently the field has seen rapid development by a younger crop of researchers. Thus, between the lines of its mathematical exposition, in the text there also lies a record of the excitement resulting from the development of this particular line of research over the last 30 years.
The main goal of Reverse Mathematics is to classify mathematical arguments based on the axiomatic strength required to validate a theorem. In other words one asks “is the axiom necessary to prove the theorem?” i.e., “can the theorem be deduced from a strictly weaker axiom?” The meaning and technicalities of the specific version of the subject all follow from the way in which the word weaker is defined via the selected base theory; in the particular case of Reverse Mathematics the relevant base theory essentially formalizes the idea of a Turing reduction. The program of Reverse Mathematics was formally introduced by Friedman in 1975; it sought to calibrate the strengths of mathematical theorems via yardsticks provided by certain “special” subsystems of Second-Order Arithmetic. Over the years these special subsystems have come to be known as the “Big Five” because many theorems from classical mathematics are equivalent to one of them over the weak base theory
${\mathsf {RCA_0}}$
that essentially models computable mathematics, possibly in a nonstandard universe. Intuitively speaking, if Theorem A implies Theorem B over
${\mathsf {RCA_0}}$
, then constructions obtained via applications of Theorem B can be simply (i.e., algorithmically) obtained via constructions that follow from Theorem A.
The most distinguishing feature of this book is referenced by the first two-thirds of its subtitle, namely the book’s focus on Problems and their relations via Reductions. The foundation for this modern, more informal, and computability-centered perspective on Reverse Mathematics, is established in Part I via its coverage of:
-
• the essential computability-theoretic foundations for all that follows, including basic definitions and standard material on topics such as
$\Pi ^0_1-$
classes, including the Low and Hyperimmune-Free Basis Theorems of Jockusch and Soare, as well as the computability characteristics of hyperimmune and PA Turing degrees; -
• the arithmetization of analytic mathematics via computable formulations of various specific problems (i.e., theorems) introduced and well-studied in the context of Reverse Mathematics at its outset, including König’s Lemma and Ramsey’s Theorem, as well as relevant computability properties potentially possessed by their solutions;
-
• problem reducibilities that use concepts from Computability Theory to obtain methods for constructing solutions to one problem when given oracle access to the solutions for another problem.
It is really the final item above that distinguishes this text from others on the subject. While other texts take a more formal approach, the one taken here by Dzhafarov and Mummert reveals the natural connection between Reverse and Computable Mathematics. More specifically, the modern methods utilized here reveal strong connections between logical implication in Second-Order Arithmetic and various computability-theoretic reducibilities, including (strong) computable, (strong) Weihrauch, and
$\omega $
-reducibility.
The next part of the text discusses relevant logical background tangential to pure Computability Theory, including the formalities of Second-Order Arithmetic, induction, and forcing. Beginning with the model theory of Second-Order Arithmetic, this part introduces the formal setting of Reverse Mathematics, giving precise formulations of the Big Five subsystems that have historically taken center stage in Reverse Mathematics. This is followed by introductions to general logical concepts that only really acquire significance in a formal context, such as conservativity, First-Order Arithmetic, and relevant relations between logical implication and computable reduction. Chapter 6 gives in depth coverage of induction and bounding principles, their relationships via the Kirby–Paris Hierarchy, and characterizations via combinatorial principles. Next, effective forcing and genericity are discussed, with a focus on the utility of Mathias forcing as a method for constructing cohesive sets.
Part III comprises the heart of the text and chronicles the development of a major line of research from the end of the last century through the book’s publication; these two chapters make up roughly a third of the text’s content. Chapter 8 deals mainly with the Reverse Mathematics of Ramsey’s Theorem for pairs. The first half of the chapter begins with relatively older results of Jockusch and others that establish basic upper and lower bounds, then goes on to the fundamental insights of Seetapun relating Ramsey’s Theorem to Mathias forcing, eventually revealing the deeper insights of Cholak, Jockusch, and Slaman that decompose Ramsey’s Theorem for pairs into the Cohesive Principle and a stable version of the theorem. Meanwhile, the second half of the chapter covers more recent hard technical results characterizing Ramsey’s Theorem for pairs in a wider context. Chapter 9 expands on the methods of the previous chapter to reveal the subtle and intricate relationships between many combinatorial principles related to Ramsey’s Theorem for pairs, including chain/antichain theorems for linear and partial orders, variants of Ramsey’s Theorem, the Erdős–Moser Theorem, Hindman’s Theorem, Milliken’s Tree Theorem, and many more. The chapter concludes on pages 356–7 with a large and complex illustration of the “zoo” of combinatorial principles that have been previously studied in this context, and the many subtle relationships between them that have been developed by many researchers, young and old, over the last quarter century.
Part IV concludes the text by reviewing some results that classify theorems from Analysis and Topology, Algebra, and Set Theory in the reverse mathematical context, and concludes with some discussion on Higher-Order Reverse Mathematics. A more thorough treatment of the older results here can be found in Simpson’s text, but the section also contains more recent results like those of Day on dynamics, Hirst and Mummert on vector spaces, Solomon on orderings, and many others.
Mainly through the development of the material contained in this book, Reverse Mathematics has attracted many mathematicians in recent years and remains one of the more popular areas of research for mathematicians interested in Computability Theory. This book does an excellent job of bringing new researchers up to speed by showing how the subject acquired its modern form through its recent history.
