20世紀20年代，希爾伯特提出希爾伯特規劃，開創了證明論研究。此後幾年，包括希爾伯特在內的眾多數學家都樂觀地相信，用嚴格的方法重建數學基礎的嚐試很快就要一勞永逸地解決了。然而，一位年輕數學家——哥德爾——的一項偉大發現，改變了一切。
第一節哥德爾的發現
哥德爾（1906～1978），數學家，邏輯學家。
哥德爾生於奧匈帝國的布爾諾(今屬捷克斯洛伐克)，他有一個幸福的童年，但他膽小又愛吵鬧，在8歲時患了急性風濕熱，此後哥德爾就有了疑病性神經症傾向，很可能是這次患病的後果。哥德爾的才智很早就顯露出來。由於他經常提出各式各樣的問題，家裏人常稱他為“為什麼先生”(MrWhy)。在1916～1924年期間，他的學習成績優秀，特別是在數學、語言和神學方麵表現尤為突出。
1924年，他以近乎完美的成績結束了中學的學習，並進入維也納大學。在大學裏，哥德爾先是攻讀物理，後來在聽了數論課程之後，整數中蘊含的美使他意識到，數學才應是自己真正的追求。1926年哥德爾轉而攻讀數學。在大學中，哥德爾對哲學也很有興趣，實際上對哲學的探索始終貫穿著他的一生。他聽哲學教授講課，特別是經常參加維也納小組的活動。他的哲學觀點促使他對於數理邏輯進行深入的鑽研。
1929年夏季，當時隻有23歲的哥德爾證明了希爾伯特提出的一個重要問題，得出一階謂詞演算的完全性定理。由此，在1930年2月他獲得了博士學位。隨後，他進一步研究希爾伯特規劃，他希望用有限方法證明自然數形式係統的協調性問題。但他得到的是意想不到的結果。1930年9月7日在柯尼斯堡召開的數學討論會上，他第一次正式公布了他的偉大發現：第一不完全性定理。不久，他又證明了第二不完全性定理。
從1933年到1938年，哥德爾在維也納大學當講師。1939年9月，二戰爆發後他去了美國。1940年春，哥德爾成為普林斯頓高級研究院的成員。1943年後，哥德爾逐漸把注意力轉向數學哲學乃至一般的哲學問題，隻間或對數理邏輯做些工作。哥德爾中年時代在普林斯頓最親密的朋友是著名物理學家愛因斯坦。他們經常散步和閑談，直至愛因斯坦1955年去世。在哥德爾晚年，美籍華裔邏輯學家王浩是他最好的朋友之一，他們就數學基礎和哲學問題有過許多內容深刻的交談。
哥德爾是個天才，但他總疑心自己有心髒病，在他成年後，他因過度抑鬱和焦慮而數次進入療養院。他在飲食方麵很小心，年紀漸老後，他吃得越來越少，而且隻吃他妻子送來的食物，唯恐有人對他下毒。到64歲時，他的體重僅86磅（約39千克）。1977年當妻子動大手術住院後，他竟完全停止進食，次年1月因“人格紊亂”導致的“營養不良和身體機能的衰竭”與世長辭，死時的體重隻有約60磅。由於他在邏輯方麵的傑出貢獻，人們把他視為自亞裏士多德以來最偉大的邏輯學家。
1930年哥德爾思考並得出的研究結果發表於1931年。在題為“論《數學原理》及有關係統中的形式不可判定命題”的論文中，哥德爾證明了：任何一個足以包含自然數算術的形式係統，如果它是相容的，則它必定存在一個不可判定的命題，即存在某一命題S，使S與S的否定在這係統中都不可證。
哥德爾的這一結論後來被稱為哥德爾第一不完全性定理。那麼，他是如何證明這一深刻又令人驚歎不已的結果的呢？
哥德爾是如此表述自己的證明思路的：“從形式的觀點看，所謂證明實際上就是公式的一個有限序列。對於元數學來說，究竟用什麼東西來作為基本符號當然是沒有關係的。我們不妨就用自然數來作基本符號，如此，一個公式就是一個自然數的有限序列，而一個證明便是一個有限的自然數序列的序列。據此，元數學的概念（命題）也就變成了關於自然數或其序列的基本概念（命題），從而即可（至少是部分地）在對象係統本身的符號中得到表示，特別是人們可以證明‘公式’、‘證明’、‘可證公式’等都可在對象係統中加以定義。”簡而言之，哥德爾的思路就是構造出一種“自相關”：把自然數算術形式係統的問題轉化為關於自然數的問題，然後再用關於自然數的理論（算術係統自身）來討論這些問題。
在具體做法中，哥德爾引入的第一個關鍵思想是“配數法”，為形式算術係統的形式對象（如初始符號、公式、變形規則等）配給特殊的自然數，使得不同的自然數對應於不同的形式對象，這樣就把形式算術係統（TF）算術化了，使它成為一種直觀算術即一種T理論的內容。這相當於在TF與T之間做了一個映射：TF→T。
哥德爾再把元數學（Tm）也算術化，由於TF理論算術化了，因而關於TF理論的元理論命題就變成了關於這些相應的自然數及其彼此之間的算術關係的命題，它們當然也是直觀算術即T理論中的內容。這相當於在Tm與T之間做了一個映射：Tm→T。
進而，哥德爾證明了一些在T理論中“真”的命題，在形式算術係統TF中能找出相對應的可證公式。換而言之，同形式係統中的元數學命題相對應的直觀算術命題在形式係統中是“數字可表達的”。這相當於在T與TF之間做了一個映射：T→TF。與上一映射合在一起，我們得出元理論的命題可轉化為形式算術理論中的命題，元數學可被形式化。因而，元數學自身就在一個形式邏輯係統內部發展出來，外部被帶到了形式係統內部，從係統外看係統變成係統內的證明。這樣，形式算術係統實現了自相關。
在通過上述3個層次的映射，在幾個層次之間繞來繞去，並借助精湛的數學技巧後，哥德爾得出：形式算術係統中的某命題和它在元數學中的通過配數法和數字表達得出來的相應命題具有共同的真假。
下一步，哥德爾在形式係統內構造了一個命題G，使它所表達的元數學命題G′表示：“G在係統中是不可證的。”我們在原形式係統一致即無矛盾的前提下，對命題G進行考察。
首先，命題G是真的。用反證法，假設G為假，推知G′為假（根據上麵我們已經得出的G與它的元數學命題具有共同的真假性），進而推知G可證（根據G′的表示：“G在係統中是不可證的”為假），G為真（在形式係統內可以證明的命題自然是真的），與假設G為假矛盾。
其次，命題G不可證。這一點更易說明。由上知，命題G是真的，推知G′為真，由G′的表示，馬上得出G在係統中不可證。
再次，命題G的否定不可證。理由如下：命題G為真，則它的否定命題為假。而假的命題自然無法在形式係統中推出，即不可證。
因而命題G具有這樣的性質：它和它的否定在形式化係統中都不可證。為了強調這種性質，人們把G稱為不可判定命題。但這也不能強調得太過分，因為這種不可判定性隻與係統內部的可證性相關。從我們外部的觀點來看，G是真的。簡而言之，這意味著在一個無矛盾的形式係統內部存在著這樣的不可判定命題：它從係統外部看是真命題，但卻無法在係統內部獲得證明。
在希爾伯特形式主義方案中，除了無矛盾性，對數學理論體係還有另一個重要的要求是完全性。所謂完全性就是指：一個係統中所有的真命題在這個係統中都是可證的定理。有了完全性就能保證一個係統內所有命題可以一分為二：一部分是可證的，即真的命題；另一部分是可反駁的，即假的命題。這就意味著這個形式係統對數學理論做了完全的刻畫。而如果一個理論是不完全的，那就會把許多與之有關的真命題“漏”掉，這樣的理論體係當然不完善。通俗而言，無矛盾性是說理論中所有已證的命題都是真的，完全性是說所有真命題都可以在理論體係內得到證明。顯然，既滿足無矛盾性又滿足完全性的體係是好的。希爾伯特對一個好的公理化體係提出了這樣的要求（無矛盾性、完全性，還有一個相對而言不太重要的獨立性），他也確信，按照其計劃，人們會證明許多形式化係統滿足這些好的要求。
而哥德爾的上述第一不完全性定理卻表明，無矛盾性的形式化係統是不完全的。對於任何一個特定的包含了自然數公理係統的形式係統而言，都會有數學問題超越於它。另一方麵，從原則上講，每一個這樣的問題都會導向一個更強的係統，在該係統中能夠得到這個問題的解答。我們可以想象出更強係統的等級體係，每一個較強的係統都可以解決較弱的係統所遺留的問題。學會用更強的係統來解決棘手的問題，是哥德爾為數學家們留下的一份遺產。但這理論上無可爭議的設想，在何種程度上會成為數學實踐卻是模糊不清的。
哥德爾第一不完全性定理除了證明強邏輯係統也不可能把全部數學真理包含在內，從而摧毀了希爾伯特信念中的一方麵之外，還使人們對“真”的限度有了更深入的了解。在哥德爾第一不完全性定理提出後，人們清楚地意識到：雖然可證的是真，但真的卻並不一定可證。因而，就最本質的意義上說，哥德爾定理所做的無非是永遠地擊碎了真與證明同一的信念。簡單說，“真”大於“證明”。
哥德爾1930年最初公布自己這一發現的那次會議並非高級別的，幾乎所有聽到這一結果的人都沒有什麼反應，除了一個人——馮·諾伊曼。其實，諾伊曼在哥德爾之前已為證明算術一致性付出了極大努力。後來他曾向人講述過自己的一則故事：
一天的工作結束後，我會去上床睡覺，在夜裏我經常因為有了新的洞見而醒來……這時我會努力為算術一致性給出一個證明，但卻未能成功！有一天夜裏，我夢見了如何去克服我的困難，並且把我的證明繼續推進……第二天一大早，我就著手攻克難關，這一次我又沒有成功，又一次在夜裏身心疲憊地上床睡了覺，然後開始做夢。這回我又夢見了克服困難的方法，但是當我醒來之後……我看到那裏仍然有一道無法跨越的鴻溝。
當這道鴻溝被哥德爾跨過時，諾伊曼立刻明白了哥德爾所講的，而且在繼續思考後，他意識到在哥德爾結果基礎上再進一步，會得出一個對希爾伯特規劃而言更具摧毀性的結論。他馬上寫信向哥德爾通知自己的發現，很快哥德爾的回複寄到了。諾伊曼沮喪地知道了，哥德爾已經早於他將含有同一結論的論文拿去發表了。後來諾伊曼與哥德爾成了好朋友，正是他後來稱讚哥德爾是自亞裏士多德之後最偉大的邏輯學家。
哥德爾早於諾伊曼發表的——作為哥德爾第一不完全性定理的自然延續和深化——的結果，後來以哥德爾第二不完全性定理著稱。它表明的是：如果一個足以包含自然數算術的公理係統是無矛盾的，那麼這種無矛盾性在該係統內是不可證明的。這意味著，對希爾伯特所希望證明的自然數係統的無矛盾性而言，答案完全是否定的：即便初等算術係統是協調的，那麼這種協調性也不可能在算術係統內證明。希爾伯特綱領走到了盡頭。多年後，法國傑出數學家韋伊就此評論道：因為數學具有一致性，所以上帝與我們同在；因為我們不能證明這一點，所以魔鬼亦與我們同在。