Narrow Results

As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let be the halting probability of U^A; this gives a natural uniform way of producing an A-random real for every A ∈ 2^ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory and this Omega operator. But unlike the jump, which is invariant (up to computable permutation) under the choice of an effective enumeration of the partial computable functions, can be vastly different for different choices of U. Even for a fixed U, there are oracles A =* B such that and are 1-random relative to each other. We prove this and many other interesting properties of Omega operators. We investigate these operators from the perspective of analysis, computability theory, and of course, algorithmic randomness.

Several notions of computability-theoretic reducibility between ${\mathrm{\Pi }}_2^1$ principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each $n\ge 3$, there is an instance of RT${}_2^n$ all of whose solutions have PA degree over ${\varnothing }^{(n-2)},$ and use this to show that König’s Lemma lies strictly between RT${}_2^2$ and RT${}_2^3$ under one of these notions. We also answer two questions raised by Dorais, Dzhafarov, Hirst, Mileti, and Shafer (2016) on comparing versions of Ramsey’s Theorem and of the Thin Set Theorem with the same exponent but different numbers of colors. Still on the topic of the effect of the number of colors on the computable aspects of Ramsey-theoretic properties, we show that for each $m\ge 2$, there is an $(m+1)$-coloring $c$ of $\mathbb{N}$ such that every $m$-coloring of $\mathbb{N}$ has an infinite homogeneous set that does not compute any infinite homogeneous set for $c$, and connect this result with the notion of infinite information reducibility introduced by Dzhafarov and Igusa (to appear). Next, we introduce and study a new notion that provides a uniform version of the idea of implication with respect to $\omega$-models of RCA₀, and related notions that allow us to count how many applications of a principle $P$ are needed to reduce another principle to $P$. Finally, we fill in a gap in the proof of Theorem 12.2 in Cholak, Jockusch, and Slaman (2001).

Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between ${\mathrm{\Pi }}_2^1$ principles over $\omega$-models of ${RCA}_0$. They also introduced a version of this game that similarly captures provability over ${RCA}_0$. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication $Q\to P$ between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between ${\mathrm{\Pi }}_2^1$ principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of $B{\mathrm{\Sigma }}_2^0$, uncovering new differences between their logical strengths.

For $A\subseteq \omega$, the coarse similarity class of A, denoted by $[A]$, is the set of all $B\subseteq \omega$ such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric $\delta$ on the space ${𝒮}$ of coarse similarity classes defined by letting $\delta ([A],[B])$ be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form $\{[A]:A\in {𝒰}\}$ where ${𝒰}$ is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of ${𝒰}$.

We then define a distance between Turing degrees based on Hausdorff distance in the metric space $({𝒮},\delta )$. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, $1/2$, and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance $1/2$ from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability.

Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic.

Finally, we study the completeness of $({𝒮},\delta )$ from the perspectives of computability theory and reverse mathematics.

Solovay showed that there are noncomputable reals α such that H(α ↾ n) ⩽ H(1ⁿ) + O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem. Therefore, our construction of an H-trivial computably enumerable set is an easy, injury-free construction of an incomplete computably enumerable set. Finally, we relate the H-trivials to other classes of “highly nonrandom” reals that have been previously studied.

In this paper we study constructive measure and dimension in the class of limit computable sets. We prove that the lower cone of any Turing-incomplete set in has -dimension 0, and in contrast, that although the upper cone of a noncomputable set in always has -measure 0, upper cones in have nonzero -dimension. In particular the -dimension of the Turing degree of (the Halting Problem) is 1. Finally, it is proven that the low sets do not have -measure 0, which means that they do not form a small subset of . This result has consequences for the existence of bi-immune sets.

We study the reverse mathematics and computability-theoretic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that implies DNR over RCA₀ but COH does not, and answer a question of Mileti by showing that every computable stable 2-coloring of pairs has an incomplete infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that does not imply .

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

The following sections are included:

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