We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for pairs (...) (RT₂²) splits into a stable version (SRT₂²) and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for RT₂² and SRT₂²). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL₀, DNR, and BΣ₂. We show, for instance, that WKL₀ is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is Π₁¹-conservative over the base system RCA₀. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply SRT₂² (and so does not imply RT₂²). This answers a question of Cholak, Jockusch, and Slaman. Our proofs suggest that the essential distinction between ADS and CAC on the one hand and RT₂² on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions. (shrink)

Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...) class in a way that is effective enough to preserve the property in which we are interested. In this paper, we show how to transfer a number of computability-theoretic properties from directed graphs to structures in the following classes: symmetric, irreflexive graphs; partial orderings; lattices; rings ; integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. This allows us to show that several theorems about degree spectra of relations on computable structures, nonpreservation of computable categoricity, and degree spectra of structures remain true when we restrict our attention to structures in any of the classes on this list. The codings we present are general enough to be viewed as establishing that the theories mentioned above are computably complete in the sense that, for a wide range of computability-theoretic nonstructure type properties, if there are any examples of structures with such properties then there are such examples that are models of each of these theories. (shrink)

Several notions of computability-theoretic reducibility between [Formula: see text] 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 [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...) text] under one of these notions. We also answer two questions raised by Dorais, Dzhafarov, Hirst, Mileti, and Shafer 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 [Formula: see text], there is an [Formula: see text]-coloring [Formula: see text] of [Formula: see text] such that every [Formula: see text]-coloring of [Formula: see text] has an infinite homogeneous set that does not compute any infinite homogeneous set for [Formula: see text], and connect this result with the notion of infinite information reducibility introduced by Dzhafarov and Igusa. Next, we introduce and study a new notion that provides a uniform version of the idea of implication with respect to [Formula: see text]-models of RCA0, and related notions that allow us to count how many applications of a principle [Formula: see text] are needed to reduce another principle to [Formula: see text]. Finally, we fill in a gap in the proof of Theorem 12.2 in Cholak, Jockusch, and Slaman. (shrink)

Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.

We build an א₁-categorical but not א₀-categorical theory whose only computably presentable model is the saturated one. As a tool, we introduce a notion related to limitwise monotonic functions.

We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ (...) ω∪{ω } then for any α-c.e. degree a > 0 there exists an intrinsically α-c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. All of these results also hold for m-degree spectra of relations. (shrink)

There has been increasing interest over the last few decades in the study of the effective content of Mathematics. One field whose effective content has been the subject of a large body of work, dating back at least to the early 1960s, is model theory. Several different notions of effectiveness of model-theoretic structures have been investigated. This communication is concerned withcomputablestructures, that is, structures with computable domains whose constants, functions, and relations are uniformly computable.In model theory, we identify isomorphic structures. (...) From the point of view of computable model theory, however, two isomorphic structures might be very different. For example, under the standard ordering of ω the success or relation is computable, but it is not hard to construct a computable linear ordering of type ω in which the successor relation is not computable. In fact, for every computably enumerable degree a, we can construct a computable linear ordering of type ω in which the successor relation has degree a. It is also possible to build two isomorphic computable groups, only one of which has a computable center, or two isomorphic Boolean algebras, only one of which has a computable set of atoms. Thus, for the purposes of computable model theory, studying structures up to isomorphism is not enough. (shrink)

We show that for every computably enumerable degree a > 0 there is an intrinsically c.e. relation on the domain of a computable structure of computable dimension 2 whose degree spectrum is { 0 , a } , thus answering a question of Goncharov and Khoussainov 55–57). We also show that this theorem remains true with α -c.e. in place of c.e. for any α∈ω∪{ω} . A modification of the proof of this result similar to what was done in (...) class='Hi'>Hirschfeldt shows that for any α∈ω∪{ω} and any α -c.e. degrees a 0 ,…, a n there is an intrinsically α -c.e. relation on the domain of a computable structure of computable dimension n+1 whose degree spectrum is { a 0 ,…, a n } . These results also hold for m-degree spectra of relations. (shrink)

We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 (...) -categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [23] to establish the same result for computable relations on computable linear orderings. We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ 0 2 -categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [14]. (shrink)

We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa’s result that there are no minimal pairs for relative generic computability and answers a basic structural question mentioned in several papers in the area.

