Ramsey-like theorems and moduli of computation

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

Abstract

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,283

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.

Analytics

Added to PP
2020-10-28

Downloads
10 (#1,199,114)

6 months
3 (#984,114)

Historical graph of downloads
How can I increase my downloads?