We prove the following result: there is a family of subsets of ω such that for every stable coloring hyperarithmetical in R and every finite collection of Turing functionals, there is an infinite homogeneous set H for c such that none of the finitely many functionals map to an infinite cohesive set for R. This provides a partial answer to a question in computable combinatorics, whether is omnisciently computably reducible to .
V.Brattka, G.Gherardi and A.Pauly, Weihrauch complexity in computable analysis. to appear.
2.
V.Brattka and T.Rakotoniaina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic82(4) (2017), 1278–1316. doi:10.1017/jsl.2017.43.
3.
P.Cholak, D.D.Dzhafarov, D.R.Hirschfeldt and L.Patey, Some results concerning the vs. problem, submitted.
4.
P.A.Cholak, C.G.Jockusch and T.A.Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic66(1) (2001), 1–55. doi:10.2307/2694910.
5.
C.T.Chong, S.Lempp and Y.Yang, On the role of the collection principle for -formulas in second-order reverse mathematics, Proc. Amer. Math. Soc.138(3) (2010), 1093–1100. doi:10.1090/S0002-9939-09-10115-6.
6.
Denis and R.Hirschfeldt, Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific Publishing Company Incorporated, 2014.
7.
F.G.Dorais, D.D.Dzhafarov, J.L.Hirst, J.R.Mileti and P.Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc.368(2) (2016), 1321–1359. doi:10.1090/tran/6465.
8.
D.D.Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc.143(2) (2015), 869–876. doi:10.1090/S0002-9939-2014-12261-1.
9.
D.D.Dzhafarov, Strong reductions between combinatorial principles, J. Symbolic Logic81(4) (2016), 1405–1431. doi:10.1017/jsl.2016.1.
10.
D.D.Dzhafarov, J.Le Goh, D.R.Hirschfeldt, L.Patey and A.Pauly, Ramsey’s theorem and products in the Weihrauch degrees, Computability, to appear.
11.
D.D.Dzhafarov, L.Patey, R.Solomon and L.Brown Westrick, Ramsey’s theorem for singletons and strong computable reducibility, Proc. Amer. Math. Soc.145(3) (2017), 1343–1355. doi:10.1090/proc/13315.
12.
D.R.Hirschfeldt and C.G.JockuschJr., On notions of computability-theoretic reduction between principles, J. Math. Log.16(1) (2016), 1650002. doi:10.1142/S0219061316500021.
13.
J.L.Hirst and C.Mummert, Using Ramsey’s theorem once, to appear.
14.
B.Monin and L.Patey, encodability and omniscient reductions, Notre Dame Journal of Formal Logic, to appear.
15.
B.Monin and L.Patey, does not imply in ω-models, to appear.
16.
L.Patey, Partial orders and immunity in reverse mathematics, in: Pursuit of the Universal, Lecture Notes in Comput. Sci., Vol. 9709, Springer, Cham, 2016, pp. 353–363. doi:10.1007/978-3-319-40189-8_36.
17.
L.Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math.216(2) (2016), 905–955. doi:10.1007/s11856-016-1433-3.
