哥德尔的不完备性定理震撼了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年召开时，“现代数学不能没有集合论”已成为大家的看法。康托尔的声望已经得到举世公认。
没有康托尔，现代数学的发展将完全难以发展。现在有哪个数学分支不使用“集合”与“映射”概念的？康托尔说他的超限数理论证明了实无限的存在。他也用对角线方法“证明”了实数的数目大于自然数的数目——也就是说，无限可以比较大小。对于这样一个“数学成果”，哲学家维特根斯坦表示质疑。
閱讀更多 船山評論 的文章
