1930年以后，數(shù)學(xué)邏輯開(kāi)始成為一個(gè)專門(mén)學(xué)科，得到了蓬勃發(fā)展。哥德?tīng)柕膬蓚�(gè)定理證明之后，希爾伯特的有限主義綱領(lǐng)行不通，證明論出現(xiàn)新的情況，主要有兩方面：通過(guò)放寬有限主義的限制來(lái)證明算術(shù)無(wú)矛盾性以及把證明形式化、標(biāo)準(zhǔn)化，這些主要是在三十年代完成。同時(shí)哥德?tīng)栆�進(jìn)遞歸函數(shù)，發(fā)展成遞歸論的新分支，開(kāi)始研究判定問(wèn)題。而哥德?tīng)柋救宿D(zhuǎn)向公理集合論的研究，從此出現(xiàn)公理集合論的黃金時(shí)代。五十年代模型論應(yīng)運(yùn)而生，它與數(shù)學(xué)有著密切聯(lián)系，并逐步產(chǎn)生積極的作用。

　　1、證明論

　　證明論又稱元數(shù)學(xué)，它研究數(shù)學(xué)的最基本活動(dòng)—證明的合理性問(wèn)題。研究這類數(shù)學(xué)基礎(chǔ)的問(wèn)題原來(lái)一直是哲學(xué)家的事，后來(lái)才成為數(shù)學(xué)家的事。這個(gè)轉(zhuǎn)變發(fā)生在1893年弗雷格發(fā)表《算術(shù)基礎(chǔ)規(guī)則》之時(shí)，后來(lái)希爾伯特和他的許多合作者使這種思想發(fā)展成一門(mén)學(xué)科—元數(shù)學(xué)，目的是用數(shù)學(xué)方法來(lái)研究整個(gè)數(shù)學(xué)理論。

　　要使數(shù)學(xué)理論成為一個(gè)合適的研究對(duì)象，就必須使之形式化。自從希爾伯特和阿克曼所著《理論邏輯綱要》第一版在1928年出版以來(lái)，在實(shí)踐中用得最多的是具有等式的一階謂詞演算(以及高階謂詞演算)。許多理論可以用一階理論來(lái)表述，它比較簡(jiǎn)單方便，具有多種形式。

　　從基礎(chǔ)的觀點(diǎn)來(lái)看，有兩個(gè)理論最為重要，因而研究也最多。這兩個(gè)理論就是形式化的皮亞諾算術(shù)理論與形式化的集合論。因?yàn)榇蠖鄶?shù)觀代數(shù)學(xué)理論都可以在這兩個(gè)理論范圍內(nèi)發(fā)展，所以這兩個(gè)理論的合理性如果得到證實(shí)，也就是向數(shù)學(xué)的可靠性邁進(jìn)了一大步。“希爾伯特計(jì)劃”無(wú)非就是要找到一個(gè)有限的證明步驟來(lái)證明算術(shù)的無(wú)矛盾性。

　　這里“有限”的意義是由法國(guó)年輕數(shù)學(xué)家厄布朗明確提出的，他認(rèn)為下列條件必須滿足：必須只討論確定的有限數(shù)目的對(duì)象及函數(shù)；這些對(duì)象及函數(shù)要能確定它們的真值產(chǎn)生協(xié)調(diào)一致的計(jì)算結(jié)果；一個(gè)對(duì)象如不指出如何構(gòu)造它就不能肯定其存在；必須永遠(yuǎn)不考慮一個(gè)無(wú)窮集體中所有對(duì)象的集合；一個(gè)定理對(duì)于一組對(duì)象都成立的意思是，對(duì)于每個(gè)特殊的對(duì)象，可以重復(fù)所講的普遍論證，而這普遍論證只能看成是結(jié)果特殊論證的原型。

　　數(shù)學(xué)理論的無(wú)矛盾性有了這種有限的、可構(gòu)造性的論證之后，任何人都可以放心了。希爾伯特計(jì)劃提出后，幾組數(shù)學(xué)家分別為實(shí)現(xiàn)它而努力：一組是希爾伯特及貝耐斯，以及阿克曼關(guān)于把數(shù)學(xué)理論形式化的研究，一組是馮·諾依曼關(guān)于算術(shù)無(wú)矛盾性的初步研究及哥德?tīng)柕牟煌耆�性定理以及甘岑的最后解決；還有一組是厄布朗及甘岑關(guān)于證明的標(biāo)準(zhǔn)形式等的研究。

