We study model theoretic tree properties and their associated cardinal invariants. In particular, we obtain a quantitative refinement of Shelah’s theorem for countable theories, show that [Formula: see text] is always witnessed by a formula in a single variable and that weak [Formula: see text] is equivalent to [Formula: see text]. Besides, we give a characterization of [Formula: see text] via a version of independent amalgamation of types and apply this criterion to verify that some examples in the literature (...) are indeed [Formula: see text]. (shrink)

We study Kim-independence over arbitrary sets. Assuming that forking satisfies existence, we establish Kim's lemma for Kim-dividing over arbitrary sets in an NSOP1 theory. We deduce symmetry of Kim-independence and the independence theorem for Lascar strong types.

We consider the relation between versions of Ramsey’s Theorem and König’s Infinity Lemma, in the absence of the axiom of choice.

This paper addresses the strength of Ramsey's theorem for pairs ($RT^2_2$) over a weak base theory from the perspective of 'proof mining'. Let $RT^{2-}_2$ denote Ramsey's theorem for pairs where the coloring is given by an explicit term involving only numeric variables. We add this principle to a weak base theory that includes weak König's Lemma and a substantial amount of $\Sigma^0_1$-induction (enough to prove the totality of all primitive recursive functions but not of all primitive (...) recursive functionals). In the resulting theory we show the extractability of primitive recursive programs and uniform bounds from proofs of $\forall\exists$-theorems. There are two components of this work. The first component is a general proof-theoretic result, due to the second author, that establishes conservation results for restricted principles of choice and comprehension over primitive recursive arithmetic PRA as well as a method for the extraction of primitive recursive bounds from proofs based on such principles. The second component is the main novelty of the paper: it is shown that a proof of Ramsey's theorem due to Erdős and Rado can be formalized using these restricted principles. So from the perspective of proof unwinding the computational content of concrete proofs based on $RT^2_2$ the computational complexity will, in most practical cases, not go beyond primitive recursive complexity. This even is the case when the theorem to be proved has function parameters f and the proof uses instances of $RT^2_2$ that are primitive recursive in f. (shrink)

The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ (...) but not in general. We also answer the analogs of two well-known questions about the stable Ramsey's theorem by showing that our weaker principle does not imply COH or WKL 0 in the context of reverse mathematics. (shrink)

The purpose is to study the strength of Ramsey’s Theorem for pairs restricted to recursive assignments ofk-many colors, with respect to Intuitionistic Heyting Arithmetic. We prove that for every natural number$k \ge 2$, Ramsey’s Theorem for pairs and recursive assignments ofkcolors is equivalent to the Limited Lesser Principle of Omniscience for${\rm{\Sigma }}_3^0$formulas over Heyting Arithmetic. Alternatively, the same theorem over intuitionistic arithmetic is equivalent to: for every recursively enumerable infinitek-ary tree there is some$i < k$and some branch (...) with infinitely many children of indexi. (shrink)

It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$, where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every (...) computable 2-coloring of pairs admits a pair of low₂ infinite homogeneous sets whose degrees form a minimal pair. (shrink)

We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let (...) IΣ n and BΣ n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0. (shrink)

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)

We consider the relation between versions of Ramsey’s Theorem and König’s Infinity Lemma, in the absence of the axiom of choice.

We prove that any proof of a [Formula: see text] sentence in the theory [Formula: see text] can be translated into a proof in [Formula: see text] at the cost of a polynomial increase in size. In fact, the proof in [Formula: see text] can be obtained by a polynomial-time algorithm. On the other hand, [Formula: see text] has nonelementary speedup over the weaker base theory [Formula: see text] for proofs of [Formula: see text] sentences. We also show that for (...) [Formula: see text], proofs of [Formula: see text] sentences in [Formula: see text] can be translated into proofs in [Formula: see text] at a polynomial cost in size. Moreover, the [Formula: see text]-conservativity of [Formula: see text] over [Formula: see text] can be proved in [Formula: see text], a fragment of bounded arithmetic corresponding to polynomial-time computation. For [Formula: see text], this answers a question of Clote, Hájek and Paris. (shrink)

