楊躍

1 引言：談談緊致性

語言及其指稱的討論在哲學中甚至在生活中都屢見不鮮。為了不離題太遠，我們只考察一個比較容易刻畫的問題：能不能用語言精確地描述一個數(shù)學結構？這樣說有些模糊，因為“語言”和“精確地描述”都可能有不同的解讀。我們必須引進數(shù)理邏輯的術語把問題更準確地敘述成：

問題：是否存在一個（一階）語句集S，使得任何兩個滿足S的數(shù)學結構都是同構的？

答案不難，只需對數(shù)理邏輯稍有了解，但有意思的是結論依賴于所討論結構（或“世界”）的大小。

斷言1如果一個數(shù)學結構A中只有有窮多個元素，則滿足上述問題條件的語句集S存在；甚至只要一個語句就夠了，即，存在單個語句σ，使得A滿足σ，且任何滿足σ的結構B都同構于A。

證明思路很自然：先考慮結構涉及的關系和函數(shù)是有窮的情形。我們只需把A里面元素之間的關系和函數(shù)列成一張大表，可以證明這張表是有窮的。σ基本上就是把這張表的所有信息記錄下來。如果結構涉及的關系和函數(shù)是無窮的，則需要先論證其中存在一個有窮子集，只要在子集中的關系和函數(shù)上表現(xiàn)相同，則在所有關系和函數(shù)上都表現(xiàn)相同，這樣就歸約到了第一種情形。

那么無窮的結構呢？

斷言2如果一個數(shù)學結構A中有無窮多個元素，則不存在一個的語句集S（這里S可以是無窮集合），使得A滿足S，且任何滿足S的結構B都同構于A。

斷言2 的證明要用到數(shù)理邏輯中的緊致性定理（Compactness），也就引出了我們的主題。

數(shù)理邏輯中的緊致性定理：如果一個（一階）語句集S的任何有窮子集都是可滿足的，則S本身也是可滿足的。

利用緊致性定理，可以證明：如果結構A有無窮多個元素，則存在結構B，B的基數(shù)大于A（因而不同構于A），且和A滿足同樣的語句集。細心的讀者可能會問，難道不能把結構的基數(shù)也敘述出來，例如要求A是可數(shù)無窮的嗎？問題就在這里，在“一階”語言中，我們只能談論結構里的個體，而無法斷言是否存在結構的子集或定義在結構上的函數(shù)，因而也無法談論結構的基數(shù)。

讓我們簡單回顧一下上述緊致性定理的歷史。最早的版本來自哥德爾的1929年的博士論文。哥德爾在論文中證明了一階邏輯的完全性，而緊致性定理是完全性定理的推論。但哥德爾只論證了緊致性定理的可數(shù)情形，因為他不需要更一般的情形。哥德爾完全性定理的證明用到了一個“人們熟知的論證”，他沒有說是什么，后人猜測為類似于弱柯尼西引理（Weak K?nig Lemma）式的論證。弱柯尼西引理敘述為任何無窮的二叉樹必有無窮支。顯然它對有窮分叉的樹都成立。后來人們發(fā)現(xiàn)，弱柯尼西引理也是緊致性的一種表現(xiàn)形式。

下面我們小結一下緊致性幾種形式，順便進一步解釋一下弱柯尼西引理。

· 很多人第一次接觸到“緊致性”是在數(shù)學分析中學Heine-Borel 定理的時候，該定理說實數(shù)上[0,1]區(qū)間上任一開覆蓋必有有窮子覆蓋。

· 上文提到的數(shù)理邏輯中的緊致性定理：如果一個語句集S的任何有窮子集都是可滿足的，則S本身也是可滿足的。

· 還有弱柯尼西引理：任何無窮的二叉樹必有無窮支。

這幾種形式表面上看完全不同，但背后都涉及“有窮-無窮”之間的聯(lián)系。粗略地說，Heine-Borel 定理把無窮覆蓋歸約到某個有窮覆蓋；邏輯中的緊致性定理把無窮語句集是否能被滿足的問題歸約為某個有窮集上的問題。而最后提到的弱柯尼西引理則需要解釋一下。

