集合组合性质与计算性质间的关系

Recently, many computability theoretic results are obtained by applying combinatorial technique. Many of them are based on Mathias forcing, combined with various combinatorial technique. Liu[22] combined Mathias forcing with Pigeonhole principle, not only solved many important problems in various fields, but also reproved some known results. But when applying this method on proving SRT2 does not imply COH (within standard arithmetic model), studying computability theoretic power about 2-partition vs enumerable trees, or studying computability theoretic power about 2-partitions vs n-m-partitions, we met some similar difficulty. The same difficulty appears in different questions indicated that overcome this difficulty is extremely important, which required new technique. In this project we will focus on the above problems. The method itself is obviously more prospective. For example, the method can be used to simplify the proofs of questions originally proved by Kummabe's bushy-tree method. However, bushy-tree method is derived from set theory. Therefore it's quite tempting to apply the method in set theory. While proofs concerning Mathias forcing technique combined with different combinatorial technique have many common places, this project will try to summerize these common places and make appropriate generalization.

近年，组合数学技巧频繁应用于解决计算理论问题。其中许多证明以Mathias力迫法为基础，结合不同的组合数学技巧。Liu[22]将Mathias力迫与鸽子原理结合解决了若干领域的许多重要问题，及重新证明了一些已有结论。但把该方法用于解决SRT2不蕴含COH（标准模型中）、比较2-划分与可枚举树的计算理论性质、或比较2-划分与n-m-划分的计算理论性质等一些列问题时，遇到了相似的困难。同一困难在若干问题中出现意味着克服这一困难极其重要，也意味着需要新的技术。本项目将着重突破上述问题。该方法显然有更广阔的前景。如，该方法重新证明了一些原本用Kummabe bushy-tree方法解决的问题。而bushy-tree方法来自于集合论，可以想见该方法进一步推广应能在集合论中有不平凡的应用。而Mathias力迫结合不同的组合数学技巧的证明过程有着许多相似之处，本项目将极力概括这些相似之处，并加以推广。

反推数学研究数学命题证明轮强度之间的关系。大多数数学命题能够在二阶算术理论中表述。Friedman发现二阶算术的五个子系统，使得许多数学命题的证明论强度与之等价。然而经过研究发现，许多组合数学概念导致的命题并不落入这五个系统中的任何一个。其中RT（拉姆齐染色定理）相关定理是最早发现的这样的命题之一。作者之前解决了RT22与WKL0（五大子系统之一）间的关系。研究RT22的过程中发明了一种力迫方法，该方法的研究本身十分重要，其很有希望成为研究组合数学与计算理论性质关系的一种框架。项目期间，本人在Tran.Amer.Math的论文按照审稿人的意见修改并最终发表，该文解决了涉及反推数学和算法随机性理论的若干问题，包括RT22与WWKL0(一个比WKL0更弱的系统)的关系、Joe-Miller问题等，此外还重新证明了许多反推数学、算法随机性理论中的已有结果。我们进一步修改了该方法，并用其解决了Kjos-Hanssen问题。该文虽尚未发表，但已在学术会议(New challenges in reverse mathematics——新加坡国立大学)上报告，并获得了认可。解决了Simpson在11年反推数学成果展示会议上向我们提出的问题（通过邮件回复了Simpson本人）。解决了本人自己在之前一篇论文中提出的问题，RT21与RT31之间的关系。该结果也被许多其他学者相互独立地研究了。研究这些问题本身的意义并不仅限于反推数学或算法随机性理论，还有组合数学与计算理论间关系这一课题。计算理论与组合数学都有相应的概念刻画集合的复杂性。例如计算理论中的图灵度；组合数学中集合不同的划分数或密度导致的不同的复杂性。等图灵机可以看做是连续的partial函数。因此，研究组合数学性与计算理论性质间的关系，或许可以找到计算理论与其他数学分支之间的更多联系。这一趋势已经体现在若干研究中。例如，近年来，反推数学研究热点不再局限于命题的证明论强度，不再局限于可构造的instance，而是任意instance。

内容获取失败，请点击重试