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.

MSC (2010):
Primary 03D80, 03F35, 05D10

Published electronically:
September 15, 2016

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We answer a question posed by Hirschfeldt and Jockusch by showing that whenever , Ramsey's theorem for singletons and -colorings, , is not strongly computably reducible to the stable Ramsey's theorem for -colorings, . Our proof actually establishes the following considerably stronger fact: given , there is a coloring such that for every stable coloring (computable from or not), there is an infinite homogeneous set for that computes no infinite homogeneous set for . This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, , is not strongly computably reducible to the stable Ramsey's theorem for all colorings, . The latter is the strongest partial result to date in the direction of giving a negative answer to the longstanding open question of whether is implied by the stable Ramsey's theorem in -models of .

- [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**, 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**, 10.2307/2694910**[6]**C. T. Chong, Steffen Lempp, and Yue Yang,*On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics*, Proc. Amer. Math. Soc.**138**(2010), no. 3, 1093–1100. MR**2566574**, 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**, 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**, 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 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**, 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**, 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**, 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**, 10.1090/S0002-9947-1978-0491103-7- [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.

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