　　厄布朗是法國(guó)天才的青年數(shù)學(xué)家，1931年8月在登阿爾卑斯山時(shí)遇難，年僅23歲。他對(duì)代數(shù)數(shù)論尤其是數(shù)理邏輯進(jìn)行過(guò)重要的研究工作，1929年他在博士論文《證明論研究》中提出他的基本定理。從某種意義上來(lái)講，這個(gè)定理是想把謂詞演算歸結(jié)為命題演算。由于前一理論是不可判定的，而后一理論是可判定的，因此這種歸結(jié)不可能是完全的。

　　但是，由于厄布朗局限于希爾伯特有限主義立場(chǎng)，他應(yīng)用的證明方法比較繞彎子。而且在1963年發(fā)現(xiàn)，他的證明中有漏洞，他的錯(cuò)誤很快就得到了彌補(bǔ)。厄布朗定理可以便我們?cè)谧C明中擺脫三段論法。他的許多結(jié)果，后來(lái)也為甘岑獨(dú)立地得出。

　　甘岑的自然演繹系統(tǒng)是把數(shù)學(xué)中的證明加以形式化的結(jié)果。他由此得出所謂“主定理”，即任何純粹邏輯的證明，都可以表示成為某種正規(guī)形式，雖然正規(guī)形式不一定是唯一的。為了證明這個(gè)主定理，他又引進(jìn)了所謂的式列(Sequenz)演算。

　　在普通的數(shù)學(xué)證明中，最常用則是三段論法，即如果A→B，且若A成立，則B成立。其實(shí)這就是甘岑推論圖中的“斷”。但是甘岑的主定理就是從任何證明圖中可以消除掉所有的“斷”。也就是：如果在一個(gè)證明中用到三段論法，那么定理表明，它也可以化成為不用三段論法的證明，也得到同樣的結(jié)論。

　　這個(gè)定理乍一看來(lái)似乎不可理解，其實(shí)正如甘岑所說(shuō)，一個(gè)證明圖中有三段論法實(shí)際上是“繞了彎子”，而不用三段論法是走直路。這種沒(méi)有三段論法的證明圖稱為“正規(guī)形式”，利用這沒(méi)有三段論法的證明圖稱為“正規(guī)形式”。利用這個(gè)主定理很容易得出許多重要結(jié)果，其中之一就是極為簡(jiǎn)單地證明“一階謂詞演算是無(wú)矛盾的”，而且能夠推出許多無(wú)矛盾性的結(jié)果。后來(lái)還可以用來(lái)證明哥德?tīng)柕耐耆�性及不完全性定理，�?dāng)然，最重要的事還是要證明算術(shù)的無(wú)矛盾性。

　　希爾伯特引進(jìn)證明論的目標(biāo)是證明整個(gè)數(shù)學(xué)的無(wú)矛盾性，其中最重要的是集合論的無(wú)矛盾性(至少ZF系統(tǒng)無(wú)矛盾)、數(shù)學(xué)分析的無(wú)矛盾性，最基本的當(dāng)然是算術(shù)的無(wú)矛盾性。哥德?tīng)柕牟煌耆�性定理說(shuō)明，用有限的辦法這個(gè)目標(biāo)是達(dá)不到的。由于哥德?tīng)柌煌耆�定理的沖擊，希爾伯特計(jì)劃需要修改。

　　有限主義行不通就要用非有限的超窮步驟。1935年，甘岑用超窮歸納法證明自然數(shù)算術(shù)形式系統(tǒng)的無(wú)矛盾性。其后幾年，他和其他人又給出了其他的證明。這種放寬了的希爾伯特計(jì)劃在第二次世界大戰(zhàn)之后發(fā)展成為證明論的分支，這些證明也推廣到分支類型論及其他理論。

