哥德爾不完全定理與數學認知的局限性

摘 要：哥德爾不完全定理揭示了數學認知的局限性，任何一個含有初等數論及一階謂詞邏輯的形式證明系統(tǒng)中，都存在這樣的命題，在此（封閉）系統(tǒng)中，依靠系統(tǒng)中的公理及一階邏輯演算方法，既不能證明該命題為真，也不能證明它為假。哥德爾在定理的證明中開啟可計算理論（遞歸論）之門，用現在成熟遞歸論的結果重新認識哥德爾不完全定理，使其變得更容易接受。近年來，機器學習取得突破性成果，由此引發(fā)有關人工智能是否可以完全代替人的思維能力等熱點問題討論。針對這一問題，如果承認“人工智能”是在一個交互計算系統(tǒng)中完成的，那么哥德爾不完全定理給出的是否定回答。

關鍵詞：數學認知；遞歸論；形式系統(tǒng)；哥德爾不完全定理

中圖分類號：O141.1

文獻標識碼： A

人類文明的進步體現在對自然和社會認知的推進，數學作為一種抽象的表達工具，在認知過程中起到重要作用。伴隨著數學的發(fā)展，人們對自然和社會發(fā)展規(guī)律具有更深刻的認識。在數學發(fā)展的歷史長河中，不同時代的數學家們都力圖想用一個統(tǒng)一的數學系統(tǒng)“一統(tǒng)天下”。早在古希臘時期，畢達哥拉斯學派認為“萬物皆數”（這里的數指有理數），結果發(fā)現直角邊長為1的等腰三角形的斜邊長（2）無法用有理數表示，由此產生第一次數學危機，從而導出無理數的產生[1]。用現在數學的眼光看，實數集R中有理數部分僅占很小的一部分，稀疏到測度為0。

到了二十世紀初，希爾伯特曾經有一個宏偉計劃：想為全部的數學提供一個（排除悖論在外）安全的理論基礎，讓所有數學證明過程能夠統(tǒng)一到一個形式系統(tǒng)中，按照一套通用規(guī)則，完成任意一個真命題的證明。不幸的是哥德爾不完全定理的出現，完全毀滅了這個美好的愿望。

1 哥德爾不完全定理概述

1931年，著名數學家哥德爾（Gdel）提出形式系統(tǒng)的不完全性理論，具體內容包含兩個定理[2-4]：

第一定理：任意一個包含一階謂詞邏輯與初等數論的形式系統(tǒng)，都存在一個命題，在這個系統(tǒng)中，既不能證明該命題為真，也不能證明它為假。

第二定理：如果形式系統(tǒng)S含有初等數論，當S無矛盾時，它的無矛盾性不能在S內證明。

初等數論是指建立在自然數集合N上的算術系統(tǒng)，其運算包括普通的加、減、乘、除法運算、其命題涉及數的性質、數之間的關系等。當然，其中的減法和除法需要作一些簡單限制，保證運算封閉。一階謂詞邏輯主要提供一個符號化描述語言及形式證明方法，以其合式公式描述一個合法的命題（判斷）陳述，以其形式推理描述一個命題的形式化證明過程。

形式系統(tǒng)需要一個描述語言L，初等數論指Peano算術系統(tǒng)，Peano算術系統(tǒng)中公理集是由真命題構成的一個遞歸集。在嚴格的數學語言表達下，哥德爾得到的不完全定理可陳述為[3]：存在語言L中的一個命題描述σ，滿足如下條件：

（a） 如果Peano算術系統(tǒng)是協(xié)調的，則σ不可證明；

（b） 如果Peano算術系統(tǒng)是ω-協(xié)調的，則σ不可證明。

其中，協(xié)調性指不存這樣的命題，在系統(tǒng)內能同時形式推導出命題本身及其否定命題。

哥德爾不完全理論被稱為20世紀最有意義的數學真理中最杰出、最具有代表性、最有震撼力的發(fā)現，是現代邏輯史上一座重要的里程碑。哥德爾不完全性定理告訴我們： 真與可證是兩個概念?？勺C的一定是真的，但真的不一定可證。通俗地說，真的只保證存在性，但可證你得給出證明過程。

