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)

• On the logical strengths of partial solutions to mathematical problems
• Relationships between computability-theoretic properties of problems
• Strong reductions between combinatorial principles
• Using Ramsey's theorem once
• On the uniform computational content of Ramsey's theorem
• Some Questions in Computable Mathematics
• Some logically weak Ramseyan theorems
• The uniform content of partial and linear orders
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Algebraic properties of the first-order part of a problem
• COH, SRT 2 2 , and multiple functionals
• Controlling iterated jumps of solutions to combinatorial problems
• Thin set theorems and cone avoidance
• Partial orders and immunity in reverse mathematics
• On notions of computability-theoretic reduction between Π21 principles
• Dominating the Erdős-Moser theorem in reverse mathematics
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• 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
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)
• 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)