An inside/outside Ramsey theorem and recursion theory
An inside/outside Ramsey theorem and recursion theory
复制标题
内/外拉姆齐定理和递归理论
DOI：
10.1090/tran/8561
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Fiori-Carones M
中科院分区：
文献类型：
--
作者：
Fiori-Carones M
受拉姆齐定理的启发，Rival和Sands证明了我们所说的内部/外部拉姆齐定理：每个无限图都包含一个无限子集，使得的每个顶点都不与任何一个、一个或无限多个顶点相邻。从逆向数学和Weihrauch度的角度分析了Rival-Sands定理。在逆向数学中，我们发现Rival-Sands定理等价于算术理解，因此比Ramsey定理更强。我们还确定了一个弱形式的Rival-Sands定理，相当于拉姆齐定理对。我们转向Weihrauch度，给出Rival-Sands定理的计算强度的更精细的分析。我们发现Rival-Sands定理是Weihrauch等价于弱König引理的双跳。我们相信，Rival-Sands定理是第一个显示出这种力量的自然定理。此外，通过将我们的结果与Brattka和Rakotoniaina的结果相结合，我们得到，解决Rival-Sands定理的一个实例正好对应于同时解决对的Ramsey定理的可数多个实例。最后，我们表明，弱Rival-Sands定理的统一的计算强度是弱于拉姆齐定理对显示一些著名的后果拉姆齐定理对不Weihrauch减少到弱Rival-Sands定理。我们还解决了一个明显的差距，在文献中关于Weihrauch度对应的上升/下降序列的原则和无限鸽子洞原则之间的关系。引用
Inspired by Ramsey’s theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graphcontains an infinite subsetsuch that every vertex ofis adjacent to precisely none, one, or infinitely many vertices of. 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
登录
查看更多内容
影响因子：
0.4
作者：
Antonio Montalbán
通讯作者：
Antonio Montalbán
论可计算性理论的统一计算内容
影响因子：
0.5
作者：
V. Brattka;Matthew Hendtlass;A. Kreuzer
通讯作者：
A. Kreuzer
勘误：“关于拉姆齐对定理的强度”
DOI：
10.2178/jsl/1254748700
发表时间：
2009
期刊：
The Journal of Symbolic Logic
影响因子：
--
作者：
Peter A. Cholak;T. Slaman;C. Jockusch
通讯作者：
C. Jockusch
圆锥避免闭集
DOI：
10.1090/s0002-9947-2014-06049-2
发表时间：
2014
期刊：
arXiv: Logic
影响因子：
--
作者：
Lu Liu
通讯作者：
Lu Liu
影响因子：
0.6
作者：
Brattka, Vasco;Gherardi, Guido
通讯作者：
Gherardi, Guido