离散数学—无限集合(11.15版)

《离散数学—无限集合(11.15版)》由会员分享，可在线阅读，更多相关《离散数学—无限集合(11.15版)（30页珍藏版）》请在金锄头文库上搜索。

1、第五章 无 限 集 合,5.1 可数和不可数集合5.2 基数的比较5.3 基数算术 （了解）,无限集合如何计数？,偶数的个数比自然数的个数少。（ ）（五年级）20世纪著名数学家希尔伯特(D.Hilbert) 没有任何问题可以像无穷那样深深地触动人的情感, 很少有别的观念能像无穷那样激励理智、产生富有成果的思想,然而也没有任何其他的概念能像无穷那样需要加以阐明。 康托被誉为对20世纪数学发展的影响最深的学者之一，他的研究就是从查点集合中元素数目开始的，而其独创性在于对无限集合（自然数集、整数集等）的研究。康托发现人们在计数时应用了一一对应的方法，并由此把“无穷的各种关系弄得完全明朗。”,5.1

2、可数和不可数集合,5.1.1 有限和无限集合,定义5.1-1 N的初始段是前n个(包括0个)自然数的集合0,1,n-1或N自身。 定义5.1-2 如果有从N的初始段0,1,n-1到A的双射函数, 那么集合A是有限的, 具有基数nN。 如果集合A不是有限的, 那么它是无限的。,定理5.1-1 自然数集合N是无限的。 证 为了证明N不是有限的, 我们必须证明没有nN使从0,1,2,n-1 到N的双射函数存在。设n是N的任意元素, f是任意从0,1,n-1到N的函数, 令k=1+maxf(0),f(1),f(n-1)那么kN, 但对每一x0,1,2,n-1, f(x)k。 这说明, f不是一个满射函

3、数, 所以f不是一个双射函数。 因为n和f都是任意选取的, 我们得出N是无限的。 证毕。,定理5.1-2 有限集合的每一子集是有限的。 推论5.1-2 设S是T的子集, 如果S是无限集, 那么T是无限集。,5.1.2 可数集合 度量集合大小的数叫基数或势。为确定有限集的大小, 我们把称作N的初始段的集合0,1,n-1作为“标准集合”, 用双射函数做工具, 对它们进行比较。当且仅当从0,1,2,n-1到集合A存在一双射函数时, 称集合A具有基数n, 记为|A|=n, 记为|A|=n,这就是日常生活中的数数的概念。,5.1.2 可数集合 把Z中的元素按如下顺序排列0，-1，1，-2，2，-3，3，

4、-4，4，让上面的每个元素与它的序号对应就建立了一个从Z到N的一一映射。 是否说明Z与N的元素个数相同？,某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为1，2，3，我们不妨管它叫无穷旅馆。有一天开大会，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老板于是引用“旅馆公理”说：“满了就是满了，非常对不起！”。正好这时候，聪明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬一下，从这间房搬到下一间”。于是1号房间的客人搬到2号房间，2号房间的客人搬到3号房间依此类推。最后1号房间空出来，请这位迟到的客人住下了。

5、这是怎么回事呢？第二天又来了五对夫妇旅游度假。无穷饭店能不能接待他们？可以，老板聪明了，只不过把每个客人都一一移到高5号的房间中去，空出的1到5号房就给这5对夫妇。第三天，无穷旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数无穷多位代表一定要住，这回不仅把老板难住了，连女儿也被难住了。聪明的女儿想了很久，终于也想出了办法。你想到了吗？,运用了一一对应的方法：第一天让住第n间房的人搬到第n+1间房：2 3 4 5 6n3 4 5 6 7n+1这样就空出了第1间房；第二天让住第n间房的人搬到第n+6间房，这样就空出了5间房；第三天呢？她说：“您让1号房间客人搬到2号，2号房间客人搬到4号，k号

6、房间客人搬到2k号，这样，1号，3号，5号，房间就都空出来了，代表团的代表都能住下了。”,如我们所知，任何一个有限集都不能与它的一个真子集建立一一对应的关系。对于无穷集这点就不成立了。看上去这样就违反了整体大于局部这一古老法则。确实，一个无穷集可以定义为能够与它的一个真子集一一对应的集。,关于无穷大还有很多悖论。计数用的数是无穷大等级中最低一级的无穷数。在整个宇宙中的点数是第二级无穷大数，第三级无穷大数比这要多得多！德国数学家乔治康托发现了无穷大的这种等级，他把这种新型的奇异等级称为阿列夫零、阿列夫1、阿列夫2等等。关于阿列夫数有很多深刻的神秘性，解决它们是现代数学中最激动人心的挑战之一。,5

7、.1.2 可数集合 度量集合大小的数叫基数或势。为确定有限集的大小, 我们把称作N的初始段的集合0,1,n-1作为“标准集合”, 用双射函数做工具, 对它们进行比较。当且仅当从0,1,2,n-1到集合A存在一双射函数时, 称集合A具有基数n, 记为|A|=n, 记为|A|=n,这就是日常生活中的数数的概念。 现在我们将这种想法加以推广。 通过选取一些新的“标准集合”, 建立无限集合的基数的概念。,定义5.1-3 如果存在一个从N到A的双射函数,那么集合A的基数是 0 , 记为|A|= 。 显然, 存在从N到N的双射函数, 所以, |N|= , 读做阿列夫零, 是希伯来文第一个字母。,例2,函数

