The weakness of being cohesive, thin or free in reverse mathematics

DOI10.1007/S11856-016-1433-3MaRDI QIDQ503277zbMATH OpenOpenAlexFDO

Authors Ludovic Patey

Publication date 11 January 2017

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

stablereverse mathematicsMathias forcingRamseythin setfree setCOHcohesive setsSRTSTS

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: Informally, a mathematical statement is robust if its strength is left unchanged under variations of the statement. In this paper, we investigate the lack of robustness of Ramsey's theorem and its consequence under the frameworks of reverse mathematics and computable reducibility. To this end, we study the degrees of unsolvability of cohesive sets for different uniformly computable sequence of sets and identify different layers of unsolvability. This analysis enables us to answer some questions of Wang about how typical sets help computing cohesive sets. We also study the impact of the number of colors in the computable reducibility between coloring statements. In particular, we strengthen the proof by Dzhafarov that cohesiveness does not strongly reduce to stable Ramsey's theorem for pairs, revealing the combinatorial nature of this non-reducibility and prove that whenever $k$ is greater than $ell$, stable Ramsey's theorem for $n$-tuples and $k$ colors is not computably reducible to Ramsey's theorem for $n$-tuples and $ell$ colors. In this sense, Ramsey's theorem is not robust with respect to his number of colors over computable reducibility. Finally, we separate the thin set and free set theorem from Ramsey's theorem for pairs and identify an infinite decreasing hierarchy of thin set theorems in reverse mathematics. This shows that in reverse mathematics, the strength of Ramsey's theorem is very sensitive to the number of colors in the output set. In particular, it enables us to answer several related questions asked by Cholak, Giusto, Hirst and Jockusch.

Recommendations

• Ramsey's theorem for singletons and strong computable reducibility
• Cohesive avoidance and strong reductions
• Some logically weak Ramseyan theorems
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• On the strength of Ramsey's theorem for pairs

Cites work

• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 5064956 (Why is no real title available?)
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)
• Π₀¹-classes and Rado's selection principle
• A cohesive set which is not high
• A criterion for completeness of degrees of unsolvability
• Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
• An extension of the recursively enumerable Turing degrees
• An improved zero-one law for algorithmically random sequences
• Cohesive avoidance and strong reductions
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Controlling iterated jumps of solutions to combinatorial problems
• Degrees bounding principles and universal instances in reverse mathematics
• Forcing with bushy trees
• Infinite subsets of random sets of integers
• Iterative forcing and hyperimmunity in reverse mathematics
• Lowness for Kurtz randomness
• Omitting cohesive sets
• On degrees of unsolvability
• On notions of computability-theoretic reduction between Π21 principles
• 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 uniform computational content of Ramsey's theorem
• On uniform relationships between combinatorial problems
• Open questions in reverse mathematics
• Partition Theorems and Computability Theory
• Ramsey's theorem and recursion theory
• Separating principles below Ramsey's theorem for pairs
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• Some logically weak Ramseyan theorems
• Strong reductions between combinatorial principles
• Subsystems of second order arithmetic
• The Degrees of Hyperimmune Sets
• The axiomatization of randomness
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• The strength of infinitary Ramseyan principles can be accessed by their densities
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(30)

• Some logically weak Ramseyan theorems
• Iterative forcing and hyperimmunity in reverse mathematics
• Relationships between computability-theoretic properties of problems
• On notions of computability-theoretic reduction between Π21 principles
• Algebraic properties of the first-order part of a problem
• The uniform content of partial and linear orders
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)
• More automorphism groups of countable, arithmetically saturated models of Peano arithmetic
• Using Ramsey's theorem once
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Pigeons do not jump high
• Reduction games, provability and compactness
• Partial orders and immunity in reverse mathematics
• Some Questions in Computable Mathematics
• On the logical strengths of partial solutions to mathematical problems
• Cohesive sets and rainbows
• Computable reductions and reverse mathematics
• Constructing sequences one step at a time
• Thin set theorems and cone avoidance
• Ramsey's theorem for singletons and strong computable reducibility
• Strong reductions between combinatorial principles
• THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Dominating the Erdős-Moser theorem in reverse mathematics
• COH, SRT 2 2 , and multiple functionals
• On the uniform computational content of Ramsey's theorem
• Controlling iterated jumps of solutions to combinatorial problems
• Weihrauch Complexity in Computable Analysis
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• Open questions about Ramsey-type statements in reverse mathematics

This page was built for publication: The weakness of being cohesive, thin or free in reverse mathematics

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