首先，我們只考察可數(shù)的二叉樹，從而可以把二叉樹T視為有窮0-1 串{0,1}＜ω的子集，且滿足下述封閉性：如果σ ∈T且τ是σ的前節(jié)，則τ ∈T。T里的元素稱為節(jié)點。我們稱一棵樹T是無窮的，如果T作為節(jié)點的集合是無窮的。T上的一“支”就是它的一個子集B使得對任何σ,τ ∈B，或者σ是τ的前節(jié)，或者τ是σ的前節(jié)。弱柯尼西引理看上去太顯然了，幾乎不用證明大家也會相信。難怪有本學術著作給出了下面類似童話的“證明”：從前，有一只老虎和一個獵人，他們最開始都在樹T的根節(jié)點上，老虎的背后就是T上無窮多的節(jié)點。T是二叉的，所以老虎后面有兩條路，它該選那一條呢？如果左邊的路通向無窮多節(jié)點（聰明的老虎當然能辨別有窮和無窮），它就向左跑；如果T的左一半只有有窮多節(jié)點，那它右一半就必有無窮多節(jié)點，那么老虎就向右跑。老虎跑一步，獵人當然就追一步。但每次老虎后面都有無窮多節(jié)點，所以獵人總追不上它。最后，他們跑過的節(jié)點就是我們要找的無窮支。

回到前面的緊致性。一般來說（這里我們有些模糊，因為略過了對背景語言的討論），描述一個集合是無窮的需要兩個無界量詞，即，對任意n個點的子集，都存在一個不在該子集中的新點。但如果我們想知道一個二叉樹T是否是無窮的，我們只要說，對任意n，在第n層上都存在一個T節(jié)點。但二叉樹第n層至多只有2n個節(jié)點，所以第二個存在量詞是有界量詞。這樣，緊致性體現(xiàn)在幫我們省掉了一個量詞。也許有人會說這是樹對前節(jié)封閉性造成的，不需要緊致性。但假如我們考察一下無窮分支的樹，它也有對前節(jié)的封閉性，但是無窮樹卻可以沒有無窮支！

2 緊致性與數(shù)學哲學

眾所周知，數(shù)學哲學的基本問題之一是：既然數(shù)學對象不存在于物理世界（時空）中，那么數(shù)學知識是關于什么的知識？按照對數(shù)學對象本體論上的定位，數(shù)學哲學家大概歸屬于以下兩大陣營：實在論（或柏拉圖主義）和反實在論（或虛構主義）。

在一些反實在論者看來，整個數(shù)學知識應該被劃分成兩部分，一部分是關于有窮世界的知識（特別是在物理世界中有實例的部分），這部分知識是有意義的，也有真假；而關于無窮世界的部分（特別是實無窮的那部分），都是“虛構”的，這部分知識或許有用，但它們沒有意義，也談不上真假。

然而，如果人們認可緊致性定理這類“人們熟知的論證”，反實在論者在有窮與無窮之間畫的這條線就顯得過于人為，畫這條線的動機不是出于數(shù)學的內在需要，而是為了貫徹哲學上的某種世界觀。如果我們承認緊致性定理，則也要承認有窮世界和無窮世界是有聯(lián)系的。緊致性定理有如下的推論

緊致性定理推論

如果一個（一階）語句集有任意大的有窮模型，則它必有一個無窮模型。

例如，我們考察代數(shù)里群的結構，令σ為?x?y(x·y=y·x)，即滿足σ的都是交換群。由于有任意有窮階的交換群存在，緊致性定理告訴我們一定會有無窮的交換群存在。當然這個例子數(shù)學上過于簡單，我們不需要通過緊致性定理也知道有無窮的交換群存在。數(shù)理邏輯里面有很多更自然的類似例子，但由于涉及更多的背景知識（如算術的非標準模型），我們這里不想多談。我們想強調的是：如果一個人承認關于有窮世界的陳述是有意義的，不能虛構。那他或她也必須承認，我們也不能任意地去“虛構”無窮世界的事實。例如，你不可能讓一個在有窮世界里都真的語句σ，在所有的無窮世界里都假。在這個意義上，σ在有窮世界中的意義會賦予它在某些無窮世界中的意義。

