离散数学课件08函数

第8章函数,离散数学,中国地质大学本科生课程,本章说明,本章的主要内容函数的定义函数的性质函数的逆函数的合成本章与后续各章的关系是代数系统的基础,8.1函数的定义与性质8.2函数的复合与反函数8.3一个电话系统的描述实例本章小结习题作业,本章内容,8.1函数的定义与性质,定义8.1设F为二元关系，若xdomF，都存在唯一的yranF使xFy成立，则称F为函数(function)(或称作映射(mapping)。对于函数F，如果有xFy，则记作yF(x)，并称y为F在x的值。,举例判断下列关系是否为函数F1,F2,是函数不是函数,说明,函数是特殊的二元关系。函数的定义域为domF，而不是它的真子集。一个x只能对应唯一的y。,定义8.2设F,G为函数，则FGFGGF,由定义可知，两个函数F和G相等,一定满足下面两个条件：（1）domFdomG（2）xdomFdomG，都有F(x)G(x),例如函数F(x)(x21)/(x+1)，G(x)x1不相等,因为domFx|xRx-1domGR显然，domFdomG，所以两个函数不相等。,函数相等,定义8.3设A,B为集合，如果f为函数，domfA，ranfB，则称f为从A到B的函数，记作f：AB。例如：f：NN，f(x)2x是从N到N的函数，g：NN，g(x)2也是从N到N的函数。,定义8.4所有从A到B的函数的集合记作BA，读作“B上A”，符号化表示为BAf|f：AB。,从A到B的函数,例8.2设A1,2,3，Ba,b，求BA。,解答BAf0,f1,f2,f3,f4,f5,f6,f7。其中,f0,f1,f2,f3,f4,f5,f6,f7,例8.2,说明,若|A|m，|B|n，且m,n0，则|BA|nm。当A或B至少有一个集合是空集时：A且B，则BA。A且B，则BAB。A且B，则BAA。,定义8.5设函数f：AB，A1A，B1B。（1）令f(A1)f(x)|xA1，称f(A1)为A1在f下的像(image)。特别地，当A1A时，称f(A)为函数的像。（2）令f1(B1)x|xAf(x)B1，称f1(B1)为B1在f下的完全原像(preimage)。,说明,函数的像和完全原像,注意区别函数的值和像两个不同的概念。函数值f(x)B，而函数的像f(A1)B。,讨论,设B1B，显然B1在f下的原像f-1(B1)是A的子集。设A1A，那么f(A1)B。f(A1)的完全原像就是f-1(f(A1)。一般来说，f-1(f(A1)A1，但是A1f-1(f(A1)。例如函数f:1,2,30,1，满足f(1)f(2)0，f(3)1令A11，那么f-1(f(A1)f-1(f(1)f-1(0)1,2这时，A1是f-1(f(A1)的真子集。,例8.3设f:NN，且令A0,1，B2，求f(A)和f1(B)。,解答f(A)f(0,1)f(0),f(1)0,2f1(B)f1(2)1,4(因为f(1)2,f(4)2),例8.3,定义8.6设f:AB，（1）若ranfB，则称f:AB是满射(surjection)的。（2）若yranf都存在唯一的xA使得f(x)y，则称f:AB是单射(injection)的。（3）若f既是满射又是单射的，则称f:AB是双射(bijection)的(一一映像(one-to-onemapping)。,说明,满射、入射、双射,如果f:AB是满射的，则对于任意的yB，都存在xA，使得f(x)y。如果f:AB是单射的，则对于x1、x2A且x1x2，一定有f(x1)f(x2)。换句话说，如果对于x1、x2A有f(x1)f(x2)，则一定有x1x2。,不同类型的对应关系的示例,单射,不是函数,双射,函数,满射,例8.4判断下面函数是否为单射、满射、双射的，为什么?(1)f：RR，f(x)=-x2+2x-1(2)f：Z+R，f(x)=lnx，Z+为正整数集(3)f：RZ，f(x)=x(4)f：RR，f(x)=2x+1(5)f：R+R+，f(x)=(x2+1)/x，其中R+为正实数集。,例8.4,（1）f在x=1取得极大值0。既不是单射也不是满射的。（2）f是单调上升的，是单射的，但不满射。ranf=ln1,ln2,。（3）f是满射的，但不是单射的，例如f(1.5)=f(1.2)=1。（4）f是满射、单射、双射的，因为它是单调函数并且ranf=R。（5）f有极小值f(1)=2。该函数既不是单射的，也不是满射的。,分析,实数集合上函数性质的判断方法,例8.5,例8.5对于以下各题给定的A,B和f，判断是否构成函数f:AB。如果是，说明f:AB是否为单射、满射和双射的，并根据要求进行计算。(1)A1,2,3,4,5，B6,7,8,9,10，f,能构成f:AB，f不是单射的，因为f(3)f(5)9,f不是满射的，因为7ranf。(2)A1,2,3,4,5，B6,7,8,9,10，f,不能构成f:AB，因为f且f。,例8.5,(3)A1,2,3,4,5，B6,7,8,9,10，f,不能构成f:AB，因为domf1,2,3,4A。(4)ABR，f(x)x能构成f:AB，且f是双射的。(5)ABR+，f(x)x/(x2+1)（xR+）能构成f:AB，但f既不是单射的也不是满射的。因为该函数在x1取得极大值f(1)1/2，函数不是单调的，且ranfR+。,例8.5,(6)ABRR，f()令L|x,yRyx+1，计算f(L)。能构成f:AB，且f是双射的。f(L)|xR|xRR-1(7)ANN，BN，f()|x2-y2|计算f(N0),f-1(0)。能构成f:AB，但f既不是单射也不是满射的。因为f()f()0，且2ranf。f(N0)n2-02|nNn2|nNf-1(0)|nN,例8.6,例8.6对于给定的集合A和B构造双射函数f:AB。（1）AP(1,2,3),B0,11,2,3（2）A0,1,B1/4,1/2（3）AZ,BN（4）A/2,3/2,B1,1,例8.6的解答,（1）AP(1,2,3),B0,11,2,3A,1,2,3,1,2,1,3,2,3,1,2,3。Bf0,f1,f7,其中f0,f1,f2,f3,f4,f5,f6,f7,。令f:AB,f()f0,f(1)f1,f(2)f2,f(3)f3,f(1,2)f4,f(1,3)f5,f(2,3)f6,f(1,2,3)f7,例8.6的解答,（2）A0,1,B1/4,1/2令f:AB,f(x)(x+1)/4。（3）AZ,BN将Z中元素以下列顺序排列并与N中元素对应：Z：0112233N：0123456则这种对应所表示的函数是：,（4）A=/2,3/2,B=1,1令f:AB，f(x)sinx。,常用函数常函数和恒等函数,设f：AB，如果存在cB，使得对所有的xA都有f(x)c，则称f：AB是常函数。设f：AB，对所有的xA都有IA(x)x，称IA为A上的恒等函数。,常用函数单调递增函数,设，为偏序集，f：AB，如果对任意的x1,x2A，x1x2，就有f(x1)f(x2)，则称f为单调递增的；如果对任意的x1,x2A,x1x2,就有f(x1)f(x2),则称f为严格单调递增的。类似的也可以定义单调递减和严格单调递减的函数。举例：f:RR,f(x)x+1是严格单调递增的。偏序集，R为包含关系，为一般的小于等于关系。令f：P(a,b)0,1，f()f(a)f(b)0，f(a,b)=1，f是单调递增的,但不是严格单调递增的。,常用函数特征函数,设A为集合，对于任意的AA，A的特征函数A:A0,1定义为,举例:A的每一个子集A都对应于一个特征函数，不同的子集对应于不同的特征函数。例如Aa,b,c,则有,，a,a,b,常用函数自然映射,设R是A上的等价关系，令g：AA/Rg(a)=a，aA称g是从A到商集A/R的自然映射。,给定集合A和A上的等价关系R，就可以确定一个自然映射g：AA/R。例如A1,2,3，R,IAg(1)g(2)1,2,g(3)3不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射，而其他的自然映射一般来说只是满射。,定义在自然数集合上的计数函数,对于给定规模为n的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。排序和检索问题的基本运算是比较。矩阵乘法的基本运算是元素的相乘。估计算法在最坏情况下所做基本运算的次数记为W(n)。估计算法在平均情况下所做基本运算的次数记为A(n)。设f是定义在自然数集合上的函数，当n变得很大时，函数值f(n)的增长取决于函数的阶。阶越高的函数，算法的复杂度就越高，同时意味着算法的效率越低。算法分析的主要工作就是估计复杂度函数的阶。阶可以是：n，n2，n3，nlogn，logn，2n,定义在自然数集合上的计数函数,若存在正数c和n0，使得对一切nn0，有0f(n)cg(n)，记作f(n)O(g(n)。若存在正数c和n0，使得对一切nn0，有0cg(n)f(n)，记作f(n)(g(n)。若f(n)O(g(n)且f(n)(g(n)，则f(n)(g(n)。例如f(n)1/2n2-3n，则f(n)(n2)g(n)6n3，则g(n)(n3),构造从A到B的双射函数,有穷集之间的构造例1A=P(1,2,3),B=0,11,2,3解A=,1,2,3,1,2,1,3,2,3,1,2,3.B=f0,f1,f7,其中f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,.,令f:AB,f()=f0,f(1)=f1,f(2)=f2,f(3)=f3,f(1,2)=f4,f(1,3)=f5,f(2,3)=f6,f(1,2,3)=f7,实数区间之间构造双射构造方法：直线方程例2A=0,1B=1/4,1/2构造双射f:AB,构造从A到B的双射函数(续),解令f:0,11/4,1/2f(x)=(x+1)/4,A与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应,构造从A到B的双射函数(续),例3A=Z,B=N，构造双射f:AB,将Z中元素以下列顺序排列并与N中元素对应：Z：0112233N：0123456则这种对应所表示的函数是：,8.2函数的复合与反函数,函数的复合就是关系的右复合，一切和关系右复合有关的定理都适用于函数的复合。本节重点考虑在复合中特有的性质。,定理8.1(复合函数基本定理),定理8.1设F,G是函数，则FG也是函数，且满足（1）dom(FG)x|xdomFF(x)domG（2）xdom(FG)，有FG(x)G(F(x),证明：先证明FG是函数。因为F、G是关系，所以FG也是关系。若对某个xdom(FG)，若有xFGy1和xFGy2，则FGFGt1(FG)t2(FG)t1t2(t1t2GG)（F为函数）y1y2（G为函数）所以FG为函数。,定理8.1的证明,定理8.1的证明,任取x，(要证明dom(FG)x|xdomFF(x)domG)xdom(FG)ty(FG)t(xdomFtF(x)tdomG)xx|xdomFF(x)domG所以（1）得证。任取x，（要证明xdom(FG)，有FG(x)G(F(x)）xdomFF(x)domGFGFGxdom(FG)FG(x)G(F(x)所以（2）得证。,推论1设F,G,H为函数，则(FG)H和F(GH)都是函数，且(FG)H=F(GH)证明：由定理8.1（复合函数基本定理）和定理7.2（关系合成具有结合性）得证。,定理8.1的推论1,推论2设f：AB，g：BC，则fg：AC，且xA都有fg(x)=g(f(x)。证明：由定理8.1（复合函数基本定理）可知fg是函数，且dom(fg)x|xdomff(x)domgx|xAf(x)BAran(fg)rangC因此fg：AC，且xA有fg(x)g(f(x)。,定理8.1的推论2,定理8.2设f：AB，g：BC。（1）如果f：AB，g：BC都是满射的，则fg：AC也是满射的。（2）如果f：AB，g：BC都是单射的，则fg：AC也是单射的。（3）如果f：AB，g：BC都是双射的，则fg：AC也是双射的。,说明,函数的复合运算的性质,该定理说明函数的复合能够保持函数单射、满射、双射的性质。,定理8.2的证明,(1)如果f：AB，g：BC都是满射的，则fg：AC也是满射的。证明：任取cC，由g：BC的满射性，所以bB使得g(b)=c。对于这个b，由f：AB的满射性，所以aA使得f(a)=b。由合成定理有fg(a)g(f(a)g(b)c所以，fg：AC是满射的。,定理8.2的证明,(2)如果f：AB，g：BC都是单射的，则fg：AC也是单射的。证明：假设存在x1,x2A使得fg(x1)fg(x2)，由合成定理有g(f(x1)=g(f(x2)因为g：BC是单射的，故f(x1)f(x2)。又由于f：AB也是单射的，所以x1x2。所以，fog：AC是单射的。,(3)如果f：AB，g：BC都是双射的，则fg：AC也是双射的。证明：由（1）和（2）得证。,定理8.2之逆不为真,考虑集合Aa1,a2,a3，Bb1,b2,b3,b4，Cc1,c2,c3。令f,g,则fg=,那么f:AB和fg:AC都是单射的，但g:BC不是单射的。考虑集合A=a1,a2,a3，B=b1,b2,b3，C=c1,c2。令f,g,则fg,那么g:BC和fg:AC是满射的，但f:AB不是满射的。,定理8.3,定理8.3设f：AB，则ffoIBIAof证明：由定理8.1的推论2可知foIB：AB和IAof：AB任取，,ffyBfIBfoIB所以，ffoIB,foIBt(fIB)ft=yf所以，foIBf,所以，ffoIB同理可证fIAof,什么样的函数f：AB，它的逆f1是从B到A的函数呢？任给函数F,它的逆F1不一定是函数,只是一个二元关系。F，F-1，任给单射函数f：AB,则f1是函数,且是从ranf到A的双射函数,但不一定是从B到A的双射函数。因为对于某些yBranf，f-1没有值与之对应。任给满射函数f：AB，则f1不一定是函数。对于双射函数f：AB,f1：BA是从B到A的双射函数。,反函数,定理8.4设f：AB是双射的，则f1：BA也是双射的。证明：先证明f-1：BA是函数，且domf1B，ranf1A。因为f是函数，所以f1是关系，且domf1ranfB,ranf1domfA，对于任意的xBdomf1，假设有y1,y2A，使得f1f1成立，则由逆的定义有，ff。根据f的单射性，可得y1y2。所以，f-1是函数。,反函数存在的条件,再证明f-1：BA的双射性质。（证明单射）若存在x1,x2B，使得f1(x1)=f1(x2)=y，从而有f1f1ffx1x2（因为f是函数）所以，f-1是单射的。（证明满射）对于任意的yA，因为f是双射的，所以必存在xB，使得f，所以f1，所以，f1是满射的。综上所述，f1是双射函数。,说明,定理8.4的证明,对于双射函数f：AB，称f-1：BA是它的反函数。,反函数的性质,定理8.5设f：AB是双射的，则f-1f=IB，ff-1=IA证明：根据定理可知f-1：BA也是双射的，且f-1f：BB，ff-1：AA。任取,f1ft(f1f)t(ff)x=yx,yBIB所以，f-1fIB,IBxyx,yBt(ff)t(f1f)f-1f所以，IBf-1f,综上所述，f-1fIB。同理可证ff-1IA,例8.8,例8.8设f：RR,g：RR求fg，gf。如果f和g存在反函数，求出它们的反函数。解答,g：RR是双射的，它的反函数是g1：RR，g1(x)=x2,定义8.8设A,B是集合，如果存在着从A到B的双射函数，就称A和B是等势（samecardinality）的，记作AB。如果A不与B等势，则记作AB。,8.3双射函数与集合的基数,通俗的说，集合的势是量度集合所含元素多少的量。集合的势越大，所含的元素越多。,（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)，,2,等势集合的实例(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集合的基数,上一节我们只是抽象地讨论了集合的等势与优势。本节将进一步研究度量集合的势的方法。最简单的集合是有穷集。尽管前面已经多次用到“有穷集”这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。,定义9.38.10设a为集合，称aa为a的后继，记作a+，即a+=aa。,例考虑空集的一系列后继。,+=,+=+=,=,+,+=,+=,=,=,+,+,后继,说明,前边的集合都是后边集合的元素。前边的集合都是后边集合的子集。,利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，即0=1=0+02=1+,0,132+,+,0,1,2n0,1,n1,说明,自然数的定义,这种定义没有概括出自然数的共同特征。,（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.11有穷集、无穷集（1）一个集合是有穷的当且仅当它与某个自然数等势；（2）如果一个集合不是有穷的，就称作无穷集。例如：a,b,c是有穷集，因为30,1,2，且a,b,c0,1,23N和R都是无穷集，因为没有自然数与N和R等势。,任何有穷集只与唯一的自然数等势。,说明,有穷集和无穷集,定义8.12（1）对于有穷集合A，称与A等势的那个唯一的自然数为A的基数，记作cardA，即cardAnAn（对于有穷集A，cardA也可以记作|A|）（2）自然数集合N的基数记作0，即cardN=0（3）实数集R的基数记作（读作阿列夫），即cardR=,基数(cardinality),定义8.13设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.14设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都是有穷集时，会求A到B的函数的个数。掌握A到B的函数是单射、满射、和双射的定义及证明方法。掌握常函数、恒等函数、单调函数、特征函数、自然映射等概念。掌握合成函数的主要性质和求合成函数的方法。掌握反函数的概念及主要性质。,本章学习要求（续）,能够证明两个集合等势。能够证明一个集合优势于另一个集合。知道什么是可数集与不可数集。会求一个简单集合的基数。,对于任意的,RR,有,证明：任取RR，存在RR，使得,因此f是满射的。,因此f是单射的。,例题,证明f既是满射的，也是单射的。其中,例题,令Xx1,x2,xm，Y=y1,y2,yn，问（1）有多少不同的由X到Y的关系？（2）有多少不同的X到Y的映射？（3）有多少不同的由X到Y的单射、双射？,解：（1）有2mn不同的由X到Y的关系。（2）有nm不同的X到Y的映射。（3）X到Y的单射个数为：,若mn，有0个单射。若mn，有m!个单射。只有mn时，才存在X到Y的双射，个数为m!。,若mn，有个单射。,设A、B、C、D是任意集合，f是A到B的双射，g是C到D的双射。令h:ACBD，且AC，h()=，那么h是双射吗？请证明你的判断。证明：先证明h是满射。BD，则bB，dD，因为f是A到B的双射，g是C到D的双射,所以，aA，cC，使得f(a)=b，g(c)=d，也就是AC，使得h()=,所以，h是满射。,例题,例题,再证h是单射。,AC，若h()=h()，则=所以，f(a1)=f(a2)，g(c1)=g(c2)。因为f是A到B的双射，g是C到D的双射,所以，a1=a2，c1=c2。所以，=，所以，h是单射。综上所述，h是双射。,等势的证明方法,证明集合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。（