2026/06/04 by JUN LE GOH, ELLEN HAMMATT, HEER TERN KOH +1
paper · doi:10.1017/jsl.2026.10220
crossref issued 2026/06/04 · crossref published 2026/06/04 · crossref published-online 2026/06/04 · crossref created 2026/06/04 · crossref deposited 2026/06/25 · crossref indexed 2026/07/30
Abstract We study the uniform computational content of Ramsey’s theorem using both Weihrauch reducibility and a new variant of Weihrauch reducibility, where the functions in the reduction are required to be total. In the latter setting, we show that the strength of Ramsey’s theorem varies significantly depending on how one represents its solutions, for example, using characteristic functions or using enumerations. Some of our results extend beyond variants of Ramsey’s theorem. In particular, we show that RT 2 2 \mathsf RT22 sans serif upper R upper T 2 squared where solutions are represented using characteristic functions is not totally Weihrauch reducible to any computational problem whose solutions are represented using enumerations. Next, we study the computational problems RT ∞ n \mathsf RTn∞ sans serif upper R upper T Subscript infinity Superscript n which take as input a colouring of n -tuples which has some infinite homogeneous set and asks for any such set. The problem RT ∞ 1 \mathsf RT1∞ sans serif upper R upper T Subscript infinity Superscript 1 is fairly well-studied, as it is Weihrauch equivalent to the cluster point problem on N \mathbb N double struck upper N . Our main result shows that RT ∞ 1 \mathsf RT1∞ sans serif upper R upper T Subscript infinity Superscript 1 is not Weihrauch reducible to RT N 2 \mathsf RT2_\mathbb N sans serif upper R upper T Subscript double struck upper N Superscript 2 , strengthening a result of Soldà and Valenti. We also show that the jump of RT ∞ 1 \mathsf RT1∞ sans serif upper R upper T Subscript infinity Superscript 1 is Weihrauch equivalent to SRT ∞ 2 \mathsf SRT2∞ sans serif upper S upper R upper T Subscript infinity Superscript 2 .