當然反實在論者幾乎肯定不接受緊致性定理，因為緊致性定理表述中（至少在我們提到的這三個版本里）都涉及了無窮本身。那么有沒有不接受緊致性定理理由呢？沒有緊致性的數(shù)學會是什么樣子呢？這就引出了我們下一個話題——反推數(shù)學（Reverse Mathematics）。反推數(shù)學可以告訴我們哪些數(shù)學定理是不需要緊致性定理的，哪些是必需要緊致性定理的。

最后再評論一句，對我來說，實在論與反實在論的根本分歧不在于什么是實在的什么是虛構的，而是在于承認不承認“整個世界”（無論是物理的還是數(shù)學的）背后有沒有一個統(tǒng)一的規(guī)律。（大多數(shù)的）實在論者會認為有一套貫穿“整個世界”的理性規(guī)律（或邏輯），這些規(guī)律是客觀的，不是我們虛構的。而且我們沒有必要去區(qū)分滿足這些規(guī)律的對象是否在時空中存在。以牛頓定律（或其他物理定律和方程）為例，我們沒有必要去在日月星辰和物理課本上的質點滑塊之間畫線。而（多數(shù)的）反實在論者會強調規(guī)律無非是感官經(jīng)驗的總結，像無窮集合這樣的對象由于不能被我們經(jīng)驗到，所以不可能存在關于它們的所謂規(guī)律。

3 反推數(shù)學簡介

反推數(shù)學創(chuàng)立于20 世紀70 年代，到現(xiàn)在接近半個世紀了。但恐怕對大多數(shù)讀者來說，反推數(shù)學依然是一個陌生的名詞。因此有必要做一些簡單的介紹。

反推數(shù)學關心的是數(shù)學定理的“相對強度”。例如，我們比較如下兩個代數(shù)里的命題：P:“任意交換環(huán)都有極大理想”和Q:“任意交換環(huán)都有素理想”。由于極大理想都是素理想，所以P ?Q。事實上，在大學本科教材里，素理想的存在往往就是通過極大理想的存在來論證的。那Q是否真比P弱呢？即，有沒有呢？或者說，有沒有可能一個交換環(huán)里只有素理想而沒有極大理想呢？

當然，如果我們每次都比較一對數(shù)學定理P和Q，那效率是非常低下的。事實上，反推數(shù)學做的往往不是直接比較P和Q，而是建立嚴格的邏輯公理系統(tǒng)分層Γ0＜Γ1＜...，來論證Γi能證Q但不能證P。這里每個Γi都代表一個邏輯系統(tǒng)，通常是某個數(shù)學基礎研究中常見系統(tǒng)（如，一階算術、二階算術或集合論）的子系統(tǒng)，其中的＜一般表示左邊的系統(tǒng)的邏輯后承是右邊系統(tǒng)邏輯后承的真子集。而論證Γi不能證P的方法常常是找到某個j ＞i然后用P證Γj；通俗地說，就是在邏輯公理系統(tǒng)里建立一把尺子，用它去量數(shù)學中的定理，如果P的刻度是3 而Q的刻度是2，則這樣做的好處一是邏輯系統(tǒng)的強弱相對來說更容易用數(shù)理邏輯中的工具（如對角線法，或用不完全性定理）來論證；二是邏輯往往為各個不同的學科提供了一個共同的舞臺，直接比較兩個不同領域里的（如圖論的和概率的）定理恐怕要花很大的功夫先去統(tǒng)一語言和符號，因而較為困難，但我們卻可以通過把它們分別和邏輯系統(tǒng)比較來間接達到我們的目的。

