4.2 无限集合
大卫·希尔伯特(David Hilbert,1862—1943)是他那一代人里面最伟大的数学家,他讲过一个有趣的故事。想象一下,你拥有一家客房数量无限多的酒店。我们不妨称其为“希尔伯特酒店”。这一天,酒店的生意很好,无限多的客房中每一间都有客人入住。此时又有一位客人开车前来,他需要一个房间。你不想在一个寒风大作的夜晚把他打发走,但你所有的房间都满了。怎么办呢?希尔伯特提出了一项建议:打开酒店广播,让无穷多个客人中的每一个都转移到下一个房间里去。于是57号房间的客人转移到58号房间里去,53462号房间的客人转移到53463号房间里去。总而言之, n 号房间里的每一名客人都转移到 n +1号房间里去。这样就能把1号房间空出来,留给这位深表感激的新客人入住了。
让我们继续讲述这个故事。正当所有客人都在自己的新房间里安顿下来,美美地安睡之时,一辆长途汽车停在希尔伯特酒店的门口,车上下来了无限多位旅客,每个人都要求住一个房间。你的无限多的客房中每一间都已经住了客人,而你急切地需要无限多个空房间。一位诚实的酒店经理应该怎么办呢?希尔伯特仍然有好点子:打开酒店广播,让每一位客人都换到房间号是他们目前房间号两倍的房间里去。也就是说,57号房间的客人换到114号房间去,53462号房间的客人换到106924号房间去。总而言之, n 号房间里的每一名客人都转移到2 n 号房间里去。这样一来,所有偶数号房间都会住上人,而所有奇数号房间都会空出来,供乘坐长途汽车而来的疲惫旅人入住。
需要注意的是,这些花招不适用于那些房间数量有限的无趣标准酒店。只有在房间数量无限的酷炫的希尔伯特酒店里,我们才能随意转移客人,不用担心失去任何客源。在第一个例子中,希尔伯特真正向我们指出的是,房间号的无限集合{1,2,3,4,5,…}和它的真子集{2,3,4,5,…}存在各项元素一一对应的关系。在第二个例子中,希尔伯特指出房间号的集合{1,2,3,4,5,…}和它的真子集{2,4,6,8,10,…}存在各项元素一一对应的关系。这些违反直觉的奇怪配对关系就是我们将要在本节探讨的内容。
与其讲述关于虚构酒店的故事,不如让我们来看一些真正的无限集合。无限集合的例子有很多,但这些集合必须不能是物体的集合,因为宇宙中物体的数量是有限的。许多其他概念如数可以构成无限集合。有很多常见的无限数集合:
•自然数, N ={0,1,2,3,…}
•整数, Z ={…,-3,-2,-1,0,1,2,3,…}
•有理数或分数, Q ={ m / n : m 和 n 属于 Z 且 n 不等于0}
•实数, R
自然数是所有整数的真子集。每个整数 n 都可以认为是分数 n /1,所以整数可以看成是所有有理数的真子集。最后,实数是所有数的集合,甚至包括那些无法用分数表示的数。早在2500多年前,人们就知道某些数无法写成分数,如 、e、-π和 。这样的数称为“无理数”。 实数集 R 包括所有有理数和无理数。所以有理数是实数的真子集。
思考偶数集合:
E ={0,2,4,6,…}
每个偶数都是自然数,所以 E 显然是自然数集合 N 的真子集。实际上,我们可以说自然数的数量是偶数的两倍,毕竟自然数包括 偶数 和 奇数 这两种数。但我们先不要那么信任我们对集合和子集的直觉。相反,让我们重拾4.1节中提到的对等势的定义。自然数和偶数之间存在一一的对应关系,只需要让每个自然数 n 与相应的偶数2 n 对应即可:
这说明 N 和 E 的大小相等。这怎么可能呢?自然数的数量怎么可能和偶数的数量一样多呢?奇数呢?部分的大小怎么会等于整体呢?
我们在哪里弄错了?答案是我们并没有弄错。我们在这里使用了用在有限集合上的推理过程。然而,对于有限集合,拥有相同的大小符合我们的直觉。对于无限集合,逻辑学认为我们的直觉不再有效,而且需要修正。伽利略·伽利雷(Galileo Galilei,1564—1642)是第一个在写作中提到无限集合的这点奇异之处的人。他指出一个无限集合可以和自身的真子集等势。在自伽利略以来的近400年里,这个新定义已经被所有数学和物理学领域接受了。我们不能因为它违反我们的直觉而忽视它。相反,这种定义对于我们在理解宇宙的过程中使用的模型而言是至关重要的,而且它还被用来进行科学预测。我们必须理解并接受这种定义。我们的直觉需要调整。
继续来看更多无限集合吧!假设集合 S 为平方数的和,也就是说,这些数是整数与其自身的乘积:
S ={0,1,4,9,16,25,…}
这个集合是无限集合,而且它还是自然数集合 N 的真子集。平方数的数量比偶数的数量少得多:在前100个自然数中,只有10个平方数。然而, S 可以和自然数形成一一对应的关系:
这种对应关系表明自然数和它们的真子集平方数是等势的,也就是它们拥有相等的势。我们能用数来描述这些集合中元素的数量吗?显然任何有限的数都无法胜任这项任务。康托尔用 0 符号表示这些无限集合的势,该符号读作“阿列夫零”(aleph-null)。阿列夫( )是希伯来字母表中的第一个字母。所有与自然数集合 N 等势的集合,其势都等于 0 ,并被称为 可数无限 (countably infinite)集合。必须意识到的是,我们无法数完这样的无限集合。然而我们至少可以开始数它们。通过查看与自然数的对比关系,我们可以说出第0个元素是什么,第1个元素是什么,第2个元素是什么,等等。
还有其他集合拥有这样的势。还记得素数吗?如果一个数只能被1和它本身整除,它就是素数。思考由所有素数组成的集合:
P={2,3,5,7,11,13,…}
虽然看上去素数的数量比自然数少得多,但一一对应的关系仍然存在:
这表明 P 等势于自然数集合。我们如何描述这种对应关系呢?第42个素数是什么?不存在任何简单的公式向我们提供这个信息。然而,即使不容易描述这种对应关系,我们只需要这样一种对应关系 存在 ,并且它表明 P 的势等于 0 就够了。
到目前为止,我们讨论过的所有无限集合都是自然数集合的真子集。那些看上去比自然数集合更大的集合呢?这些集合真的比自然数集合更大吗?思考整数集合:
Z={…,-3,-2,-1,0,1,2,3,…}
自然数集合是集合 Z 的真子集,因为 Z 还包括负整数和零。我们如何在自然数集合 N 和同时包括正负整数和零的集合 Z 之间建立对应关系呢?幸运的是,像康托尔这样极为聪明的人着手研究了这个问题,并且找到了一种简单的对应方式:
通过机智地将 N (暂时忽略零)分为偶数和奇数,我们可以让 N 的奇数对应 Z 的正整数,让 N 的偶数对应 Z 的负整数。由于我们永远无法穷尽奇数或偶数,因此 Z 的每个元素都会得到配对。这正是我们在希尔伯特酒店里所做的事,我们给老客人组成的无限集合分配了偶数号房间,给新客人组成的无限集合分配了奇数号房间。
让我们看看一个真正巨大的集合吧。思考由自然数有序对构成的集合 N × N 。它是数字对< m , n >的集合,其中 m 和 n 都是自然数。对于每个 m ,都存在一个自然数集合 N 的副本:
< m ,0>,< m ,1>,< m ,2>,< m ,3>,…
因为 m 有无限多个,所以集合 N × N 有无限多个 N 的副本。整数集合 Z 拥有 N 的两个副本,一个副本是正的,一个副本是负的。相比之下,集合 N × N 有 无限多个 N 的副本。直觉告诉我们,这个集合的元素数量比 N 多得多。我们的直觉是错误的!康托尔是一个非常聪明的人,他在 N 和 N × N 这两个集合之间也找到了对应方式:
为了清楚地看出这种对应关系,可以将自然数看成一个很长的数列,如图4-1所示。
图4-1 N 是一条无限长的蛇
按照图4-2的方式将 N × N 写出来,从左下角开始按照之字形路线将这些数连接起来。
图4-2 N 和 N × N 之间的对应关系
由于这两个集合是无限集合,而我们只有一张面积有限的纸,因此我们无法将它们的对应关系全部展示出来。不过按照这种模式,每个有序自然数对,包括<303,1227>在内,最终都会与 N 中的某个自然数对应。出于显而易见的原因,这种证明有时称为 之字形证明 (zigzag proof)。总之,集合 N × N 与集合 N 等势,其势为 0 。
那么有理数的集合 Q 呢?分数的数量当然比自然数多!毕竟集合 N 中的每个 n 都是集合 Q 中的 n /1。所以 Q 含有 N 的一个副本:
0/1,1/1,2/1,3/1,…
但是 Q 还含有:
n /1, n /2, n /3, n /4,…
我们也不要忘记负分数:
- n /1,- n /2,- n /3,- n /4,…
除此之外,需要注意的是任意两个分数——比如3/5和4/5——之间总会存在另一个分数:7/10。我们还可以继续列举下去:3/5和7/10之间还有13/20。看上去似乎很明显,有理数的数量比自然数多多了。然而,现在你应该能够预料到,事情并不简单。有理数的数量看上去比自然数多得多,但是实际上,它们是同样多的。为了说明这一点,我们将展示 N 和 Q 之间的对应关系,如图4-3所示。
图4-3 N 和 Q 之间的对应关系
再一次,自然数“蛇行”贯穿分数,最终将每个分数串联起来。这种证明方式有时称为 项链证明 (necklace proof)。你能看出为什么叫这个名字吗?
然而这里存在一个小小的问题。我们在图4-3中列出的有理数存在重复的情况。有理数4/7的值等于8/14。所以我们真的建立了 N 和有理数集合的对应关系吗?实际上,我们做到了更难的事情:我们建立了 N 和一个比有理数更大的集合的对应关系。不过也有办法建立 N 和有理数集合的关系,只需要让这条连线跳过之前已经出现过的分数即可。
综上所述,许多看上去比自然数集合无限大的集合实际上与自然数集合等势。是否存在某个无限集合真的比自然数集合更大呢?