【專欄】康托爾、哥德爾、圖靈——永恒的金色對角線（12）

羅素悖論

學過邏輯的人大約肯定是知道著名的羅素悖論的，羅素悖論用數學的形式來描述就是：

R = {X:X不屬于X};

這個悖論最初是從康托爾的無窮集合論里面引申出來的。當初康托爾在思考無窮集合的時候發現可以稱“一切集合的集合”，這樣一個集合由于它本身也是一個集合，所以它就屬于它自身。也就是說，我們現在可以稱世界上存在一類屬于自己的集合，除此之外當然就是不屬于自己的集合了。而我們把所有不屬于自己的集合收集起來做成一個集合R，這就是上面這個著名的羅素悖論了。

我們來看R是否屬于R，如果R屬于R，根據R的定義，R就不應該屬于R。而如果R不屬于R，則再次根據R的定義，R就應該屬于R。

這個悖論促使了集合論的公理化。后來策梅羅公理化的集合論里面就不允許X屬于X（不過可惜的是，盡管如此還是沒法證明這樣的集合論不可能產生出新的悖論。而且永遠沒法證明——這就是哥德爾第二不完備性定理的結論——一個包含了PA的形式化公理系統永遠無法在內部證明其自身的一致（無矛盾）性。從而希爾伯特想從元數學推出所有數學系統的一致性的企圖也就失敗了，因為元數學的一致性又得由元元數學來證明，后者的一致性又得由元元元數學來證明…）。

這里我們只關心羅素是如何想出這個絕妙的悖論的。還是對角線方法！我們羅列出所有的集合，S1,S2,S3…

  S1 S2 S3 …

S1 0 1 1 …

S2 1 1 0 …

S3 0 0 0 …

……

右側縱向列出所有集合，頂行橫向列出所有集合。0/1矩陣的(i,j)處的元素表示Si是否包含Sj，記為Si(j)?，F在我們只需構造一個新的0/1序列L，它的第i位與矩陣的(i,i)處的值恰恰相反：L(i)=1-Si(i)。我們看到，這個新的序列其實對應了一個集合，不妨也記為L，L(i)表示L是否包含Si。根據L的定義，如果矩陣的(i,i)處值為0（也就是說，如果Si不包含Si），那么L這個集合就包含Si,否則就不包含。我們注意到這個新的集合L肯定等于某個Sk（因為我們已經列出了所有的集合），L=Sk。既然L與Sk是同一集合，那么它們肯定包含同樣的元素，從而對于任意n，有L(n)=Sk(n)。于是通過令n=k，得到L(k)=Sk(k)，而根據L的定義，L(k)=1-Sk(k)。這就有Sk(k)=1-Sk(k)，矛盾。

通過抽象簡化以上過程，我們看到，我們構造的L其實是“包含了所有不包含它自身的集合的集合”，用數學的描述正是羅素悖論！

敏銳的你可能會注意到所有集合的數目是不可數的從而根本不能S1,S2…的一一列舉出來。沒錯，但通過假設它們可以列舉出來，我們發現了一個與可列性無關的悖論。所以這里的對角線方法其實可以說是一種啟發式方法。

同樣的手法也可以用到證明P(A)（A的所有子集構成的集合，也叫冪集）無法跟A構成一一對應上面。證明就留給聰明的你了。

（待續；此文的修訂版已收錄《暗時間》一書，由電子工業出版社2011年8月出版。作者于2009年7月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）