第四章 · 正整数变量的函数的极限

有限集合与无限集合

§52 20 分钟

无限集合就是不是有限的集合;对正整数的集合来说,这意味着没有最大的元素。

为什么重要

本章其余部分的每一个定义,都建立在两个词上:有限和无限。“只有有限多项落在带外”就是极限的全部内容;而“除有限多个以外的所有 nn”与“无穷多个 nn”之间的差别,就是收敛与不收敛之间的差别。§52 停下来说明这两个词是什么意思,特别是说明“无穷数目”不是一个数。

基本想法

一个类 (class),今天叫作集合 (set),是具有某种性质的所有事物的全体:英国臣民、议会议员、正整数、实数。如果一个集合有某个确定的元素个数 0,1,2,…0, 1, 2, \dots,哪怕谁也不知道这个数是多少,它就是有限的。哈代的例子是过去、现在和将来全体英国臣民组成的集合:它是有限的,尽管我们说不出它有多少个元素。

正整数就不一样了。随便说出一个数 nn,无论它多么大(一千、一百万),正整数都多于 nn 个:光是 1,2,…,n+11, 2, \dots, n+1 就已经够了。“无限”的意思就只是这样。试试下面的挑战:说出一个数,看看每个集合能不能胜过它。

探索 说出一个数:这个集合能胜过它吗?

试一试:选一个集合,把 nn 调大。试试 360360 的因数,先取 n=23n = 23,再取 n=24n = 24。然后选素数,对几个不同的 nn 读一读“欧几里得的证据”。

集合 {2,3,5,7,… }\{2, 3, 5, 7, \dots\}
这里有 11 个不同的元素,多于 n=10n = 10:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31。欧几里得:任何有限的素数表都不可能是完整的(见下文)。
欧几里得的证据。把前 10 个素数(2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29)相乘再加 1:P=6469693231P = 6469693231。用其中任何一个素数去除 PP,余数都是 1,所以 PP 的最小素因数 331331 是表中没有的素数。
留意什么

无限集合对每个 nn 都能拿出 n+1n + 1 个元素来应对。有限集合则在某个确定的地方用完,而且从此再也拿不出来。素数是有意思的情形:我们之所以能列出 n+1n + 1 个素数,只是因为欧几里得的论证保证了任何有限的素数表都不完整;“证据”每次都用旧的素数造出一个新的素数。

所以,“素数有无穷多个”是“素数组成的集合不是有限的”的简略说法。它并不是说素数的个数是某个叫作“无穷”的巨大的数。同样的提醒在 §55 中还会出现,符号 ∞\infty 就是在那里第一次登场的。

精确表述

定义 有限集合与无限集合 哈代:§52

如果对某个整数 N≥0N \ge 0,一个集合的元素可以列成 a1,a2,…,aNa_1, a_2, \dots, a_N(空集取 N=0N = 0),就说这个集合是有限的。不是有限的集合称为无限的。等价地说,如果对每个正整数 nn,一个集合的元素都多于 nn 个,它就是无限的。

对正整数的集合(后面几节只需要这种集合),有一个更精确、也非常实用的判别方法。

定理 正整数的有限集合

正整数的集合 EE 是有限的,当且仅当 EE 是空集,或者 EE 有最大的元素。等价地说,EE 是无限的,当且仅当对每个 n0n_0,EE 都含有某个 n>n0n > n_0。

定理 素数有无穷多个 哈代:欧几里得;例题 XXIII, 2

素数组成的集合是无限的。

证明

证明 正整数的有限集合
思路

有限的一张表有最大的一项;反过来,有最大元素 MM 的正整数集合包含在 1,2,…,M1, 2, \dots, M 之中,而后者是有限的。

有限且非空,则有最大元素

把元素列成 a1,…,aNa_1, \dots, a_N,其中 N≥1N \ge 1。两个数中总有较大的一个,把这一步重复 N−1N - 1 次,就得到 a1,…,aNa_1, \dots, a_N 中最大的一个。

有最大元素,则有限

设 MM 是最大的元素,那么每个元素都是 1,2,…,M1, 2, \dots, M 中的一个。所以 EE 至多有 MM 个元素;把 1,…,M1, \dots, M 中属于 EE 的那些列出来,就得到一张有限的表。

改写成关于无限集合的说法

取否定。EE 是无限的,当且仅当它非空且没有最大元素,也就是说,每个元素 n0n_0(从而任何一个数 n0n_0)都被 EE 的某个元素超过。

这个定理把“有限多个例外”转化成了“过了某个位置就没有例外”。这一转化就是下一节的全部内容。

证明 素数有无穷多个
思路

证明任何有限的素数表都不可能包含所有素数:由这张表造出一个数,它的素因数都不在表中。

任取一张有限的素数表

设 p1,p2,…,pNp_1, p_2, \dots, p_N 是任意一些素数(例如前 NN 个)。

令 P=p1p2⋯pN+1P = p_1 p_2 \cdots p_N + 1

于是 P≥2P \ge 2,所以 PP 至少有一个素因数:它大于 11 的最小因数是素数,因为这个因数的任何因数都会是 PP 的更小的因数。

没有哪个 pkp_k 整除 PP

用 pkp_k 去除 PP,余数是 11,因为 pkp_k 整除乘积 p1⋯pNp_1 \cdots p_N。所以 PP 的每个素因数都是不在表中的素数。

得出结论

每张有限的素数表都漏掉了某个素数,所以素数组成的集合不是有限的。用定义的语言说:对每个 nn,素数都多于 nn 个。