8、f: NI+, f(x)=x+1是一双射函数。,是一双射函数。,定义5.1-4 如果存在从N的初始段到集合A的双射函数, 则称集合A是可数的或可列的;如果 , 则称集合A是可数无限的; 如果集合A不是可数的, 则称集合A是不可数的或不可数无限的。,一个集合A, 如果它的元素可列成表, 我们说这个集合是可枚举的。这个表可以是有限的也可以是无限的, A的元素也可以在表中重复出现, 即不要求表中的所有项都是有别的。 如果一张表列出集合A, 那么表的每一项是A的一个元素, 而A的每一元素是表的一项。,定义5.1-5 设A是一集合, A的枚举是从N的初始段到A的一个满射函数f。如果f也是单射的(所以是双

9、射的), 那么f是一个无重复枚举; 如果f不是单射的, 那么f是重复枚举。 枚举函数f通常是用给出序列f(0),f(1),f(2),含蓄地指定。,例3 (1) 如果A=x,y, 那么x,y,x和y,x都是A的有限枚举, 第一个是重复枚举, 第二个是无重复枚举。 (2) 设A是非负的3的整倍数集合, 那么 0,3,6,和3,0,9,6,15,12,都是A的无重复枚举, 后者的枚举函数是,定理5.1-3 一个集合A是可数的当且仅当存在A的枚举。 定理5.1-4 可数个可数集合的并是可数的。,5.1.3 基数c 不是所有无限集都是可数无限的, 下一定理说明需要新的无限集基数。 定理5.1-7 实数的

10、子集0,1不是可数无限。,定义5.1-6 如果有从0,1到集合A的双射函数,那么A的基数是c。 选用字母c是根据集合0,1常叫做连续统(Continuum)这个事实。,连续统是一个数学概念。当人们笼统地说：“在实数集里实数可以连续变动”，也就可以说实数集是个连续统；更严格的描述需要使用序理论、拓扑学等数学工具。这里的连续是相对于离散的概念而言的。在不讨论精确的定义前，有时人们也会谈到一个量可以在某范围内连续取值，或者说该量的变化范围是一个连续统。在数学上，连续统这一术语至少有两种精确定义，但并不等价。,5.2 基数的比较,5.2.1 基数比较 我们知道, 如果A和B是有限集, |A|=n, |

11、B|=m, 那么 (a) 如果存在一个从A到B的双射函数, 那么n=m。 (b) 如果存在一个从A到B的单射函数, 那么nm。 (c) 如果存在一个从A到B的单射函数, 但不存在双射函数, 那么nm。,定义5.2-1 设A和B是任意集合。 (1) 如果有一个从A到B的双射函数, 那么称A和B有相同的基数(或等势), 记为|A|=|B|。 (2) 如果有一个从A到B的单射函数, 那么称A的基数小于等于B的基数, 记为|A|B|。 (3) 如果有一个从A到B的单射函数, 但不存在双射函数, 那么称A的基数小于B的基数, 记为|A|B|。,第一个定理叫做三歧性定律。 定理5.2-2(Zermelo)

12、 设A和B是集合,那么下述情况恰有一个成立: (a) |A|B|, (b) |B|A|, (c) |A|=|B|。 第二个定理断言关系是反对称的。,策梅洛（德语：Ernst Friedrich FerdinandZermelo1871年7月27日1953年5月21日）生于柏林，是德国数学家，其工作主要为数学基础，因而对哲学有重要影响。1889年，他毕业于柏林大学。他然后在柏林大学、Halle和弗莱堡研究数学、物理和哲学。他于1894年在柏林大学完成博士学位，其博士论文是关于变分法的。策梅洛留在柏林大学，他被聘为普朗克的助手，在其指导下，他开始研究流体力学。在1897年，策梅洛去了格丁根，那时是

13、整个世界的数学研究的中心，在那里他于1899年完成了教员资格论文。策海洛于1953年5月21日在弗赖堡逝世。,定理5.2-5 设A是有限集合, 那么 。,5.2.3 无限集合的特性 定理5.2-6 每一无限集合包含一可数无限集合。 证 设A是无限集合, 应用选择公理于A的子集的序列，我们构造一无限序列a0,a1,a2,如下:,从A中选取a0 从A-a0中 选取a1 从A-a0,a1中选取a2 从A-a0,a1,a2中选取a3,集合A-a0,a1,a2,an的每一个都是无限的。若不然, A将等于两个有限集合A-a0,a1,an和a0,a1,an的并, 而两个有限集合的并是有限集合, 与A是无限集

14、合矛盾。这样, 我们能从A-a0,a1,an中选取一个新元素an+1, 从而能够构造一无限序列a0,a1,a2,而没有重复。这个序列的元素组成一个A的可数无限子集B。 于是定理得证。,定理5.2-7 是最小的无限集基数。 证 根据定理5.2-6, 如果A是无限集合, 那么A包含一可数无限子集B。因为映射f: BA, f(x)=x, xB是从B到A的单射函数, 这得出|B|A|, 而 , 我们得 。,5.2.4 基数的无限性和连续统假设,定理5.2-9 (Cantor)设A是一集合, 那么|A|(A)|。证 容易看出, 函数f: A(A), f(a)=a是单射的。 所以, |A|(A)|。 ;

15、下面我们证明|A|(A)|。; 设g:A(A)是任意函数, 我们要证明g不是满射的, 因而不是双射的。 函数g映射A的每一元素x到A的子集g(x), 元素x可能在子集g(x)中, 即xg(x),也可能 。定义集合S是A的子集。,现在证明对任一aA, g(a)S。用反证法, 假设g(a)=S, 则 根据S的定义 ;根据定义S的谓词 ; 根据假设g(a)=S 这是一个矛盾, 所以g(a)=S是假。因为a是任意的, 这得出g不是满射函数, 因此不是双射函数。又g是任意函数, 这证明了没有双射函数存在, 所以|A|(A)|。证毕。 应用本定理我们能够构造一个可数无限的无限基数的集合。 其中每一个都大于它前边的一个。|N|(N)|(N)|,