We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for (...) recursive formulas. We also show that Ramsey's Theorem for Pairs is strong enough to prove some sentences in first order arithmetic which are not provable within . In particular, Ramsey's Theorem for Pairs is not conservative over for -sentences. (shrink)

In this paper, we show that equation image is a equation image-conservative extension of BΣ1 + exp, thus it does not imply IΣ1.

We show that \\) cannot be proved with one typical application of \\) in an intuitionistic extension of \ to higher types, but that this does not remain true when the law of the excluded middle is added. The argument uses Kohlenbach’s axiomatization of higher order reverse mathematics, results related to modified reducibility, and a formalization of Weihrauch reducibility.

In this paper we study with proof-theoretic methods the function(al) s provably recursive relative to Ramsey's theorem for pairs and the cohesive principle (COH). Our main result on COH is that the type 2 functional provably recursive from $RCA_0 + COH + \Pi _1^0 - CP$ are primitive recursive. This also provides a uniform method to extract bounds from proofs that use these principles. As a consequence we obtain a new proof of the fact that $WKL_0 + \Pi (...) _1^0 - CP + COH$ is $\Pi _1^0 $ -conservative over PRA. Recent work of the first author showed that $\Pi _1^0 + CP + COH$ is equivalent to a weak variant of the Bolzano-Weierstraß principle. This makes it possible to use our results to analyze not only combinatorial but also analytical proofs. For Ramsey's theorem for pairs and two colors $\left( {RT_2^2 } \right)$ we obtain the upper bounded that the type 2 functionals provable recursive relative to $RCA_0 + \sum\nolimits_2^0 {IA + RT_2^2 } $ are in T₁. This is the fragment of Gödel's system T containing only type 1 recursion—roughly speaking it consists of functions of Ackermann type. With this we also obtain a uniform method for the extraction of T₁-bounds from proofs that use RT2..... Moreover, this yields a new proof of the fact that $WKL_0 + \sum\nolimits_2^0 {IA} + RT_2^2 $ is $\Pi _1^0 $ -conservative over $RCA_0 + \sum\nolimits_2^0 { - IA} $ . The results are obtained in two steps: in the first step a term including Skolem functions for the above principles is extracted from a given proof. This is done using Gödel's functional interpretation. After this the term is normalized, such that only specific instances of the Skolem functions are used. In the second step this term is interpreted using $\Pi _1^0 $ -comprehension. The comprehension is then eliminated in favor of induction using either elimination of monotone Skolem functions (for COH) or Howard's ordinal analysis of bar recursion (for $RT_2^2 $. (shrink)

We study the first-order consequences of Ramsey’s Theorem fork-colourings ofn-tuples, for fixed$n, k \ge 2$, over the relatively weak second-order arithmetic theory$\mathrm {RCA}^*_0$. Using the Chong–Mourad coding lemma, we show that in a model of$\mathrm {RCA}^*_0$that does not satisfy$\Sigma ^0_1$induction,$\mathrm {RT}^n_k$is equivalent to its relativization to any proper$\Sigma ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.We give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$for$n (...) \ge 3$. We show that they form a non-finitely axiomatizable subtheory of$\mathrm {PA}$whose$\Pi _3$fragment coincides with$\mathrm {B} \Sigma _1 + \exp $and whose$\Pi _{\ell +3}$fragment for$\ell \ge 1$lies between$\mathrm {I} \Sigma _\ell \Rightarrow \mathrm {B} \Sigma _{\ell +1}$and$\mathrm {B} \Sigma _{\ell +1}$. We also give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^2_k + \neg \mathrm {I} \Sigma _1$. In general, we show that the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^2_k$form a subtheory of$\mathrm {I} \Sigma _2$whose$\Pi _3$fragment coincides with$\mathrm {B} \Sigma _1 + \exp $and whose$\Pi _4$fragment is strictly weaker than$\mathrm {B} \Sigma _2$but not contained in$\mathrm {I} \Sigma _1$.Additionally, we consider a principle$\Delta ^0_2$-$\mathrm {RT}^2_2$which is defined like$\mathrm {RT}^2_2$but with both the$2$-colourings and the solutions allowed to be$\Delta ^0_2$-sets rather than just sets. We show that the behaviour of$\Delta ^0_2$-$\mathrm {RT}^2_2$over$\mathrm {RCA}_0 + \mathrm {B}\Sigma ^0_2$is in many ways analogous to that of$\mathrm {RT}^2_2$over$\mathrm {RCA}^*_0$, and that$\mathrm {RCA}_0 + \mathrm {B} \Sigma ^0_2 + \Delta ^0_2$-$\mathrm {RT}^2_2$is$\Pi _4$- but not$\Pi _5$-conservative over$\mathrm {B} \Sigma _2$. However, the statement we use to witness failure of$\Pi _5$-conservativity is not provable in$\mathrm {RCA}_0 +\mathrm {RT}^2_2$. (shrink)

