On the Weihrauch degree of the additive Ramsey theorem

Article type: Research Article

Authors: Pauly, Arno^{a; *} | Pradic, Cécilia^b | Soldà, Giovanni^c

Affiliations: [a] School of Mathematics and Computer Science, Swansea University, United Kingdom | [b] School of Mathematics and Computer Science, Swansea University, United Kingdom | [c] School of Mathematics and Computer Science, Swansea University**, United Kingdom

Correspondence: [*] Corresponding author. arno.m.pauly@gmail.com.

Note: [**] Soldà has since moved to Ghent University, Belgium.

Abstract: 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 Σ20-induction over RCA0. The associated problems in the Weihrauch lattice are related to TCN∗, (LPO′)∗ or their product, depending on their precise formalizations.

Keywords: Weihrauch reducibility, reverse mathematics, additive Ramsey, Σ₀²-induction

DOI: 10.3233/COM-230437

Journal: Computability, vol. Pre-press, no. Pre-press, pp. 1-25, 2024