Ramsey’s theorem for singletons and strong computable reducibility
HTML articles powered by AMS MathViewer
- by Damir D. Dzhafarov, Ludovic Patey, Reed Solomon and Linda Brown Westrick PDF
- Proc. Amer. Math. Soc. 145 (2017), 1343-1355 Request permission
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
- Vasco Brattka, Bibliography on Weihrauch complexity, website: http://cca-net.de/publications/weibib.php
- Vasco Brattka and Tahina Rakotoniaina, On the uniform computational content of Ramsey’s theorem, to appear.
- 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, DOI 10.1016/j.apal.2014.04.011
- Peter A. Cholak, Damir D. Dzhafarov, and Mariya I. Soskova, Generics for Mathias forcing over general Turing ideals, Israel J. Math., to appear.
- 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, DOI 10.2307/2694910
- 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, DOI 10.1090/S0002-9939-09-10115-6
- 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, DOI 10.1090/tran/6465
- Damir D. Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143 (2015), no. 2, 869–876. MR 3283673, DOI 10.1090/S0002-9939-2014-12261-1
- Damir D. Dzhafarov, Strong reductions between combinatorial principles, J. Symbolic Logic, to appear.
- Marcia J. Groszek and Theodore A. Slaman, Moduli of computation, in preparation.
- 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
- Denis R. Hirschfeldt and Carl G. Jockusch, Jr., On notions of computability theoretic reduction between $\Pi ^1_2$ principles, to appear.
- 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, DOI 10.2178/jsl/1174668391
- 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
- Carl Jockusch and Frank Stephan, A cohesive set which is not high, Math. Logic Quart. 39 (1993), no. 4, 515–530. MR 1270396, DOI 10.1002/malq.19930390153
- 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, DOI 10.1142/S0219061313500074
- 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
- Ludovic Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math., to appear.
- Tahina Rakotoniaina, The Computational Strength of Ramsey’s Theorem, PhD thesis, University of Cape Town, 2015.
- 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, DOI 10.1142/9789814699952_{0}002
- 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, DOI 10.1017/CBO9780511581007
- Theodore A. Slaman and Yue Yang, The metamathematics of stable Ramsey’s theorem for pairs, to appear.
- Robert I. Soare, Computability theory and applications, Theory and Applications of Computability. Springer, New York, to appear.
- Robert M. Solovay, Hyperarithmetically encodable sets, Trans. Amer. Math. Soc. 239 (1978), 99–122. MR 491103, DOI 10.1090/S0002-9947-1978-0491103-7
- 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.
Additional Information
- Damir D. Dzhafarov
- Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
- MR Author ID: 781680
- ORCID: 0000-0003-4921-7561
- Email: damir@math.uconn.edu
- Ludovic Patey
- Affiliation: Laboratoire PPS, Universite Paris Diderot, Paris, France
- MR Author ID: 1102703
- ORCID: 0000-0002-0304-7926
- Email: ludovic.patey@computability.fr
- Reed Solomon
- Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
- MR Author ID: 646849
- Email: david.solomon@uconn.edu
- Linda Brown Westrick
- Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269
- Email: linda.westrick@uconn.edu
- 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
- © Copyright 2016 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 1343-1355
- MSC (2010): Primary 03D80, 03F35, 05D10
- DOI: https://doi.org/10.1090/proc/13315
- MathSciNet review: 3589330