康托尔：在无限中摸索

1, 2, 3, ...的序列永无尽头，这就是所谓的自然数。无论开始的数有多大，你总能通过加上1来得到一个更大的数。这样一个不断超越任何有限界限的过程，被亚里士多德称之为一种潜无限。然而，亚里士多德认为“完成”的无限或“实”无限是不合理的。

在18和19世纪对于数学变得如此重要的微积分的极限过程正是潜无限的例子。关于这一点，伟大的德国数学家高斯曾经警告说：

我极力反对把无限当成一种完成的东西来使用，这在数学上是绝不能允许的。无限只不过是言语上的一个比喻罢了。

19世纪中叶以后，只有格奥尔格·康托尔不顾高斯的警告，迎接挑战去创立一种关于实无限的深刻而一致的数学理论。弗雷格支持康托尔对实无限的信念，他认识到了它对数学未来的重要性。

弗雷格肯定想不到，由康托尔的无限所引发的激烈的讨论，研究和争辩有一天会为通用数字计算机的发展提供重要的启发。

工程师还是数学家

哈勒大学的领衔数学家爱德华·海捏发现了康托尔超凡的数学能力，并建议他研究一些与无穷级数有关的问题。

康托尔研究了三角级数，他希望弄清楚在何种情况下两个这种类型的不同级数会收敛于同一值。他发现为了得到希望的结果，他不得不把无穷集当作完成了的整体来处理，并且对其进行复杂的运算。不久，他就把集合论（Mengenlehre）发展成一门独立的学科。

无穷集的大小是不同的

即使我们认为把所有自然数1，2，3，...所组成的集合当成一个完成了的实无限来处理是有意义的，如果我们问这个集合中有多少数，这难道也是有意义吗？

莱布尼茨对其作了如下推理：

只要一个集合中的元素可以同另一个集合中的元素一一对应起来，我们就可以说这两个集合的元素数目是相等的，即使我们不知道这个数目到底是多少。例如，例如如果我们发现一个礼堂中既没有空座位，又没有站着的人，那么我们不必清点就可以下结论说，礼堂中的人数与座位数是相等的——我们其实把每一个座位与每一个人——对应了起来。

莱布尼茨认为，如果真有无限数这样的东西存在，那么同样的思想也可以应用于它们：倘若两个无限集之间可以建立一个一一对应的关系，则我们就可以下结论说，这两个集合拥有同样数目的元素。接着，他建议把这一观念运用到如下两个集合上：由所有自然数所组成的集合1，2，3，...以及由素有偶数所组成的集合2，4，6，...在这两个集合之间很容易设计出一种一一对应的关系，我们只要把每一个自然数与它的二倍对应起来就可以了。

1 2 3 4 ...
↕ ↕ ↕ ↕
2 4 6 8 ...

请注意，即使自然数集与偶数集都是无限集，在这两个集合间也可以建立起这种一一对应关系。比如对应着117这个自然数的偶数是234，对应着4288这个自然数的偶数是8456等等。

莱布尼茨推论说，如果真有像无限数这样的东西，那么这种一一对应的存在就会迫使我们下结论说，自然数的数目与偶数的数目是相等的。

但这怎么可能呢？

自然数中并非只有偶数，而且还有所有的奇数，它们又组成了一个无限集。有一条最基本的数学原理就是整体大于它的任何部分，这可以追溯到欧几里得。

于是，莱布尼茨得出结论说，或者谈论一个无限集中元素的数目没有意义的，或者某些无限集将与它的一个子集具有相同的元素数目。

然而，莱布尼茨选择了前者，康托尔却选择了后者。他开始发展一种能够应用于无限集的关于数的理论，这种理论恰恰认为一个无限集将与它的一部分拥有同样多的元素数目。

沿着莱布尼茨没有走完的道路，康托尔开始研究在两个不同的无限集之间建立一一对应在什么情况下是可能的。尽管莱布尼茨已经发现在自然数集与它的一个子集（偶数集）之间可以建立起一种一一对应关系，但康托尔还考虑比自然数集更大的集合。他所考虑的一个例子是可以被表示为正分数的数的集合，比如1/2或5/3.由于自然数可以用分数来表示，所以自然数集可以被看成这个集合的一个子集。

然后，康托尔稍加考虑，便发现他可以在由这些分数所组成的集合与自然数集之间建立起一种一一对应关系。分数可以像下面这样排成一个序列:

