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

DOI10.1007/S11856-016-1433-3zbMATH Open1368.03018arXiv1502.03709OpenAlexW2962720709MaRDI QIDQ503277FDOQ503277

Authors: Ludovic Patey 

Publication date: 11 January 2017

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

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.

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

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

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)

Cites Work

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

Cited In (30)

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

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)