Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48 .

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

An inside/outside Ramsey theorem and recursion theory
HTML articles powered by AMS MathViewer

by Marta Fiori-Carones, Paul Shafer and Giovanni Soldà PDF
Trans. Amer. Math. Soc. 375 (2022), 1977-2024 Request permission

Abstract:

Inspired by Ramsey’s theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graph $G$ contains an infinite subset $H$ such that every vertex of $G$ is adjacent to precisely none, one, or infinitely many vertices of $H$. We analyze the Rival–Sands theorem from the perspective of reverse mathematics and the Weihrauch degrees. In reverse mathematics, we find that the Rival–Sands theorem is equivalent to arithmetical comprehension and hence is stronger than Ramsey’s theorem for pairs. We also identify a weak form of the Rival–Sands theorem that is equivalent to Ramsey’s theorem for pairs. We turn to the Weihrauch degrees to give a finer analysis of the Rival–Sands theorem’s computational strength. We find that the Rival–Sands theorem is Weihrauch equivalent to the double jump of weak König’s lemma. We believe that the Rival–Sands theorem is the first natural theorem shown to exhibit exactly this strength. Furthermore, by combining our result with a result of Brattka and Rakotoniaina, we obtain that solving one instance of the Rival–Sands theorem exactly corresponds to simultaneously solving countably many instances of Ramsey’s theorem for pairs. Finally, we show that the uniform computational strength of the weak Rival–Sands theorem is weaker than that of Ramsey’s theorem for pairs by showing that a number of well-known consequences of Ramsey’s theorem for pairs do not Weihrauch reduce to the weak Rival–Sands theorem. We also address an apparent gap in the literature concerning the relationship between Weihrauch degrees corresponding to the ascending/descending sequence principle and the infinite pigeonhole principle.
References
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC (2020): 03B30, 03D30, 03F35
  • Retrieve articles in all journals with MSC (2020): 03B30, 03D30, 03F35
Additional Information
  • Marta Fiori-Carones
  • Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
  • MR Author ID: 1437660
  • ORCID: 0000-0002-5972-0542
  • Email: marta.fioricarones@outlook.it
  • Paul Shafer
  • Affiliation: School of Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom
  • MR Author ID: 920651
  • ORCID: 0000-0001-5386-9218
  • Email: p.e.shafer@leeds.ac.uk
  • Giovanni Soldà
  • Affiliation: School of Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom
  • ORCID: 0000-0003-4903-3623
  • Email: giovanni.a.solda@gmail.com
  • Received by editor(s): June 30, 2020
  • Received by editor(s) in revised form: August 11, 2021
  • Published electronically: December 23, 2021
  • Additional Notes: This project was partially supported by a grant from the John Templeton Foundation (A new dawn of intuitionism: mathematical and philosophical advances ID 60842). Additionally, Fiori-Carones was partially supported by the Italian PRIN 2017 grant Mathematical Logic: models, sets, computability. The opinions expressed in this work are those of the authors and do not necessarily reflect the views of the John Templeton Foundation.
  • © Copyright 2021 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 375 (2022), 1977-2024
  • MSC (2020): Primary 03B30, 03D30, 03F35
  • DOI: https://doi.org/10.1090/tran/8561
  • MathSciNet review: 4378086