黃汝廣

（深圳南天電力有限公司，廣東 深圳 518000）

淺談反證法的可操作性——基于康托爾對角線法、哥德爾不完全性定理、圖靈停機問題及EPR悖論

黃汝廣

（深圳南天電力有限公司，廣東 深圳 518000）

一直以來，康托爾對角線法總是與反證法密不可分，然而反證法并不如通?？吹媚菢雍唵?。文章從操作主義的觀點，針對反證法提出了幾點可操作性的要求，然后分析了幾個著名的反證法論證，發(fā)現(xiàn)都不同程度地存在一些問題。由于不恰當?shù)碾[性假設，康托爾關于實數(shù)集不可數(shù)的證明是無效的。哥德爾為證明不完全性定理而引入的一個定理違反了矛盾律，并且他關于“可證”與“真”的區(qū)分實際上是陷入了循環(huán)論證。圖靈停機問題其實是比較晚近的提法，與圖靈的原始論文有較大差別，而且有些證明思路可能還或多或少地誤解了圖靈。最后，通過分析愛因斯坦的EPR悖論，進一步強調(diào)了假設唯一以及事實認定，對于反證法的重要性。

反證法；可操作性；隱性假設；事實；康托爾對角線；哥德爾不完全性定理；圖靈停機問題；EPR悖論

康托爾用來證明(0,1)不可數(shù)的對角線法，在數(shù)學史上可謂大名鼎鼎，有些文獻也稱之為逆對角線法或反對角線法[1]；之后，該方法在哥德爾不完全性定理以及圖靈停機問題不可解的證明中，也立下了汗馬功勞，同時還在悖論領域結(jié)出累累碩果，難怪有人贊譽其為永恒的金色對角線了。

然而，該方法自問世以來，也是一直爭議不斷。比如著名的哲學家維特根斯坦，就不承認康托爾與哥德爾的證明[2]。《古今數(shù)學思想》的作者克萊因，認為康托爾的證明，“在無意中陷入了引進說不清的定義的陷阱”，也即“一個要定義的東西是用包含著這個東西在內(nèi)的一類東西來定義的”。諾貝爾物理學獎得主布里奇曼則經(jīng)歷了一個轉(zhuǎn)變：開始時，他認同康托爾的證明，而30年后，當他從物理學經(jīng)驗中獲得了操作的觀點，重回到這一問題時，卻發(fā)現(xiàn)自己再也無法心悅誠服了[3]。

事實上，康托爾對角線法總是與反證法密不可分，因此筆者更愿意稱之為對角線反證法。而且，我們不要忘記，反證法本身也是很有爭議的，比如布勞威爾等直覺主義者就不承認反證法的有效性。

從操作主義的觀點看，一個有效的反證法或歸謬法論證，應該符合下列要求：(1)首先，當然是要承認矛盾律和排中律；（2）推理過程有效，并能在有限步驟內(nèi)完成，或者符合完全歸納法；(3)排除一切不當?shù)碾[性假設，也即待證命題的反命題應是推理中的唯一假設；(4)矛盾和假設必須有邏輯關系，一旦否定假設，矛盾應隨之消除；（5）矛盾的導出必須涉及不依賴于假設的事實（有些事實由于眾所周知，或者不言自明，在推理時經(jīng)常被省略，我們可稱之為“隱性”事實）。

后面三個條件的主要目的，是為了更好地確認矛盾的根源，是在于“假設”與“事實”不相容！當然，有人或許對（2）中的“有限步驟”不以為然，這可能是個見仁見智，也不用太糾結(jié)，只要保證推理有效即可。

下面，筆者將依據(jù)上述可操作性要求，對幾個著名的反證法論證進行分析。

1 康托爾實數(shù)集不可數(shù)定理

康托爾關于(0,1)不可數(shù)的論證，大致如下[4]：假設(0,1)可數(shù)，并將其用十進制無限小數(shù)表示，可得如下一個無窮序列——

然后再構(gòu)造數(shù)b=0.b1b2…bn…（當ann=1時，取bn=2；當ann≠1時，取bn=1）?？低袪栒J為，b屬于(0,1)卻不屬于該序列，矛盾，故(0,1)不可數(shù)。

說實話，筆者對康托爾所謂“矛盾”的斷言，是感覺有點莫名其妙：既然已經(jīng)構(gòu)造出了“屬于(0,1)卻不屬于該序列”的數(shù)b，那就應該稱之為“事實”才對，怎么反倒說是“矛盾”呢？

仔細分析上述論證，我們不難發(fā)現(xiàn)，康托爾的無窮小數(shù)序列只是對(0,1)的具體展示，兩者完全等價：因此，屬于(0,1)的一定也屬于該序列，這個事實是如此不言自明，以至于康托爾都沒有想到要交代一下。實際上，正是由于康托爾潛意識里一直堅持著這個“隱性”事實，他才認為“b屬于(0,1)卻不屬于該序列”是矛盾。

然而，這種意義上的矛盾，只能是意味著：根本不存在“屬于(0,1)卻不屬于該序列”的數(shù)b！不然的話，那就只能否定上述已經(jīng)植根于康托爾潛意識的“隱性”事實，也即承認該序列只是（0，1）的真子集，或者說并非屬于（0，1）的任何一個實數(shù)都能夠?qū)懗蔁o限小數(shù)的形式，整個實數(shù)理論都需要改寫了。

