《反推數學及相關可計算性理論問題》是依託中山大學，由王瑋擔任項目負責人的面上項目。
基本介紹
- 中文名：反推數學及相關可計算性理論問題
- 項目類別：面上項目
- 項目負責人：王瑋
- 依託單位：中山大學
中文摘要,結題摘要,
中文摘要
反推數學是數理邏輯中一個溝通各個傳統分支且聯繫經典數學的新興領域，其目標是通過用二階算術形式化經典數學理論，研究經典數學定理的證明論強弱。最近二十多年來，反推數學由於可計算性理論學界的重視和推動蓬勃發展。 本項目計畫研究反推數學中最為活躍的課題- - Ramsey理論的反推數學，特別是各種與n-元關係（n ＞ 2）相關的組合原理，並將考察Ramsey定理的一個較強形式- - Hindman定理的證明論強度。最近幾年來，非標準模型方法在反推數學上有一系列異常成功的套用，我們將考察我們的課題與非標準模型的聯繫，嘗試刻畫一些二階命題的一階理論。在技術上，我們將從一些與反推數學相關可計算性理論問題入手，特別是反推數學與可計算性理論的一個新興分支- - 算法隨機性- - 的關係，並尋求回答反推數學問題的較為統一的技術方案。
結題摘要
反推數學是近年來炙手可熱的一個數理邏輯研究領域。在最近的二十年里，可計算性理論的技術極大地推動了反推數學的發展，而反推數學也給可計算性理論的發展注入一股動力。本項目主要圍繞組合數學的反推數學展開，同時研究相關的可計算性理論、圖論問題和複雜性理論及算法問題。研究工作基本按計畫展開，不過過程並非完全順利，進度略慢，但我們也取得若干深刻且出人意外的成果，並建立起反推數學和數理邏輯的其它研究領域 —— 一階算術模型論、算法隨機性 —— 的聯繫。在反推數學方面，我們引入一種分析組合原理強弱的新角度，建立這種新視角與證明論強度的聯繫，並運用它統一地重新證明了若干已知結論，同時也得到若干新結論；我們從組合原理的一階理論切入，研究反推數學與一階算術模型論的聯繫，並進一步發展了一些經典的算術模型論方法；在圖論問題上，我們對適合反推數學研究的圖論問題做了一些探索，主要針對有向圖和特殊的有向圖——競賽圖展開；同時我們考察了圖論中的複雜性和算法問題。