哥德爾不完全性定理的影響遠遠超出了數學的范圍，它不僅使數學、邏輯學發(fā)生革命性的變化，引發(fā)了許多富有挑戰(zhàn)性的問題，并且涉及到邏輯學、哲學、語言學、計算機科學、宇宙學、乃至當今的熱點話題——人工智能。2002年8月17日，著名宇宙學家霍金在北京舉行的國際弦理論會議上發(fā)表了題為《哥德爾與M理論》的報告，認為建立一個單一的描述宇宙的大一統(tǒng)理論是不太可能的，這一推測也正是基于哥德爾不完全性定理。

從辯證的角度看：可解是相對的，依賴于形式規(guī)則系統(tǒng)；不可解是絕對的，即任何界定規(guī)則系統(tǒng)中，都存在這樣的問題，在該系統(tǒng)中不能機械地完成它的求解（證）過程。正如尺規(guī)問題的不可解性，僅用直尺和圓規(guī)不能三等分任意角，但適當修改規(guī)則是可以做到的[5]。從這個意義上講，哥德爾不完全定理的出現是合情合理的。

針對近年來機器學習取得的突破性成果而引發(fā)有關人工智能是否可以完全代替人的思維能力等熱點爭論問題，如果承認“人工智能”是在一個交互計算系統(tǒng)中完成的，那么哥德爾不完全定理給出的是否定回答。

2 數學危機推動數學認知

在數學史上，曾經發(fā)生過三次數學危機，每次數學危機從產生到解決都帶來一次數學認知的飛躍[1]。危機的出現，表明數學描述的認知規(guī)律尚有漏洞；危機的解決不僅是補漏，更重要的是將數學認知推進更深層次。

2.1 第一次數學危機： 無理數的發(fā)現

危機發(fā)生于大約公元前400年左右的古希臘時期，起源于根號2的發(fā)現，到公元前370年左右，以無理數的定義作為危機結束的標志。在此之前，古希臘畢達哥拉斯學派認為“萬物皆數”。源于對長度、重量和時間等簡單度量的需要，用整數商表示分數建立有理數體系，當時認為用有理數就能足夠表達了這些實際量度。但是，邊長為1的正方形的對角線的長度表達卻超出了有理數系。這沖擊著當時希臘人持有的“一切量都可以用有理數表示”的觀念，并建立無理數概念以解決第一次數學危機。現在看來：以直線上的點所表示數，除有理數表示的點之外，尚有更大更精彩的空間。

2.2 第二次數學危機：無窮小量的表述與微積分基礎定義的爭論

危機發(fā)生在十七、十八世紀，圍繞微積分誕生初期的基礎定義展開的爭論，這場危機最終完善了微積分的定義和與實數相關的理論系統(tǒng)，并基本解決了第一次數學危機時關于無窮計算的連續(xù)性問題。微積分的應用推向所有與數學相關的學科加以應用，得益于這場大討論。

其實，這次危機的萌芽出現在大約公元前450年，芝諾注意到由于對無限性的理解問題而產生的矛盾。芝諾的關于時空的有限與無限的四個悖論中，“兩分法”悖論最為著名：向著一個目的地運動的物體，首先必須經過路程的中點，然而要經過這點，又必須先經過路程的1/4點……，如此類推以至無窮。結論是：無窮是不可窮盡的過程，運動是不可能的。

芝諾揭示的矛盾是深刻而復雜的。經過許多人多年的努力，終于在17世紀晚期，形成了無窮小演算——微積分這門學科。在微積分大范圍應用的同時，有關微積分基礎的問題也越來越嚴重。關鍵問題就是無窮小量究竟是不是零？無窮小及其分析是否合理？由此而引起了數學界甚至哲學界長達一個半世紀的爭論，造成了第二次數學危機。

