2012/12/04 by Damir D. Dzhafarov, Dzhafarov, Damir D.
Computer Science · Mathematics · #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.1212.0828
openalex publication_date 2012/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An open question in reverse mathematics is whether the cohesive principle, \COH, is implied by the stable form of Ramsey's theorem for pairs, \SRT22, in ω-models of \RCA. One typical way of establishing this implication would be to show that for every sequence R of subsets of ω, there is a set A that is Δ02 in R such that every infinite subset of A or A computes an R-cohesive set. In this article, this is shown to be false, even under far less stringent assumptions: for all natural numbers n ≥ 2 and m < 2n, there is a sequence R = \sequenceR0,...,Rn-1 of subsets of ω such that for any partition A0,...,Am-1 of ω arithmetical in R, there is an infinite subset of some Aj that computes no set cohesive for 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.