注意 PP 本身不一定是素数:2⋅3⋅5⋅7⋅11⋅13+1=30031=59⋅5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509。论证只需要 PP 的某个素因数是新的。

例题与习题

习题 有限还是无限? ●○○ 哈代:§52

判断下列集合是有限的还是无限的:(a) 完全平方数;(b) 满足 n2<1000n^2 < 1000 的正整数 nn;(c) 100100 的倍数;(d) x5−3x+1=0x^5 - 3x + 1 = 0 的实根;(e) (0,1)(0, 1) 中的分数;(f) 2000 年以后的闰年。

提示
对每个无限集合,说明对任意 nn 怎样拿出多于 nn 个元素。对每个有限集合,给出元素个数的一个上界。

解答

(a) 无限:12,22,…,(n+1)21^2, 2^2, \dots, (n+1)^2 是 n+1n + 1 个不同的元素。(b) 有限:n2<1000n^2 < 1000 迫使 n≤31n \le 31,所以恰有 3131 个元素。(c) 无限:100,200,…,100(n+1)100, 200, \dots, 100(n+1)。(d) 有限:55 次多项式至多有 55 个根(实际上这个多项式有 33 个实根)。(e) 无限:12,13,…,1n+2\tfrac12, \tfrac13, \dots, \tfrac{1}{n+2}。(f) 无限:按格里高利历的规则,每个 2000+400k2000 + 400k 年(k≥1k \ge 1)都是闰年。

习题 集合的组合 ●○○ 哈代:§52

证明:(a) 有限集合的子集是有限的;(b) 两个有限集合的并集是有限的;(c) 含有无限子集的集合是无限的。

解答

(a) 若 AA 有 NN 个元素且 B⊆AB \subseteq A,把 AA 的元素列出来,只保留属于 BB 的那些,就把 BB 列成了至多 NN 项的表。(b) 若 AA 有 MM 个元素,BB 有 NN 个,先列出 AA 再列出 BB,就列出了并集的每个元素,至多 M+NM + N 项;再去掉重复的即可。(c) 设 C⊇BC \supseteq B,BB 是无限的;如果 CC 是有限的,那么由 (a),BB 也是有限的,矛盾。

习题 两个互补的集合 ●●○ 哈代:§52

把正整数分成两个集合 AA 和 BB,使每个正整数恰好属于其中一个。证明 AA、BB 中至少有一个是无限的,并分别举例说明:(i) 只有 AA 是无限的;(ii) 两者都是无限的。

提示
利用上一题的 (b)。

解答

如果两者都是有限的,那么由 (b),它们的并集,即全体正整数组成的集合,也是有限的,而事实并非如此。例子:(i) A={n:n≥10}A = \{n : n \ge 10\},B={1,…,9}B = \{1, \dots, 9\};(ii) AA 为偶数,BB 为奇数。这恰好就是哈代在 §53 中区分的情形 (a) 和 (c),其中 AA 是具有某个性质的 nn,BB 是不具有这个性质的那些。

习题 欧几里得数 ●○○ 哈代:例题 XXIII, 2

计算 P=2⋅3⋅5⋅7+1P = 2 \cdot 3 \cdot 5 \cdot 7 + 1 和 P′=2⋅3⋅5⋅7⋅11⋅13⋅17+1P' = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 + 1,并为每一个找出一个不在所用素数之中的素因数。

解答

P=211P = 211,它本身就是素数(它不能被 2,3,5,7,112, 3, 5, 7, 11 或 1313 整除,而 172>21117^2 > 211)。P′=510511=19⋅26869P' = 510511 = 19 \cdot 26869;素数 1919 不在 2,…,172, \dots, 17 之中。(另一个因数 26869=97⋅27726869 = 97 \cdot 277 不是素数,但我们只需要一个新的素数。)

自测

自测 判断对错

“素数有无穷多个”的意思是:素数的个数是一个叫作无穷的非常大的数。

解析

错。它的意思只是素数组成的集合不是有限的:对每个 nn,素数都多于 nn 个。并不存在一个数“无穷”来计算素数的个数;正如哈代所强调的,这句话只是一种简略说法。

自测 单项选择

哈代说,过去、现在和将来全体英国臣民组成的集合是有限的。为什么?

解析

有限是集合本身的性质,与我们有没有能力把它数出来无关。一个集合可以是有限的,而元素个数未知。比整数“小”并不是定义(而且有些无限集合,比如偶数,也是整数的一部分)。

自测 单项选择

正整数的集合 EE 具有这样的性质:对每个 n0n_0,EE 都有某个元素大于 n0n_0。你能得出什么结论?

解析

一个在任何界限之外都有元素的正整数集合没有最大元素,所以由定理,它是无限的。它不一定包含所有大的整数:偶数在任何界限之外都有,却漏掉了每一个奇数。这个差别正是下一节的主题。

哈代的用语

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 这样的有限数。

——G. H. 哈代,§52

小结

小结
  • 如果一个类(集合)有某个确定的元素个数 NN,无论这个数是否已知,它就是有限的;不是有限的,就是无限的。
  • 等价地说,无限的意思是:对每个 nn,元素都多于 nn 个。“无穷数目”是一种简略说法,不是一个数。
  • 正整数的集合是有限的,当且仅当它是空集或者有最大元素;它是无限的,当且仅当它在每个 n0n_0 之外都有元素。
  • 欧几里得:任何有限的素数表都会漏掉某个素数,所以素数组成无限集合。