直到19世紀20年代，一些數學家開始關注微積分的嚴格基礎。從波爾查諾、阿貝爾、柯西、狄里赫利等人的工作開始，到威爾斯特拉斯、戴德金和康托的工作結束，經歷了半個多世紀，基本上解決了這些矛盾，為數學分析奠定了一個嚴格的基礎。

危機并不可怕，第二次數學危機不但沒有阻礙微積分的迅猛發(fā)展和廣泛應用，反而讓微積分在各個科技領域得到廣泛應用，解決了大量的物理問題、天文問題、數學問題，極大地推進了工業(yè)革命的進程。

2.3 第三次數學危機：集合論中悖論的發(fā)現

危機產生于十九世紀末和二十世紀初，當時正是數學空前興旺發(fā)達的時期。危機源于在康托爾對集合的描述性定義中被發(fā)現存在悖論。1897年，福爾蒂揭示了集合論中的第一個悖論。1902年，羅素發(fā)現了著名的羅素悖論，由集合概念本身就能直接描述這個悖論：定義滿足性質“x x”的對象全體構成一個集合A={x | x x }。那么，A作為一個對象，是否在集合A中？即“A∈A”是否成立？如果成立，那么它應該具有性質“AA”； 如果它不成立，就應該有“AA”，即A作為對象滿足集合A要求的特征性質，從而有“A∈A”。

由于數學的基礎描述工具是集合論，羅素悖論使整個數學大廈動搖。弗雷格在收到羅素的信之后，在他即將要出版的《算術的基本法則》中寫道：“一位科學家不會碰到比這更難堪的事情了，即在工作完成之時，它的基礎垮掉了，當本書等待印出的時候，羅素先生的一封信把我置于這種境地”。于是，終結了他十多年的刻苦鉆研。

解決第三次數學危機的方法是引入公理集合論，數學家們通過將集合的構造公理化，以排除上述類似集合的存在性。此后，希爾伯特曾經的宏偉計劃中，為建立安全的數學理論基礎，首先是將悖論排除在外。

7 Gdel不完全定理的簡化版本——遞歸公理系統(tǒng)的不完全性

本節(jié)給出哥德爾不完全定理的一個簡化版本——遞歸公理系統(tǒng)的不完全性，其不完全性定理的證明直接來自于“真命題集TP不是r.e.集”。實際上，由定理6.5，TP是一個產生集，系統(tǒng)中的不可證明命題不僅存在，而且可以由TP的產生函數對應的算法產生出該命題的編碼。從而否定回答第6節(jié)中的問題2：是否存在一個以真命題集TP的某個子集為公理的形式證明系統(tǒng)，在此系統(tǒng)中，可以證明TP中每一個命題？

在前述含有初等算術的一階邏輯語言L下，一個形式證明系統(tǒng)是一個序對（A，D），其中A是命題集S的一個子集，作為系統(tǒng)的公理集合；D是S中由公理可證明的形式證明下嚴格定義的集合。

考慮系統(tǒng)（A，D）滿足如下條件：

（1a） “證明”可有限描述，從而一個證明可以編碼成一個自然數；

（1b）如果公理集A是遞歸的，則問題 “p是來自公理集A某個命題σ的一個證明”是可判定的。

這樣的公理證明系統(tǒng)稱為遞歸公理證明系統(tǒng)。借助于編碼技術，集合A和D可以視為兩個自然數子集，則A和D都是遞歸集。

我們現在可以將第6節(jié)中的問題2解釋為：

（2a）A是一個遞歸集；

（2b）真命題集TP中的可證明的命題是指：利用公理A對其進行證明的命題，其證明可以“精準描述”。

在上述限制下，第6節(jié)中的問題2可以解釋為：是否有一個遞歸公理系統(tǒng)（A，D），真命題集TP每一個命題都是可證明命題？

形式上，在這種“精準描述證明”的意義下，考慮證明系統(tǒng)（A，D）的兩個基本性質：

（2b1） 協(xié)調性：不存在命題σ，使得σ，σ都可證。