注意：上面的討論包括兩個方向，我們一方面論證Γi能證Q，即用公理去證定理，這是大家所熟悉的“正推”；另一方面，我們也論證P可以證Γj，即用定理去證公理。這是反推（reverse）二字的由來。在反推數(shù)學的文獻里，常常會把反推數(shù)學的目標定為：對經(jīng)典（可數(shù)）數(shù)學中的定理，找出其證明所需的公理。這樣說沒有錯，反推數(shù)學的確是想為定理找出精確的公理“量度”。但這種說法也引來一些詰難：數(shù)學貴在創(chuàng)新，而反推數(shù)學在定理之間或定理與公理之間搞來搞去，有悖于數(shù)學的創(chuàng)新原則。這些詰難實際上源于一種典型的誤解?！暗湫汀笔且驗橥瑯拥脑戨y也經(jīng)常被用在機器證明和構造性數(shù)學等學科頭上。為什么說它是誤解，原因是為了實現(xiàn)反推的目標，常常需要找到新的證明，這恰恰是創(chuàng)新。在反推數(shù)學研究中，循規(guī)蹈矩地把經(jīng)典證明分析一遍就完成任務的論文是不受關注的；大家欣賞的依舊是那些“匪夷所思”的創(chuàng)新證明。

那么是不是每一對P和Q都可以比較呢？或者說是不是所有的數(shù)學定理的強度都能被“量”出來呢？這在反推數(shù)學發(fā)展史上是個很有意思的問題。讓我們先對反推數(shù)學多一些了解，然后再回到這個問題。

反推數(shù)學使用的是二階算術的子系統(tǒng)（也稱為片段fragments)來作為衡量定理的尺度。這里一方面有歷史原因，因為二階算術是希爾伯特比較關注的系統(tǒng)之一。另一方面的原因是在數(shù)學基礎里常見的三個系統(tǒng)當中，一階算術只談論初等數(shù)論命題，邏輯中形式系統(tǒng)能夠被編碼為自然數(shù)，所以邏輯學與一階算術關系緊密。但如果把數(shù)學里一般的內容都換成自然數(shù)來討論是既費力又不自然；集合論由于涵蓋了幾乎所有數(shù)學，它的子系統(tǒng)通?？缍确浅４?，容易漏掉細微的差別；而二階算術介于兩者之間，其中可以比較自然地討論組合和代數(shù)的問題，通過編碼也可以討論數(shù)學分析和微分方程中的問題，正好用來衡量經(jīng)典數(shù)學中的定理。

在二階算術中，人們不僅可以談論個別的自然數(shù)，也可以談論自然數(shù)的集合。讓我們稍微多解釋幾句：在二階算術中有兩組不同的變元和量詞，一組是用來談論自然數(shù)的，例如，?m?n(m ＜n)中的量詞都是管轄自然數(shù)m和n的，它是一個“一階”語句；另一組則是談論集合的，當然這兩組變元和量詞可以在同一語句內出現(xiàn)，例如，所謂“良序原則”（所有非空集都有最小元）就可以用二階算術語句表示為：

其中?X是二階的，X代表的是自然數(shù)的子集，而中括號內的除了二階參數(shù)X之外都是一階的，m和n代表的是個體自然數(shù)。反推數(shù)學中最常用的尺度是如下五大子系統(tǒng)：

（第一層或基本層）RCA0（只承認可計算的集合或函數(shù)存在）

（第二層）WKL0:RCA0加上“弱柯尼西引理”。即，承認緊致性定理。

（第三層）ACA0（承認一階算術可定義的集合存在）。

（第四、五層）ATR0和-CA0。

由于篇幅關系我們不解釋英文縮寫的涵義，而是簡略說一下分層的思想。利用二階存在量詞，我們可以直接斷言某類自然數(shù)的子集存在。系統(tǒng)越強，它（的模型）里面的集合就越多。比如，第一層的系統(tǒng)里只有可計算的集合存在；而第三層則包括了所有在一階算術內可定義的集合；第五層就更多了；這三層是借助可定義性來描述的。而第二層和第四層則是借助數(shù)學工具來間接描述的，例如，第二層就是斷言像二叉樹上無窮支那樣的集合是存在的。在第一層RCA0的世界里，只有可計算的集合存在。而遞歸論中有定理表明，存在一個遞歸的二叉樹T沒有無窮的遞歸支。這樣，生活在第一層上的人會看到這棵樹T，但卻看不到它的任何無窮支。在下文中，我們只涉及前三層，重點圍繞著第二層。所以第四、第五層就不提了。