　　甘岑在第二次大戰(zhàn)行將結(jié)束時(shí)去世，他的結(jié)果代表當(dāng)時(shí)證明論的最高成就，希爾伯特和貝納斯的《數(shù)學(xué)基礎(chǔ)》第二卷中總結(jié)了他的工作，但是證明論遠(yuǎn)遠(yuǎn)未能完成它的最初目標(biāo)。戰(zhàn)后隨著模型論和遞歸論乃至六十年代以來(lái)公理集合論的發(fā)展，證明論一直進(jìn)展不大。

　　五十年代中，日本數(shù)學(xué)家竹內(nèi)外史等人開(kāi)始對(duì)于實(shí)數(shù)理論(或數(shù)學(xué)分析)的無(wú)矛盾性進(jìn)行探索。因?yàn)閷?shí)數(shù)一開(kāi)始就同有理數(shù)的無(wú)窮集和有關(guān)，描述它的語(yǔ)言用一階謂詞演算就不夠了，所以第一步就要先把甘岑的工作推廣到高階謂詞演算中去。

　　1967年，日本年輕數(shù)學(xué)家高橋元男用非構(gòu)造的方法證明，單純類型論中也可以消去三段論法。由此可以推出數(shù)學(xué)分析子系統(tǒng)的無(wú)矛盾性。但是，由于證明不是構(gòu)造的，數(shù)學(xué)分析的無(wú)矛盾性至今仍然有待解決。

　　厄布朗及甘岑的結(jié)果雖然不可能完成希爾伯特計(jì)劃的最初目標(biāo)，但是由于其有限性、可構(gòu)造性的特點(diǎn)，現(xiàn)在已廣泛地應(yīng)用于機(jī)械化證明，成為這門(mén)學(xué)科的理論基礎(chǔ)。

　　證明論的方法對(duì)于數(shù)理邏輯本身有很大的推動(dòng)，特別是得出新的不可判定命題。最近，英國(guó)年輕數(shù)學(xué)家巴黎斯等人有了一項(xiàng)驚人的發(fā)現(xiàn)。他們發(fā)現(xiàn)了一個(gè)在皮亞諾算術(shù)中既不能證明也不能否證的純粹組合問(wèn)題，這不僅給哥德?tīng)柌煌耆�性定理一個(gè)具體的實(shí)例，而且使人懷疑要解決許多至今尚未解決的數(shù)論難題可能都是白費(fèi)力氣。這無(wú)疑開(kāi)辟了證明論一個(gè)完全新的方向。

　　2、遞歸論

　　遞歸論討論的是從形式上刻劃一個(gè)運(yùn)算或一個(gè)進(jìn)程的“能行”性這種直觀的觀念，也就是從原則上講，它們能機(jī)械地進(jìn)行而產(chǎn)生一個(gè)確定的結(jié)果。“能行”的這個(gè)概念含有可具體實(shí)現(xiàn)的、有效的、有實(shí)效的等等意思。法國(guó)數(shù)學(xué)家保萊爾首先在1898年他的函數(shù)論教科書(shū)中引進(jìn)了這個(gè)詞，他把數(shù)學(xué)的對(duì)象局限于能行的對(duì)象，這種主張實(shí)際上就是“法國(guó)經(jīng)驗(yàn)主義”。因?yàn)楹瘮?shù)論主要討論集合、函數(shù)、積分等等，從這種觀點(diǎn)產(chǎn)生出描述集合論、拜爾函數(shù)等概念。

　　遞歸論中所討論的函數(shù)是比較簡(jiǎn)單的。它討論有效可計(jì)算的函數(shù)，也就是遞歸函數(shù)。遞歸函數(shù)在歷史上曾從不同角度提出來(lái)，后來(lái)證明它們都是等價(jià)的。

　　1931年秋天，丘奇在普林斯頓開(kāi)了一門(mén)邏輯課，克林和羅塞爾當(dāng)時(shí)作為學(xué)生記了筆記。丘奇在講課中引進(jìn)了他的系統(tǒng)，并且在其中定義自然數(shù)。這就很自然引起一個(gè)問(wèn)題，在丘奇系統(tǒng)中如何發(fā)展一個(gè)自然數(shù)理論。于是克林開(kāi)始進(jìn)行研究，結(jié)果克林和丘奇得到一類可計(jì)算的函數(shù)，他們稱之為A可定義函數(shù)。

