Ramsey-like theorems and moduli of computation

DOI10.1017/JSL.2020.69MaRDI QIDQ5070463zbMATH OpenOpenAlexFDO

Authors Ludovic Patey

Publication date 12 April 2022

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

computability theoryreverse mathematicsmodulusRamsey's theory

Mathematics Subject Classification ID

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)

Abstract: Ramsey's theorem asserts that every $k$-coloring of $[omega{]}^n$ admits an infinite monochromatic set. Whenever $ngeq3$, there exists a computable $k$-coloring of $[omega{]}^n$ whose solutions compute the halting set. On the other hand, for every computable $k$-coloring of $[omega{]}^2$ and every non-computable set $C$, there is an infinite monochromatic set $H$ such that $Cotle{q}_{T}H$. The latter property is known as cone avoidance. In this article, we design a natural class of Ramsey-like theorems encompassing many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every $k$-coloring of $[omega{]}^n$, of an infinite subdomain $Hsubseteqomega$ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions.

Recommendations

• Ramsey's theorem and cone avoidance
• Effective versions of Ramsey's Theorem: Avoiding the cone above 0′
• Some logically weak Ramseyan theorems
• Thin set theorems and cone avoidance
• A packed Ramsey’s theorem and computability theory

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)
• Bounding prime models
• Coloring trees in reverse mathematics
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Hyperarithmetically Encodable Sets
• Iterative forcing and hyperimmunity in reverse mathematics
• Iterative forcing and hyperimmunity in reverse mathematics
• On notions of computability-theoretic reduction between Π21 principles
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• On uniform relationships between combinatorial problems
• Open questions about Ramsey-type statements in reverse mathematics
• Partition Theorems and Computability Theory
• Pigeons do not jump high
• Ramsey's theorem and cone avoidance
• Ramsey's theorem and recursion theory
• Reverse mathematics, computability, and partitions of trees
• Some logically weak Ramseyan theorems
• Subsystems of second order arithmetic
• The strength of infinitary Ramseyan principles can be accessed by their densities
• The strength of the rainbow Ramsey Theorem
• Thin set theorems and cone avoidance
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)

Cited in

(12)

• Co-Nondeterminism in Compositions
• Relationships between computability-theoretic properties of problems
• Lawvere-Tierney topologies for computability theorists
• On the combination of the Bernays-Schönfinkel-Ramsey fragment with simple linear integer arithmetic
• A recursion theoretic analysis of the clopen Ramsey theorem
• Effective versions of Ramsey's Theorem: Avoiding the cone above 0′
• Thin set theorems and cone avoidance
• Ramsey's theorem and cone avoidance
• A packed Ramsey’s theorem and computability theory
• Erdős-Moser and \(I \Sigma_2\)
• The reverse mathematics of \textsf{CAC for trees}
• The canonical Ramsey theorem and computability theory

This page was built for publication: Ramsey-like theorems and moduli of computation

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