离散数学无限集合1115版

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 无 限 集 合,无限集合如何计数,？,偶数的个数比自然数的个数少。 五年级,20世纪著名数学家希尔伯特(D.Hilbert),没有任何问题可以像无穷那样深深地触动人的情感, 很少有别的观念能像无穷那样鼓励理智、产生富有成果的思想,然而也没有任何其他的概念能像无穷那样需要加以说明。,康托被誉为对20世纪数学开展的影响最深的学者之一，他的研究就是从查点集合中元素数目开场的，而其独创性在于对无限集合自然数集、整数集等的研究。康托发现人们在计数时应用了一一对应的方法，并由此把“无穷的各种关系弄得完全明朗。,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,是有限的, 具有,基数,n,N,。 如果集合,A,不是有限的, 那么它,是无限的,。,定理5.1-1,自然数集合,N,是无限的。,证,为了证明,N,不是有限的, 我们必须证明没有,n,N,使从0,1,2,n,-1 到,N,的双射函数存在。设,n,是,N,的任意元素,f,是任意从0,1,n,-1到,N,的函数, 令,k,=1+max,f,(0),f,(1),f,(,n,-1)那么,k,N, 但对每一,x,0,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, 记为|A|=n, 记为|A|=n,这就是日常生活中的数数的概念。,5.1.2 可数集合,把Z中的元素按如下顺序排列0，-1，1，-2，2，-3，3，-4，4，让上面的每个元素与它的序号对应就建立了一个从Z到N的一一映射。,是否说明Z与N的元素个数一样？,某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只,是房间数不是有限而是无穷多间，房间号码为1，2，3，,我们不妨管它叫无穷旅馆。,有一天开大会，所有房间都住满了。后来来了一位客人，坚持,要住房间。旅馆老板于是引用“旅馆公理说：“满了就是满了，,非常对不起！。正好这时候，聪明的旅馆老板的女儿来了，她,看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬,一下，从这间房搬到下一间。于是1号房间的客人搬到2号房,间，2号房间的客人搬到3号房间依此类推。最后1号房间空,出来，请这位迟到的客人住下了。这是怎么回事呢？,第二天又来了五对夫妇旅游度假。无穷饭店能不能接待他们？,可以，老板聪明了，只不过把每个客人都一一移到高5号的房间,中去，空出的1到5号房就给这5对夫妇。,第三天，无穷旅馆又来了一个庞大的代表团要求住旅馆，他们,声称有可数无穷多位代表一定要住，这回不仅把老板难住了，,连女儿也被难住了。聪明的女儿想了很久，终于也想出了方法。,你想到了吗？,运用了一一对应的方法：,第一天让住第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号，房间就都空出来了，代表团,的代表都能住下了。,如我们所知，任何一个有限集都不能与它的一个真子集建立一一对应的关系。对于无穷集这点就不成立了。看上去这样就违反了整体大于局部这一古老法那么。确实，一个无穷集可以定义为能够与它的一个真子集一一对应的集。,关于无穷大还有很多悖论。计数用的数是无穷大等级中最低一级的无穷数。在整个宇宙中的点数是第二级无穷大数，第三级无穷大数比这要多得多！,德国数学家乔治康托发现了无穷大的这种等级，他把这种新型的奇异等级称为阿列夫零、阿列夫1、阿列夫2等等。关于阿列夫数有很多深刻的神秘性，解决它们是现代数学中最冲动人心的挑战之一。,5.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,函数,f,:,N,I,+,f,(,x,)=,x,+1是一双射函数。,函数,f,:,N,I,当,x,是偶数时,当,x,是奇数时,是一双射函数。,定义5.1-4 如果存在从N的初始段到集合A的双射函数, 那么称集合A是可数的或可列的;如果 , 那么称集合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),含蓄地指定。,例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,1到集合,A,的双射函数,那么,A,的基数是,c,。,选用字母,c,是根据集合0,1常叫做连续统(Continuum)这个事实。,连续统是一个数学概念。当人们笼统地说：“在实数集里实数可以连续变动，也就可以说实数集是个连续统；更严格的描述需要使用序理论、拓扑学等数学工具。这里的连续是相对于离散的概念而言的。在不讨论准确的定义前，有时人们也会谈到一个量可以在某范围内连续取值，或者说该量的变化范围是一个连续统。在数学上，连续统这一术语至少有两种准确定义，但并不等价。,5.2 基数的比较,5.2.1 基数比较,我们知道, 如果A和B是有限集, |A|=n, |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) ,设,A,和,B,是集合,那么下述情况恰有一个成立:,(,a,) |,A,|,B,|, (,b,) |,B,|,A,|, (,c,) |,A,|=|,B,|。,第二个定理断言关系是反对称的。,策梅洛德语：Ernst Friedrich FerdinandZermelo1871年7月,27日1953年5月21日,生于柏林，是德国数学家，其工作主要为,数学根底，因而对哲学有重要影响。1889,年，他毕业于柏林大学。他然后在柏林大,学、Halle和弗莱堡研究数学、物理和哲学,。他于1894年在柏林大学完成博士学位，,其博士论文是关于变分法的。策梅洛留在,柏林大学，他被聘为普朗克的助手，在其指导下，他开场研究,流体力学。在1897年，策梅洛去了格丁根，那时是整个世界的,数学研究的中心，在那里他于1899年完成了教员资格论文。策,海洛于1953年5月21日在弗赖堡逝世。,定理5.2-5,设,A,是有限集合, 那么 。,5.2.3 无限集合的特性,定理5.2-6,每一无限集合包含一可数无限集合。,证,设,A,是无限集合, 应用选择公理于A的子集的序列，我们构造一无限序列,a,0,a,1,a,2,如下:,从,A,中选取,a,0,从,A,-,a,0,中 选取,a,1,从,A,-,a,0,a,1,中选取,a,2,从,A,-,a,0,a,1,a,2,中选取,a,3,集合A-a0,a1,a2,an的每一个都是无限的。假设不然, 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,:,B,A,f,(,x,)=,x,x,B,是从,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,的子集,g,(,x,), 元素,x,可能在子集,g,(,x,)中, 即,x,g,(,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)|,如果集合,A,有,n,个元素, 则,(,A,)有2,n,个元素, 本节例3证明了,(,N,)=,c, 于是人们认为 。,A,是有限集时, |,A,|和|,(,A,)|之间存在着其它基数, 于是康脱提出和,c,之间是否也存在其它基数 连续统假设断言不存在这样的基数。 从前已经知道连续统假设和集合论公理是一致的。但1963年科恩(Paue Cohen)证明连续统假设的反命题也和集合论公理一致，即连续统假设和集合论公理是独立的。这就给我们带来一个问题, 例如, 我们要证明所给集合A有基数c, 如果接受连续统假设, 那么我们只需证明|A|c和 。 如果拒绝这一假设, 那么这样的证明是不充分的, 可能有 。 我们应避开使用这一假设。,