　　1934年春天，哥德?tīng)栐谄樟炙诡D做了一系列講演(克林和羅塞爾記了筆記)。在講演中，哥德?tīng)栆�進(jìn)了另外一套可以精確定義的可計(jì)算函數(shù)類，他稱為一般遞歸函數(shù)。據(jù)他講，他是受了厄布朗的啟發(fā)得到的。

　　這時(shí)自然出現(xiàn)了一個(gè)問(wèn)題。一般遞歸函數(shù)類是否包括所有能行可計(jì)算的函數(shù)，它是否與克林與丘奇研究的A可定義函數(shù)類重合。1934年春末，丘奇和哥德?tīng)栍懻撘话氵f歸函數(shù)問(wèn)題，結(jié)果丘奇明確提出他的“論點(diǎn)”，所有直覺(jué)上可看成能行可計(jì)算函數(shù)都是λ可定義函數(shù)，于是丘奇花了好幾個(gè)月反復(fù)思考。當(dāng)時(shí)克林表示懷疑，他認(rèn)為這論點(diǎn)不太可能是對(duì)的，他想如果從A可定義函數(shù)類用對(duì)角化方法可以得出另外一個(gè)能行可計(jì)算函數(shù)，那么它就不是A可定義的。但他又想到這事行不通。不久之后，丘奇和克林在1936年分別發(fā)表論文，證明A可定義函數(shù)類正好就是一般遞歸函數(shù)類。有了這個(gè)有力的證據(jù)，丘奇于是公開(kāi)發(fā)表他的“論點(diǎn)”。

　　也是在1936年，英國(guó)年輕數(shù)學(xué)家圖林發(fā)表了另外一篇重要文章，這標(biāo)志著所謂圖林機(jī)的產(chǎn)生。在這篇文章中，圖林也定義了一類可計(jì)算函數(shù)，也就是用圖林機(jī)可以計(jì)算的函數(shù)。同時(shí)，他也提出他的一個(gè)論點(diǎn)：“能行可計(jì)算的函數(shù)”與“用圖林機(jī)可計(jì)算的函數(shù)”是一回事。1937年圖林證明了用圖林機(jī)可計(jì)算的函數(shù)類與可定義函數(shù)類是一致的，當(dāng)然，也就和一般遞歸函數(shù)類相重合。這樣一來(lái)，丘奇的論點(diǎn)與圖林的論點(diǎn)就是一回事。當(dāng)時(shí)許多人對(duì)于丘奇的論點(diǎn)表示懷疑，由于圖林的思想表述得如此清楚，從而消除了許多人的疑慮，哥德?tīng)柧褪瞧渲幸晃弧�從這時(shí)起大家對(duì)于丘奇—圖林論點(diǎn)一般都抱支持的態(tài)度了。

　　與圖林同時(shí)，美國(guó)數(shù)學(xué)家波斯特也發(fā)表了一篇文章，類似于圖林的可計(jì)算函數(shù)，他的文章過(guò)于簡(jiǎn)短，一直到1943年波斯特才發(fā)表了第四個(gè)表述，結(jié)果證明他的與別人的也都一樣。

　　遞歸的概念并不難理解，它就是由前面的結(jié)果可以遞推得到后面的結(jié)果。哥德?tīng)柕热艘�進(jìn)的實(shí)際上是一般遞歸函數(shù)，一股遞歸函數(shù)都可以由原始遞歸函數(shù)算出來(lái)。

　　另一個(gè)復(fù)雜一些的概念稱為遞歸集合S，它的定義是存在一種能行的辦法來(lái)判斷任何正整數(shù)n是否屬于S。正數(shù)數(shù)集合是遞歸的當(dāng)且僅當(dāng)它與它在N中的補(bǔ)集都是遞歸可枚舉的。任何無(wú)窮遞歸可枚舉集都包含一個(gè)無(wú)窮遞歸集。但是，存在正整數(shù)的遞歸可枚舉集而不是遞歸集。

　　于是波斯特提出問(wèn)題：是否存在兩個(gè)遞歸可按舉但是非遞歸的集合，使得第一個(gè)集合相對(duì)于第二個(gè)是遞歸的，但第二個(gè)相對(duì)于第一個(gè)卻不是遞歸的。一直到十二年后的1956年，蘇聯(lián)人穆其尼克及美國(guó)人弗里德伯格才獨(dú)立地肯定地解決了這個(gè)問(wèn)題。