反推數(shù)學自從1970 年代創(chuàng)立以來，直到2000 年，主要結果都是把數(shù)學定理歸類到這五大子系統(tǒng)中去。反推數(shù)學的標準參考書，辛普森的專著（[6]）就是對這些成果的一個全面總結。例如，Heine-Borel 定理，哥德爾完全性定理，素理想存在定理等等都等價于第二層的WKL0。大學本科里所涉及的數(shù)學內容，幾乎都能被這五大子系統(tǒng)度量出來。有人開玩笑說：“人們驚奇地發(fā)現(xiàn)，從古到今數(shù)學家只證了五個定理”。這就向反推數(shù)學家提出了挑戰(zhàn)，要么給出一個哲學上的解釋，為什么數(shù)學上定理的強度會排得這么整齊；要么發(fā)現(xiàn)不在這五大系統(tǒng)里的重要的數(shù)學定理。這就引出了我們下一節(jié)——拉姆塞定理。

4 拉姆塞定理

拉姆塞（F.P.Ramsey），是英國的數(shù)學家、哲學家兼經(jīng)濟學家。雖然英年早逝，但卻在很多領域都做出了杰出的貢獻。拉姆塞定理是他在論文[4]（《形式邏輯上的一個問題》）中證明的。論文提交于1928 年，發(fā)表于1930 年。拉姆塞文章的主旨是邏輯中的判定性問題，只是為了技術上的需要他才先證了拉姆塞定理；而如今該定理已成為組合數(shù)學中的一個重要分支，稱為拉姆塞理論。

拉姆塞定理：對任一f:[N]n →{0,1,...,k-1}，都存在一個無窮的齊性（或稱同色homogeneous set）H ?N，即，f限制在[H]n是常數(shù)。（這里，對A ?N,符號[A]n表示A的n-元子集的集合。）

通常稱f為“一個k-染色”。上述版本記為，我們主要關心——格點上的拉姆塞定理?？匆粋€簡單的例子，對自然數(shù)x ＜y，我們定義如下的染色f：

則所有素數(shù)的集合是一個無窮的染0 的同色集，因為任意一對素數(shù)顯然互素；而由2 的各次冪組成的集合{2,4,8,16,...}則是一個無窮的染1 的同色集，因為任意一對都有公因子2。

考察自然數(shù)二元子集上的一個紅藍染色f。首先我們先“捋順尾巴”：取a0=0。固定住a0。先選一個無窮集B0，使得對所有b ∈B0，f(a0,b)同色。這樣的B0總是有的（想想上面老虎背后的森林，道理是一樣的）。無妨設對任一b ∈B0，f(a0,b)都是紅色。此時，讓我們稱a0為“紅點”。從現(xiàn)在起只考慮B0里的元素。令a1為B0的最小元，再選無窮集B1?B0使得對所有b ∈B1，f(a1,b)同色，讓我們假設他們都是藍色，我們就稱a1為一個“藍點”。這樣一直做下去，我們每次都把“尾巴”（即，集合B0,B1,...等等）縮小，使得“尾巴”里的元素與前面的點（即a0,a1,...等等）都分別地染同一種顏色，與此同時，得到一個紅藍點的無窮序列（即序列(a0,a1,...)）。紅點和藍點組成的子序列至少有一個是無窮的。那就是我們要的H。

順帶評論一下：以上的證明直觀上很簡單，但同色集H的復雜度會很高。為什么呢？因為，在拿B0的時候，我們需要知道和a0配起來是紅的有無窮多還是藍的有無窮多，這樣B0就比染色f“多了兩個量詞”（見前面對弱柯尼西引理的討論）。接下來，B1又比B0“多兩個量詞”，這樣一直做下去，拿到的紅藍點的序列就涉及了“無窮多量詞”。這還沒完，在紅藍點序列中，我們還要再分一次，挑出一個無窮集來，這又（在無窮個量詞之上）“多兩個量詞”。總之，從可定義的角度看，這樣拿到的同色集H是非常復雜的。

拉姆塞定理是組合數(shù)學里帶有哲學意義的重要定理之一。我們可以把它解讀成：任何混亂（即染色）中都有某種秩序（即同色集）。有數(shù)學家評論說：拉姆塞定理表明“絕對混亂的系統(tǒng)是不存在的”。這樣的解讀多少帶一些理性樂觀主義的味道。