問題出在哪里？事實上，數(shù)b既屬于(0,1)也屬于該序列，根本不存在什么矛盾！很顯然，“b屬于(0,1)”的結(jié)論，是純粹由 b=0.b1b2…bn…自身形式?jīng)Q定的，應該不存在任何異議。那么，康托爾認為b“卻不屬于該序列”，是什么原因呢？這就要從構(gòu)造數(shù)b的對角線法說起。

筆者認為，單純依據(jù)對角線構(gòu)造法，康托爾只能說 b在對角線之外（不被貫穿），而不能進一步推論b“卻不屬于該序列”。要推論b“卻不屬于該序列”，以下一個隱性假設是不可或缺的：康托爾對角線能夠貫穿該序列的任何一個，也即可以遍歷整個序列，不存在漏項問題。在這里，康托爾大概是被對角線的無限延伸性給迷惑了，以為對角線的無限延伸性，可以確保其遍歷性。

然而事實并非如此。對于十進制小數(shù)，每一數(shù)位上都有十種不同的取值可能，這一事實注定對角線必然要漏項。先考慮屬于(0,1)的所有n位小數(shù)，其序列只有n列但遠遠不止n行，而對角線卻僅能貫穿n列n行，占總行數(shù)的比例很小；再令n趨于無窮大，即得到康托爾的無窮序列，但此時上述比例極限卻為0：換言之，對角線無限延伸時，其漏項率幾乎100%，而數(shù)b僅僅是其中之一；再形象點說，即b這條魚雖然漏在了對角線這張漁網(wǎng)之外，但它仍然留在作為池子的無窮序列里。

更有趣的是，即便從康托爾的基數(shù)理論看，其對角線也必然漏項：因為(0,1)的基數(shù)是?1，共有?1個元素，但對角線只能貫穿?0個；并且按康托爾的奇怪法則，應該有?0/?1=0，（?1-?0）/?1=1，即漏項率可達100%。

