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?)

  • [1] Vasco Brattka, Bibliography on Weihrauch complexity, website: http://cca-net.de/publications/weibib.php
  • [2] Vasco Brattka and Tahina Rakotoniaina, On the uniform computational content of Ramsey's theorem, to appear.
  • [3] Peter A. Cholak, Damir D. Dzhafarov, Jeffry L. Hirst, and Theodore A. Slaman, Generics for computable Mathias forcing, Ann. Pure Appl. Logic 165 (2014), no. 9, 1418-1428. MR 3210076, https://doi.org/10.1016/j.apal.2014.04.011
  • [4] Peter A. Cholak, Damir D. Dzhafarov, and Mariya I. Soskova, Generics for Mathias forcing over general Turing ideals, Israel J. Math., to appear.
  • [5] Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey's theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1-55. MR 1825173, https://doi.org/10.2307/2694910
  • [6] C. T. Chong, Steffen Lempp, and Yue Yang, On the role of the collection principle for $ \Sigma ^0_2$-formulas in second-order reverse mathematics, Proc. Amer. Math. Soc. 138 (2010), no. 3, 1093-1100. MR 2566574, https://doi.org/10.1090/S0002-9939-09-10115-6
  • [7] François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc. 368 (2016), no. 2, 1321-1359. MR 3430365, https://doi.org/10.1090/tran/6465
  • [8] Damir D. Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143 (2015), no. 2, 869-876. MR 3283673, https://doi.org/10.1090/S0002-9939-2014-12261-1
  • [9] Damir D. Dzhafarov, Strong reductions between combinatorial principles, J. Symbolic Logic, to appear.
  • [10] Marcia J. Groszek and Theodore A. Slaman, Moduli of computation, in preparation.
  • [11] Denis R. Hirschfeldt, Slicing the truth, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. On the computable and reverse mathematics of combinatorial principles; Edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin and Yue Yang. MR 3244278
  • [12] Denis R. Hirschfeldt and Carl G. Jockusch, Jr., On notions of computability theoretic reduction between $ \Pi ^1_2$ principles, to appear.
  • [13] Denis R. Hirschfeldt and Richard A. Shore, Combinatorial principles weaker than Ramsey's theorem for pairs, J. Symbolic Logic 72 (2007), no. 1, 171-206. MR 2298478, https://doi.org/10.2178/jsl/1174668391
  • [14] Jeffry Lynn Hirst, COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)-The Pennsylvania State University. MR 2635978
  • [15] Carl Jockusch and Frank Stephan, A cohesive set which is not high, Math. Logic Quart. 39 (1993), no. 4, 515-530. MR 1270396, https://doi.org/10.1002/malq.19930390153
  • [16] Manuel Lerman, Reed Solomon, and Henry Towsner, Separating principles below Ramsey's theorem for pairs, J. Math. Log. 13 (2013), no. 2, 1350007, 44. MR 3125903
  • [17] Joseph Roy Mileti, Partition theorems and computability theory, ProQuest LLC, Ann Arbor, MI, 2004. Thesis (Ph.D.)-University of Illinois at Urbana-Champaign. MR 2706695
  • [18] Ludovic Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math., to appear.
  • [19] Tahina Rakotoniaina, The Computational Strength of Ramsey's Theorem, PhD thesis, University of Cape Town, 2015.
  • [20] Richard A. Shore, The Turing degrees: an introduction, Forcing, iterated ultrapowers, and Turing degrees, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 29, World Sci. Publ., Hackensack, NJ, 2016, pp. 39-121. MR 3411034, https://doi.org/10.1142/9789814699952_0002
  • [21] Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689
  • [22] Theodore A. Slaman and Yue Yang, The metamathematics of stable Ramsey's theorem for pairs, to appear.
  • [23] Robert I. Soare, Computability theory and applications, Theory and Applications of Computability. Springer, New York, to appear.
  • [24] Robert M. Solovay, Hyperarithmetically encodable sets, Trans. Amer. Math. Soc. 239 (1978), 99-122. MR 0491103
  • [25] K. Weihrauch, The degrees of discontinuity of some translators between representations of the real numbers, Technical report TR-92-050, International Computer Science Institute, Berkeley, 1992.

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

American Mathematical Society