EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

COMPARING VARIANTS OF RAMSEY’S THEOREM USING UNIFORM REDUCIBILITIES

JUN LE GOH, ELLEN HAMMATT, HEER TERN KOH, KENG MENG NG

The Journal of Symbolic Logic · 04.06.2026 · 1-33

DOI: 10.1017/jsl.2026.10220 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Journal of Symbolic Logic, online erschienen am 04.06.2026. Verfasst von JUN LE GOH und 3 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 {RT}^{2}_{2}$ 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 {RT}^{n}_{\infty }$ 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 {RT}^{1}_{\infty }$ 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 {RT}^{1}_{\infty }$ sans serif upper R upper T Subscript infinity Superscript 1 is not Weihrauch reducible to RT N 2 $\mathsf {RT}^{2}_{\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 {RT}^{1}_{\infty }$ sans serif upper R upper T Subscript infinity Superscript 1 is Weihrauch equivalent to SRT ∞ 2 $\mathsf {SRT}^{2}_{\infty }$ sans serif upper S upper R upper T Subscript infinity Superscript 2 .

Zitieren

APA

GOH, J. L., HAMMATT, E., KOH, H. T., & NG, K. M. (2026). COMPARING VARIANTS OF RAMSEY’S THEOREM USING UNIFORM REDUCIBILITIES. The Journal of Symbolic Logic, 1-33. https://doi.org/10.1017/jsl.2026.10220

Vancouver

GOH JL, HAMMATT E, KOH HT, NG KM. COMPARING VARIANTS OF RAMSEY’S THEOREM USING UNIFORM REDUCIBILITIES. The Journal of Symbolic Logic. 2026:1-33. doi:10.1017/jsl.2026.10220

BibTeX
@article{GOH2026,
  author = {GOH, JUN LE and HAMMATT, ELLEN and KOH, HEER TERN and NG, KENG MENG},
  title = {COMPARING VARIANTS OF RAMSEY’S THEOREM USING UNIFORM REDUCIBILITIES},
  journal = {The Journal of Symbolic Logic},
  year = {2026},
  pages = {1--33},
  doi = {10.1017/jsl.2026.10220}
}
Kostenlos starten →