它们是按照每一个分数的分子与分母之和进行分组的：首先是和为2的分数（这样的分数只有1个），然后是和为3的分数（这样的分数有2个），然后是和为4的分数（这样的分数有3个），再后是和为5的分数（这样的分数有4个），以此类推。现在很容易在它们与自然数之间建立起一一对应的关系：

| 1 | 1 2 | 1 2 3 | 1 2 3 4 | 1 2 3 4 5 |
| - | - - | - - - | - - - - | - - - - - |
| 1 | 2 1 | 3 2 1 | 4 3 2 1 | 5 4 3 2 1 |
  ↕   ↕ ↕   ↕ ↕ ↕   ↕ ↕ ↕ ↕   ↕ ↕ ↕ ↕ ↕
  1   2 3   4 5 6   7 8 9 10 11 ...

这里要注意,不同的分数可以表示同一个数，比如:

1   2   3
- = - = - ...
2   4   6

所以分数与自然数之间的一一对应是作为符号的分数的对应，而不是符号所代表的数的对应。

由于从直观上看，分数要比自然数多许多，所以这一证明可能会使我们猜想，每一个无限集都可以与自然数之间建立起一一对应的关系。康托尔的伟大贡献就是说明情况并非如此。

可以用分数来表示的数被称为有理数。如果一个有理数是用小数来表示的，那么最终会出现无限循环小数。比如1/3， 1/4，5/3，24/11，9/7.

可以用小数来表示的数被称为实数，其无限不循环小数被称为无理数。比如√2，π。

像√2这样的数连同所有的有理数被称为代数数，这是因为它们可以作为代数方程的根。而业已证明，π不可能是任何代数方程的根，这样的数被称为超越数。

在表明了分数可以与自然数之间建立起一一对应的关系之后，康托尔把注意力转向了由所有代数数所组合成的集合，他又一次轻松地找到了一种方法，可以把它们与自然数一一对应起来。很自然地，他接着把注意力转向了所有实数所组成的集合。很快，他证明了实数集无法与自然数集之间建立起一一对应，无限集至少有两种大小。

康托尔对无限数的探求

在日常语言中，人们用两种不同但却相互有关联的方式来使用自然数1，2，3, ...它们分别被用于计数和排序。

日常用基数和序数之间的差别来体现这一点：一，二，三......和第一，第二，第三......基数用于指明某个集合中有多少个东西，序数则用于指明这些东西是如何以一定次序排列的。

康托尔关于自然数与实数之间不存在一一对应的发现促使他思考了无穷基数，他关于三角级数的工作则暗示了一种把无穷序数概念化的方法。

康托尔假定每一个集合（无论是有限的还是无限的）都有唯一一个基数。特别地，如果两个集合可以被一一对应起来，那么它们就有同一个基数。设M表示某个完全任意的集合，康托尔引入记号|M|表示集合M的基数。例如，如果

A = {♣ ♦ ♦ ♥ ♠}, B = {3, 6, 7, 8}, 且C＝{6, 5}

那么

|A| = |B| = 4, |C| = 2

当然，A与B之间很容易建立起一个一一对应关系：

♣ ♦ ♥ ♠
↕ ↕ ↕ ↕
3 6 7 8

如果两个集合基数不同，用符号来讲，这个问题就是说，对于集合M与集合N而言，什么时候|M| ≠ |N|。在这种情况下，两个基数中一个较大一个较小。利用标准符号＜和＞，我们可以用|M|<|N|（或者等价的|N|>|M|)来表示N具有较大的基数。为了证明这一点，我们只需在M和N的某个子集之间建立一个一一对应关系。

事实上，对于任何两个不等的基数，其中一个必定要大于另一个这一命题对于无穷集来说并不是显然成立的。但是康托尔当时并没有发现这一点。

于是，在上面那个|A| > |C|的例子中（因为4 > 2), A的子集|{♦ ♥}|可以这样与C对应：

6 5
♦ ♥

康托尔把无限集的基数称为超限数。他关于超限数的第一个例子是自然数集的基数，并用א0来表示。א0通常读作”阿列夫零“，א是希伯来字母表上的第一个字母。

康托尔用符号C来表示实数集的基数（因为实数集有时被称为连续统[continuum])。康托尔深信，C就是א0之后的下一个超限基数。א0与C之间不存在别的基数，这一猜想被称为连续统假设。

在康托尔关于三角级数的工作中，他考虑了某种可以被一步步反复应用的特定过程：第一步，第二步，第三步等等。然而使康托尔跨入超限领域的是，他意识到在所有这些无限步后还有更多的步。不久，他开始谈及第ω步，第（ω＋1）步以及更多的步，并且发展出后来被他称为超限序数的算数。

