On the Weihrauch degree of the additive Ramsey theorem

被引:1
|
作者
Pauly, Arno [1 ]
Pradic, Cecilia [1 ]
Solda, Giovanni [1 ]
机构
[1] Swansea Univ, Sch Math & Comp Sci, Swansea, Wales
来源
COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE | 2024年 / 13卷 / 3-4期
关键词
Weihrauch reducibility; reverse mathematics; additive Ramsey; E; 0; 2-induction;
D O I
10.3233/COM-230437
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 E 2 0-induction over RCA0. The associated problems in the Weihrauch lattice are related to TC * N , ( LPO ' ) * or their product, depending on their precise formalizations.
引用
收藏
页码:459 / 483
页数:25
相关论文
共 28 条
  • [1] On the Weihrauch Degree of the Additive Ramsey Theorem over the Rationals
    Pradic, Pierre
    Solda, Giovanni
    REVOLUTIONS AND REVELATIONS IN COMPUTABILITY, CIE 2022, 2022, 13359 : 259 - 271
  • [2] Ramsey's theorem and products in the Weihrauch degrees
    Dzhafarov, Damir D.
    Goh, Jun Le
    Hirschfeldt, Denis R.
    Patey, Ludovic
    Pauly, Arno
    COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE, 2020, 9 (02): : 85 - 110
  • [3] Effectiveness for the Dual Ramsey Theorem
    Dzhafarov, Damir
    Flood, Stephen
    Solomon, Reed
    Westrick, Linda
    NOTRE DAME JOURNAL OF FORMAL LOGIC, 2021, 62 (03) : 455 - 490
  • [4] Using Ramsey's theorem once
    Hirst, Jeffry L.
    Mummert, Carl
    ARCHIVE FOR MATHEMATICAL LOGIC, 2019, 58 (7-8) : 857 - 866
  • [5] The canonical Ramsey theorem and computability theory
    Mileti, Joseph R.
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2008, 360 (03) : 1309 - 1340
  • [6] Using Ramsey’s theorem once
    Jeffry L. Hirst
    Carl Mummert
    Archive for Mathematical Logic, 2019, 58 : 857 - 866
  • [7] Stable Ramsey's Theorem and Measure
    Dzhafarov, Damir D.
    NOTRE DAME JOURNAL OF FORMAL LOGIC, 2011, 52 (01) : 95 - 112
  • [8] On the strength of Ramsey's theorem for trees
    Chong, C. T.
    Li, Wei
    Wang, Wei
    Yang, Yue
    ADVANCES IN MATHEMATICS, 2020, 369
  • [9] On the strength of Ramsey's theorem for pairs
    Cholak, PA
    Jockusch, CG
    Slaman, TA
    JOURNAL OF SYMBOLIC LOGIC, 2001, 66 (01) : 1 - 55
  • [10] THE WEIHRAUCH LATTICE AT THE LEVEL OF.11-CA0: THE CANTOR-BENDIXSON THEOREM
    Cipriani, Vittorio
    Marcone, Alberto
    Valenti, Manlio
    JOURNAL OF SYMBOLIC LOGIC, 2025,