Slicing the Truth

The following sections are included:

• Contents
• Foreword by Series Editors
• Foreword by Volume Editors
• Preface
• Acknowledgments

Every mathematician knows that if 2 + 2 = 5 then Bertrand Russell is the pope. Indeed, Russell is credited with having given a proof of that fact in a lecture by arguing as follows: If 2+2 = 5, then, subtracting 3 from each side, 1 = 2. The pope and Russell are two, therefore they are one. Of course, from the point of view of classical logic, no such proof is needed, since a false statement implies every statement. Contrapositively, every statement implies a given true statement. But suppose we were to take seriously the task of proving that, say, the Four Color Theorem implies that there are infinitely many primes. What are the chances that any of us could come up with a proof that “really uses” the Four Color Theorem? The exercise may seem as pointless as it is difficult, but of course mathematicians do set and perform tasks of this kind on a regular basis. “Use the Bolzano-Weierstrass Theorem to show that if f : [0, 1] → ℝ is continuous, then f is uniformly continuous.” is a typical homework problem in analysis, and the question “Can Chaitin's information-theoretic version of Gödel's First Incompleteness Theorem be used to prove Gödel's Second Incompleteness Theorem?” led to a lovely recent paper by Kritchman and Raz [116]. There is also a well-established practice of showing that a given theorem can be proved without using certain methods, for instance in the exercise of proving the irrationality of without using the fundamental theorem of arithmetic, or in elementary proofs of the prime number theorem. We have all heard our teachers and colleagues say things like “Theorems A and B are equivalent.” or “Theorem C does not just follow from Theorem D.” or “Using Lemma E in proving Theorem F is convenient but not necessary.” These are often crucial things to understand about an area of mathematics…

In this chapter, we first review a few essential computability theoretic concepts, as a reminder and to fix notation; for more information, see [158,159,170,196,197] or Chapter 2 of [40]. This review assumes knowledge of basic concepts such as computable (also known as recursive) sets and functions, computably enumerable (also known as recursively enumerable) sets, and Turing reductions. We then introduce the important technique of forcing, originally developed in the context of set theory but of great usefulness in computability theory and reverse mathematics.

In this chapter, we explore in greater detail the example mentioned in Section 1.2: the computability theoretic analysis of versions of König's Lemma. Once we have introduced the framework and some of the basic systems of reverse mathematics in the next chapter, we will be able to use the results and arguments in this chapter to provide a reverse mathematical analysis of versions of König's Lemma as well. As we will see, Weak König's Lemma plays a particularly important role in reverse mathematics…

The reverse mathematics program was initiated by Friedman [59, 60] and further developed by Simpson, his students and collaborators, and, more recently, an increasing number of researchers from computability theory, proof theory, and other areas of mathematical logic. In this chapter, we formally introduce its framework and some of its basic systems. For more details and discussion, see Simpson [191]. Although we work in what is called “second order arithmetic”, the underlying logic of our formal systems is the usual first order logic of any of the standard introductory textbooks in the area such as Enderton [53]. Almost all of this book will focus on principles provable in the system ACA₀, which will be introduced in Section 4.3 and corresponds to arithmetic mathematics (i.e., mathematics that can be done without using sets outside the arithmetic hierarchy), so we will concentrate on this and weaker systems. There is a great deal of work in reverse mathematics beyond ACA₀, however, a small amount of which we will discuss in Section 10.3…

Aesthetically, I am allergic to neatness. This preference for a certain amount of disarray is in line with (or perhaps engenders… ) my epistemological views. I tend to believe that, in any interesting setting, when the truth has been fully systematized and organized, the truth has long since lain elsewhere. I do believe in organization and classification, but my systems are ones in which the organizing principles themselves are complicated enough to need organization, where connections range all the way from the completely tight to the very tenuous, and where the great engine of ineffability is continually generating…

Ramsey's Theorem [166] captures the idea that total disorder is impossible: a sufficiently large structure will always contain a large ordered substructure. A well-known special case of the finite version is that in any group of six people, there are at least three people who all know each other or three people who are all strangers to each other. We will examine the following infinite versions of Ramsey's Theorem. As we will see, the computability theoretic and reverse mathematical analysis of these and related principles makes for an excellent case study, as it involves a range of central techniques and ideas in these areas…

Sometimes it is possible to prove theorems of the form “P does not imply Q over the base theory R” for a whole class of principles Q at once, based purely on their logical form. Such theorems can give us a great deal of information about the power of R + P relative to the power of R alone…

Let us summarize some of the results of the previous chapters. In all of the diagrams below, no other implications than the ones shown (or implied by transitivity) hold. Readers may find it useful to go through the following diagrams and justify the implications and nonimplications, using results given above. Expanded versions of some of these diagrams can be found in Hirschfeldt and Jockusch [85]. These diagrams were generated by hand, but there is a tool available for automating the drawing of such diagrams, known as “The Reverse Mathematics Zoo”. At the time of writing, it is maintained by Damir Dzhafarov at rmzoo.uconn.edu…

Unlike the case of WKL₀, there do not seem to be many principles equivalent to over RCA₀. There is, however, a whole world of principles, particularly combinatorial ones, below (i.e., provable in ) in the reverse mathematical universe. We have already discussed and COH. In this chapter, we consider a few more, to illustrate some of the workings of this world below . We begin by focusing on a principle called ADS, as an extended example. We then briefly mention several other combinatorial principles provable from . Finally, we discuss some basic theorems that come from what would seem like quite a different area of mathematics, namely model theory, but nevertheless also inhabit this part of the reverse mathematical universe. For the most part, the level of detail in this chapter will be lower than in our long case study of ; much more information can be found in the cited papers, among several others. The literature of this area of research continues to expand, so searching for recent papers and preprints is likely to prove rewarding. It is also a useful exercise to fill out the diagrams in the previous chapter with the principles mentioned below, either by hand or using the Reverse Mathematics Zoo mentioned in the previous chapter; several of the papers cited in this chapter also contain such extended diagrams.

In this final chapter, we discuss a small selection of topics in the computability theoretic and reverse mathematical analysis of combinatorial principles. Included are examples that illustrate some important issues and ideas in the area that were not emphasized in previous chapters, as well as some open questions of current research interest.

The following sections are included:

• Appendix. Lagniappe: A Proof of Liu's Theorem
• Bibliography