让我们首先看一看有限集｛♣ ♦ ♥｝。其成员可以按照六种不同的方式加以排列：

然而，这6种排列都显示出同一种样式：第一项后面跟着第二项，第二项后面跟着第三项。任何有限集都是这样的：对其成员进行排列的所有不同方式的背后都显示出同一种样式。如果一个集合有n项，那么任何排列都会显示第一项，第二项……最后是第n项。

康托尔发现无穷集的情况是完全不同的。无穷集可以以不同的方式排列成非常不同的样式。例如，假定把自然数1，2，3，...排列成所有偶数成员在所有奇数成员之前：

2, 4, 6, ...1, 3, 5, ...

如果我们试图用序数来说明每一项在序列中的次序，那么我们就会发现，我们所熟悉的有限的序数都被偶数用尽了：

1st 2nd 3rd ... ? ? ? ...
 ↓   ↓   ↓      ↓ ↓ ↓
 2   4   6  ... 1 3 5 ...

康托尔发现了如何用超限序数来解决这个困难。于是，在所有的有限序数之后，康托尔又设定了第一个超限序数，他用希腊字母ω来表示，在它之后是ω＋1，ω＋2等等。然后康托尔就可以很容易地为上例中的奇数排序了：

1st 2nd 3rd ... ωth (ω+1)th (ω+2)th ...
 ↓   ↓   ↓  ...  ↓     ↓       ↓   
 2   4   6  ...  1     3       5    ...

康托尔发现，自然数可以用越来越大的序数以许多不同的方式加以排列。他称有限序数即自然数1，2，3，...为第一数类，称自然数的不同序列排序的超限序数为第二数类。

康托尔研究第二数类的超限序数集时，用符号א1来表示它的基数。值得注意的是，康托尔能够证明，א1就是紧接在最小的超限基数א0之后的下一个基数。因此א1>א0，不存在大于א0而小于א1的基数。

康托尔一直努力试图证明的连续统假设是，C就是继א0之后的下一个基数。他已经知道，א1就是א0之后的下一个基数，所以连续统假设就等价于这样一个问题：

C ?= א1

不幸的是，康托尔虽然写下了这个方程，但他并没有证明它为真。

既然有第一数类和第二数类，那么是否有第三数类呢？绝对有！在为基数为א1的集合排序时，第一数类和第二数类的数就不够了。康托尔把第三数类最开始的超限基数记为ω1，并把第三数类中的所有序数所组成的集合的基数称为א2.然后，康托尔可以证明א2就是紧接着א1之后的下一个基数。康托尔发现这个过程是永无止境的：א2之后还有א3，א3之后还有א4等等。在所有这些之后是אω等等。

但康托尔提出这些思想时，他实际上是对一个从未有人到过的领域进行探索。他无法依靠任何数学规则，而不得不凭借自己的自觉独自创造。

对角线方法

如果说今天的学生从康托尔的成果中学到了某种东西，那么这多半就是他的对角线方法。

康托尔发表了他对自然数与实数之间不存在一一对应的证明，或者用他的符号表示，就是א0 < C。利用对角线方法，这个结论可以从基本逻辑原理中得出。

在解释对角线方法时，使用一个贴着标签的包裹的比喻将是有益的。特别之处在于，被用作标签的东西就是包裹里的东西。举例来说，考虑一副纸牌中的4种花色：♣ ♦ ♥ ♠。让我们把其中的一种花色作为一个“包裹”上的标签，而包裹中所包含的也正是这些花色中的某些组合，比如：

   ♣       ♦        ♥        ♠
   ↕       ↕        ↕        ↕
{ ♦ ♥ } { ♦ ♠ } { ♦ ♥ ♣ } { ♣ ♦ }

我们可以用表格的形式来表示这一信息，其中＋表示某一项在包裹内，－表示它不在包裹内.左边的一列是4种标签，包裹中的内容显示于最上方一行。对角线上的＋和－加粗，以示强调。

对角线方法是一种把相同类型的项合到一个新包裹中去的技巧，并且使这个新包裹中所含的东西与旧包裹里的都不同。

我们取出对角线上的标签，将符号相反，组成一个新表。于是，由于♣相对的是－，所以在我们的新表中，♣对应的是＋。同样♥对应－，♦对应－，♠对应＋。结果如下：

