有限集合与无限集合
无限集合就是不是有限的集合;对正整数的集合来说,这意味着没有最大的元素。
为什么重要
本章其余部分的每一个定义,都建立在两个词上:有限和无限。“只有有限多项落在带外”就是极限的全部内容;而“除有限多个以外的所有 ”与“无穷多个 ”之间的差别,就是收敛与不收敛之间的差别。§52 停下来说明这两个词是什么意思,特别是说明“无穷数目”不是一个数。
基本想法
一个类 (class),今天叫作集合 (set),是具有某种性质的所有事物的全体:英国臣民、议会议员、正整数、实数。如果一个集合有某个确定的元素个数 ,哪怕谁也不知道这个数是多少,它就是有限的。哈代的例子是过去、现在和将来全体英国臣民组成的集合:它是有限的,尽管我们说不出它有多少个元素。
正整数就不一样了。随便说出一个数 ,无论它多么大(一千、一百万),正整数都多于 个:光是 就已经够了。“无限”的意思就只是这样。试试下面的挑战:说出一个数,看看每个集合能不能胜过它。
试一试:选一个集合,把 调大。试试 的因数,先取 ,再取 。然后选素数,对几个不同的 读一读“欧几里得的证据”。
留意什么
无限集合对每个 都能拿出 个元素来应对。有限集合则在某个确定的地方用完,而且从此再也拿不出来。素数是有意思的情形:我们之所以能列出 个素数,只是因为欧几里得的论证保证了任何有限的素数表都不完整;“证据”每次都用旧的素数造出一个新的素数。
所以,“素数有无穷多个”是“素数组成的集合不是有限的”的简略说法。它并不是说素数的个数是某个叫作“无穷”的巨大的数。同样的提醒在 §55 中还会出现,符号 就是在那里第一次登场的。
精确表述
如果对某个整数 ,一个集合的元素可以列成 (空集取 ),就说这个集合是有限的。不是有限的集合称为无限的。等价地说,如果对每个正整数 ,一个集合的元素都多于 个,它就是无限的。
对正整数的集合(后面几节只需要这种集合),有一个更精确、也非常实用的判别方法。
正整数的集合 是有限的,当且仅当 是空集,或者 有最大的元素。等价地说, 是无限的,当且仅当对每个 , 都含有某个 。
素数组成的集合是无限的。
证明
有限的一张表有最大的一项;反过来,有最大元素 的正整数集合包含在 之中,而后者是有限的。
有限且非空,则有最大元素
把元素列成 ,其中 。两个数中总有较大的一个,把这一步重复 次,就得到 中最大的一个。
有最大元素,则有限
设 是最大的元素,那么每个元素都是 中的一个。所以 至多有 个元素;把 中属于 的那些列出来,就得到一张有限的表。
改写成关于无限集合的说法
取否定。 是无限的,当且仅当它非空且没有最大元素,也就是说,每个元素 (从而任何一个数 )都被 的某个元素超过。
这个定理把“有限多个例外”转化成了“过了某个位置就没有例外”。这一转化就是下一节的全部内容。
证明任何有限的素数表都不可能包含所有素数:由这张表造出一个数,它的素因数都不在表中。
任取一张有限的素数表
设 是任意一些素数(例如前 个)。
令
于是 ,所以 至少有一个素因数:它大于 的最小因数是素数,因为这个因数的任何因数都会是 的更小的因数。
没有哪个 整除
用 去除 ,余数是 ,因为 整除乘积 。所以 的每个素因数都是不在表中的素数。
得出结论
每张有限的素数表都漏掉了某个素数,所以素数组成的集合不是有限的。用定义的语言说:对每个 ,素数都多于 个。
注意 本身不一定是素数:。论证只需要 的某个素因数是新的。
例题与习题
判断下列集合是有限的还是无限的:(a) 完全平方数;(b) 满足 的正整数 ;(c) 的倍数;(d) 的实根;(e) 中的分数;(f) 2000 年以后的闰年。
提示
解答
(a) 无限: 是 个不同的元素。(b) 有限: 迫使 ,所以恰有 个元素。(c) 无限:。(d) 有限: 次多项式至多有 个根(实际上这个多项式有 个实根)。(e) 无限:。(f) 无限:按格里高利历的规则,每个 年()都是闰年。
证明:(a) 有限集合的子集是有限的;(b) 两个有限集合的并集是有限的;(c) 含有无限子集的集合是无限的。
解答
(a) 若 有 个元素且 ,把 的元素列出来,只保留属于 的那些,就把 列成了至多 项的表。(b) 若 有 个元素, 有 个,先列出 再列出 ,就列出了并集的每个元素,至多 项;再去掉重复的即可。(c) 设 , 是无限的;如果 是有限的,那么由 (a), 也是有限的,矛盾。
把正整数分成两个集合 和 ,使每个正整数恰好属于其中一个。证明 、 中至少有一个是无限的,并分别举例说明:(i) 只有 是无限的;(ii) 两者都是无限的。
提示
解答
如果两者都是有限的,那么由 (b),它们的并集,即全体正整数组成的集合,也是有限的,而事实并非如此。例子:(i) ,;(ii) 为偶数, 为奇数。这恰好就是哈代在 §53 中区分的情形 (a) 和 (c),其中 是具有某个性质的 , 是不具有这个性质的那些。
计算 和 ,并为每一个找出一个不在所用素数之中的素因数。
解答
,它本身就是素数(它不能被 或 整除,而 )。;素数 不在 之中。(另一个因数 不是素数,但我们只需要一个新的素数。)
自测
“素数有无穷多个”的意思是:素数的个数是一个叫作无穷的非常大的数。
错。它的意思只是素数组成的集合不是有限的:对每个 ,素数都多于 个。并不存在一个数“无穷”来计算素数的个数;正如哈代所强调的,这句话只是一种简略说法。
哈代说,过去、现在和将来全体英国臣民组成的集合是有限的。为什么?
有限是集合本身的性质,与我们有没有能力把它数出来无关。一个集合可以是有限的,而元素个数未知。比整数“小”并不是定义(而且有些无限集合,比如偶数,也是整数的一部分)。
正整数的集合 具有这样的性质:对每个 , 都有某个元素大于 。你能得出什么结论?
一个在任何界限之外都有元素的正整数集合没有最大元素,所以由定理,它是无限的。它不一定包含所有大的整数:偶数在任何界限之外都有,却漏掉了每一个奇数。这个差别正是下一节的主题。
哈代的用语
But the reader must be careful always to remember that by saying this we mean simply that the class in question has not a finite number of members such as 1000, or 1,000,000.
但读者必须时时小心记住:我们这样说,意思仅仅是所说的这个类的元素个数不是像 1000 或 1,000,000 这样的有限数。
小结
- 如果一个类(集合)有某个确定的元素个数 ,无论这个数是否已知,它就是有限的;不是有限的,就是无限的。
- 等价地说,无限的意思是:对每个 ,元素都多于 个。“无穷数目”是一种简略说法,不是一个数。
- 正整数的集合是有限的,当且仅当它是空集或者有最大元素;它是无限的,当且仅当它在每个 之外都有元素。
- 欧几里得:任何有限的素数表都会漏掉某个素数,所以素数组成无限集合。