Proceedings of the American Mathematical Society · 2014 · 28 citations · 16 references
Natural SciencesMathematicsDiscrete MathematicsSet TheoryTopologyAxiomatic Set TheoryRamsey TheoryRamsey PropertyRamsey's TheoremReductions
An open question in reverse mathematics is whether the cohesive principle, $\mathsf {COH}$, is implied by the stable form of Ramseyâs theorem for pairs, $\mathsf {SRT}^2_2$, in $\omega$-models of $\mathsf {RCA}_0$. One typical way of establishing this implication would be to show that for every sequence $\vec {R}$ of subsets of $\omega$, there is a set $A$ that is $\Delta ^0_2$ in $\vec {R}$ such that every infinite subset of $A$ or $\overline {A}$ computes an $\vec {R}$-cohesive set. In this article, this is shown to be false, even under far less stringent assumptions: for all natural numbers $n \geq 2$ and $m < 2^n$, there is a sequence $\vec {R} = \langle {R_0,\ldots ,R_{n-1}}\rangle$ of subsets of $\omega$ such that for any partition $A_0,\ldots ,A_{m-1}$ of $\omega$ hyperarithmetical in $\vec {R}$, there is an infinite subset of some $A_j$ that computes no set cohesive for $\vec {R}$. This complements a number of previous results in computability theory on the computational feebleness of infinite sets of numbers with prescribed combinatorial properties. The proof is a forcing argument using an adaptation of the method of Seetapun showing that every finite coloring of pairs of integers has an infinite homogeneous set not computing a given non-computable set.
16
Recursively enumerable sets and degrees
Robert I. Soare · Bulletin of the American Mathematical Society · 1978 · 1.6K citations · Full text
On the strength of Ramsey's theorem for pairs
Peter Cholak, Carl G. Jockusch, Theodore A. Slaman · Journal of Symbolic Logic · 2001 · 210 citations
On the Strength of Ramsey's Theorem
David Seetapun, Theodore A. Slaman · Notre Dame Journal of Formal Logic · 1995 · 117 citations · Full text