哥德爾的不完備性定理震撼了20世紀數學界的天空，其數學意義顛覆了希爾伯特的形式化數學的宏偉計劃，其哲學意義直到21世紀的今天仍然不斷被延伸到各個自然學科，深刻影響著人們的思維。圖靈為了解決希爾伯特著名的第十問題而提出有效計算模型，進而作出了可計算理論和現代計算機的奠基性工作，著名的停機問題給出了機械計算模型的能力極限，其深刻的意義和漂亮的證明使它成為可計算理論中的標誌性定理之一。丘齊，跟圖靈同時代的天才，則從另一個抽象角度提出了lambda算子的思想，與圖靈機抽象的傾向於硬件性不同，丘齊的lambda算子理論是從數學的角度進行抽象，不關心運算的機械過程而只關心運算的抽象性質，只用最簡潔的幾條公理便建立起了與圖靈機完全等價的計算模型，其體現出來的數學抽象美開出了函數式編程語言這朵奇葩，Lisp、Scheme、Haskell… 這些以抽象性和簡潔美為特點的語言至今仍然活躍在計算機科學界，雖然由於其本質上源於lambda算子理論的抽象方式不符合人的思維習慣從而註定無法成為主流的編程語言，然而這仍然無法妨礙它們成為編程理論乃至計算機學科的最佳教本。而誕生於函數式編程語言的神奇的Y combinator至今仍然讓人們陷入深沉的震撼和反思當中…然而，這一切的一切，看似不很相關卻又有點相關，認真思考其關係卻又有點一頭霧水的背後，其實隱隱藏著一條線，這條線把它們從本質上串到了一起，而順著時光的河流逆流而上，我們將會看到，這條線的盡頭，不是別人，正是隻手撥開被不嚴密性問題困擾的19世紀數學界陰沉天空的天才數學家康托爾。
康托爾創造性地將一一對應和對角線方法運用到無窮集合理論的建立當中，這個被希爾伯特稱為“誰也無法將我們從康托爾為我們創造的樂園中驅逐出去”、被羅素稱為“19世紀最偉大的智者之一”的人，他在集合論方面的工作終於驅散了不嚴密性問題帶來的陰霾，彷彿一道金色的陽光刺破烏雲，19世紀的數學終於看到了真正嚴格化的曙光，數學終於得以站在了前所未有的堅固的基礎之上；集合論至今仍是數學裡最基礎和最重要的理論之一。而康托爾當初在研究無窮集合時最具天才的方法之一——對角線方法——則帶來了極其深遠的影響，其純粹而直指事物本質的思想如洪鐘大呂般響徹數學和哲學的每一個角落。
歌德爾的不完備性定理，圖靈的停機問題，lambda算子理論中神奇的Y combinator、乃至著名的羅素悖論、理髮師悖論等等，其實都源自這個簡潔、純粹而同時又是最優美的數學方法，反過來說，從康托爾的對角線方法出發，我們可以輕而易舉地推導出哥德爾的不完備性定理，而由後者又可以輕易導出停機問題和Y combinator，實際上，我們將會看到，後兩者也可以直接由康托爾的對角線方法導出。尤其是Y combinator，這個形式上繞來繞去，本質上捉摸不透，看上去神秘莫測的算子，其實只是一個非常自然而然的推論，如果從哥德爾的不完備性定理出發，它甚至比停機問題還要來得直接簡單。總之，你將會看到這些看似深奧的理論是如何由一個至為簡單而又至為深刻的數學方法得出的，你將會看到最純粹的數學美。
康托爾，全名格奧爾格·康托爾（Georg Cantor，1845年3月3日—1918年1月6日），康托爾是19世紀末20世紀初德國偉大的數學家，集合論的創立者。是數學史上最富有想象力，最有爭議的人物之一。19世紀末他所從事的關於連續性和無窮的研究從根本上背離了數學中關於無窮的使用和解釋的傳統，從而引起了激烈的爭論乃至嚴厲的譴責。然而數學的發展最終證明康托爾是正確的。他所創立的集合論被譽為20世紀最偉大的數學創造，集合概念大大擴充了數學的研究領域，給數學結構提供了一個基礎，集合論不僅影響了現代數學，而且也深深影響了現代哲學和邏輯。他的著作有：《G·康托爾全集》1卷及《康托爾—戴德金通信集》等。
要評價康托爾的影響，首先需要知道他做了什麼。
他的主要貢獻在於兩個：
1，集合論
2，超窮數理論。
這兩個都對應著同一個元數學對象，那就是“無窮”。
介紹下背景和影響：
所謂“集合論”
集合論在19世紀誕生的基本原因，來自數學分析基礎的批判運動。數學分析的發展必然涉及到無窮過程，無窮小和無窮大這些無窮概念。在18世紀，由於無窮概念沒有精確的定義，使微積分理論不僅遇到嚴重的邏輯困難，而且還使實無窮概念在數學中信譽掃地。19世紀上半葉，柯西給出了極限概念的精確描述。在這基礎上建立起連續、導數、微分、積分以及無窮級數的理論。正是這19世紀發展起來的極限理論相當完美的解決了微積分理論所遇到的邏輯困難。但是，柯西並沒有徹底完成微積分的嚴密化。柯西思想有一定的模糊性，甚至產生邏輯矛盾。19世紀後期的數學家們發現使柯西產生邏輯矛盾的問題的原因在奠定微積分基礎的極限概念上。嚴格地說柯西的極限概念並沒有真正地擺脫幾何直觀，確實地建立在純粹嚴密的算術的基礎上。於是，許多受分析基礎危機影響的數學家致力於分析的嚴格化。在這一過程中，都涉及到對微積分的基本研究對象——連續函數的描述。在數與連續性的定義中，有涉及關於無限的理論。因此，無限集合在數學上的存在問題又被提出來了。這自然也就導致尋求無限集合的理論基礎的工作。總之，為尋求微積分徹底嚴密的算術化傾向，成了集合論產生的一個重要原因。
康託在柏林大學的導師是外爾斯托拉斯，庫曼和克羅內克。庫曼教授是數論專家，他以引進理想數並大大推動費馬大定理的研究而舉世聞名。克羅內克是一位大數學家，當時許多人都以得到他的讚許為榮。外爾斯托拉斯是一位優秀教師也是一位大數學家。他的演講給數學分析奠定了一個精確而穩定的基礎。例如，微積分中著名的觀念就是他首先引進的。正是由於這些人的影響，康托爾對數論較早產生興趣，並集中精力對高斯所留下的問題作了深入的研究。他的畢業論論文就是關於++=0的素數問題的。這是高斯在《算術研究》中提出而未解決的問題。這片論文寫得相當出色，它足以證明作者具有深刻的洞察力和對優秀思想的繼承能力。然而，他的超窮集合論的創立，並沒有受惠於早期對數論的研究。相反，他很快接受了數學家海涅的建議轉向了其他領域。海涅鼓勵康托爾研究一個十分有趣，也是較困難的問題：任意函數的三角級數的表達式是否唯一？對康托爾來說這個問題是促使他建立集合論的最直接原因。函數可用三角級數表示，最早是1822年傅立葉提出來的。此後對於間斷點的研究，越來越成為分析領域中引人注目的問題，從19世紀30年代起，不少傑出的數學家從事著對不連續函數的研究，並且都在一定程度上與集合這一概念掛起了鉤。這就為康托爾最終建立集合論創造了條件。1870年，海涅證明，如果表示一個函數的三角級數在區間[-π,π]中去掉函數間斷點的任意小鄰域後剩下的部分上是一致收斂的，那麼級數是唯一的。至於間斷點的函數情況如何，海涅沒有解決。康托爾開始著手解決這個以如此簡潔的方式表達的唯一性問題。於是他跨出了集合論的第一步。
康托爾一下子就表現出比海涅更強的研究能力。他決定儘可能多地取消限制，當然這會使問題本身增加難度。為了給出最有普遍性的解，康托爾引進了一些新的概念。在其後的三年中，康託先後發表了五篇有關這一題目的文章。1872年當康托爾將海涅提出的一致收斂的條件減弱為函數具有無窮個間斷點的情況時，他已經將唯一性結果推廣到允許例外值是無窮集的情況。康托爾1872年的論文是從間斷點問題過度到點集論的極為重要的環節，使無窮點集成為明確的研究對象。
集合論裡的中心，難點是無窮集合這個概念本身。從希臘時代以來，無窮集合很自然地引起數學家們和哲學家們的注意。而這種集合的本質以及看來是矛盾的性質，很難象有窮集合那樣來把握它。所以對這種集合的理解沒有任何進展。早在中世紀，人們已經注意到這樣的事實：如果從兩個同心圓出發畫射線，那麼射線就在這兩個圓的點與點之間建立了一一對應，然而兩圓的周長是不一樣的。16世紀，伽俐略還舉例說，可以在兩個不同長的線段ab與cd之間建立一一對應，從而想象出它們具有同樣的點。
集合論在誕生的基本原因，來自數學分析基礎的批判運動。數學分析的發展必然涉及到無窮過程，無窮小和無窮大這些無窮概念，但是這些概念數學家並沒有準確的在元數學層面去“定位”他，雖然數學分析理論在此時已經初見規模，但是不解決這個理論基礎問題，總歸體系不明。柯西在《極限理論》解決了這些基本的邏輯困難。但是並沒有徹底完成“分析”的嚴密化，有一定的模糊性，因為沒有真正拜託幾何直觀，不深入到基礎中去，無法達成良好自恰。。。
而讓康托爾開始深入到“分析”領域的其實是這樣與個問題：
“任意函數的三角級數的表達式是否唯一？”
海涅證明了“定義區間裡除去間斷點任意小鄰域保持一直收斂”。。但間斷點的情況如何呢？
康托爾做了如下理論建立：點集論，也就是將無窮點集作為對象。
而這種思想的影響大概在以下幾點：
1，一個無窮集合能夠和它的部分構成一一對應，恰恰反應了無窮集合的一個本質特徵。
2，確立了實數不可數性質。
3，n維連續空間與一維連續統具有相同的基數。
4，給出了超窮數的一個完全一般的理論，其中藉助良序集的序型引進了超窮序數的整個譜系。
5，康托爾對於“無窮”在元數學上的立場和認識，讓哲學認識論領域的“千年老坑”被炸了出來，正愁沒事幹的哲學家們瞬間找到目標了，大量關於集合論本身的數學哲學討論，以及其他哲學領域的討論被炸了出來，這也算是元數學研究對於哲學命題方向的一次指導。
6，這種新的理論概念已經滲透到代數、拓撲和分析等許多數學分支以及物理學和質點力學等一些自然科學部門，也引起了哲學方法論的一些討論。
而“超限數理論”進一步擴充了他的研究，作用在於：
改變了早期用公理定義(序)數的方法，採用集合作為基本概念。他給出了超限基數和超限序數的定義，引進了它們的符號；依勢的大小把它們排成一個“序列”；規定了它們基本運算。
擴充過後的集合論基礎又引起廣泛探討，反對者如，數學界：克羅內克等哲學界：魏爾等等一大堆。
然後就是喜聞樂見的哲學家們的“打臉”時間：
布拉裡-福蒂悖論
序數按照它們的自然順序形成一個良序集。這個良序集合根據定義也有一個序數Ω，這個序數Ω由定義應該屬於這個良序集。可是由序數的定義，序數序列中任何一段的序數要大於這段之內的任何序數，因此Ω應該比任何序數都大，從而又不屬於Ω。
康托爾最大基數悖論
證明: 假定相反情況，並設 C 為最大基數。則(在馮·諾伊曼基數公式化中) C 是一個集合因此有冪集 2C通過康托爾定理，它有嚴格的大於 C 的勢。但是根據定義 C 的勢是 C 自身，所以我們展示了一個大於被假定為最大基數的 C 的勢(就是 2C)。有這個矛盾達成了這樣的基數不存在。
羅素悖論
Q∈P 還是 Q?P？ 若Q∈P，則根據第一類集合的定義，必有Q∈Q，而Q中的任何集合都有A?A的性質，因為Q∈Q，所以Q?Q，引出矛盾。若Q?P，根據第二類集合的定義，A?A，而P中的任何集合都有A∈A的性質，所以Q∈P，還是矛盾。
然後，這些悖論和質疑直接引起著名三次數學危機就開始爆發了，而這次危機的在數學體系內的解決方案就是“公理化”。
康托爾支持者，以希爾伯特為代表，開始解決這些事情。
戴德金及皮亞諾對算術及實數理論進行公理化，推動了公理化運動。
而公理化運動的最大成就則是希爾伯特在1899年對於初等幾何的公理化。
但是在數學體系內部，公理化可以解決這個問題，元數學上也可繼續研究。但是這給哲學家又留下了一個目前沒有共識的“千年老坑。。
但是康托爾總歸給僅僅著眼於瑣碎問題的現代數學家們給了一個更為整體，更為基礎更為完善的數學基礎體系和一個更為有遠見的數學思維方式這便是康托爾作為現代數學基礎建築師的成就。
1872年康托爾在瑞士結識了J.W.R.戴德金，此後時常往來並通信討論。1873年他估計，雖然全體正有理數可以和正整數建立一一對應，但全體正實數似乎不能。他在1874年的論文《關於一切實代數數的一個性質》中證明了他的估計，並且指出一切實代數數和正整數可以建立一一對應，這就證明了超越數是存在的而且有無窮多。在這篇論文中，他用一一對應關係作為對無窮集合分類的準則。
在整數和實數兩個不同的無窮集合之外，是否還有更大的無窮?從1874年初起,康托爾開始考慮面上的點集和線上的點集有無一一對應。經過三年多的探索，1877說，“我見到了，但我不相信。”這似乎抹煞了維數的區別。論文於1878年發表後引起了很大的懷疑。P.D.G.杜布瓦－雷蒙和克羅內克都反對，而戴德金早在1877年7月就看到,不同維數空間的點可以建立不連續的一一對應關係，而不能有連續的一一對應。此問題直到1910年才由L.E.J.布勞威爾給出證明。
康托爾在1878年這篇論文裡已明確提出“勢”的概念(又稱為基數)並且用“與自身的真子集有一一對應”作為無窮集的特徵。
著名的康托爾完全集是這樣構成的：給出閉區間[0,1],把它三等分,第一次刪去中間的那個子集(1/3,2/3),剩下[0,1/3]和[2 /3,1],再把這兩個閉區間三等分,第二次刪去中間的子集(1/9,2/9)、（7/9，8/9），剩下[0,1/9]、[2/9,1/3]、[2 /3,7/9]、[8/9,1]，如此繼續下去直至無窮，那麼最終剩下的集合的測度可用下式計算：
1-（1/3+2/9+4/27+……）=1-（1/3）/（1-2/3）=0康托爾由此得出，剩下的集合是測度為0的連續基數集，這就是康托爾完全集。
同樣給出[0,1],把它三等分,假使我們第一次刪去[0,1/3),(2/3,1]剩下[1/3,2/3],第二次刪去[1/3,4/9),(5 /9,2/3]剩下[4/9,5/9],如此繼續下去直至無窮,那麼剩下的區間連同[0,1]構成一個區間套序列,根據區間套原理有且僅有一點包含於區間 套序列中,在這個“不斷刪去”的過程中，中間的子集收縮成一點。
回過頭再來考察康托爾完全集，可發現位於區間兩頭的子集也發生同樣的收縮而成為一點，其他子集均勻分佈於[0,1]中[第一次刪去的(1/3,2/3)較 大],所以他們也同樣收縮成一點,這樣的話,最終剩下的康托爾完全集就是一個離散的連續基數集（基數等於2^N,用三進制編碼，與實數等勢）。要構造康託 爾完全集也可取五等分、七等分……由此得到的集合的基數是2^N和6^N,只不過五等分,七等分導致的收斂較快:
五等分 1-(1/5+4/25+16/125+……）=1-（1/5）/（1-4/5）=0七等分 1-（1/7+6/49+36/343+……）=1-（1/7）/（1-6/7）=0勒貝格測度是賦予歐幾里得空間的子集的一個長度、面積、或者體積的標準方法，可以賦予一個體積的集合被稱為勒貝格可測，可測集的體積即為測度。由以上描述可以知道，康托爾完全集中的所有子集收縮成一點，並離散的分佈於[0,1]中，由此康托爾集稱為一個勒貝格測度為零的不可數集的典型範例。
集合論裡的中心，難點是無窮集合這個概念本身。從希臘時代以來，無窮集合很自然地引起數學家們和哲學家們的注意。而這種集合的本質以及看來是矛盾的性質，很難象有窮集合那樣來把握它。所以對這種集合的理解沒有任何進展。早在中世紀，人們已經注意到這樣的事實：如果從兩個同心圓出發畫射線，那麼射線就在這兩個圓的點與點之間建立了一一對應，然而兩圓的周長是不一樣的。16世紀，伽俐略還舉例說，可以在兩個不同長的線段ab與cd之間建立一一對應，從而想象出它們具有同樣的點。
他又注意到正整數可以和它們的平方構成一一對應，只要使每個正整數同它們的平方對應起來就行了:
1 2 3 4 … … n … …
1 4 9 16 … … n2… …
但這導致無窮大的不同的“數量級”，伽俐略以為這是不可能的.因為所有無窮大都一樣大。
不僅是伽俐略，在康托爾之前的數學家大多不贊成在無窮集之間使用一一對應的比較手段，因為它將出現部分等於全體的矛盾.高斯明確表態：“我反對把一個無窮量當作實體，這在數學中是從來不允許的。無窮只是一種說話的方式… …”柯西也不承認無窮集合的存在。他不能允許部分同整體構成一一對應這件事。當然，潛無窮在一定條件下是便於使用的，但若把它作為無窮觀則是片面的。數學的發展表明，只承認潛無窮，否認實無窮是不行的。康托爾把時間用到對研究對象的深沉思考中。他要用事實來說明問題，說服大家。康托爾認為，一個無窮集合能夠和它的部分構成一一對應不是什麼壞事，它恰恰反應了無窮集合的一個本質特徵。對康托爾來說，如果一個集合能夠和它的一部分構成一一對應，它就是無窮的。它定義了基數,可數集合等概念。並且證明了實數集是不可數的，代數數是可數的。康托爾最初的證明發表在1874年的一篇題為《關於全體實代數數的特徵》的文章中,它標誌著集合論的誕生。
隨著實數不可數性質的確立，康托爾又提出一個新的，更大膽的問題。1874年，他考慮了能否建立平面上的點和直線上的點之間的一一對應。從直觀上說，平面上的點顯然要比線上的點要多得多。康託自己起初也是這樣認識的。但三年後，康託宣佈：不僅平面和直線之間可以建立一一對應，而且與一般的n維連續空間也可以建立一一對應！這一結果是出人意外的。就連康託本人也覺得“簡直不能相信”。然而這又是明擺著的事實，它說明直觀是靠不住的，只有靠理性才能發現真理，避免謬誤。
既然n維連續空間與一維連續統具有相同的基數，於是，康托爾在1879到1884年間集中於線性連續統的研究，相繼發表了六篇系列文章，彙集成《關於無窮的線性點集》。前四篇直接建立了集合論的一些重要結果，包括集合論在函數論等方面的應用。其中第五篇發表於1883年，它的篇幅最長，內容也最豐富。它不僅超出了線性點集的研究範圍，而且給出了超窮數的一個完全一般的理論，其中藉助良序集的序型引進了超窮序數的整個譜系。同時還專門討論了由集合論產生的哲學問題，包括回答反對者們對康托爾所採取的實無窮立場的非難。這篇文章對康托爾是極為重要的。1883年，康托爾將它以《集合論基礎》為題作為專著單獨出版。
《集合論基礎》的出版，是康托爾數學研究的里程碑。其主要成果是引進了作為自然數系的獨立和系統擴充的超窮數。康托爾清醒地認識到，他這樣做是一種大膽的冒進。“我很瞭解這樣做將使我自己處於某種與數學中關於無窮和自然數性質的傳統觀念相對立的地位，但我深信，超窮數終將被承認是對數概念最簡單、最適當和最自然的擴充。”《集合論基礎》是康托爾關於早期集合理論的系統闡述，也是他將做出具有深遠影響的特殊貢獻的開端。
康托爾於1895年和1897年先後發表了兩篇對超限數理論具有決定意義的論文。在該文中,他改變了早期用公理定義(序)數的方法，採用集合作為基本概念。他給出了超限基數和超限序數的定義，引進了它們的符號；依勢的大小把它們排成一個“序列”；規定了它們的加法，乘法和乘方… …。到此為止，康托爾所能做的關於超限基數和超限序數理論已臻於完成。但是集合論的內在矛盾開始暴露出來。康托爾自己首先發現了集合論的內在矛盾。他在1895年的文章中遺留下兩個懸而未決的問題：一個是連續統假說；另一個是所有超窮基數的可比較性。他雖然認為無窮基數有最小數而沒有最大數，但沒有明顯敘述其矛盾之處。一直到1903年羅素髮表了他的著名悖論。集合論的內在矛盾才突出出來，成為20世紀集合論和數學基礎研究的出發點。
康托爾的集合論是數學上最具有革命性的理論。他處理了數學上最棘手的對象——無窮集合。因此，他的發展道路也自然很不平坦。他拋棄了一切經驗和直觀，用徹底的理論來論證，因此他所得出的結論既高度地另人吃驚，難以置信，又確確實實，毋庸置疑。數學史上沒有比康托爾更大膽的設想和採取的步驟了。因此，它不可避免地遭到了傳統思想的反對。
19世紀被普遍承認的關於存在性的證明是構造性的。你要證明什麼東西存在，那就要具體造出來。因此，人只能從具體得數或形出發，一步一步經過有限多步得出結論來。至於“無窮”，許多人更是認為它是一個超乎於人的能力所能認識的世界，不要說去數它，就是它是否存在也難以肯定，而康託竟然“漫無邊際地”去數它，去比較它們的大小，去設想沒有最大基數的無窮集合的存在……這自然遭到反對和斥責。
集合論最激烈的反對者是克羅內克，他認為只有他研究的數論及代數才最可靠。因為自然數是上帝創造的，其餘的是人的工作。他對康託的研究對象和論證手段都表示強烈的反對。由於柏林是當時的數學中心，克羅內克又是柏林學派的領袖人物，所以他對康托爾及其集合論的發展前途的阻礙作用是非常大的。另一位德國的知覺主義者魏爾認為，康托爾把無窮分成等級是霧上之霧。法國數學界的權威人物龐加萊曾預言：我們的“後一代將把（康托爾的）集合論當作一種疾病”等等。由於兩千年來無窮概念數學帶來的困難，也由於反對派的權威地位,康托爾的成就不僅沒有得到應有的評價，反而受到排斥。1891年，克羅內克去世之後，康托爾的處境開始好轉。
另一方面，許多大數學家支持康托爾的集合論。除了狄德金以外，瑞典的數學家米大格·列夫勒在自己創辦的國際性數學雜誌上把康托爾的集合論的論文用法文轉載，從而大大促進了集合論在國際上的傳播。1897年在第一次國際數學家大會上，霍爾維次在對解析函數的最新進展進行概括時，就對康托爾的集合論的貢獻進行了闡述。三年後的第二次國際數學家大會上，為了捍衛集合論而勇敢戰鬥的希爾伯特又進一步強調了康托爾工作的重要性。他把連續統假設列為20世紀初有待解決的23個主要數學問題之首。希爾伯特宣稱:“沒有人能把我們從康托爾為我們創造的樂園中驅逐出去。”特別自1901年勒貝格積分產生以及勒貝格的測度理論充實了集合論之後，集合論得到了公認，康托爾的工作獲得崇高的評價。當第三次國際數學家大會於1904年召開時，“現代數學不能沒有集合論”已成為大家的看法。康托爾的聲望已經得到舉世公認。
沒有康托爾，現代數學的發展將完全難以發展。現在有哪個數學分支不使用“集合”與“映射”概念的？康托爾說他的超限數理論證明了實無限的存在。他也用對角線方法“證明”了實數的數目大於自然數的數目——也就是說，無限可以比較大小。對於這樣一個“數學成果”，哲學家維特根斯坦表示質疑。
閱讀更多 船山評論 的文章
