Cohesive avoidance and strong reductions

DOI10.1090/S0002-9939-2014-12261-1MaRDI QIDQ5496327zbMATH OpenFDO

Authors Damir D. Dzhafarov

Publication date 30 January 2015

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.0828

zbMATH Keywords

cohesive principleRamsey's theorem for pairsreverse mathematics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Ramsey theory (05D10)

Abstract: An open question in reverse mathematics is whether the cohesive principle, $COH$, is implied by the stable form of Ramsey's theorem for pairs, $SR{T}_2^2$, in $omega$-models of $RCA$. One typical way of establishing this implication would be to show that for every sequence $vecR$ of subsets of $omega$, there is a set $A$ that is $Delt{a}_2^0$ in $vecR$ such that every infinite subset of $A$ or $$ computes an $vecR$-cohesive set. In this article, this is shown to be false, even under far less stringent assumptions: for all natural numbers $ngeq2$ and $m<2^n$, there is a sequence $vecR=sequence{R}_0,\mathrm{...},R_{n-1}$ of subsets of $omega$ such that for any partition $A_0,\mathrm{...},A_{m-1}$ of $omega$ arithmetical in $vecR$, there is an infinite subset of some $A_j$ that computes no set cohesive for $vecR$. 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.

Recommendations

• Reduction and minimality of coexhausters
• Coherence and compatibility: a stronger approach
• Reducibility and nonbinding
• scientific article; zbMATH DE number 3851045
• scientific article; zbMATH DE number 1531931
• Robust reductions
• scientific article; zbMATH DE number 1222831
• Strong Positive Reducibilities
• Reduction Strategies and Acyclicity
• Strong reductions between combinatorial principles

Cites work

• A cohesive set which is not high
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Generalized cohesiveness
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• Infinite subsets of random sets of integers
• Jump equivalence of the Δ₂⁰ hyperimmune sets
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• On the strength of the finite intersection principle
• Ramsey's theorem and cone avoidance
• Recursion theory week. Proceedings of a conference held in Oberwolfach, Germany, March 19-25, 1989
• Rigidity and biinterpretability in the hyperdegrees
• Sets with no subset of higher degree
• Subsystems of second order arithmetic
• The atomic model theorem and type omitting
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• Upward closure and cohesive degrees

Cited in

(24)

• Embeddings between well-orderings: computability-theoretic reductions
• New bounds on the strength of some restrictions of Hindman's theorem
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• The uniform content of partial and linear orders
• A _2⁰ set with no infinite low subset in either it or its complement
• On uniform relationships between combinatorial problems
• Omitting cohesive sets
• Ramsey's theorem for singletons and strong computable reducibility
• Controlling iterated jumps of solutions to combinatorial problems
• Borel-piecewise continuous reducibility for uniformization problems
• The strength of the tree theorem for pairs in reverse mathematics
• Nonstandard methods in Ramsey's theorem for pairs
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Cohesive sets and rainbows
• On the uniform computational content of Ramsey's theorem
• COH, SRT 2 2 , and multiple functionals
• Weihrauch Complexity in Computable Analysis
• The weakness of being cohesive, thin or free in reverse mathematics
• Reduction games, provability and compactness
• Some results concerning the \(\mathsf{SRT}_2^2\) vs. \(\mathsf{COH}\) problem
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Notions of robust information coding
• Open questions about Ramsey-type statements in reverse mathematics
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective

This page was built for publication: Cohesive avoidance and strong reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496327)