第八章函数与集合的势.ppt

《第八章函数与集合的势.ppt》由会员分享，可在线阅读，更多相关《第八章函数与集合的势.ppt（51页珍藏版）》请在三一文库上搜索。

1、1/51,第八章 函数与集合的势,8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理,2/51,哪个集合的元素多？,A=1,2,3,4,5, B=2,4,6,8,10, ,可选答案： A多 一样多 不能确定,3/51,伽利略的困惑,早在1638年，天文学家伽利略发现在一定意义下，正整数的平方数集合 S1=1, 4, 9, 16, 25, 和正整数集合 S2=1, 2, 3, 4, 5, 的元素一样多。 因为，任给一个正整数nS2，则必有唯一的一个n2S1，这是一个一一对应，说明S1与S2所含不同元素的数目相等。 但是，另一方面 S1

2、又是S2的真子集。,4/51,势(cardinality),规定用 |A| 来表示一个集合A所含有的不同元素的多少， 称为集合A的势(或称基数)。,显然， | |=0,注意： 一般规定card(A)表示集合A的势，而在A是有限集时用|A|表示，本书有限集情况较多，为统一起见用|A| 表示。,5/51,|A|=|B|,定义1 A，B是两个集合， 若存在f:AB，且 f是双射函数， 则称集合A与集合B的势相等，记为 |A|=|B|,6/51,有限集、无限集,定义2 A是一个集合， 若存在nN，使得 |A|=|0,1, ,n-1|， 则称集合A是有限集，并记 |A|=n 如果A不是有限集，它就是无限

3、集。,7/51,定理1 自然数集N是无限集。,证明：用反证法，设存在nN，使得 |N|=| 0, 1, 2, , n-1 | 。 令 g: 0, 1, 2, , n-1 N是双射。 设 k=1+maxg(0), g(1), ,g(n-1)， 显然，kN，但对于任意的x0, 1, 2, , n-1， g(x) k， 因此g不是满射函数，与 g是双射函数矛盾。 矛盾说明不存在n，使得|N|=| 0, 1, 2, , n-1 |。 所以，N不是有限集, N是无限集。,8/51,阿列夫零 0,定义3 A是一个集合，若|A|=|N|， 则称A为可数无限集，记 |A|= 0 (读作“阿列夫零”, 是康托引

4、入的)。,一个可数无限集A可以表示为 A=a1, a2, ,an, ,9/51,例 偶数与自然数一样多,B=nN存在kN，n=2k 显然， B是偶数集， 它是自然数集N的真子集。 令 g:NB，对于任意的nN， g(n)=2n 不难证明 g是双射函数，也即有 |B|=|N|= 0,10/51,例1 Z是可数无限集。,0, -1, 1, -2, 2, -3, 3, -4, 4, ,11/51,例2 两个可数无限集A和B 的 AB仍然是可数无限集,解：设 A=a1, a2, , an, B=b1, b2, , bn, 考察元素列： a1, b1, a2, b2, ,an, bn, 消去重复出现的元

5、素，可以建立N中元素与上面序列消去重复出现的元素后剩下的元素安排的次序所建立的元素之间的一一对应，也即 |AB|=0,12/51,例3 两个可数无限集A和B 的AB仍然是可数无限集,解：设 A=a1, a2, , an, , B=b1, b2, , bn, ,先把 AB中的元素按一定规则安排出来，见图8.1，每一个有序对(i,j) 表示有序对(ai,bj)，按箭头所指方向把 AB中的元素排成一列，对于任意的(i,j) NN，有关系(i1,j1):,图8.1 两个可数无限集的排列图,13/51,定理2 无限集存在可数子集,A是一个任意无限集，则A中存在子集A， |A|=0,证明：任取 A中的一个

6、元素，记a0A； 在A a0中任意取一个元素，记a1A， ，以此类推。 若Aa0, a1, ,an-1，在A a0, a1, ,an-1中任取一个元素，记为anA。 因为A是无限集，以上工作可以一直进行下去，因此建立函数f： 对应于任意的nN，f(n)=an。 f是一一对应，也即|A|=0，且 AA。,14/51,定理3 无限集存在等势的真子集,A是无限集当且仅当 A中存在真子集A，使 |A|=|A|。,分析： A=a1,a2,a3, A A= (A-A) a1,a2,a3,a4, A= (A-A) a2,a3,a4,15/51,定理3 A是无限集当且仅当A中存在真子集A，使 |A|=|A|。

