《集合組合性質與計算性質間的關係》是依託中南大學，由劉路擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：集合組合性質與計算性質間的關係
- 項目類別：青年科學基金項目
- 項目負責人：劉路
- 依託單位：中南大學
項目摘要,結題摘要,
項目摘要
近年，組合數學技巧頻繁套用於解決計算理論問題。其中許多證明以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。
