4.3 还有比无限更大的吗?
读完第3章之后,有人会得出这样的结论:只要足够聪明,每个无限集合都可以和自然数集合形成一一对应的关系。康托尔一度也是这么想的,直到他考虑到实数。
康托尔思考了0和1之间所有实数构成的实数的子集。这个子集表示为(0,1)
,包含像0.43905346...、0.5、0.373468...这样的数。他试图在自然数集合
N
和集合(0,1)之间找到一一对应的关系。他想寻找与在4.2节中非常奏效的之字形证明或项链证明类似的某种技巧。或许我们可以让自然数以某种方式“蛇行”穿过(0,1)的每一个点,就像图4-4中所描绘的那样。
![](https://bookbk.img.zhangyue01.com/group62/rL/6v/e0449c8295c278c38146494c5b2b9787.jpg?v=X_nsIkKh&t=fwAAAWZJaIk.)
图4-4 在 N 和(0,1)之间建立联系的(失败)尝试
位于图4-4中的横轴上方的数是自然数,横轴下方的数是和这些自然数相对应的实数。这种对应关系如下所示:
![](https://bookbk.img.zhangyue01.com/group62/IH/GH/5fc2af69ee3f61c7b049e06e946a7c07.jpg?v=QA3vCLqh&t=fwAAAWZJaIk.)
但是这种对应关系并不奏效。实际上,康托尔将自然数与(0,1)一一对应的每种尝试都失败了。他发现(0,1)总会有部分元素在自己尝试的配对关系中被漏掉。
康托尔没能找到一一对应的关系,但他证明了比这有趣得多的事情:
这种对应关系没有存在的可能
。
他指出,并不是因为自己不够聪明,所以找不到这种对应关系。无论一个人有多聪明,都找不到这样的对应关系,因为这样的对应关系不可能存在。通过指出自然数与集合(0,1)之间不存在一一对应的关系,康托尔证明了集合(0,1)其实比自然数集合
N
更大。我们马上就会呈现这种优雅简洁的证明方法。
与自然数集合等势的无限集合被称作 可数无限 的。我们至少可以开始数这些集合有多少元素。和自然数的对应关系可以帮助我们数一数这些集合有多少元素。我们在4.2节中看到,集合 N 、 E 、 P 、 Z 、 N × N 和 Q 都是可数无限的。按照这种推理方式,不能和自然数形成对应关系的无限集合被称作 不可数无限 (uncountably infinite)的。我们甚至无法逐个列出不可数无限集合开头的若干元素。我们将证明(0,1)是不可数无限的。与可数无限集合相比,不可数无限集合大得多。
康托尔的研究结果是无限存在不同类型或层次的首个证据。这太违反直觉了。毕竟,谁能想到“永永远远,绝不停息”还会有不同的类型呢?但实际上就是有。通过严格遵循两个集合大小相等的逻辑定义,康托尔得出了这个重要结论。再一次地——而且这一点怎么强调也不为过,无限的不同层次之间的差别被用在现代微积分学中。掌握了这种知识,工程师和物理学家制造出了桥梁和火箭。如果你知道某位工程师不相信康托尔的工作,你还敢穿过他设计建造的现代吊桥,那你未免也太鲁莽了。虽然看上去很违反直觉,但无限的不同层次奠定了我们对宇宙的理解。
这个证明实际上是反证法。为了指出 N 和(0,1)不存在一一对应的关系,康托尔(错误地)假设这种对应是存在的,并由此推导出了矛盾。
按照第1章中的样式,我们写道:
N
和(0,1)之间有对应关系
矛盾。
推导出来的矛盾是存在某个0和1之间的实数,它无法与假设对应关系中的任何相应元素配对。由于我们假设这种对应关系能够将0和1之间的每个实数与每个自然数一一配对,因此就产生了矛盾。
通俗地说,该证明描述了一个0和1之间的实数,而且:
这个实数不位于假设的对应关系中。
或者更精确地说,
这个实数和假设对应关系中的其他每个数都不同。
该证明称作 对角化证明 (diagonalization proof),证明过程如下。假设全体自然数和(0,1)的每个元素之间都存在某种奇妙的一一对应关系。我们可以将这种对应关系用图4-5表示出来。
![](https://bookbk.img.zhangyue01.com/group62/1b/Gp/be53c883304d592f1711019cc18fa577.jpg?v=CoCXmxRA&t=fwAAAWZJaIk.)
图4-5 N 和(0,1)所谓的对应关系及其对角线
竖轴左边一列是自然数,然后我们在竖轴右边写下与每个自然数相对应的(0,1)中的数。在这种所谓的对应关系下,我们仍然可以描述出一个这张清单上不可能有的数。这个数是0和1之间的一个实数,表示为 D [“diagonal”(对角线)的首字母]。 D 这个数是从图4-5列出的对应关系的对角线中推导出来的。
• D 的小数点后第0位数字是6,因为它比与自然数0对应的实数的小数点后第0位数字5大1。
• D 的小数点后第1位数字是4,因为它比与自然数1对应的实数的小数点后第1位数字3大1。
• D 的小数点后第2位数字是0,因为它比与自然数2对应的实数的小数点后第2位数字9不同。
• D 的小数点后第3位数字是……
D 在每一位上的数字都以此类推。我们可以删去图4-5中不重要的部分,看看图4-6对 D 的描述。
![](https://bookbk.img.zhangyue01.com/group62/VU/i6/9e86a2377703fe45622d9f23cb5ca9d3.jpg?v=dtRupKe5&t=fwAAAWZJaIk.)
图4-6 对不存在于假设的对应关系中的数 D 的描述
所以这个数是0.640914187...这个数显然属于集合(0,1)。然而它不在假设的对应关系中。让我们找找它的位置。
• D 无法与0对应,因为自然数0对应的有理数的小数点后第0位数字是5,而 D 的小数点后第0位数字是6。
• D 无法与1对应,因为自然数1对应的有理数的小数点后第1位数字是3,而 D 的小数点后第1位数字是4。
• D 无法与2对应,因为自然数2对应的有理数的小数点后第2位数字是9,而 D 的小数点后第2位数字是0。
• D 无法与3对应,因为自然数3对应的有理数的小数点后第3位数字是8,而 D 的小数点后第3位数字是9。
……
• D 无法与 d 0 对应,因为自然数 d 0 对应的有理数的小数点后第 d 0 位数字是 x ,而 D 的小数点后第 d 0 位数字不是 x 。
……
由于 D 不在这种对应关系中,因此我们的结论是,这种假设的对应关系根本就不是真正一一对应的关系。实际上,我们所做的事情就是描述了一个和假设对应表格每一行数字都不相同的数 D 。需要注意的是, D 不是唯一一个不出现在这种对应关系中的数。想要发现这样的数,只需要逐个查看每一行数字并改掉某些位置的数字即可。通过这种方式,我们就能发现那些与表格中的任何一行都不同的数。在上面的例子中,我们沿着对角线改动了每一行数字某一位置上的数字,但我们也可以用别的方式实现这一点。我们的改动是在相应数字上加1(9除外,我们将9改成了0),然而还有其他很多种方式可以用来改动这些数字。
也许会有人尝试描述另一种可能的对应关系,令
D
出现在这个对应表格中。然而同样的方法同样适用于新提出的对应关系。会有0和1之间的另一个数
D
'无法出现在对应表格中,尽管按照假设它应该在里面。任何可能的对应关系都会遗漏(0,1)的部分元素。
我们的结论是,在任何假设的对应关系中,集合(0,1)中没有得到配对的数比得到配对的数多得多。也就是说,集合(0,1)比自然数集合大得多。与可数无限集合相比,不可数无限集合极为庞大。在这本书里,我们将反复回顾这个事实。许多集合将被指出是可数无限的,和不可数无限的大集合相比,它们显得甚为小巧。实际上,当我们从不可数无限集合中“减去”一个可数无限集合时,我们仍然会得到一个不可数无限集合。
还有许多其他不可数无限集合。思考自然数集合的幂集
(
N
),也就是
N
的所有子集的集合。我们已经知道,对于拥有
n
个元素的有限集合,
(
N
)的大小是2
n
。有人可能会认为,对于无限集合而言,可能存在某种方法令一个集合与它的幂集建立一一对应的关系。这种想法并不正确。无限集合与其幂集的对应关系不可能存在。
同样可以用反证法证明这一点:
N
和
(
N
)之间存在一一对应的关系
矛盾。
推导出矛盾的方式是描述自然数的一个子集,也就是
(
N
)的一个元素,且它不在假设的对应关系中。由于我们假设自然数集合的每一个子集都能与某个自然数配对,矛盾就产生了。
通俗地说,该证明描述了自然数的一个子集,而且
自然数的这个子集不存在于假设的对应关系中。
或者更精确地说,
自然数的这个子集和这种对应关系中自然数的每个子集都不同。
同样可以用对角化证明来指出这一点。假设
N
和
(
N
)之间存在某种一一对应的关系——也就是说,存在某种方式,令每个自然数
n
与自然数集合
N
的每个子集一一对应起来。我们不列出每个子集的元素,而是用“是”或“否”标明某个元素是否在该子集中。对这种对应关系的描述见图4-7。
![](https://bookbk.img.zhangyue01.com/group62/rk/hH/a0e108c8838e4d875be4b217393f05a6.jpg?v=4TSFnWLL&t=fwAAAWZJaIk.)
图4-7
N
与
(
N
)之间的一种假设对应关系及其对角线
让我们来看看其中的一些子集。与1对应的子集包括0,不包括1,包括2,包括5,等等。所以这个子集是
{0,2,5,…}
与7对应的子集是
{1,5,7,8,…}
这种对应关系不可能包含 N 的所有子集。通过观察这条对角线,我们就能找到一个不在这张清单上的子集。让我们看看这条对角线的反面是什么,如图4-8所示。
![](https://bookbk.img.zhangyue01.com/group62/bo/I9/c313aa63606e46e874e9b8f462a54a6b.jpg?v=sriS1dvr&t=fwAAAWZJaIk.)
图4-8 不存在于假设对应关系中的 N 的子集
子集 D :
•不包含0,因为与自然数0对应的子集包含0;
•包含1,因为与自然数1对应的子集不包含1;
•不包含2,因为与自然数2对应的子集包含2;
•不包含3,因为与自然数3对应的子集包含3;
……
•当且仅当与自然数 d 0 对应的子集不包含 d 0 时,才包含 d 0 ;
……
我们其实是在描述这样一个自然数的子集:
D ={ N 中的数 d :与 d 对应的子集不包含 d }
结论是 D 不和自然数集合中的任何元素对应。如果有人说子集 D 与某个数 d 0 对应,那就来看看 d 0 是否在 D 中。
当且仅当 d 0 不在与 d 0 对应的子集中时, d 0 才在 D 中。
也就是说,
当且仅当 d 0 不在 D 中时, d 0 才在 D 中。
矛盾出现了。我们的结论是子集 D 不同于和自然数 d 0 对应的子集。实际上也就是说, D 不同于假设对应关系中的任何子集。因此,我们提出的对应关系遗漏了至少一个子集。
在这个证明中,自然数其实并没有起到很重要的作用。我们可以对这个证明进行广义的归纳并指出,对于任何集合 S , S 的幂集都无法与 S 形成一一对应的关系。也就是说,集合的子集比集合的元素多。这与本书的自我指涉相关局限这一主题形成了绝妙的呼应。集合 S 的元素不能“对应”“描述”或“处理”与集合 S 的组成有关的性质。
简短的证明如下:(错误地)假想
S
和
(
S
)之间存在一一对应的关系。现在思考如下集合:
D ={ S 中的元素 d :与 d 对应的 S 的子集不包含 d }
D
是
S
的子集,因此是
(
S
)的一个元素,但
D
不与
S
的任何元素对应。实际上,
D
所说的是:
本子集不同于假设对应关系中的任何子集。
如果你(错误地)宣称 S 中有一个 d 0 与 D 对应,那就看一看这个元素 d 0 吧:
当且仅当 d 0 不在 D 中时, d 0 才在 D 中。
矛盾出现了,于是我们可以判断
D
不在假想的对应关系中。所以
(
S
)大于
S
。
我们已经看出(0,1)和
(
N
)都比
N
大。实际上,这两个集合之间存在一一对应的关系(我将不会在本书中描述),说明它们拥有相等的势。由于大小为
n
的集合,其幂集的势为2
n
,而
N
的势为
0
,所以
(
N
)的势为
。因为它也是连续区间(0,1)的势,所以它又称“连续统的势”(cardinality of the continuum)。
为什么我们要局限于(0,1)呢?为什么不考虑整个实数集 R 呢?整个实数集看上去似乎比(0,1)大得多。毕竟,实数还包括区间(1,2)和(2,3)。不要忘记负数区间如(-23,-18)。实数集合包含无数多个(0,1)的副本。然而根据我们对两个集合大小相等的定义,可以证明(0,1)等势于 R 。该证明的正式名称是 球面投影证明 (proof by stereographic projection),但我更喜欢的名字是更加亲切的 阳光证明 (sunshine proof)。该证明基本如图4-9所示。
首先假设有一个明亮的太阳位于画面上方。然后将区间(0,1)放置在太阳下方并弯曲起来。接下来将代表集合 R 的实数线放置在画面底部。需要意识到,这条实线是向左右两边无限延伸的。对(0,1)和 R 之间一一对应关系的描述如下:对于(0,1)中的每一点 x ,都可以画一条直线令其穿过太阳和 x ,而且该直线会与 R 相交于一点。这条直线与 R 的交点与 x 对应,并表示为 x 。想要看出这是一种充分的对应关系,我们只需要意识到,(0,1)中两个不同的点 y 和 y '将对应 R 中两个不同的点 y 和 y '。想要证明 R 中的每个点 z 都存在于这种对应关系中,只需要用直线将 R 中的 z 点与太阳连接起来。这条线将穿过(0,1)中某个独一无二的点。总之,(0,1)和 R 之间存在一一对应的关系,因此它们是等势的。
![](https://bookbk.img.zhangyue01.com/group62/tp/b7/e9f896828087421201fea1538c8aaa56.jpg?v=WvQpw63b&t=fwAAAWZJaIk.)
图4-9 (0,1)和 R 之间的对应关系
我们已经指出,实际上有两种方法可以证明某无限集合的势大于
0
。第一,可以用对角化证明指出该集合无法与自然数形成一一对应的关系。第二,可以指出该集合和另一个已知其势大于
0
的集合存在一一对应的关系。
我们已经描述了几个其势等于
0
的无限集合。我们还见到了几个势等于
的集合。显而易见的问题是,是否存在势大于
的无限集合。答案是“存在”。集合的幂集一定比该集合大。因此我们可以知道,(0,1)的幂集——表示为
(0,1)——不可能和(0,1)对应。也就是说,单位区间(0,1)的子集的集合比(0,1)大。这个集合的势是
。这样的一个集合是很难想象的。不妨试试将它的一些元素写下来。
当然,我们没有止步于此的理由。我们可以继续用幂集的方式描述出势更高的集合。这些位于无限的不同层次的集合彼此不可能形成一一对应的关系。