We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey’s theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey’s theorem for pairs () is Weihrauch-incomparable to the parallel product of the stable Ramsey’s theorem for pairs and the cohesive principle ().
E.P.Astor, D.D.Dzhafarov, R.Solomon and J.Suggs, The uniform content of partial and linear orders, Ann. Pure Appl. Logic168(6) (2017), 1153–1171. doi:10.1016/j.apal.2016.11.010.
2.
V.Brattka, Bibliography on Weihrauch complexity, http://cca-net.de/publications/weibib.php.
3.
V.Brattka, G.Gherardi and A.Marcone, The Bolzano–Weierstrass theorem is the jump of weak Kőnig’s lemma, Ann. Pure Appl. Logic163(6) (2012), 623–655. doi:10.1016/j.apal.2011.10.006.
4.
V.Brattka, G.Gherardi and A.Pauly, Weihrauch complexity in computable analysis, To appear, arXiv:1707.03202.
5.
V.Brattka, M.Hendtlass and A.Kreuzer, On the uniform computational content of computability theory, Theory of Computing Systems61(4) (2017). doi:10.1007/s00224-017-9798-1.
6.
V.Brattka, R.Hölzl and R.Kuyper. Monte Carlo computability, in: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Dagstuhl, Germany, H.Vollmer and B.Vallée, eds, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 66, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017, pp. 17:1–17:14.
7.
V.Brattka, A.Kawamura, A.Marcone and A.Pauly, Measuring the complexity of computational content (Dagstuhl Seminar 15392), Dagstuhl Reports5(9) (2016), 77–104.
8.
V.Brattka, S.Le Roux, J.Miller and A.Pauly, Connected choice and Brouwer’s fixed point theorem, J. Math. Log.19(1) (2019). doi:10.1142/S0219061319500041.
9.
V.Brattka and A.Pauly, On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci.14(4:4) (2018), 1–36.
10.
V.Brattka and T.Rakotoniaina, On the uniform computational content of Ramsey’s theorem, J. Symbolic Logic82(4) (2017), 1278–1316. doi:10.1017/jsl.2017.43.
11.
G.J.CarlJr., Ramsey’s theorem and recursion theory, J. Symbolic Logic37 (1972), 268–280. doi:10.2307/2272972.
12.
P.A.Cholak, C.G.JockuschJr. and T.A.Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic66(1) (2001), 1–55. doi:10.2307/2694910.
13.
P.A.Cholak, C.G.JockuschJr. and T.A.Slaman, Corrigendum to: “On the strength of Ramsey’s theorem for pairs”, J. Symbolic Logic74(4) (2009), 1438–1439. doi:10.2178/jsl/1254748700.
14.
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.
15.
Denis, R.Hirschfeldt, R.A.Shore and T.A.Slaman, The atomic model theorem and type omitting, Trans. Amer. Math. Soc.361(11) (2009), 5805–5837. doi:10.1090/S0002-9947-09-04847-8.
16.
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.
17.
R.G.Downey and D.R.Hirschfeldt, Algorithmic Randomness and Complexity. Theory and Applications of Computability, Springer, New York, 2010.
18.
D.D.Dzhafarov, Strong reductions between combinatorial principles, J. Symbolic Logic81(4) (2016), 1405–1431. doi:10.1017/jsl.2016.1.
19.
D.D.Dzhafarov, Joins in the strong Weihrauch degrees, Math. Res. Lett.26 (2019), 749–767. doi:10.4310/MRL.2019.v26.n3.a5.
20.
D.D.Dzhafarov and C.G.JockuschJr., Ramsey’s theorem and cone avoidance, J. Symbolic Logic74(2) (2009), 557–578. doi:10.2178/jsl/1243948327.
21.
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.
22.
K.Higuchi and A.Pauly, The degree structure of Weihrauch reducibility, Log. Methods Comput. Sci.9(2) (2013). doi:10.2168/LMCS-9(2:2)2013.
23.
D.R.Hirschfeldt and C.G.JockuschJr., On notions of computability-theoretic reduction between principles, J. Math. Log.16(1) (2016), 1650002, 59.
24.
D.R.Hirschfeldt, C.G.JockuschJr., B.Kjos-Hanssen, S.Lempp and T.A.Slaman, The strength of some combinatorial principles related to Ramsey’s theorem for pairs, in: Computational Prospects of Infinity, C.Chong, Q.Feng, T.A.Slaman, W.H.Woodin and Y.Yang, eds, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 2008, pp. 143–161.
25.
J.L.Hirst and C.Mummert, Reverse mathematics of matroids, in: Computability and Complexity, Lecture Notes in Comput. Sci., Vol. 10010, Springer, Cham, 2017, pp. 143–159. doi:10.1007/978-3-319-50062-1_12.
26.
J.L.Hirst and C.Mummert, Using Ramsey’s theorem once, Arch. Math. Logic58(7–8) (2019), 857–866. doi:10.1007/s00153-019-00664-z.
27.
J.Liu, does not imply , J. Symbolic Logic77(2) (2012), 609–620. doi:10.2178/jsl/1333566640.
28.
B.Monin and L.Patey, encodability and omniscient reductions, Notre Dame J. Form. Log.60 (2019), 1–12. doi:10.1215/00294527-2018-0020.
29.
E.Neumann and A.Pauly, A topological view on algebraic computation models, J. Complexity44 (2018), 1–22. doi:10.1016/j.jco.2017.08.003.
30.
D.Nichols, Strong reductions between relatives of the stable Ramsey’s theorem, To appear, arXiv:1711.06532.
31.
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.
32.
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.
33.
A.Pauly, W.Fouché and G.Davie, Weihrauch-completeness for layerwise computability, Log. Methods in Comput. Sci.14 (2018).
34.
S.G.Simpson, Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn, Cambridge University Press, Cambridge, 2009.