For [Formula: see text], the coarse similarity class of [Formula: see text], denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of [Formula: see text] and [Formula: see text] has asymptotic density [Formula: see text]. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of [Formula: see text] and (...) [Formula: see text]. 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 [Formula: see text] where [Formula: see text] 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 [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly [Formula: see text], [Formula: see text], and [Formula: see text], and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree [Formula: see text] to be attractive if the class of all degrees at distance [Formula: see text] from [Formula: see text] has measure [Formula: see text], 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 [Formula: see text]-random, as well as a perfect set whose elements are mutually [Formula: see text]-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. (shrink)

We examine the reverse mathematical strength of a variation of Hindman’s Theorem (HT) constructed by essentially combining HT with the Thin Set Theorem to obtain a principle that we call thin-HT. This principle states that every coloring c:N→N has an infinite set S⊆N whose finite sums are thin for c, meaning that there is an i with c(s)≠i for all nonempty sums s of finitely many distinct elements of S. We show that there is a computable instance of thin-HT such (...) that every solution computes ∅′, as is the case with HT, as shown by Blass, Hirst, and Simpson (1987). In analyzing this proof, we deduce that thin-HT implies ACA0 over RCA0+IΣ20. On the other hand, using Rumyantsev and Shen’s computable version of the Lovász Local Lemma, we show that there is a computable instance of the restriction of thin-HT to sums of exactly 2 elements such that any solution has diagonally noncomputable degree relative to ∅′. Hence there is a computable instance of this restriction of thin-HT with no Σ20 solution. (shrink)

We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically invariant relation whose degree spectrum consists of all nontrivial r-degrees. We extend this construction to show that can be replaced by either or.

We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level (...) randomness notions going back to the work of Kurtz [73], Kautz [61], and Solovay [125]; and other calibrations of randomness based on definitions along the lines of Schnorr [117].These notions have complex interrelationships, and connections to classical notions from computability theory such as relative computability and enumerability. Computability figures in obvious ways in definitions of effective randomness, but there are also applications of notions related to randomness in computability theory. For instance, an exciting by-product of the program we describe is a more-or-less naturalrequirement-freesolution to Post's Problem, much along the lines of the Dekker deficiency set. (shrink)

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 [Formula: see text] be the halting probability of UA; 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 under the choice of an effective enumeration of the partial computable functions, [Formula: see text] can be vastly different for different choices of U. Even for a fixed U, there are oracles A =* B such that [Formula: see text] and [Formula: see text] 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. (shrink)

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of RCA 0 + SRT 2 2 must contain a nonlow set.

A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...) X is $low_2$ if $X\prime\prime$ $\leq_{T} 0\prime$ . To prove that a $low_2$ set X is not prime bounding we use a $0\prime$ -computable listing of the array of sets { Y : Y $\leq_{T}$ X } to build a CAD theory T which diagonalizes against all potential X-decidable prime models U of T. To prove that any $non-low_{2}$ ; X is indeed prime bounding, we fix a function f $\leq_T$ X that is not dominated by a certain $0\prime$ -computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula $\varphi (\bar{x})$ consistent with T, a principal type which contains it, and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. 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 [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] 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 [math] 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 [math], uncovering new differences between their logical strengths. (shrink)

We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof.

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...) single CD theory T such that every homogeneous model of T has a PA degree. (shrink)

A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.

1. Setting off: An introduction. 1.1. A measure of motivation. 1.2. Computable mathematics. 1.3. Reverse mathematics. 1.4. An overview. 1.5. Further reading -- 2. Gathering our tools: Basic concepts and notation. 2.1. Computability theory. 2.2. Computability theoretic reductions. 2.3. Forcing -- 3. Finding our path: Konig's lemma and computability. 3.1. II[symbol] classes, basis theorems, and PA degrees. 3.2. Versions of Konig's lemma -- 4. Gauging our strength: Reverse mathematics. 4.1. RCA[symbol]. 4.2. Working in RCA[symbol]. 4.3. ACA[symbol]. 4.4. WKL[symbol]. 4.5. [symbol]-models. (...) 4.6. First order axioms. 4.7. Further remarks -- 5. In defense of disarray -- 6. Achieving consensus: Ramsey's theorem. 6.1. Three proofs of Ramsey's theorem. 6.2. Ramsey's theorem and the arithmetic hierarchy. 6.3. RT, ACA[symbol], and the Paris-Harrington theorem. 6.4. Stability and cohesiveness. 6.5. Mathias forcing and cohesive sets. 6.6. Mathias forcing and stable colorings. 6.7. Seetapun's theorem and its extensions. 6.8. Ramsey's theorem and first order axioms. 6.9. Uniformity -- 7. Preserving our power: Conservativity. 7.1. Conservativity over first order systems. 7.2. WKL[symbol] and II[symbol]-conservativity. 7.3. COH and r-II[symbol]-conservativity -- 8. Drawing a map: Five diagrams -- 9. Exploring our surroundings: The world below RT[symbol]. 9.1. Ascending and descending sequences. 9.2. Other combinatorial principles provable from RT[symbol]. 9.3. Atomic models and omitting types -- 10. Charging ahead: Further topics. 10.1. The Dushnik-Miller theorem. 10.2. Linearizing well-founded partial orders. 10.3. The world above ACA[symbol]. 10.4. Still further topics, and a final exercise. (shrink)