In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from RT, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below RT has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that ADS is not equivalent to CAC and that EM is not equivalent to RT.

It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best possible in (...) various senses. (shrink)

We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.

We formulate a polarized version of Ramsey’s theorem for trees. For those exponents greater than 2, both the reverse mathematics and the computability theory associated with this theorem parallel that of its linear analog. For pairs, the situation is more complex. In particular, there are many reasonable notions of stability in the tree setting, complicating the analysis of the related results.

This fourth edition of one of the classic logic textbooks has been thoroughly revised by John Burgess. The aim is to increase the pedagogical value of the book for the core market of students of philosophy and for students of mathematics and computer science as well. This book has become a classic because of its accessibility to students without a mathematical background, and because it covers not simply the staple topics of an intermediate logic course such as Godel's Incompleteness Theorems, (...) but also a large number of optional topics from Turing's theory of computability to Ramsey's theorem. John Burgess has now enhanced the book by adding a selection of problems at the end of each chapter, and by reorganising and rewriting chapters to make them more independent of each other and thus to increase the range of options available to instructors as to what to cover and what to defer. (shrink)

In [3] F. P. Ramsey proved as a theorem of Zermelo-Fraenkel set theory (ZF) with the Axiom of Choice (AC) the following result:(1) Theorem. Let A be an infinite class. For each integer n and partition {X, Y} of the size n subsets of A, there exists an infinite subclass of A all of whose size n subsets are contained in only one of X or Y.

This paper reconstructs and evaluates the representation theorem presented by Ramsey in his essay 'Truth and Probability', showing how its proof depends on a novel application of Hölder's theory of measurement. I argue that it must be understood as a solution to the problem of measuring partial belief, a solution that in many ways remains unsurpassed. Finally I show that the method it employs may be interpreted in such a way as to avoid a well known objection to it (...) due to Richard Jeffrey. (shrink)

This paper reconstructs and evaluates the representation theorem presented by Ramsey in his essay 'Truth and Probability', showing how its proof depends on a novel application of Hölder's theory of measurement. I argue that it must be understood as a solution to the problem of measuring partial belief, a solution that in many ways remains unsurpassed. Finally I show that the method it employs may be interpreted in such a way as to avoid a well known objection to it (...) due to Richard Jeffrey. (shrink)

We examine the Dual Ramsey Theorem and two related combinatorial principles VW(k,l) and OVW(k,l) from the perspectives of reverse mathematics and effective mathematics. We give a statement of the Dual Ramsey Theorem for open colorings in second order arithmetic and formalize work of Carlson and Simpson [1] to show that this statement implies ACA 0 over RCA 0 . We show that neither VW(2,2) nor OVW(2,2) is provable in WKL 0 . These results give partial answers to questions (...) posed by Friedman and Simpson [3]. (shrink)

We show that it is consistent that the reaping number r is less than u , the size of the smallest base for an ultrafilter. To show that our forcing preserves certain ultrafilters, we prove a general partition theorem involving Ramsey ideals.

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$, there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$. The latter property is known as cone avoidance.In this article, we design a natural class of Ramsey-like theorems (...) encompassing many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every k-coloring of $[\omega ]^n$, of an infinite subdomain $H \subseteq \omega $ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions. (shrink)