　　蘇聯(lián)數(shù)學(xué)家馬爾科夫在1947年發(fā)表《算法論》，首先明確提出算法的概念。但是它同以前定義的遞歸函數(shù)及可計(jì)算函數(shù)的計(jì)算過(guò)程都是等價(jià)的。這幾個(gè)定義表面上很不相同，并有著十分不同的邏輯出發(fā)點(diǎn)，卻全都證明是等價(jià)的。這件事看來(lái)決非巧合。它表明：所有這些定義都是同一個(gè)概念，而且這個(gè)概念是自然的、基本的、有用的。這就是“算法”概念的精確的數(shù)學(xué)定義。大家都接受了這個(gè)定義之后，判定問(wèn)題從我們平時(shí)直觀的概念也上升為精確的數(shù)學(xué)概念，判定問(wèn)題也成為一門(mén)數(shù)理邏輯的重要分支了。從這時(shí)起，判定問(wèn)題有突飛猛進(jìn)的發(fā)展。

　　判定問(wèn)題有了精確的數(shù)學(xué)表述之后，立即在數(shù)學(xué)基礎(chǔ)乃至整個(gè)數(shù)學(xué)中產(chǎn)生了巨大的影響。因?yàn)檫@時(shí)一些不可判定命題的出現(xiàn)，標(biāo)志著人們?cè)跀?shù)學(xué)歷史上第一次認(rèn)識(shí)到：有一些問(wèn)題是不可能找到算法解的。在過(guò)去，人們一直模模糊糊地覺(jué)得，任何一個(gè)精確表述的數(shù)學(xué)問(wèn)題總可以通過(guò)有限步驟來(lái)判定它是對(duì)還是錯(cuò)，是有解還是沒(méi)有解。找到不可判定問(wèn)題再一次說(shuō)明用有限過(guò)程對(duì)付無(wú)窮的局限性，它從另外一個(gè)角度反映了數(shù)學(xué)的內(nèi)在固有矛盾。

　　怎樣得到這些結(jié)果的呢？丘奇的論點(diǎn)發(fā)表之后，不難看出存在不可計(jì)算的函數(shù)，也就是非一般遞歸的函數(shù)。因?yàn)樗�有可能不同的算法共有可�?shù)無(wú)窮多(粗淺來(lái)講，算法都是用有限多個(gè)字來(lái)描述的)，可是所有數(shù)論函數(shù)的集合卻是不可數(shù)的。

　　不過(guò)，頭一個(gè)明顯的不可判定的結(jié)果是1936年丘奇得到的。他首先得到與λ可定義性有關(guān)的不可判定結(jié)果。然后，他把這個(gè)結(jié)果應(yīng)用到形式系統(tǒng)的判定問(wèn)題上，特別他證明，形式化的一階數(shù)論N是不可判定的。也是在1936年，丘奇證明純粹的謂詞演算也是不可判定的。當(dāng)時(shí)大家的反應(yīng)是：這種不完全性的范圍到底有多廣？

　　甚至于象丘奇這樣的數(shù)學(xué)家，也想找到一條出路能避開(kāi)哥德?tīng)柕慕Y(jié)果。比如說(shuō)，可以采用伺哥德?tīng)査�用的系統(tǒng)完全不同的其他的特殊系統(tǒng)。一旦算法的精確定義和丘奇論點(diǎn)出現(xiàn)之后，大家就認(rèn)識(shí)到躲不過(guò)哥德?tīng)柌煌耆�性定理的影響，可�?jì)算性和不完全性這兩個(gè)概念是緊密聯(lián)系在一起的。

　　實(shí)際上克林在1936年就證明了(作為丘奇論點(diǎn)的應(yīng)用)：甚至在能夠能行地認(rèn)出公理和證明的形式系統(tǒng)中，哥德?tīng)柕亩ɡ砣匀怀闪ⅰＯ�去量詞方法對(duì)許多理論行不通。一般的判定問(wèn)題是試圖找出一個(gè)能行的步驟，通過(guò)這個(gè)步驟可以決定什么東西具有某種指定的元數(shù)學(xué)特征。

