Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

Ramsey's theorem for singletons and strong computable reducibility


Authors: Damir D. Dzhafarov, Ludovic Patey, Reed Solomon and Linda Brown Westrick
Journal: Proc. Amer. Math. Soc. 145 (2017), 1343-1355
MSC (2010): Primary 03D80, 03F35, 05D10
DOI: https://doi.org/10.1090/proc/13315
Published electronically: September 15, 2016
MathSciNet review: 3589330
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We answer a question posed by Hirschfeldt and Jockusch by showing that whenever $ k > \ell $, Ramsey's theorem for singletons and $ k$-colorings, $ \mathsf {RT}^1_k$, is not strongly computably reducible to the stable Ramsey's theorem for $ \ell $-colorings, $ \mathsf {SRT}^2_\ell $. Our proof actually establishes the following considerably stronger fact: given $ k > \ell $, there is a coloring $ c : \omega \to k$ such that for every stable coloring $ d : [\omega ]^2 \to \ell $ (computable from $ c$ or not), there is an infinite homogeneous set $ H$ for $ d$ that computes no infinite homogeneous set for $ c$. This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, $ \mathsf {COH}$, is not strongly computably reducible to the stable Ramsey's theorem for all colorings, $ \mathsf {SRT}^2_{<\infty }$. The latter is the strongest partial result to date in the direction of giving a negative answer to the longstanding open question of whether $ \mathsf {COH}$ is implied by the stable Ramsey's theorem in $ \omega $-models of $ \mathsf {RCA}_0$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D80, 03F35, 05D10

Retrieve articles in all journals with MSC (2010): 03D80, 03F35, 05D10


Additional Information

Damir D. Dzhafarov
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
Email: damir@math.uconn.edu

Ludovic Patey
Affiliation: Laboratoire PPS, Universite Paris Diderot, Paris, France
Email: ludovic.patey@computability.fr

Reed Solomon
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
Email: david.solomon@uconn.edu

Linda Brown Westrick
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
Email: linda.westrick@uconn.edu

DOI: https://doi.org/10.1090/proc/13315
Received by editor(s): February 13, 2016
Received by editor(s) in revised form: March 28, 2016, April 25, 2016, and May 11, 2016
Published electronically: September 15, 2016
Additional Notes: The first author was partially supported by NSF grant DMS-1400267
The second author was funded by the John Templeton Foundation (‘Structure and Randomness in the Theory of Computation’ project)
The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation. The authors are grateful to the anonymous referee for a number of helpful comments and suggestions
Communicated by: Mirna Džamonja
Article copyright: © Copyright 2016 American Mathematical Society