STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES
STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES
复制标题
组合原理之间的大幅简化
DOI：
10.1017/jsl.2016.1
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Dzhafarov
中科院分区：
文献类型：
--
作者：
D. Dzhafarov
摘要本文是对二阶算术${\rm {\Pi}}_2^1 $语句间强可约性研究的一个贡献，它被看作是传统的逆向数学分析的一个扩展.我们回答了Hirschfeldt和Jockusch [13]关于Weihrauch（均匀）和强可计算约简的几个问题，这些约简是与Ramsey对定理相关的各种组合原理之间的约简。在其他结果中，我们建立了$SRT_2^2 $不是Weihrauch或强可计算可约为$D_{<\infty}^2 $，COH不是Weihrauch可约为$SRT_{<\infty}^2 $或强可计算可约为$SRT_2^2 $。最后一个结果也推广了Dzhafarov [9]的一个结果.我们引入了一些新的技术，用于控制我们在我们的论点中构建的问题和解决方案的组合和可计算性理论属性。
Abstract This paper is a contribution to the growing investigation of strong reducibilities between ${\rm{\Pi }}_2^1$ statements of second-order arithmetic, viewed as an extension of the traditional analysis of reverse mathematics. We answer several questions of Hirschfeldt and Jockusch [13] about Weihrauch (uniform) and strong computable reductions between various combinatorial principles related to Ramsey’s theorem for pairs. Among other results, we establish that the principle $SRT_2^2$ is not Weihrauch or strongly computably reducible to $D_{ < \infty }^2$ , and that COH is not Weihrauch reducible to $SRT_{ < \infty }^2$ , or strongly computably reducible to $SRT_2^2$ . The last result also extends a prior result of Dzhafarov [9]. We introduce a number of new techniques for controlling the combinatorial and computability-theoretic properties of the problems and solutions we construct in our arguments.