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

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

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

2、法，并由此把“无穷的各种关系弄得完全明朗。” 第五章 无 限 集 合 5.1 可数和不可数集合 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

3、),f(n-1)那么kN, 但对每一x0,1,2,n-1, f(x)k。 这说明, f不是一个满射函数, 所以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, 记

4、为|A|=n, 记为|A|=n,这就是日常生活中的数数的概念。第五章 无 限 集 合 5.1.2 可数集合 把Z中的元素按如下顺序排列0，-1，1，-2，2，-3，3，-4，4，让上面的每个元素与它的序号对应就建立了一个从Z到N的一一映射。是否说明Z与N的元素个数相同？第五章 无 限 集 合 某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只 是房间数不是有限而是无穷多间，房间号码为1，2，3， 我们不妨管它叫无穷旅馆。 有一天开大会，所有房间都住满了。后来来了一位客人，坚持 要住房间。旅馆老板于是引用“旅馆公理”说：“满了就是满了， 非常对不起！”。正好这时候，聪明的旅馆老板的女儿来了，

5、她 看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬 一下，从这间房搬到下一间”。于是1号房间的客人搬到2号房 间，2号房间的客人搬到3号房间依此类推。最后1号房间空 出来，请这位迟到的客人住下了。这是怎么回事呢？ 第二天又来了五对夫妇旅游度假。无穷饭店能不能接待他们？ 可以，老板聪明了，只不过把每个客人都一一移到高5号的房间 中去，空出的1到5号房就给这5对夫妇。 第三天，无穷旅馆又来了一个庞大的代表团要求住旅馆，他们 声称有可数无穷多位代表一定要住，这回不仅把老板难住了， 连女儿也被难住了。聪明的女儿想了很久，终于也想出了办法 。 你想到了吗？第五章 无 限 集 合 运用了一一对应

6、的方法： 第一天让住第n间房的人搬到第n+1间房： 2 3 4 5 6n 3 4 5 6 7n+1 这样就空出了第1间房；第二天让住第n间房的人搬到第n+6间 房，这样就空出了5间房；第三天呢？她说：“您让1号房间客 人搬到2号，2号房间客人搬到4号，k号房间客人搬到2k 号，这样，1号，3号，5号，房间就都空出来了，代表团 的代表都能住下了。” 如我们所知，任何一个有限集都不能与它的一个真子集建立 一一对应的关系。对于无穷集这点就不成立了。看上去这 样就违反了整体大于局部这一古老法则。确实，一个无穷集 可以定义为能够与它的一个真子集一一对应的集。 第五章 无 限 集 合 关于无穷大还有很多悖

7、论。计数用的数是无穷 大等级中最低一级的无穷数。在整个宇宙中的 点数是第二级无穷大数，第三级无穷大数比这 要多得多！ 德国数学家乔治康托发现了无穷大的这种等级 ，他把这种新型的奇异等级称为阿列夫零、阿 列夫1、阿列夫2等等。关于阿列夫数有很多深 刻的神秘性，解决它们是现代数学中最激动人 心的挑战之一。 第五章 无 限 集 合 5.1.2 可数集合 度量集合大小的数叫基数或势。为确定有限集的大小, 我们把称作N的初始段的集合0,1,n-1作为“标准集合”, 用双射函数做工具, 对它们进行比较。当且仅当从0,1,2,n-1到集合A存在一双射函数时, 称集合A具有基数n, 记为|A|=n, 记为|A

8、|=n,这就是日常生活中的数数的概念。 现在我们将这种想法加以推广。 通过选取一些新的“标准集合”, 建立无限集合的基数的概念。 第五章 无 限 集 合 定义5.1-3 如果存在一个从N到A的双射函数,那么集合A的基数是 0 , 记为|A|= 。显然, 存在从N到N的双射函数, 所以, |N|= , 读做阿列夫零, 是希伯来文第一个字母。 第五章 无 限 集 合 例2函数f: NI+, f(x)=x+1是一双射函数。 函数f: NI , 当x是偶数时 当x是奇数时 是一双射函数。 第五章 无 限 集 合 定义5.1-4 如果存在从N的初始段到集合A的双射函数, 则称集合A是可数的或可列的;如果

9、 , 则称集合A是可数无限的; 如果集合A不是可数的, 则称集合A是不可数的或不可数无限的。 一个集合A, 如果它的元素可列成表, 我们说这个集合是可枚举的。这个表可以是有限的也可以是无限的, A的元素也可以在表中重复出现, 即不要求表中的所有项都是有别的。 如果一张表列出集合A, 那么表的每一项是A的一个元素, 而A的每一元素是表的一项。 第五章 无 限 集 合 定义5.1-5 设A是一集合, A的枚举是从N的初始段到A的一个满射函数f。如果f也是单射的(所以是双射的), 那么f是一个无重复枚举; 如果f不是单射的, 那么f是重复枚举。枚举函数f通常是用给出序列f(0),f(1),f(2),

10、含蓄地指定。 第五章 无 限 集 合 例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 实数的子集0,1不是可数无限。第五章 无 限 集 合 定义5.1-6 如果有从0

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

12、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(

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

14、开始研究 流体力学。在1897年，策梅洛去了格丁根，那时是整个世界的 数学研究的中心，在那里他于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的每一个都

15、是无限的。若不然, A将等于两个有限集合A-a0,a1,an和a0,a1,an的并, 而两个有限集合的并是有限集合, 与A是无限集合矛盾。这样, 我们能从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)|。 ;下面我们证明|A|(A)|。;设g:A(A)是任意函数, 我们要证明g不是满射的, 因而不是 双射的。函数g映射A的每一元素x到A的