（2b2）完全性：對任意的命題σ，或σ可證明，或σ可證明（σ可反駁）。

于是，不完全性是指：存在命題σ，σ和σ都不可證。即σ成真不可證明，成假也不可反駁。

由于可證明和可反駁都是需要算法支撐的，所以，哥德爾不完全定理在遞歸系統(tǒng)下考慮是合理而自然的。這樣一來，遞歸論的方法就能用上。

引理7.1 在任意一個遞歸證明系統(tǒng)（A，D）中，可證明命題集Pr是一個r.e.集。

證明 設Pr是真命題集TP中可證明命題集，由于證明都可以有限描述，則Pr是一個能行枚舉集。由于公理集A是遞歸集，則下面定義的謂詞M（x，y）是可判定謂詞。

9 結束語

哥德爾不完全定理所述的Peano算術系統(tǒng)是一個遞歸系統(tǒng)，借助于哥德爾編碼技術，將可以有限描述的命題對象、形式證明編碼成自然數，則問題討論轉移到自然數集上。于是，遞歸論中的工具和結論可以熟練運用。

本文基于遞歸論的一些基本結果解讀哥德爾不完全定理及其證明，文章中的相關結果主要來自文獻[3]。全文中一個關鍵性的遞歸可枚舉（r.e.）集合K={x：φx（x）↓}及其補集K作為產生集的性質起到重要作用，其中集合K本身的定義來自于對角線思想。

在證明過程中，結合可證明命題集關聯指標集Pr*，以及可反駁命題集關聯的指標集Ref*都是r.e.集的性質，利用伴隨于產生集K的產生函數的全可計算性，哥德爾不完全定理中所需要的自身及其否定均不可證明的命題σ：=m—K— 可以能行構造。

為方便讀者理解哥德爾不完全定理及其證明，文中比較全面地羅列了相關背景、基礎知識和處理方法，部分內容略顯多余和重復。

一個數學系統(tǒng)或體系總是在一套公理假設和一套形式推演規(guī)則下建立起來的，新結果的推導和結論的重用不斷地豐富這一體系，但其“根”還是在公理系統(tǒng)和推演規(guī)則，只要系統(tǒng)的協(xié)調性還在，一切形式推理的結果都連著這個“根”，哥德爾不完全定理表明：基于一個協(xié)調的封閉數學系統(tǒng)，其認知有其局限性。從辯證的角度看：可知亦可解的問題對象不過是相對的存在，不可知亦不可解的問題對象是絕對的存在。

哥德爾不完全定理的內涵及應用涉及領域較多，限于水平，作者不敢妄加評述。近年來，機器學習取得突破性成果，由此引發(fā)人工智能是否可以完全代替人的思維能力等熱點問題討論，針對這一問題，作者認為：如果承認“人工智能”是在一個交互計算系統(tǒng)中完成的，那么哥德爾不完全定理給出的是否定回答。

參考文獻：

[1]胡作玄.第三次數學危機[M]. 成都：四川人民出版社，1985.

[2]360百科.哥德爾不完全性定理[EB/OL].[2018-04-28].https：//baike.so.com/doc/6603875-6817662.html.

[3]CUTLAND N. Computability——An introduction to rescurisive function theorem[M]. Cambridge： Cambridge University Press， 1980.

[4]楊東屏. 哥德爾不完全定理的剖析[J]. 曲阜師范大學學報， 1993， 19（1）： 31-36.

[5]R·柯朗，H·羅賓. 什么是數學[M]. 左平，張飴慈，譯. 上海：復旦大學出版社，2004.

[6]ARORA S， BARAK B. Computational Complexity——An Modern Approach[M]. Cambridge： Cambridge University Press， 2009.

[7]WEIHRAUCH K. Computable Analysis——An Introduction[M]. Berlin： Springer-Verlag， 2000.

[8]M.戴維斯. 可計算性與不可解性[M].沈泓等，譯. 北京：北京大學出版社，1984.

（責任編輯：周曉南）