7、,证明：A是无限集， 则A 中有子集A”, 使得|A”|=0 。 设A”= a1，a2，a3, 。 令 A=A a1，则 A是A的真子集。 作 f: AA，,显然, f是一一对应，即 |A|=|A|。,16/51,定理3 A是无限集当且仅当A中存在真子集A，使 |A|=|A|。,证明： 用反证法， 若A不是无限集， 则 A是有限集，不妨设|A|=n， 并设A=a1,a2, ,an。 则A的任何真子集与A之间不存在一一对应，与条件矛盾。 故 A是无限集。,17/51,例4 A=xR0x1不是可数无限集,证：若|A|=0， 则存在g: NA， g是双射。 不失一般性，设 g(0)=0.a00a01

8、a02a03a04 g(1)=0.a10a11a12a13a14 g(2)=0.a20a21a22a23a24 g(3)=0.a30a31a32a33a34 g(4)=0.a40a41a42a43a44 ,g(0)=0.a00a01a02a03a04 g(1)=0.a10a11a12a13a14 g(2)=0.a20a21a22a23a24 g(3)=0.a30a31a32a33a34 g(4)=0.a40a41a42a43a44 ,作：b=0.b0b1b2b3b4,显然, 如果aii bi, 则 g(i) b,19/51,例4 证(续),作：b=0.b0b1b2，其中,显然，0b1，即bA，

9、但 iN，g(i) b， 这是因为iN，aii bi。 这与g是双射矛盾，矛盾说明|N|A|。 即A不是可数无限集。,20/51,例5,设 A=xR0x1，则|A|=|R|， 其中R 是实数集。 解：令 g:AR， xA，g(x)=cot(x)。 则 g是一个双射， 故有 |R|=|A|。,注意: cot(0)与cot()没有定义, 书上有误.,21/51,例6,设A=xR0 x 1，B=xR0 x 1 求证： |A|=|B|。,证明：作 g:AB， g(0)=0,显然，g是双射，所以|A|=|B|。,22/51,例,用势相等的定义证明下面两集合等势。 A=xR0x1 A=xR0x1 其中 R

10、是实数集。,23/51,例 设A,B,C,D为四个集合。若 |A|=|B|, |C|=|D|, 且 AC=, BD= 则 |AC|=|BD|,证： 因为 |A|=|B|，故存在A到B双射函数f: AB,又因 |C|=|D|，故存在C到D双射函数g: CD 现在定义从AC到BD的函数h如下： 对于任意元素x AC,显然，由交集为空集的条件知，h(x)有唯一定义。容易说明h(x)为双射函数。,24/51,第八章 函数与集合的势,8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理,25/51,|A|B| 与 |A|B|,定义 A、B是两个

11、集合， 若存在f:AB是单射函数， 则称集合A的势小于等于集合B的势，记为 |A|B|。 若|A|B| 且|A|B|， 则称集合A的势小于集合B的势，记为 |A|B|。,26/51,|N| |R|,例4(p98) A=xR0x1不是可数无限集,27/51,定理1 |A|2A|,证：作 g:A2A， 对于xA，令g(x)=x。 显然，g是一个函数，且是单射函数， 故有|A|2A|。 可用反证法证明 |A|2A|。,28/51,反证法证明 |A|2A|,若存在:A2A双射， 则xA, (x) 2A, 即(x)A。 构造集合M=xxA且x(x)。 由M定义, 有AM，即M2A。 因为是双射， 所以存

12、在aA，使得(a)=M。,29/51,反证法证明 |A|2A|,下面我们来看一个矛盾现象， a是一个元素， M是一个集合，按我们约定：aM或者aM，二者有一种且仅有一种可能出现。 若aM，因为(a)=M，所以 a(a)，但由M的定义知 aM，矛盾。所以 aM不成立。 若aM，因为(a)=M，所以 a(a)，但由M的定义知 aM, 又出现矛盾。所以aM也不成立。 出现这种矛盾现象说明假设有问题， 即不存在A到2A的双射函数，所以|A|2A|。,30/51,定理1 |A|2A|,有没有最大势的集合？,31/51,定理2,若|A|B| 且|B|C|， 则 |A|C|,证明：因为|A|B|， 则存在f

