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

项目名称： 集合组合性质与计算性质间的关系

项目编号： No.11301548

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 刘路

作者单位： 中南大学

项目金额： 23万元

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

中文关键词： 可计算性；反推数学；算法随机性理论；拉姆齐染色定理；

英文摘要： 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 generaliz

英文关键词： computability；reverse mathematics；algorithmic randomness theory；ramsey's theorem；