期刊
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY
卷 375, 期 3, 页码 1977-2024出版社
AMER MATHEMATICAL SOC
DOI: 10.1090/tran/8561
关键词
Computability theory; reverse mathematics; Weihrauch degrees; Ramsey theory
类别
资金
- John Templeton Foundation [60842]
- Italian PRIN 2017 grant Mathematical Logic: models, sets, computability
Inspired by Ramsey's theorem, Rival and Sands proved the inside/outside Ramsey theorem which has strong computational strength and is equivalent to arithmetical comprehension. They also identified a weaker form that is equivalent to Ramsey's theorem for pairs. Combining their result with previous research, they showed that solving one instance of the Rival-Sands theorem corresponds to solving countably many instances of Ramsey's theorem for pairs simultaneously. They also analyzed the Weihrauch degrees and found that the Rival-Sands theorem has the same computational strength as the double jump of weak Konig's lemma.
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 Konig'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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据