13、:AB是单射， 又|B|C|， 则存在g:BC是单射。 于是 gf:AC也是单射， 故 |A|C|。,32/51,定理3（伯恩斯坦定理）,A和B是两个任意集合。 若 |A|B| 且 |B|A| 则 |A| = |B|,33/51,伯恩斯坦（ Sergi Natanovich Bernstein，18801968）,原苏联数学家。 1880年3月6日生于敖德萨； 1968年10月26日卒于莫斯科。 1893年毕业于法国巴黎大学， 1901年又毕业于巴黎综合工科学校。 1904年在巴黎获数学博士学位， 1907年成为教授。 1914年在哈尔科夫又获纯粹数学博士学位。,“在概率论方面伯恩斯坦最早提出

14、并发展了概率论的公理化结构，建立了关于独立随机变量之和的中心极限定理。” 摘自中国大百科全书（数学卷）,34/51,定理4 有理数集Q是可数无限集,证明：作f: NQ ，xN, f(x)=x。 显然 f是单射，则|Q|N|。 又Z是整数集，我们知道 |Z|=|N| 且 |ZZ|=|N|。 作g:QZZ, 对x=q/pQ, 其中p,qZ, 互质, p0，令 g(x)=g(q/p)=(q,p) 则 g也是单射，所以 |Q| |ZZ|=|N|。 故由伯恩斯坦定理知，|Q|=|N|。,35/51,定理 (康托) 1= (0),连续统实数集即直线上点的集合。 1连续统的势（大小） 康托定理证明连续统势等

15、于自然数集的幂集的势,证明详见董晓蕾，曹珍富编著离散数学，机械工业出版社，2009年，第143页,36/51,连续统假设,如果集合有个元素，(A)有n个元素， 在|与(A)之间存在着其它基数（势）。 于是，康托提出: 在阿列夫零0与阿列夫之间是否也存在其它基数？ 连续统假设断言不存在这样的基数。,37/51,第八章 函数与集合的势,8.1 函数的基本概念 8.2 函数的复合和可逆函数 8.3 无限集 8.4 集合势大小的比较 8.5 鸽巢原理,38/51,鸽巢原理,任意取出3个自然数，至少有两个数是同奇偶的 任意11个人各自写出一个幸运数字，则至少有两人写出的幸运数字相同。 任意13个人说出自

16、己的生日星座，则至少有两人的生日星座相同。,39/51,鸽巢原理,如果有几个鸽子住在几个鸽巢中，鸽子的数目比鸽巢数目多，那么一定会有一个鸽巢至少住有两只鸽子。,40/51,鸽巢原理,设D和S是两个有限集，且 |D|S| 那么对于任意一个f:DS，一定存在d1d2D，使得 f(d1)=f(d2)。,41/51,鸽巢原理,设D和S是两个有限集，且 |D|2|S| 那么对于任意一个f:DS，一定存在三个不同元素d1,d2,d3D，使得 f(d1)=f(d2) =f(d3) 。,42/51,鸽巢原理,设D和S是两个有限集，记 i=|D|/|S|。 这里，x表示不小于x的最小整数。 即有： |D|（i-

17、1）|S| 。 那么对于任意的f:DS，D中必存在 i个不同元素 d1,d2,di，使得 f(d1)=f(d2)=f(di)。,43/51,狄利克雷（G. Lejeune Dirichlet 1805.2.131859.5.5 ）,德国数学家、力学家。 柏林大学教授。 贡献涉及数学的各个方面，其中以数论、分析和位势论最著名，并是解析数论的创始人。他解决了n=5的费马大定理(x5+y5=z5没有非平凡整数解)。,鸽巢原理(Pigeonhole Principle)最早由狄利克雷在1834年提出的(“drawer principle”抽屉原理 )。,44/51,例1证明在任意选取的 n+1个整数中

