We characterize the strength, in terms of Weihrauch degrees, of certain problems related to Ramsey-like theorems concerning colourings of the rationals and of the natural numbers. The theorems we are chiefly interested in assert the existence of almost-homogeneous sets for colourings of pairs of rationals respectively natural numbers satisfying properties determined by some additional algebraic structure on the set of colours.
In the context of reverse mathematics, most of the principles we study are equivalent to -induction over . The associated problems in the Weihrauch lattice are related to , or their product, depending on their precise formalizations.
V.Brattka, M.de Brecht and A.Pauly, Closed choice and a uniform low basis theorem, Annals of Pure and Applied Logic163(8) (2012), 968–1008. doi:10.1016/j.apal.2011.12.020.
2.
V.Brattka and G.Gherardi, Completion of choice, Annals of Pure and Applied Logic172(3) (2021), 102914. doi:10.1016/j.apal.2020.102914.
3.
V.Brattka, G.Gherardi and A.Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, V.Brattka and P.Hertling, eds, Springer International Publishing, Cham, 2021, pp. 367–417. ISBN 978-3-030-59234-9. doi:10.1007/978-3-030-59234-9_11.
4.
V.Brattka and T.Rakotoniaina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic82 (2017), 1278–1316. doi:10.1017/jsl.2017.43.
5.
O.Carton, T.Colcombet and G.Puppis, Regular languages of words over countable linear orderings, in: ICALP 2011 Proceedings, Part II, 2011, pp. 125–136. doi:10.1007/978-3-642-22012-8_9.
6.
V.Cipriani and A.Pauly, Embeddability of graphs and Weihrauch degrees, 2023. doi:10.48550/arXiv.2305.00935.
7.
C.Davis, D.R.Hirschfeldt, J.L.Hirst, J.Pardo, A.Pauly and K.Yokoyama, Combinatorial principles equivalent to weak induction, Comput.9(3–4) (2020), 219–229. doi:10.3233/COM-180244.
8.
D.D.Dzhafarov, J.L.Goh, D.R.Hirschfeldt, L.Patey and A.Pauly, Ramsey’s theorem and products in the Weihrauch degrees, Computability9(2) (2020). doi:10.3233/COM-180203.
9.
D.D.Dzhafarov, R.Solomon and M.Valenti, The tree pigeonhole principle in the Weihrauch degrees, 2023, https://arxiv.org/abs/2312.10535.
10.
D.D.Dzhafarov, R.Solomon and K.Yokoyama, On the first-order parts of problems in the Weihrauch degrees, 2023, https://arxiv.org/abs/2301.12733.
11.
M.Fiori-Carones, L.A.Kołodziejczyk and K.W.Kowalik, Weaker cousins of Ramsey’s theorem over a weak base theory, Annals of Pure and Applied Logic172(10) (2021), 103028, ISSN 0168-0072, https://www.sciencedirect.com/science/article/pii/S0168007221000865. doi:10.1016/j.apal.2021.103028.
12.
E.Frittaion and L.Patey, Coloring the rationals in reverse mathematics, Computability6(4) (2017), 319–331. doi:10.3233/COM-160067.
13.
K.Gill, Two studies in complexity, PhD thesis, Pennsylvania State University, 2023.
14.
K.Gill, Indivisibility and uniform computational strength, 2023, https://arxiv.org/abs/2312.03919.
15.
J.L.Goh, A.Pauly and M.Valenti, Finding descending sequences through ill-founded linear orders, Journal of Symbolic Logic86(2) (2021). doi:10.1017/jsl.2021.15.
16.
D.R.Hirschfeldt, Slicing the Truth, World Scientific, 2014. doi:10.1142/9208.
17.
J.L.Hirst, Combinatorics in subsystems of second order arithmetic, Phd thesis, Pennsylvania State University, 1987.
18.
L.A.Kolodziejczyk, H.Michalewski, C.Pradic and M.Skrzypczak, The logical strength of Büchi’s decidability theorem, Log. Methods Comput. Sci.15(2) (2019). doi:10.23638/LMCS-15(2:16)2019.
19.
S.Le Roux and A.Pauly, Finite choice, convex choice and finding roots, Logical Methods in Computer Science (2015). doi:10.2168/LMCS-11(4:6)2015.
20.
E.Neumann and A.Pauly, A topological view on algebraic computation models, J. Complex.44 (2018), 1–22. doi:10.1016/j.jco.2017.08.003.
21.
D.Perrin and J.-É.Pin, Infinite Words: Automata, Semigroups, Logic and Games, Pure and Applied Mathematics, 2004. ISBN 0-12-532111-2.
22.
C.Pradic and G.Soldà, On the Weihrauch degree of the additive Ramsey theorem over the rationals, in: Revolutions and Revelations in Computability – 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, U.Berger, J.N.Y.Franklin, F.Manea and A.Pauly, eds, Lecture Notes in Computer Science, Vol. 13359, Springer, 2022, pp. 259–271, Proceedings. doi:10.1007/978-3-031-08740-0_22.
23.
S.Shelah, The monadic theory of order, Ann. of Math. (2)102(3) (1975), 379–419, ISSN 0003-486X. doi:10.2307/1971037.
24.
S.G.Simpson, Subsystems of Second Order Arithmetic, Perspectives in Mathematical Logic, 1999, p. 445. ISBN 3-540-64882-8. doi:10.1007/978-3-642-59971-2.
25.
S.G.Simpson and R.L.Smith, Factorization of polynomials and induction, Annals of Pure and Applied Logic31 (1986), 289–306, ISSN 0168-0072, https://www.sciencedirect.com/science/article/pii/0168007286900746. doi:10.1016/0168-0072(86)90074-6.
26.
G.Soldà and M.Valenti, Algebraic properties of the first-order part of a problem, Ann. Pure Appl. Log.174(7) (2023), 103270. doi:10.1016/j.apal.2023.103270.
