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 investigate the notion of a semi-retraction between two first-order structures (in typically different signatures) that was introduced by the second author as a link between the Ramsey property and generalized indiscernible sequences. We look at semi-retractions through a new lens establishing transfers of the Ramsey property and finite Ramsey degrees under quite general conditions that are optimal as demonstrated by counterexamples. Finally, we compare semi-retractions to the category theoretic notion of a pre-adjunction.

We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ (...) over $\mathsf {RCA}_0$. For each fixed $k \geq 3$, the Rival–Sands theorem for infinite partial orders of width $\leq \!k$ is equivalent to $\mathsf {ADS}$ over $\mathsf {RCA}_0$. The Rival–Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $\mathsf {SADS}$ over $\mathsf {RCA}_0$. Here $\mathsf {RCA}_0$ denotes the recursive comprehension axiomatic system, $\mathsf {I}\Sigma ^0_{2}$ denotes the $\Sigma ^0_2$ induction scheme, $\mathsf {ADS}$ denotes the ascending/descending sequence principle, and $\mathsf {SADS}$ denotes the stable ascending/descending sequence principle. To the best of our knowledge, these versions of the Rival–Sands theorem for partial orders are the first examples of theorems from the general mathematics literature whose strength is exactly characterized by $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$, by $\mathsf {ADS}$, and by $\mathsf {SADS}$. Furthermore, we give a new purely combinatorial result by extending the Rival–Sands theorem to infinite partial orders that do not have infinite antichains, and we show that this extension is equivalent to arithmetical comprehension over $\mathsf {RCA}_0$. (shrink)

Ramsey algebras are an attempt to investigate Ramsey spaces generated by algebras in a purely combinatorial fashion. Previous studies have focused on the basic properties of Ramsey algebras and a few specific examples. In this article, we study the properties of Ramsey algebras from a structural point of view. For instance, we will see that isomorphic algebras have the same Ramsey algebraic properties, but elementarily equivalent algebras need not be so, as expected. We also answer an open question about Cartesian (...) products of Ramsey algebras. (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)

Henle, Mathias, and Woodin proved in [21] that, provided that${\omega }{\rightarrow }({\omega })^{{\omega }}$holds in a modelMof ZF, then forcing with$([{\omega }]^{{\omega }},{\subseteq }^*)$overMadds no new sets of ordinals, thus earning the name a “barren” extension. Moreover, under an additional assumption, they proved that this generic extension preserves all strong partition cardinals. This forcing thus produces a model$M[\mathcal {U}]$, where$\mathcal {U}$is a Ramsey ultrafilter, with many properties of the original modelM. This begged the question of how important the Ramseyness of$\mathcal (...) {U}$is for these results. In this paper, we show that several classes of$\sigma $-closed forcings which generate non-Ramsey ultrafilters have the same properties. Such ultrafilters include Milliken–Taylor ultrafilters, a class of rapid p-points of Laflamme,k-arrow p-points of Baumgartner and Taylor, and extensions to a class of ultrafilters constructed by Dobrinen, Mijares, and Trujillo. Furthermore, the class of Boolean algebras$\mathcal {P}({\omega }^{{\alpha }})/{\mathrm {Fin}}^{\otimes {\alpha }}$,$2\le {\alpha }<{\omega }_1$, forcing non-p-points also produce barren extensions. (shrink)

We investigate Maker–Breaker games on graphs of size $\aleph _1$ in which Maker’s goal is to build a copy of the host graph. We establish a firm dependence of the outcome of the game on the axiomatic framework. Relating to this, we prove that there is a winning strategy for Maker in the $K_{\omega,\omega _1}$ -game under ZFC+MA+ $\neg $ CH and a winning strategy for Breaker under ZFC+CH. We prove a similar result for the $K_{\omega _1}$ -game. Here, Maker (...) has a winning strategy under ZF+DC+AD, while Breaker has one under ZFC+CH again. (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)