In this paper we study the automorphism groups of countable arithmetically saturated models of Peano Arithmetic. The automorphism groups of such structures form a rich class of permutation groups. When studying the automorphism group of a model, one is interested to what extent a model is recoverable from its automorphism group. Kossak-Schmerl [12] show that ifMis a countable, arithmetically saturated model of Peano Arithmetic, then Aut(M) codes SSy(M). Using that result they prove:Let M1. M2be countable arithmetically saturated models of Peano (...) Arithmetic such that Aut(M1)≅ Aut(M2).ThenSSy(M1) = SSy(M2).We show that ifMis a countable arithmetically saturated of Peano Arithmetic, then Aut(M) can recognize if some maximal open subgroup is a stabilizer of a nonstandard element, which is smaller than any nonstandard definable element. That fact is used to show the main theorem:Let M1,M2be countable arithmetically saturated models of Peano Arithmetic such thatAut(M1) ≅ Aut(M2).Then for every n<ωHere RT2nis Infinite Ramsey's Theorem stating that every 2-coloring of [ω]nhas an infinite homogeneous set. Theorem 0.2 shows that for models of a false arithmetic the converse of Kossak-Schmerl Theorem 0.1 is not true. Using the results of Reverse Mathematics we obtain the following corollary:There exist four countable arithmetically saturated models of Peano Arithmetic such that they have the same standard system but their automorphism groups are pairwise non-isomorphic. (shrink)

We use the model theoretic notion of coheir to give short proofs of old and new theorems in Ramsey Theory. As an illustration we start from Ramsey's theorem itself. Then we prove Hindman's theorem and the Hales-Jewett theorem. Finally, we prove the two Ramsey theoretic principles that have among their consequences partition theorems due to Carlson and to Gowers.

We show, relative to the base theory RCA₀: A nontrivial tree satisfies Ramsey's Theorem only if it is biembeddable with the complete binary tree. There is a class of partial orderings for which Ramsey's Theorem for pairs is equivalent to ACA₀. Ramsey's Theorem for singletons for the complete binary tree is stronger than $B\sum_{2}^{0}$ , hence stronger than Ramsey's Theorem for singletons for ω. These results lead to extensions of results, or answers (...) to questions, of Chubb, Hirst, and McNicholl [3]. (shrink)

A general method for constructing a new class of topological Ramsey spaces is presented. Members of such spaces are infinite sequences of products of Fraïssé classes of finite relational structures satisfying the Ramsey property. The Product Ramsey Theorem of Sokič is extended to equivalence relations for finite products of structures from Fraïssé classes of finite relational structures satisfying the Ramsey property and the Order-Prescribed Free Amalgamation Property. This is essential to proving Ramsey-classification theorems for equivalence relations on fronts, generalizing (...) the Pudlák–Rödl Theorem to this class of topological Ramsey spaces. To each topological Ramsey space in this framework corresponds an associated ultrafilter satisfying some weak partition property. By using the correct Fraïssé classes, we construct topological Ramsey spaces which are dense in the partial orders of Baumgartner and Taylor generating p-points which are k-arrow but not \-arrow, and in a partial order of Blass producing a diamond shape in the Rudin-Keisler structure of p-points. Any space in our framework in which blocks are products of n many structures produces ultrafilters with initial Tukey structure exactly the Boolean algebra \\). If the number of Fraïssé classes on each block grows without bound, then the Tukey types of the p-points below the space’s associated ultrafilter have the structure exactly \. In contrast, the set of isomorphism types of any product of finitely many Fraïssé classes of finite relational structures satisfying the Ramsey property and the OPFAP, partially ordered by embedding, is realized as the initial Rudin-Keisler structure of some p-point generated by a space constructed from our template. (shrink)

When the Canonical Ramsey’s Theorem by Erdős and Rado is applied to regressive functions, one obtains the Regressive Ramsey’s Theorem by Kanamori and McAloon. Taylor proved a “canonical” version of Hindman’s Theorem, analogous to the Canonical Ramsey’s Theorem. We introduce the restriction of Taylor’s Canonical Hindman’s Theorem to a subclass of the regressive functions, the $$\lambda $$ λ -regressive functions, relative to an adequate version of min-homogeneity and prove some results about the Reverse Mathematics of (...) this Regressive Hindman’s Theorem and of natural restrictions of it. In particular we prove that the first non-trivial restriction of the principle is equivalent to Arithmetical Comprehension. We furthermore prove that the well-ordering-preservation principle for base-$$\omega $$ ω exponentiation is reducible to this same principle by a uniform computable reduction. (shrink)