双射函数与集合的基数.ppt

8.3集合的基数,离散数学,南京农业大学本科生课程,数学系,本章说明,本章的主要内容集合的等势及其性质重要的等势或不等势的结果集合的优势及其性质自然数与自然数集合集合的基数可数集,8.3.1集合的等势与优势8.3.2集合的基数本节小结习题作业,本章内容,定义8.8设A,B是集合，如果存在着从A到B的双射函数，就称A和B是等势（samecardinality）的，记作AB。如果A不与B等势，则记作AB。,8.3.1集合的等势与优势,通俗的说，集合的势是量度集合所含元素多少的量。集合的势越大，所含的元素越多。,（1）ZN。,则f是Z到N的双射函数。从而证明了ZN。,等势集合的实例(1),等势集合的实例(2),（2）NNN。,双射函数,等势集合的实例(3),（3）NQ。把所有形式为p/q(p,q为整数且q0)的数排成一张表。,-2/1,5,-1/1,4,-3/1,18,2/1,10,3/1,11,0/1,0,1/1,1,-2/2,-1/2,3,-3/2,17,2/2,3/2,12,0/2,1/2,2,-2/3,6,-1/3,7,-3/3,2/3,9,3/3,0/3,1/3,8,-2/4,-1/4,15,-3/4,16,2/4,3/4,13,0/4,1/4,14,以0/1作为第一个数，按照箭头规定的顺序可以“数遍”表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。,等势集合的实例(4),（4）(0,1)R。其中实数区间(0,1)=x|xR0x1。,令双射函数,则f是(0,1)到R的双射函数。从而证明了(0,1)R。,等势集合的实例(5),（5）0,1(0,1)。其中(0,1)和0,1分别为实数开区间和闭区间。,双射函数f:0,1(0,1)，,等势集合的实例(6),（6）对任何a,bR，ab，0,1a,b。双射函数f：0,1a,b，f(x)(ba)x+a。,例8.10设A为任意集合，则P(A)0,1A。,构造f：P(A)0,1A，f(A)=A，AP(A)。其中A是集合A的特征函数。(1)易证f是单射的。(2)对于任意的g0,1A，那么有g：A0,1。令B=x|xAg(x)=1则BA，且B=g，即BP(A)，使得f(B)=g。所以f是满射的。由等势定义得P(A)0,1A。,例8.10,证明,复习,定理8.6设A，B，C是任意集合，（1）AA。（2）若AB，则BA。（3）若AB，BC，则AC。,（1）IA是从A到A的双射，因此AA。（2）假设AB，存在f:AB是双射，那么f1:BA是从B到A的双射，所以BA。（3）假设AB，BC，存在f:AB，g:BC是双射，则fg:AC是从A到C的双射。所以AC。,等势的性质,证明,NZQNNR0,1(0,1)任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合R等势。问题：N和R是否等势？,若干等势集合,（1）如果能证明N0,1，就可以断定NR。只需证明任何函数f：N0,1都不是满射的。构造一个0,1区间的小数b，使得b在N中不存在原像。（2）任取函数f：AP(A)，构造BP(A)，使得B在A中不存在原像。或者使用反证法。,定理8.7康托定理（1）NR。（2）对任意集合A都有AP(A)。,康托定理,分析,（1）首先规定0,1中数的表示。对任意的x0,1，令x=0.x1x2,（0xi9）注意：为了保证表示式的唯一性，如果遇到0.24999，则将x表示为0.25000。设f:N0,1是从N到0,1的任何一个函数。f的所有函数值为：f(0)=0.a1(1)a2(1)f(1)=0.a1(2)a2(2)f(n1)=0.a1(n)a2(n)令y的表示式为0.b1b2，并且满足biai(i)，i=1,2,，则y0,1，但y与上面列出的任何一个函数值都不相等。即f不是满射的。所以，NR。,康托定理,康托定理,假设AP(A)，则必有函数f:AP(A)是双射函数。如下构造集合B：Bx|xAxf(x)可知BP(A)。于是存在唯一一个元素bA，使得f(b)B。若bB，则由B的定义知，bf(b)，即bB，矛盾。若bB，则bf(b)，于是由B的定义知，bB，矛盾。,（2）设g：AP(A)是从A到P(A)的任意函数，如下构造集合B：Bx|xAxg(x)则BP(A)。但是对任意xA，都有xBxg(x)所以，对任意的xA都有Bg(x)，即Brang即P(A)中存在元素B，在A中找不到原像。所以，g不是满射的。所以，AP(A)。,说明,康托定理,定义8.9（1）设A,B是集合，如果存在从A到B的单射函数，就称B优势于A，记作AB。如果B不是优势于A，则记作AB。（2）设A,B是集合，若AB且AB，则称B真优势于A，记作AB。如果B不是真优势于A，则记作AB。例如：,NNNRAP(A),NRAP(A),RNNN,优势,定理8.8设A,B,C是任意的集合，则（1）AA。（2）若AB且BA，则AB。（3）若AB且BC,则AC。证明：（1）IA是A到A的单射，因此AA。（2）证明略。（3）假设AB且BC，那么存在单射f:AB，g:BC，于是fg：AC也是单射的，因此AC。,优势的性质,说明,该定理为证明集合之间的等势提供了有力的工具。构造两个单射f：AB和g：BA函数容易集合等势。,例题,例题：证明0,1与(0,1)等势。证明：构造两个单射函数f:(0,1)0,1，f(x)xg:0,1(0,1)，g(x)x/2+1/4,证明0,1N0,1),(1)设x0,1)，0.x1x2是x的二进制表示。为了使表示唯一，规定表示式中不允许出现连续无数个1。例如x0.1010111，应按规定记为0.1011000。对于x，如下定义f：0,1)0,1N，使得f(x)=tx，且tx：N0,1，tx(n)=xn+1，n=0,1,2,例如x=0.10110100，则对应于x的函数tx是：n01234567tx(n)10110100易见tx0,1N，且对于x,y0,1)，xy，必有txty，即f(x)f(y)。所以，f：0,1)0,1N是单射的。,(2)定义函数g：0,1N0,1)。g的映射法则恰好与f相反，即t0,1N，t：N0,1，g(t)=0.x1x2,其中xn+1=t(n)。但不同的是，将0.x1x2看作数x的十进制表示。例如t1，t20,1N，且g(t1)0.0111，g(t2)0.1000，若将g(t1)和g(t2)都看成二进制表示，则g(t1)g(t2)；但若看成十进制表示，则g(t1)g(t2)。所以，g：0,1N0,1)是单射的。根据定理9.3，有0,1N0,1)。,证明0,1N0,1),总结,NZQNNRa,b(c,d)0,1NP(N)其中a,b，(c,d)代表任意的实数闭区间和开区间。0,1AP(A)NRAP(A),8.3.2集合的基数,上一节我们只是抽象地讨论了集合的等势与优势。本节将进一步研究度量集合的势的方法。最简单的集合是有穷集。尽管前面已经多次用到“有穷集”这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。,定义8.10设a为集合，称aa为a的后继，记作a+，即a+=aa。,例考虑空集的一系列后继。,+=,+=+=,=,+,+=,+=,=,=,+,+,后继,说明,前边的集合都是后边集合的元素。前边的集合都是后边集合的子集。,利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，即0=1=0+02=1+,0,132+,+,0,1,2n0,1,n1,说明,自然数的定义,这种定义没有概括出自然数的共同特征。,定义8.11设A为集合，如果满足下面的两个条件：（1）A（2）a(aAa+A)称A是归纳集。,例如：下面的集合,+,+,+,+,+,+,a,a+,a+,a+,都是归纳集。,归纳集,定义8.12自然数（1）一个自然数n是属于每一个归纳集的集合。（2）自然数集N是所有归纳集的交集。说明：根据定义8.12得到的自然数集N恰好由,+,+,+,等集合构成。而这些集合正是构造性方法所定义的全体自然数。,例如：自然数都是集合，集合的运算对自然数都适用。250,10,1,2,3,40,1,2,3,45340,1,20,1,2,30,1,234-20,1,2,3-0,1=2,3230,10,1,2,自然数n和自然数集合N的定义,P(1)P(0),00,1230,10,1,2f|f：0,1,20,1f0,f1,f7其中f0,f1,f2,f3,f4,f5,f6,f7,举例,（1）对任何自然数n，有nn。（2）对任何自然数n,m，若mn，则mn。（3）对任何自然数n,m，若mn，则mn。（4）对任何自然数n和m，以下三个式子：mn，mn，nm必成立其一且仅成立其一。（5）自然数的相等与大小顺序对任何自然数m和n，有m=nmnmnmn,自然数的性质,定义8.13有穷集、无穷集（1）一个集合是有穷的当且仅当它与某个自然数等势；（2）如果一个集合不是有穷的，就称作无穷集。例如：a,b,c是有穷集，因为30,1,2，且a,b,c0,1,23N和R都是无穷集，因为没有自然数与N和R等势。,任何有穷集只与唯一的自然数等势。,说明,有穷集和无穷集,定义8.14（1）对于有穷集合A，称与A等势的那个唯一的自然数为A的基数，记作cardA，即cardAnAn（对于有穷集A，cardA也可以记作|A|）（2）自然数集合N的基数记作0，即cardN=0（3）实数集R的基数记作（读作阿列夫），即cardR=,基数(cardinality),定义8.15设A,B为集合，则（1）cardAcardBAB（2）cardAcardBAB（3）cardAcardBcardAcardBcardAcardB例如：cardZcardQcardNN0cardP(N)card2Ncarda,bcard(c,d)0说明：集合的基数就是集合的势，基数越大，势就越大。,基数的相等和大小,关于基数的说明,由于对任何集合A都满足AP(A)，所以有cardAcardP(A)，这说明不存在最大的基数。将已知的基数按从小到大的顺序排列就得到：0,1,2,n,0,0,1,2,n,是全体自然数，是有穷基数。0,是无穷基数。0是最小的无穷基数，后面还有更大的基数，如cardP(R)等。,可数集,定义8.16设A为集合，若cardA0，则称A为可数集(enumerable)或可列集。例如：a,b,c、5、整数集Z、有理数集Q、NN等都是可数集。实数集R不是可数集，与R等势的集合也不是可数集。,对于任何的可数集，都可以找到一个“数遍”集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。,说明,（1）可数集的任何子集都是可数集。一个集合的无限子集若不可数，则该集合也不可数。（2）两个可数集的并是可数集。（3）两个可数集的笛卡儿积是可数集。（4）可数个可数集的笛卡儿积仍是可数集。（5）无穷集A的幂集P(A)不是可数集。,可数集的性质,例8.11求下列集合的基数。（1）Tx|x是单词“BASEBALL”中的字母（2）Bx|xRx2=92x=8（3）CP(A),A=1,3,7,11,（1）由TB,A,S,E,L知，cardT5。（2）由B可知，cardB0。（3）由|A|4可知，cardCcardP(A)|P(A)|2416。,解答,例8.11,方法一由cardA0，cardBn，可知A,B都是可数集。令A=a0,a1,a2,，B=b0,b1,b2,bn1。对任意的，AB，有ikjl定义函数f：ABNf()in+j,i0,1,j0,1,n1由于f是AB到N的双射函数，所以cardABcardN。,例8.12,解答,例8.12设A,B为集合，且cardA0，cardBn，n是自然数，n0。求cardAB。,例8.12,方法二因为cardA0，cardBn，所以A,B都是可数集。根据性质（3）可知，AB也是可数集，所以，cardAB0当B时，cardAcardAB，这就推出0cardAB综合所述，cardAB0,本章主要内容,集合等势的定义等势的性质集合优势的定义优势的性质重要的集合等势以及优势的结果自然数及其自然数集合的定义可数集与不可数集集合的基数,本章学习要求,能够证明两个集合等势。能够证明一个集合优势于另一个集合。知道什么是可数集与不可数集。会求一个简单集合的基数。,等势的证明方法,证明集合A与B等势的方法直接构造从A到B的双射函数f需要证明f的满射性和f的单射性。构造两个单射函数f：AB和g：BA。给出函数f和g，证明f和g的单射性。利用等势的传递性直接计算A与B的基数，得到cardAcardB。证明集合A与自然数集合N等势的方法找到一个“数遍”A中元素的顺序。,例题选讲,1已知An7|nN，Bn109|nN，求下列各题：（1）cardA（2）cardB（3）card(AB)（4）card(AB),（1）构造双射函数f：NA，f(n)=n7，因此cardA0。（2）构造双射函数g：NA，g(n)=n109，因此cardB0。（3）可数集的并仍旧是可数集(或者由于ABN)，因此card(AB)0，但是0cardAcard(AB)，从而得到card(AB)0。（4）因为7与109互素，card(AB)n7109|nN，与（1）类似得到card(AB)0。,解答,例题选讲,2.已知cardA0，且cardBcardA，求card(AB)。,由ABA，得到card(AB)cardA，即card(AB)0。由cardBcardA可知，B为有穷集，即存在自然数n，使得cardB=n。假设card(AB)0，那么存在自然数m，使card(AB)m。从而得到，cardAcard(AB)B)n+m与cardA0矛盾。因此，card(AB)0。,解答,复习特征函数,设A为集合，对于任意的AA，A的特征函数A:A0,1定义为,举例:A的每一个子集A都对应于一个特征函数，不同的子集对应于不同的特征函数。例如Aa,b,c,则有,，a,a,b,例题选讲(略),1设A,B为二集合，证明：如果AB，则P(A)P(B)。,因为AB，因此存在双射函数f：AB，存在反函数f1：BA，构造函数g：P(A)P(B),g(T)=f(T)，TA（这里的f(T)是T在函数f的像）首先，证明g的满射性。对于任何SB，存在f1(S)A，且g(f1(S)=ff1(S)=S。所以g是满射的。其次，证明g的单射性。g(T1)=g(T2)f(T1)=f(T2)f1(f(T1)=f1(f(T2)IA(T1)=IA(T2)T1=T2综合上述，可知P(A)P(B)。,两个可数集的并集为可数集,设A、B为可数集，不妨设AB。(1)若两个集合都是有穷集，比如Aa0,a1,an-1，Bb0,b1,bm-1，那么card(AB)n+m0。(2)如果其中一个集合是有穷集，另一个是无穷可数集，比如Aa0,a1,an-1，cardB0如下构造双射h：ABN，当xA时，xai，h(x)i；当xB时，xbj，j0,1,，那么h(x)j+n。(3)如果cardAcardB0，那么存在双射f：AN和g：BN。如下构造函数h：ABN当xA且f(x)i时，h(x)2i当xB且g(x)j时，h(x)2j+1显然h为双射。综上所述，card(AB)0。,