We study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive (respectively, n-r-cohesive) if A is almost homogeneous for every computably enumerable (respectively, computable) 2-coloring of the n-element sets of natural numbers. (Thus the 1-cohesive and 1-r-cohesive sets coincide with the cohesive and r-cohesive sets, respectively.) We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show (...) that for all n ≥ 2, there exists a Δ 0 n+1 n-cohesive set. We improve this result for n = 2 by showing that there is a Π 0 2 2-cohesive set. We show that the n-cohesive and n-r-cohesive degrees together form a linear, non-collapsing hierarchy of degrees for n ≥ 2. In addition, for n ≥ 2 we characterize the jumps of n-cohesive degrees as exactly the degrees ≥ 0 (n+1) and also characterize the jumps of the n-r-cohesive degrees. (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 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 examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.

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 study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive if A is almost homogeneous for every computably enumerable 2-coloring of the n-element sets of natural numbers. We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show that for all $n \geq 2$, there exists a $\Delta^0_{n+1}$ n-cohesive set. We improve this result for n (...) = 2 by showing that there is a $\Pi^0_2$ 2-cohesive set. We show that the n-cohesive and n-r-cohesive degrees together form a linear, non-collapsing hierarchy of degrees for $n \geq 2$. In addition, for $n \geq 2$ we characterize the jumps of n-cohesive degrees as exactly the degrees $\geq 0^{}$ and also characterize the jumps of the n-r-cohesive degrees. (shrink)

We study the proof–theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RTkndenote Ramsey's theorem fork–colorings ofn–element sets, and let RT<∞ndenote (∀k)RTkn. Our main result on computability is: For anyn≥ 2 and any computable (recursive)k–coloring of then–element sets of natural numbers, there is an infinite homogeneous setXwithX″ ≤T0(n). LetIΣnandBΣndenote the Σninduction and bounding schemes, respectively. Adapting the casen= 2 of the above result (whereXis low2) to models of arithmetic enables us to show that RCA0+IΣ2+ (...) RT22is conservative over RCA0+IΣ2for Π11statements and that RCA0+IΣ3+ RT<∞2is Π11-conservative over RCA0+IΣ3. It follows that RCA0+ RT22does not implyBΣ3. In contrast, J. Hirst showed that RCA0+ RT<∞2does implyBΣ3, and we include a proof of a slightly strengthened version of this result. It follows that RT<∞2is strictly stronger than RT22overRCA0. (shrink)

Stephen George Simpson. with definition 1.2.3 and the discussion following it. For example, taking 90(n) to be the formula n §E Y, we have an instance of comprehension, VYEIXVn(n€X<—>n¢Y), asserting that for any given set Y there exists a ...