18、，存在两个整数，它们的差能被 n整除。,证明：设x1，x2，xn+1是任意选取的n+1个整数。任何整数被n 除的余数共有n个数： 0，1，2，n-1。 n+1个任意整数算 n+1个“鸽子”，任何整数被n 除有n 个可能余数算 n个“鸽巢”，这 n+1只“鸽子”飞到 n个“鸽巢”中，一定有一个“鸽巢”至少有两只“鸽子”，设为xi，xj (1ijn+1)。 xi与xj被n除余数相同，所以 n 整除 xixj。,45/51,例2证明在小于或等于2n 的任意 n+1个整数中， 存在两个正整数，使得它们是互质的。,命题：相继的两个正整数是互质的。 证明： 设两个相继的正整数为k和k1 (2k2n)， 令

19、(k，k-1) =m表示 k与k-1的最大公因子。 若 m1，设k=pm，k-1=qm， k(k1 )=pm-qm=(p-q)m ， 所以 1=(pq)m， 从而有 0p-q=1/m1， 但 p与q是不同的正整数，产生矛盾。 所以m=1，即 k与k-1互质。,46/51,例2证明在小于或等于2n 的任意 n+1个整数中， 存在两个正整数，使得它们是互质的。,证明：先构造n个“鸽巢”： R1存放1，2； R2存放3，4； ； Rn 存放2n-1，2n。 在1到2n中(包括1和2n)任选n+1个正整数，相当于从R1，R2，Rn 个“鸽巢”中选取 n+1只“鸽 子”，一定有一个“鸽巢”中取了两只“鸽

20、子”，即 取了两个正整数，且这两个正整数是相继的。 可以证明，它们是互质的。,47/51,例3设a1，a2，a3为三个任意的整数， b1b2b3为a1，a2，a3的任一排列，则 a1-b1，a2-b2，a3-b3中至少有一个是偶数。,证明：根据鸽巢原理，a1，a2，a3这三个数中至少有两个数，或同是奇数，或同是偶数。 不妨设这两个数是 a1和a2 ，而且是奇数。 根据鸽巢原理，b1，b2中至少有一个是奇数。 由于奇数与奇数之差是偶数， 故 a1b1，a2b2 中至少有一个是偶数。 若a1，a2这两个数同是偶数，结果也是对的，因偶数与偶数之差也是偶数。,48/51,例设x1,x2,xn是任意n个

21、整数的一个排列, 求证：其中存在连续的若干项，它们的和是n的倍数。,证明： 设 ai=x1+x2+xi 若诸ai中有n的倍数，则命题成立。 若诸ai中没有n的倍数，则 由n除ai的余数只能在1（n-1）中取。 以ai（i=1, , n）作鸽子，1（n-1）作鸽巢，必至少有两个鸽子落在同一个鸽巢中。 不妨设为ai, aj （ji）落在同一个鸽巢中，则有 n | (aj-ai) 即 n| xi+1+xi+2+xj,49/51,例 证明: 由多于或等于2个人的人群，至少有两个人在这群人中朋友数相同。,证：不妨设总人数是n （1）如果每个人的朋友数都不为零，则 朋友数最多有n-1种情况： 1,2, n

22、-1。 由鸽巢原理，至少有两个人的朋友数相同。 （2）如果恰有一个人的朋友数为零，其他人的朋友数都不为零，则对其他的n-1人来说，朋友数最多有n-2种情况：1,2,n-2。 由鸽巢原理，这n-1人中至少有两个人的朋友数相同。 （3）如果至少有两个人的朋友数为零，则结论显然成立。,50/51,例证明：在 n2+1个不同的整数的序列中，或者存在一个长度为 n+1的递增子序列，或者存在一个长度为n+1 的递减子序列。,证明：设此序列为：a1,a2,ak,ak+1,。 从ak开始的最长递增子序列的长度记为xk，从ak开始的最长递减子序列的长度记为yk，每一个ak (k=1,n2+1)都对应了(xk,yk)。 若不存在长为n+1的递增或递减子序列，那么 k ，k， 形如(xk,yk) 的不同点对至多有2个，而ak有n2+1个，必有ai,aj(1i jn+1)同时对应 （i，i）（j，j）。 由于aiaj，若aiaj，则xi至少比xj大， 若aiaj，则i至少比j大， 与（i，j）（j，j）矛盾。,51/51,8.17 8.26 8.30,作业16,补1 在一次象棋比赛中，n名选手中的任意两名选手之间至多只下一盘，又每人至少下一盘，证明：总能找到两名选手，他们下棋的盘数相同。,