Ramsey-like theorems and moduli of computation

DOI10.1017/JSL.2020.69zbMATH Open1505.03028arXiv1901.04388OpenAlexW3098647228MaRDI QIDQ5070463FDOQ5070463

Authors: Ludovic Patey 

Publication date: 12 April 2022

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

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.

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

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

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)

Cites Work

• Subsystems of second order arithmetic
• 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}\)
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Ramsey's theorem and recursion theory
• Bounding prime models
• On the strength of Ramsey's theorem
• Title not available (Why is that?)
• The strength of the rainbow Ramsey Theorem
• Title not available (Why is that?)
• Some logically weak Ramseyan theorems
• Partition Theorems and Computability Theory
• On uniform relationships between combinatorial problems
• On notions of computability-theoretic reduction between Π21 principles
• Iterative forcing and hyperimmunity in reverse mathematics
• Ramsey's theorem and cone avoidance
• Hyperarithmetically Encodable Sets
• Reverse mathematics, computability, and partitions of trees
• Coloring trees in reverse mathematics
• Thin set theorems and cone avoidance
• Pigeons do not jump high
• Iterative forcing and hyperimmunity in reverse mathematics
• Open questions about Ramsey-type statements in reverse mathematics

Cited In (12)

• 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
• Co-Nondeterminism in Compositions

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)