反推數(shù)學中對拉姆塞定理的研究起始于加庫什1972 年的文章[2]。加庫什是從遞歸數(shù)學的角度來研究拉姆塞定理的，但他的結果可以直接“翻譯”成反推數(shù)學的結果。下面我們給出用反推數(shù)學語言表達的加庫什結果：

加庫什定理

·對n,k ＞2,等價于ACA0。換句話說，除了，其他版本的拉姆塞定理都恰好處在第三層。

·ACA0蘊涵；但WKL0不蘊涵。換句話說，在第三層或在第三層之下，但不在第二層更不在第二層之下。

對熟悉數(shù)理邏輯的讀者來說，加庫什定理的原版也非常有意思。加庫什證明了：對來說（1）任何遞歸的染色都有的同色集；（2）存在一個遞歸染色沒有的同色集。我們前面說過，語句大致對應無窮集合的表述。因此，加庫什定理說明，雖然同色集存在，但如果想要把它“找到”則非要借助無窮這一概念不可。結合拉姆塞定理的意義，我們可以進一步引申一下：加庫什定理告訴我們，盡管混亂中有秩序，但只有站在更高的水平上才看得到。

加庫什之后，這一領域沉寂了20 多年，直到1995 年，西塔潘和斯萊曼（[5]）才把它重新喚醒：

西塔潘-斯萊曼定理

西塔潘-斯萊曼定理的證明巧妙利用了樹的性質，于是西塔潘提出了后來以他命名的“西塔潘猜想”：蘊涵WKL0。即要想證明格點拉姆塞定理，非得用弱柯尼西引理不可，換句話說，緊致性定理是格點拉姆塞定理的必要條件。從反推數(shù)學的尺度上看，西塔潘猜想敘述為：的強度嚴格介于第二層和第三層之間。雖然格點拉姆塞定理不對應五大子系統(tǒng)中的任何一個，但西塔潘猜想意味著只需在尺子上多添一個刻度就可以了。

從此，西塔潘猜想成為反推數(shù)學里人人關心的問題，幾乎所有做反推數(shù)學的人都嘗試過。為了它還不止一次專門召開國際研討會，參會人員除了遞歸論和反推數(shù)學之外，還包括集合論、證明論、組合數(shù)學和計算機科學等領域的研究人員。大家嘗試過各種各樣的方法，如力迫法、非標準模型和概率等等。各種嘗試中有一個共同點：分而治之；也就是說把分解成一些比它還弱的組合原理，通過搞清楚這些弱的組合原理來解決西塔潘猜想。于是便產(chǎn)生了下面的圖1，大家把這張圖稱為反推數(shù)學“動物園”1這張圖也包括了一些強于 的組合原理。另外，這張圖也已過時，有興趣的讀者可以瀏覽網(wǎng)頁https://rmzoo.math.uconn.edu/。。圖里面的節(jié)點都是組合原理或邏輯子系統(tǒng)。對拉姆塞定理和反推數(shù)學有興趣的讀者可以閱讀赫施菲爾德的講義（[1]）。

西塔潘猜想最終是由我國年輕數(shù)學家劉路2文章是用“筆名”劉嘉憶發(fā)表的。否證的（[3]）。

劉路定理

劉路結果的意義一方面是技術上有重大創(chuàng)新，他的證明方法已被很多學者用來解決了很多的疑難問題；另一方面，劉路的結果確認了存在與五大子系統(tǒng)不可比的重要定理。這樣，連同其他種種“動物學”的成果，說明反推數(shù)學舊有的“范式”已經(jīng)不適用了。數(shù)學定理強度的分類肯定不會像一把直尺那樣簡單，而應該是一個偏序結構。這一偏序結構到底是什么樣子呢，有沒有它的內在規(guī)律呢？它至少不應該像動物園那樣混亂吧。有沒有一個自然的、合理的分類法是目前的對反推數(shù)學和數(shù)學哲學的挑戰(zhàn)之一。

圖1：反推數(shù)學“動物園”