离散数学—无限集合[11.15版].pptVIP

第五章 无 限 集 合 ;无限集合如何计数？ ;5.1 可数和不可数集合 ; 定理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 6……n…… 3 4 5 6 7……n+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; 定义5.1-4 如果存在从N的初始段到集合A的双射函数, 则称集合A是可数的或可列的;如果 , 则称集合A是可数无限的; 如果集合A不是可数的, 则称集合A是不可数的或不可数无限的。 ; 定义5.1-5 设A是一集合, A的枚举是从N的初始段到A的一个满射函数f。如果f也