Journal of Symbolic Logic 87 (1):72-108 (2022)

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$, 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 noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _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 $H \subseteq \omega $ 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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2020.69
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,564
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Nonstandard Combinatorics.Joram Hirshfeld - 1988 - Studia Logica 47 (3):221 - 232.
Phase Transition Results for Three Ramsey-Like Theorems.Florian Pelupessy - 2016 - Notre Dame Journal of Formal Logic 57 (2):195-207.
Selective and Ramsey Ultrafilters on G-Spaces.Oleksandr Petrenko & Igor Protasov - 2017 - Notre Dame Journal of Formal Logic 58 (3):453-459.


Added to PP index

Total views
3 ( #1,366,937 of 2,533,568 )

Recent downloads (6 months)
1 ( #390,861 of 2,533,568 )

How can I increase my downloads?


My notes