We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm{ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify 8 different multivalued functions (5 corresponding to the open Ramsey theorem and 3 corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm{ATR}_0$.


翻译:我们调查了Weihrauch Lattice的开放和黑白Ramsey理论的统一计算内容。 虽然从反向数学的角度来看,已知这些理论相当于$\mathrm{ATR_0}美元,但并没有一种粗俗的方法把它们说成是多值功能。我们确定了8种不同的多值功能(5个相当于开放的Ramsey理论,3个相当于黑白Ramsey理论),并从Weihrauch、强力的Weihrauch和算术Weishrauch的可复制性的角度研究其程度。特别是,我们的一项功能比以前研究过的美元左右的多值函数严格强。

0
下载
关闭预览

相关内容

Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
76+阅读 · 2020年5月5日
【新书】Python编程基础,669页pdf
专知会员服务
197+阅读 · 2019年10月10日
已删除
将门创投
5+阅读 · 2019年3月29日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2021年3月6日
VIP会员
相关资讯
已删除
将门创投
5+阅读 · 2019年3月29日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Top
微信扫码咨询专知VIP会员