　　在純粹邏輯演算的元理論中，有最明顯的一類判定問(wèn)題：對(duì)于給定的演算和給定類的公式，求出一個(gè)步驟，能夠在有限多步內(nèi)判定這類的任何特殊公式是否可以形式地推導(dǎo)出來(lái)。有些情形、問(wèn)題已經(jīng)得到肯定的解決，在另外一些情形，答案是否定的，可以證明不存在這樣一個(gè)步驟。這種否定的證明，特別對(duì)于數(shù)學(xué)理論，很大程度上依賴于遞歸論。

　　最早明確提出的數(shù)學(xué)判定問(wèn)題是希爾伯特第十問(wèn)題。他在1900年國(guó)際數(shù)學(xué)家大會(huì)上提出了著名的二十三個(gè)問(wèn)題，其中第十個(gè)問(wèn)題是：給定一個(gè)有任意多未知數(shù)的、系數(shù)為有理整數(shù)的丟番圖方程，設(shè)計(jì)一個(gè)步驟，通過(guò)它可以經(jīng)有限步運(yùn)算判定該方程是否有有理整數(shù)解。這個(gè)到1970年才被否定解決的問(wèn)題不僅解決了一個(gè)重大問(wèn)題，而且解決問(wèn)題過(guò)程中所得到的工具和結(jié)果對(duì)數(shù)理邏輯和數(shù)學(xué)發(fā)展有著極大影響，比如表示素?cái)?shù)的多項(xiàng)式，尤其與整個(gè)數(shù)理邏輯有關(guān)的是得出了一個(gè)更確切的哥德?tīng)柌煌耆�性定理�?/p>

　　現(xiàn)在我們來(lái)看希爾伯特第十問(wèn)題，為了清楚起見(jiàn)，我們考慮多項(xiàng)式方程，看看一般的多項(xiàng)式丟番圖方程的次數(shù)和未定元的數(shù)目是否可以降低。

　　1938年斯科蘭姆證明，任何丟番圖方程的次數(shù)可約化成次數(shù)小于等于4的方程；1974年馬蒂亞謝維奇和羅濱遜證明未定元的數(shù)目可約化成小于等于3。對(duì)于齊次方程，阿德勒在1971年證明，任何齊次方程可以能行地約化為二次齊次方程組，從而等價(jià)于一個(gè)四次齊次方程。對(duì)于一次方程早就有具體方法解丟番圖方程了。對(duì)于任意多未定元的二次方程，1972年西格爾也找到一個(gè)算法。四次方程不能判定，三次方程尚不知道。

　　解決丟番圖方程解是否存在的判定問(wèn)題的方法是引進(jìn)丟番圖集。我們把丟番圖方程的變?cè)�分成兩有一組解。每個(gè)丟番圖集合是遞歸可枚舉集。1970年，蘇聯(lián)大學(xué)生馬蒂亞謝維奇證明了每個(gè)遞歸可枚舉集也是丟番圖集合。這樣一來(lái)，由于存在不可判定的遞歸可枚舉集，所以存在一些特殊的丟番圖方程，使得對(duì)是否有解的判定問(wèn)題不可解。當(dāng)然對(duì)一般丟番圖方程的判定問(wèn)題就更不可解了。

　　另一個(gè)判定問(wèn)題是半群和群論中字的問(wèn)題，半解問(wèn)題是挪威數(shù)學(xué)家圖埃在1907年首先提出來(lái)的。問(wèn)題是對(duì)于一個(gè)半群，如果給定它的有限多生成元和有限多關(guān)系，那么能否找到一個(gè)方法來(lái)判定任何一個(gè)特殊的字是否等于單位元素。1947年，波斯特否定地解決了這個(gè)問(wèn)題。

　　群論中字的問(wèn)題更為重要，它是在1911年由德恩首先研究的，一直到1955年才由蘇聯(lián)數(shù)學(xué)家諾維科夫否定解決。這些結(jié)果給數(shù)學(xué)家指明了新的方向：不要妄圖去解決一大類問(wèn)題。不過(guò)對(duì)于更窄的一類的對(duì)象比如一類特殊的群，群的字問(wèn)題是可解的。