Over the course of human history, the sciences, and biology in particular, have often been manipulated to cause immense human suffering. For example, biology has been used to justify eugenic programs, forced sterilization, human experimentation, and death camps—all in an attempt to support notions of racial superiority. By investigating the past, the contributors to _Biology and Ideology from Descartes to Dawkins_ hope to better prepare us to discern ideological abuse of science when it occurs in the future. Denis R. (...) Alexander and Ronald L. Numbers bring together fourteen experts to examine the varied ways science has been used and abused for nonscientific purposes from the fifteenth century to the present day. Featuring an essay on eugenics from Edward J. Larson and an examination of the progress of evolution by Michael J. Ruse, _Biology and Ideology_ examines uses both benign and sinister, ultimately reminding us that ideological extrapolation continues today. An accessible survey, this collection will enlighten historians of science, their students, practicing scientists, and anyone interested in the relationship between science and culture. (shrink)

This article represents comments arising from The Compatibility of Evolution and Design by Rope Kojonen (Palgrave Macmillan, 2021) concerning the role of chance and randomness in evolution (citations from this book are shown as page numbers in brackets). The various meanings of chance and randomness as used in descriptions of biological evolution are discussed and contrasted with their meanings in mathematics and metaphysics. The discussion relates to the role of contingency in evolution and to ideological and rhetorical extrapolations from biology (...) into philosophical world views. Overall it is concluded that evolution is not a chance process, except in the epistemic sense of “chance.” Theologically, this has implications for the idea that God creates through “a free evolutionary process” and may also influence our perspectives on divine action and intentionality in evolutionary history. (shrink)

There is a common misconception that our genomes - all unique, except for those in identical twins - have the upper hand in controlling our destiny. The latest genetic discoveries, however, do not support that view. Although genetic variation does influence differences in various human behaviours to a greater or lesser degree, most of the time this does not undermine our genuine free will. Genetic determinism comes into play only in various medical conditions, notably some psychiatric syndromes. Denis Alexander (...) here demonstrates that we are not slaves to our genes. He shows how a predisposition to behave in certain ways is influenced at a molecular level by particular genes. Yet a far greater influence on our behaviours is our world-views that lie beyond science - and that have an impact on how we think the latest genetic discoveries should, or should not, be applied. Written in an engaging style, Alexander's book offers tools for understanding and assessing the latest genetic discoveries critically. (shrink)

The present volume is an introduction to the use of tools from computability theory and reverse mathematics to study combinatorial principles, in particular Ramsey's theorem and special cases such as Ramsey's theorem for pairs. It would serve as an excellent textbook for graduate students who have completed a course on computability theory.

Phosphotyrosine phosphatases (PTPases) are the enzymes which remove phosphate groups from protein tyrosine residues. An enormous number of phosphatases have been cloned and sequenced during the past decade, many of which are expressed in haematopoietic cells. This review focuses on the biochemistry and cell biology of three phosphatases, the transmembrane CD45 and the cytosolic SH2‐domain‐containing PTPases SHP‐1 and SHP‐2, to illustrate the diverse ways in which PTPases regulate receptor signal transduction. The involvement of these and other PTPases has been demonstrated (...) in haematopoietic cell development, apoptosis, activation and non‐responsiveness. A common theme in the actions of many haematopoietic cell PTPases is the way in which they modulate the thresholds for receptor signalling, thereby regulating critical events in the positive and negative selection of lymphocytes. There is growing interest in haematopoietic PTPases and their associated regulatory proteins as targets for pharmaceutical intervention and in the involvement of these enzymes in human disease. (shrink)

Goncharov and Peretyat'kin independently gave necessary and sufficient conditions for when a set of types of a complete theory is the type spectrum of some homogeneous model of. Their result can be stated as a principle of second order arithmetic, which is called the Homogeneous Model Theorem (HMT), and analyzed from the points of view of computability theory and reverse mathematics. Previous computability theoretic results by Lange suggested a close connection between HMT and the Atomic Model Theorem (AMT), which states (...) that every complete atomic theory has an atomic model. The authors show that HMT and AMT are indeed equivalent in the sense of reverse mathematics, as well as in a strong computability theoretic sense and do the same for an analogous result of Peretyat'kin giving necessary and sufficient conditions for when a set of types is the type spectrum of some model. (shrink)

We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

One of the principal reasons for the confusion in which recent technological developments, and developments in the physical, chemical and biological sciences generally, have plunged us, consists in our inability to harmonise our means and our ends, to subordinate the former to the latter, to verify constantly their appropriateness or their incompatibility, and to evaluate their overall relation to man's final ends.

This study examines the socioeconomic and familial background of Irish Catholic priests born between 1867 and 1911. Previous research has hypothesized that lack of marriage opportunities may influence adoption of celibacy as part of a religious institution. The present study traced data from Irish seminary registries for 46 Catholic priests born in County Limerick, Ireland, using 1901 Irish Census returns and Land Valuation records. Priests were more likely to originate from landholding backgrounds, and with landholdings greater in size and wealth (...) than the local average. Priests were found to originate from families with more sons than the national average, but with similar numbers of daughters. These findings are discussed in relation to competition for resources and lineage survival strategies. (shrink)