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
专知会员服务
74+阅读 · 2020年5月5日
【新书】Python编程基础,669页pdf
专知会员服务
195+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2019年3月29日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
12+阅读 · 2018年4月27日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
使用 Python 绘制《星战》词云
Datartisan数据工匠
3+阅读 · 2017年8月31日
Arxiv
0+阅读 · 2021年3月8日
Arxiv
0+阅读 · 2021年3月6日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2019年3月29日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
12+阅读 · 2018年4月27日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
使用 Python 绘制《星战》词云
Datartisan数据工匠
3+阅读 · 2017年8月31日
Top
微信扫码咨询专知VIP会员