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 条
  • [21] THE STRENGTH OF RAMSEY'S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS
    Slaman, Theodore A.
    Yokoyama, Keita
    JOURNAL OF SYMBOLIC LOGIC, 2018, 83 (04) : 1610 - 1617
  • [22] EFFECTIVE VERSIONS OF RAMSEY THEOREM - AVOIDING THE CONE ABOVE 0'
    HUMMEL, TL
    JOURNAL OF SYMBOLIC LOGIC, 1994, 59 (04) : 1301 - 1325
  • [23] Weaker cousins of Ramsey's theorem over a weak base theory
    Fiori-Carones, Marta
    Kolodziejczyk, Leszek Aleksander
    Kowalik, Katarzyna W.
    ANNALS OF PURE AND APPLIED LOGIC, 2021, 172 (10)
  • [24] In Search of the First-Order Part of Ramsey's Theorem for Pairs
    Kolodziejczyk, Leszek Aleksander
    Yokoyama, Keita
    CONNECTING WITH COMPUTABILITY, 2021, 12813 : 297 - 307
  • [25] The proof-theoretic strength of Ramsey's theorem for pairs and two colors
    Patey, Ludovic
    Yokoyama, Keita
    ADVANCES IN MATHEMATICS, 2018, 330 : 1034 - 1070
  • [26] Π11-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
    Chong, C. T.
    Slaman, Theodore A.
    Yang, Yue
    ADVANCES IN MATHEMATICS, 2012, 230 (03) : 1060 - 1077
  • [27] THE STRENGTH OF RAMSEY'S THEOREM FOR PAIRS OVER TREES: I. WEAK KONIG'S LEMMA
    Chong, Chi Tat
    Li, Wei
    Liu, Lu
    Yang, Yue
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2021, 374 (08) : 5545 - 5581
  • [28] AN EXTENSION THEOREM ON DEGREE OF APPROXIMATION OF FOURIER SERIES BY (E, q)B-MEAN
    Padhy, B. P.
    Tripathy, P.
    Misra, U. K.
    TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2021, 11 (04): : 1093 - 1099