西塔潘猜想是由英國數理邏輯學家西塔潘於20世紀90年代提出的一個反推數學領域關於拉姆齊二染色定理證明強度的猜想。拉姆齊二染色定理以弗蘭克·普倫普頓·拉姆齊正式命名，1930年他在論文On a Problem in Formal Logic（《形式邏輯上的一個問題》）證明了R(3,3)= 6。
1930年，英國數學家弗蘭克·普倫普頓·拉姆齊在一篇題為《形式邏輯上的一個問題》的論文中證明了R(3,3)=6。這條定理被命名為“拉姆齊二染色定理”。用文字來表述就是“要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識，這個數n記為R(k,l)”。拉姆齊二染色定理的通俗版本被稱為“友誼定理”，即在一群不少於6人的人中，或者有3人，他們互相都認識；或者有3人，他們互相都不認識。
拉姆齊二染色定理（Ramsey Theorem for Pair）用非形式的語言可以敘述為任何一個對邊進行2-染色的含（可數）無窮個頂點的完全圖都有一個單一染色的含有無窮個頂點的子完全圖，而弱柯尼希定理（Weak Konig Lemma）則是說任何一個（可數）無窮二叉樹都有一條無窮長的路徑。這兩條都是二階算術中的陳述，說的是一個類中滿足某種性質的子集存在，可以粗暴地認為它們在某種程度上都是在表現或者替代二階算術中的選擇公理（Axiom of Choice）（一般的“Axiom of Choice”可對超出可數無窮多的對象進行選擇）。
在反推數學中，研究的其實是二階算術的各個子系統以及它們的強度關係，而最重要的是被稱為Big Five的五個子系統RCA 0 , WKL 0 , ACA 0 （後面兩個與本猜想無關，故不列出）。其中WKL 0是基本系統RCA 0添加弱柯尼希定理的系統，而RCA 0添加拉姆齊二染色定理的系統被稱為RT2 2 (不在Big Five，類似還有RT3 2 ，在此不表) 。經過若干數學家的研究，他們發現了一些子系統間存在強弱的比較關係：和RT2 2形式接近的RT3 2比ACA 0要強(其實一樣)，而RT2 2則不比ACA 0強，（ ACA 0比WKL 0強是基本的）等等[1]，從這些結果，他們隱約認為RT22和WKL 0的強度是可以比較的，1995年英國數理邏輯學家西塔潘在一篇論文[2]中發現WKL_0並不強於RT2 2 ，於是他猜測可能RT2 2 要強於WKL 0。
這一猜想引發了大量研究，困擾了許多數學家十多年之久，直到劉路的出現，他證明了RT2 2並不包含WKL 0 ，從而給該猜想一個否定的回答。
留言列表