于是，我们的新包裹就是｛♣ ♠｝。我们何以能够确信它与任何贴了标签的包裹都不同呢？情况是这样的，它不可能是标签为♣的包裹，因为♣不在那个包裹中，而在我们新的包裹中。它也不可能是标签为♦的包裹，因为♦在那个包裹中，而不在我们的新包裹中。以此类推。

现在，包裹当然指的就是集合，而标签则是一种在集合与其成员之间建立起一一对应的方法。这种方法是完全一般的：开始时的集合是否是一个无限集，这是无关紧要的。如果用那个集合中的一个元素来做某个由这个集合中的这些元素所组成的新的集合的标签，那么就可以用对角线方法来获得一个由这些元素所组成的另一个全新的集合，它与所有已经贴过标签的集合都不同。

让我们看看，如果我们从自然数集1，2，3，...开始这种方法将这样运作。设想把这些数中的某一些装进一个包裹。它可能包含｛7，11，17｝，还可能包含所有的偶数。现在，让我们设想把自然数本身作为标签，就像下面这个无穷序列一样：

1  2  3  4 ...
↕  ↕  ↕  ↕
M1 M2 M3 M4...

其中M1，M2，M3，M4，...中的每一个都是由自然数所组成的包裹。这时，我们用下表来获得一个新的集合M，它不同于每一个集合：

换句话说，如果1不属于M1，那么1就属于M；如果2不属于M2，那么2就属于M；依次类推。因此，M是一个不同于M1，M2，...的自然数集合。由于M1，M2，M3，M4，...表示1，2，3, ...与自然数集之间任何可能的一一对应，我们发现没有什么对应可以包含自然数集的一切子集.换句话说，由一切自然数集所组成的集合的基数要大于א0.事实上，我们可以证明这个基数就是实数集的基数C。于是对角线方法就为我们提供了另一种说明实数比自然数更多的方法。

要想弄明白为什么由一切自然数集所组成的基数与实数集的基数是相同的，考虑一下只包含0和1两个数的数值的二进制表示自然数的情况是有益的。当我们写1/3＝0.3333...时，它的意思就是

1/3 = 3/10 + 3/100 + 3/1000 + 3/10000 + ...

在二进制中，小于1的正实数可以用0和1的无限长的串来表示。例如：

1/4 = 0.010000000000...
1/3 = 0.01010101010101...
1/π = 0.101000101..
√(1/2) = 0.1011010100...

这里，当我们写下时1/3 ＝ 0.010101010101...时，它的意思其实就是

1/3 = 1/4 + 1/16 + 1/16 + 1/64 + ...
(分母是2的连续幂，而非10的连续幂)

现在，无论以什么自然数集开始，我们都可以像下面这样找到唯一一个实数与之对应：如果n是给定集合的一个成员，那么我们就在第n个位置上写1，否则就写0，这样我们便产生了一串0和1的序列。例如，如果我们始自偶数集，那么我们得到的序列就是0.01010101..., 即我们已经看到的1/3.如果我们始自奇数集，那么我们得到的序列就是0.1010101010...=2/3.

这就表明，由一切自然数集所组成的集合的基数与0与1之间的实数集的基数是相同的。但康托尔证明了这个集合的基数与由所有实数所组成是我基数是相同的。

还有一点技术上的小麻烦必须提及。某些有理数将有两种不同的二进制表示，所以它们将对应于两个不同的自然数集。例如：

1/2 = 0.10000000...
    = 0.01111111...

所以实数1/2既对应着仅由1组成的集合，又对应着由除1以外的所有自然数组成的集合。尽管这破坏了我们的一一对应关系，但利用有理数集的基数为א0的事实，这一困难便可克服。

这种方法非常具有一般性，它提供了另一种产生许多超限基数的方法（与康托尔的אS序列不同）。例如，我们可以设想以实数作为标签的实数包裹。对角线方法表明，没有这样的标签可以包含一切实数集。因此，由所有这样的集合所组成的集合的基数必定大于实数集的基数C。而且没有必要就此止步。直到今天，以这种方式获得的基数是如何与康托尔的א0，א1，א2，...想联系的问题仍然是困难和争论的一个来源。

存在绝对无限

康托尔相信，在超限之外还存在着一个绝对的无限，它仅靠人类的理解力是永远无法完全企及的。甚至是出自集合论的令人苦恼的悖论也应当从这一观点来理解。例如，所有超限基数的乘积应当被认为是绝对无限的，这就是为什么仅仅认为它们是超限的就会导致矛盾的原因。

斗争的副产品

弗雷格在其隐喻中所预言的斗争最令人称奇的副产品就是阿兰·图灵关于一种通用计算机的数学模型。