因此，康托爾用以否定“假設(0,1)可數(shù)”的所謂“矛盾”，純粹是子虛烏有，而且有點諷刺的是，按照康托爾的無窮集合理論，(0,1)反倒恰恰應該是可數(shù)的：在任一自然數(shù)前添加“0.”，可構(gòu)造一個與之對應的小數(shù)，對所有自然數(shù)如法炮制，則構(gòu)造出[0.1，1），它顯然可數(shù)；再把[0.1，1）內(nèi)所有數(shù)的第一位小數(shù)數(shù)字均減 1，則得[0，0.9）可數(shù)，（0，0.1）可數(shù)；故（0，1）=（0，0.1）∪[0.1，1）必然可數(shù)。

2 哥德爾不完全性定理

必須強調(diào)，康托爾對角線法針對的僅僅是數(shù)，如果說哥德爾不完全性定理的證明也使用了該方法，那它顯然是被推廣到命題了。對于數(shù)而言，盡管康托爾對角線法并不導致矛盾，然而將其推廣到命題，卻會導致否定式的自我指涉，其所得結(jié)果在本質(zhì)上是一個矛盾式，也即“A=非A”。事實上，塔斯基正是利用這個矛盾式來定義空集的，也就是說，絕不可能存在滿足它的任何東西；而哥德爾構(gòu)造的所謂不可判定公式，實質(zhì)上就是這樣一個矛盾式。

當然，問題遠不止于此，更加糟糕的是，在哥德爾的原始論文中，一個至關重要的所謂“定理Ⅴ”，其本身就會導致矛盾。該定理的內(nèi)容如下[5]：

“對于所有遞歸關系R(x1,...,xn)，存在著n元關系符號r（含有自由變元 u1,...,un），使得對于所有的數(shù)的 n元關系組(x1,...,xn)，我們有

其中，Bew(x)表示 x是可證公式，Neg(x)表示 x的否定，的具體含義其實并不重要，關鍵是它在式（3）式（4）中完全相同，如果用 A來代替，那么就有Bew[A]與Bew[Neg(A)]。事實上，哥德爾還利用式（3）式（4）推導出了另外兩對類似的式子（周訓偉認為其推導是無效的[6]），這里的簡化也同樣適用。

該定理的問題在于，哥德爾居然要求式（3）式（4）同時成立，而且從哥德爾后面的論證看，也必須要求如此；否則的話，就不可能得到他所期望的結(jié)論。但是，在哥德爾的具體推理中，式（3）式（4）同時成立，最終將導致“A”與“Neg(A)”同時可證，而在哥德爾的理論中，“可證”的一定是“真”的：這也就是說，“A”與“Neg(A)”同時為“真”，顯然違反了矛盾律！

有人爭辯說，式（3）式（4）都是假言命題（筆者認為也許值得商榷），只看后件沒有意義。當然，單純看一個假言命題，只談其后件確實沒有意義，不過這個辯解對于哥德爾是不成立的：因為哥德爾的目的并非定理本身，他是要將其用于推理，以得到最終所期望的結(jié)論；然而，要把該定理用于推理，首先必須確定一個遞推關系，但遞推關系一旦確定，就肯定了前件，那么推理的結(jié)果必然要肯定后件——此時，所謂的“后件”已經(jīng)實現(xiàn)了身份的轉(zhuǎn)變，即由單純假言命題的后件轉(zhuǎn)化為了有效推理的結(jié)論。

事實上，在“定理Ⅴ”中，R(x1,...,xn)和(x1,...,xn)之間的關系是非常重要的：假如兩者同時存在，則式（3）式（4）同時成立，但這最終會導致矛盾；假如兩者不能同時存在，則式（3）式（4）也不能同時成立，因而不會導致矛盾。然而哥德爾并未采納后者，因為如此一來，“17Genr不是可證的”與“Neg（17Genr）不是可證的”，就無法同時得到證明了，這會導致其最終目的落空；至于17Genr的具體含義，其實并不重要，這里只需明白：假如哥德爾的公理體系是完備的，則17Genr或Neg（17Genr）必定有一個可證；換言之，只要哥德爾證明17Genr與Neg（17Genr）均不可證，其公理體系就是不完備的，從而所謂的不完全性定理也就得到了證明。

另外，哥德爾的論證可能還涉及一個所謂的“萬能定理”，即“從一個矛盾出發(fā)，結(jié)果可以是任何東西”。盡管哥德爾原始論文中并未明確提及這一點，但按照內(nèi)格爾的說法，該定理與公理體系的一致性證明有密切關系：如果一個公理系統(tǒng)不是一致的，則每一個公式都是定理；反過來說，如果并非每個公式都是定理，則該公理系統(tǒng)是一致的[7]。

既然“定理Ⅴ”最終會導致矛盾，那么再加上這個所謂的“萬能定理”，哥德爾無論推出什么結(jié)論，就都不足為奇了。更直白點講，所謂不完全性定理，不過就是哥德爾先構(gòu)造出一個固有的邏輯矛盾，然后再嫁禍于公理體系稱其不完備而已。

退一步講，假如哥德爾不完全性定理確實成立，那么最高興的恐怕反倒應該是布勞威爾等人。因為如此一來，在哥德爾的公理體系內(nèi)，命題會存在真、假、不可判定三種情況，排中律不再成立，反證法無效。但哥德爾不完全性定理的證明，卻恰恰使用了反證法。

另外，哥德爾為了自圓其說，曾對“可證”與“真”做過如下區(qū)分——“可證”的都是“真”的，但“真”的未必都“可證”，因此存在不可證的真命題，“不可證”的未必都是“假”的。然而，這只不過是一個“循環(huán)論證”而已，因為上述辯解，實際上已經(jīng)預先假設了不完全性定理的正確性。而且，在哥德爾的證明中，關于命題的兩種不同劃分——真假值與是否可證——也被混淆在一起了。

3 圖靈停機問題不可判定定理

關于圖靈停機問題不可判定的證明，也與對角線法大有關系，依據(jù)張再躍的《數(shù)理邏輯》，論證如下[8]：

“假設停機問題可解，則存在能行過程H，對任意程序 Pe與輸入X，H能判斷 Pe對輸入X是否停機，設當 Pe對輸入X停機時有H( Pe,X)=1，當Pe對輸入X 不停機時有H( Pe,X)=0。利用H定義過程F：對任意自然數(shù)n，若H( Pe, n)=1，則F( n)=H( Pe,n )+1；若H( Pe, n)=0，則F( n)=0。因為過程H是能行的，所以過程F也是能行的，設計算F的程序編號為 e0，則F可表示為Pe0，即對任意n均有F( n)=Pe0(n)。接下來考察程序Pe0對輸入e0的情況：若停機，則H( Pe0,e0)=1，從而F( e0)=Pe0(e0)+1≠Pe0(e0)；若不停機，則Pe0(e0)無定義，而由H( Pe0,e0)=0，卻得F( e0)=0≠Pe0(e0)。上述矛盾表明，停機問題是不可解的?！?/p>

首先，既然“若H( Pe, n)=1，則F( n)=H( Pe, n)+1”，為什么不把H( Pe, n)=1代入，從而得出F( n)=1？（這里1和0是表示狀態(tài)，故只能按布爾代數(shù)計算。）實際上，在筆者看來，拿“若H( Pe, n)=1，則F( n)=1”來對應“若H( Pe, n)=0，則F( n)=0”，是再自然不過的事：簡而言之，即“F( n)=H( Pe, n)”！但如此一來，“若停機，則H( Pe0,e0)=1，從而F( e0)=Pe0(e0)+1≠Pe0(e0)”這個所謂的矛盾就不存在了。

其次，我們要問：按照定義，假如H( P1, n)=1，H( P2, n)=0，F(xiàn)( n)=？事實上，含兩個獨立變量的函數(shù)不太可能簡化為只有一個獨立變量！要避免這個問題，似乎只能這樣定義——對任意自然數(shù)n，F(xiàn)( n)=H( Pn, n)；但這就需要Pn與n有某種確定的函數(shù)關系，比如Pn=T(n)：也即任給一個自然數(shù) n，就可以通過函數(shù)T生成一個程序 Pn，而且沒有程序是它不能生成的。顯然，這個萬能的程序生成機T，只能是個假設而已；然而由于這個隱性假設，從邏輯上講，否定H就不再是唯一的選擇了，除非你能實實在在地構(gòu)造出這樣一個T。

不過，關于圖靈停機問題的通俗讀物，更傾向于這樣一種論證思路：利用萬能圖靈機H構(gòu)造一個新程序D，它以H的輸出為輸入，若輸入為1則不停機，若輸入為0則停機；再用H來判定D，則總是導致矛盾。

很顯然，這里的新程序D是一個自我否定的死循環(huán)。但我們要問的是，一個程序要如何界定？或者說，死循環(huán)真是程序嗎？按照筆者個人的看法，一個程序的核心應該是其功能，沒有任何功能的死循環(huán)，是錯誤而不是程序。

但我們也不妨退一步，假設死循環(huán)也是程序，那么在這個前提下，萬能圖靈機H就必須滿足如下條件：能夠判斷死循環(huán)是不可停機的，并且整個判斷過程不能觸發(fā)死循環(huán)。然而，以H的輸出為輸入的死循環(huán)D卻又必然會被觸發(fā)。要消除這里所謂的矛盾，除了否定“萬能圖靈機H”外，否定“死循環(huán)是程序”同樣可以達到目的，甚至我們還可以有第三個選擇——自我否定式的死循環(huán)不是程序。

事實上，假設存在萬能圖靈機H，即使一個程序P對輸入X不停機，我們也能將其改造為可停機的：先調(diào)用H判斷P對輸入X是否停機，如果判斷停機，則對P輸入X進行運算，并輸出最終結(jié)果；如判斷不停機，則不再對P輸入X，而直接輸出。

當然，萬能圖靈機H是不可能存在的，然而筆者認為這也是不可能被證明的，至少上述兩種證明都不能讓人滿意。我們知道，在熱力學上，不存在永動機其實只是能量守恒定律的一個等價表述；也許，在計算機領域，不存在萬能圖靈機應該被提升到公理的高度上來。

4 愛因斯坦的EPR悖論

這個著名悖論和康托爾對角線法之間，當然沒有任何關系，而且也沒有什么邏輯上的錯誤。但考察一下“EPR悖論”，對理解反證法是大有好處的：因為“假設”唯一與“事實”認定的重要性，在該悖論中體現(xiàn)的最為充分。

按照馬克斯·雅默《量子力學的哲學》的分析，“EPR悖論”的論證包含了四個前提假設[9]：（1）物理實在性判據(jù)，（2）理論完備性條件，（3）量子力學的有效性，（4）相互作用的定域性。那么邏輯上講，我們是可以否定上述任何一個假設，然而多個假設造成的結(jié)果，卻是愛因斯坦和玻爾兩人各說各話。

我們知道，愛因斯坦對量子力學的幾率解釋很不滿意，他不相信上帝在擲骰子。其實在“EPR悖論”之前，愛因斯坦主要是否定量子力學的有效性，但被玻爾一一化解了，不得已，才承認其有效性，轉(zhuǎn)而否定完備性：認為量子力學的幾率描述，是由于漏了一個還未知的隱變量，而考慮隱變量的完備理論，將給出確定性描述[10]。

實際上，“EPR悖論”的關鍵是愛因斯坦認為量子糾纏態(tài)不合理，但量子糾纏態(tài)又是量子力學的必然推論，因此在邏輯上，他或許更應該否定其有效性，而不是完備性：否則，所謂的不完備性似乎就不是相對于隱變量理論而言的，倒更像是指適用范圍的局限性（不過，這兩種情況并不容易區(qū)分）。

本質(zhì)上講，數(shù)學中的“事實”都是構(gòu)造性的，而物理上的“事實”卻必須要由實驗進行確認。在進行相關實驗之前，也即事實還未確定的前提下，愛因斯坦要堅持其一貫的信念，卻又不得不承認量子力學的有效性，那么否定完備性就是他唯一的選擇。

多年之后，雖然實驗并未站在愛因斯坦一邊，但他關于量子糾纏態(tài)的計算被證明是正確的。認為愛因斯坦被偏見所誤導，或者說玻爾比愛因斯坦更高明，這都是事后諸葛亮式的不公平之論：假如實驗站在了愛因斯坦這一邊，我們豈不是也可以同樣來議論玻爾？實際上，玻爾的選擇和愛因斯坦一樣，也僅僅是要維持自己的一貫信念，并不是基于更深刻的洞察：因為這個問題只能交由實驗來判決。最起碼，玻爾在這個問題上的反駁，是遠不如他之前反駁愛因斯坦的光子盒那樣有說服力。

5 結(jié)論

反證法并不是萬能的，即便承認矛盾律和排中律，其具體運用也不是我們通常想象的那么簡單，這里有太多的陷阱。

實際上，整個反證法的真正核心，是在于對“事實”的認定。然而，推理中隱藏的不當假設往往會把我們引入歧途，以致張冠李戴，把其實毫不相關的假設做了替罪羊。

當一個反證法論證結(jié)束后，我們其實不妨再問問自己：否定這個假設，矛盾真的就可以消除么？如果否定假設，矛盾仍然存在，其結(jié)果就導致我們通常所謂的悖論；然而，這恰恰表明，矛盾與假設實際上無任何關系，我們應該轉(zhuǎn)而審查論證中是否引入了不當?shù)碾[性假設。

當然，出問題的也未必是隱性假設，比如哥德爾居然就把一個固有邏輯矛盾作為了定理。至于“從一個矛盾出發(fā)，結(jié)果可以是任何東西”的所謂“萬能定理”，根本就違背了推理的可靠性原則要求，應該從邏輯學中剔除之。

最后，不得不說，所謂永恒的康托爾金色對角線，實際上只不過是一件皇帝的新衣而已，在反證法中根本無用武之地。因此，筆者十分贊同張金成先生的呼吁：必須重新審視許多有名的反證法證明，尤其當其結(jié)論比較奇怪，或者在論證中使用了康托爾對角線、實無窮、不可數(shù)、連續(xù)統(tǒng)等概念的時候，更需要慎重對待[11]。

[1] 張建軍.邏輯悖論研究引論(修訂版)[M].北京:人民出版社,2014.

[2] 莊朝暉.基于直覺主義對哥德爾不完全性定理的評論[J].廈門大學學報(社會科學),2008(2):77-84.

[3] 杜麗燕,余靈靈.布里奇曼文選[M].余靈靈,楊富芳,譯.北京:社會科學文獻出版社,2009.

[4] 杜珣.現(xiàn)代數(shù)學引論[M].北京:北京大學出版社,1998.

[5] 陳波.邏輯學讀本[M].北京:中國人民大學出版社,2009.

[6] 內(nèi)格爾,紐曼.哥德爾證明[M].陳東威,連永君,譯.北京:中國人民大學出版社,2008.

[7] 周訓偉.哥德爾不完全性定理的證明過程有誤[J].重慶工學院學報,2007,21(2):68-71.

[8] 張再躍,張曉如.數(shù)理邏輯[M]北京:清華大學出版社,2013.

[9] 馬克斯·雅默.量子力學的哲學[M].秦克誠譯.北京:商務印書館,2014.

[10] 李曉.淺談EPR悖論與量子糾纏[J].科技創(chuàng)新與應用,2015 (29):74.

[11] 張金成.超協(xié)調(diào)邏輯原理[M].北京:北京圖書出版社,2015.

Introduction to the operability of reduction to absurdity——based on cantor diagonal method, Godel's incompleteness theorem, Turing downtime problems and EPR paradox

For a long time, cantor diagonal method and reduction to absurdity is inseparable, however, reduction to absurdity is not as simple as we usually think. According to the operating point of view, this paper puts forward some operational requirements in view of the reduction to absurdity. Then analyzed the text of several famous argument, found that there are some problems in varying degrees. Due to improper implicit assumptions, it is invalid that cantor prove real number set is uncountable. To prove incompleteness theorem, an important theorem of Godel introduced is a violation of the law of contradiction, and his excuse is a circular argument. Turing halting problem is relatively recent, but some of the popular view may be more or less misunderstood Turing. Finally, through the analysis of Einstein EPR paradox, further emphasized in reduction, assuming that the only recognized the importance of with the fact, for the reduction to absurdity, Einstein EPR paradox shows that the only assumption is very important.

the reduction to absurdity; operability; implicit assumptions; facts; Cantor diagonal; Godel's incompleteness theorem; Turing downtime issues; EPR paradox

G642

A

1008-1151(2016)09-0094-04

2016-08-10

黃汝廣（1977－），男，山東人，深圳南天電力有限公司工程師。