邱婉玲耿素云离散数学ch08

《邱婉玲耿素云离散数学ch08》由会员分享，可在线阅读，更多相关《邱婉玲耿素云离散数学ch08（60页珍藏版）》请在金锄头文库上搜索。

1、第八章第八章 函数函数主要内容主要内容函数的定义与性质函数的定义与性质l函数定义函数定义l函数性质函数性质函数运算函数运算l函数的逆函数的逆l函数的合成函数的合成双射函数与集合的基数双射函数与集合的基数18.1 函数的定义与性质函数的定义与性质主要内容主要内容函数定义与相关概念函数定义与相关概念l函数定义函数定义l函数相等函数相等l从从A到到B的函数的函数f:ABlBAl函数的像与完全原像函数的像与完全原像函数的性质函数的性质l单射、满射、双射函数的定义与实例单射、满射、双射函数的定义与实例l构造双射函数构造双射函数某些重要的函数某些重要的函数2函数定义函数定义定义定义8.1设设F 为二元关系

2、为二元关系,若若 xdomF 都存在唯一的都存在唯一的yranF 使使xFy 成立成立,则称则称F 为为函数函数对于函数对于函数F,如果有如果有xFy,则记作则记作y=F(x),并称并称y 为为F 在在x 的的值值.例例F1=,F2=,F1是函数是函数,F2不是函数不是函数定义定义8.2设设F,G 为函数为函数,则则F=G F GG F如果两个函数如果两个函数F 和和G 相等相等,一定满足下面两个条件：一定满足下面两个条件：(1)domF=domG(2) xdomF=domG 都有都有F(x)=G(x)函数函数F(x)=(x2 1)/(x+1),G(x)=x 1不相等不相等,因为因为domF

3、domG.3从从A到到B的函数的函数定义定义8.3设设A,B为集合为集合,如果如果 f 为函数为函数,domf=A,ranf B,则称则称f 为为从从A到到B的函数的函数,记作记作f：AB.例例f：NN,f(x)=2x 是从是从N到到N的函数的函数, g：NN,g(x)=2也是从也是从N到到N的函数的函数.定义定义8.4所有从所有从A到到B的函数的集合记作的函数的集合记作BA,符号化表示为符号化表示为BA =f|f：AB |A|=m,|B|=n,且且m,n0,|BA|=nmA=,则则BA=B=A且且B=,则则BA=A=4实例实例例例1设设A=1,2,3,B=a,b,求求BA.解解BA=f0,f

4、1,f7,其中其中f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,5函数的像和完全原像函数的像和完全原像定义定义8.5设函数设函数f：AB,A1 A,B1 B(1)A1在在f 下的像下的像f(A1)=f(x)|xA1,函数的像函数的像f(A)(2)B1在在f 下的完全原像下的完全原像f 1(B1)=x|xAf(x)B1注意：注意：l函数值与像的区别：函数值函数值与像的区别：函数值f(x)B,像像f(A1) Bl一般说来一般说来f 1(f(A1)A1,但是但是A1 f 1(f(A1)例例设设f：NN,且且令令A=0,1,B=2,那么有那么有f(A)=f(0,1)=f(0),f(1

5、)=0,2f 1(B)=f 1(2)=1,46函数的性质函数的性质定义定义8.6设设f：AB,(1)若若ranf=B,则称则称f:AB是是满射满射的的(2)若若 yranf 都存在唯一的都存在唯一的xA 使得使得f(x)=y,则称则称f:AB 是是单射单射的的(3)若若f:AB 既是满射又是单射的既是满射又是单射的,则称则称f:AB是是双射双射的的例例2判断下面函数是否为单射判断下面函数是否为单射,满射满射,双射的双射的,为什么为什么?(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)

6、=2x+1(5)f:R+R+,f(x)=(x2+1)/x,其中其中R+为正实数集为正实数集.7例题解答例题解答解解(1)f:RR,f(x)= x2+2x 1在在x=1取得极大值取得极大值0.既不是单射也不是满射的既不是单射也不是满射的(2)f:Z+R,f(x)=lnx是单调上升的是单调上升的,是单射的是单射的.但不满射但不满射,ranf=ln1,ln2,.(3)f:RZ,f(x)= x 是满射的是满射的,但不是单射的但不是单射的,例如例如f(1.5)=f(1.2)=1(4)f:RR,f(x)=2x+1是满射、单射、双射的是满射、单射、双射的,因为它是单调函数并且因为它是单调函数并且ranf=R

7、(5)f:R+R+,f(x)=(x2+1)/x有极小值有极小值f(1)=2.该函数既不是单射的也不是满射的该函数既不是单射的也不是满射的8实例实例例例3对于给定的集合对于给定的集合A和和B构造双射函数构造双射函数f:AB(1)A=P(1,2,3),B=0,11,2,3(2)A=0,1,B=1/4,1/2(3)A=Z,B=N(4),B= 1,19解答解答(1)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

8、)=f4,f(1,3)=f5,f(2,3)=f6,f(1,2,3)=f710(2)令令f:0,11/4,1/2,f(x)=(x+1)/4(4)令令 f: :/2,3/2 1,1f(x)=sinx解答解答(3)将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z：0 11 22 33N：0123456这种对应所表示的函数是：这种对应所表示的函数是：11某些重要函数某些重要函数定义定义8.7(1)设设f:AB,如果存在如果存在cB使得对所有的使得对所有的xA都有都有f(x)=c,则称则称f:AB是是常函数常函数.(2)称称A上的恒等关系上的恒等关系IA为为A上的上的恒

9、等函数恒等函数,对所有的对所有的xA都都有有IA(x)=x.(3)设设,为偏序集，为偏序集，f:AB，如果对任意的，如果对任意的x1,x2A,x1 x2,就有就有f(x1) f(x2),则称则称f 为为单调递增单调递增的；如的；如果对任意的果对任意的x1,x2A,x1 x2,就有就有f(x1) f(x2),则称则称f 为为严严格单调递增格单调递增的的.类似的也可以定义单调递减和严格单调递类似的也可以定义单调递减和严格单调递减的函数减的函数12(4)设设A为集合为集合,对于任意的对于任意的A A,A的的特征函数特征函数 A :A0,1定义为定义为 A(a)=1,aA A(a)=0,aA A(5)

10、设设R是是A上的等价关系上的等价关系,令令g:AA/Rg(a)=a, aA称称g 是从是从A 到商集到商集A/R 的的自然映射自然映射某些重要函数某些重要函数13实例实例例例4(1)偏序集偏序集,R 为包含关系为包含关系,为为一般的小于等于关系一般的小于等于关系,令令f:P(a,b)0,1, f()=f(a)=f(b)=0,f(a,b)=1, f 是单调递增的是单调递增的,但不是严格单调递增的但不是严格单调递增的(3)不同的等价关系确定不同的自然映射不同的等价关系确定不同的自然映射,恒等关系确定的恒等关系确定的自然映射是双射自然映射是双射,其他自然映射一般来说只是满射其他自然映射一般来说只是满

11、射.例如例如 A=1,2,3,R=,IA g: AA/R, g(1)=g(2)=1,2,g(3)=3(2)A的每一个子集的每一个子集A都对应于一个特征函数都对应于一个特征函数,不同的子集对不同的子集对应于不同的特征函数应于不同的特征函数.例如例如A=a,b,c,则有则有 =,， a,b=,148.2函数的复合与反函数函数的复合与反函数 主要内容主要内容l复合函数基本定理复合函数基本定理l函数的复合运算与函数性质函数的复合运算与函数性质l反函数的存在条件反函数的存在条件l反函数的性质反函数的性质15复合函数基本定理复合函数基本定理定理定理8.1设设F,G是函数是函数,则则F G也是函数也是函数,

12、且满足且满足(1)dom(F G)=x|xdomFF(x)domG(2) xdom(F G)有有F G(x)=G(F(x)证证先证明先证明F G是函数是函数.因为因为F,G是关系是关系,所以所以F G也是关系也是关系.若对某个若对某个xdom(F G)有有xF Gy1和和xF Gy2,则则F GF Gt1(FG) t2(FG)t1 t2(t1=t2GG（F为函数）为函数）y1=y2（G为函数）为函数）所以所以F G 为函数为函数16证明证明任取任取x,xdom(F G) t y(FG) t (xdomFt=F(x)tdomG)xx |xdomFF(x)domG 任取任取x,xdomFF(x)d

13、omGFGF Gxdom(F G)F G(x)G(F(x)所以所以(1)和和(2)得证得证17推论推论推论推论1设设F,G,H为函数为函数,则则(F G) H和和F (G H)都是函数都是函数,且且(F G) H=F (G H)证证由上述定理和运算满足结合律得证由上述定理和运算满足结合律得证.推论推论2设设f:AB,g:BC,则则f g:AC,且且 xA都有都有f g(x)=g(f(x)证证由上述定理知由上述定理知f g是函数是函数,且且dom(f g)=x|xdomff(x)domg=x|xAf(x)B=Aran(f g) rang C因此因此f g:AC,且且 xA有有f g(x)=g(f

14、(x)18函数复合与函数性质函数复合与函数性质定理定理8.2设设f:AB,g:BC(1)如果如果f:AB,g:BC是满射的是满射的,则则f g:AC也是满射的也是满射的(2)如果如果f:AB,g:BC是单射的是单射的,则则f g:AC也是单射的也是单射的(3)如果如果f:AB,g:BC是双射的是双射的,则则f g:AC也是双射的也是双射的证证(1)任取任取cC,由由g:BC的满射性的满射性, bB使得使得g(b)=c.对于这个对于这个b,由由f:AB的满射性，的满射性， aA使得使得f(a)=b.由合成定理有由合成定理有 f g(a)=g(f(a)=g(b)=c从而证明了从而证明了f g:AC

15、是满射的是满射的19证明证明(2)假设存在假设存在x1,x2A使得使得f g(x1)=f g(x2)由合成定理有由合成定理有 g(f(x1)=g(f(x2)因为因为g:BC是单射的是单射的,故故f(x1)=f(x2).又由于又由于f:AB是单射的是单射的,所所以以x1=x2.从而证明从而证明f g:AC是单射的是单射的.(3)由由(1)和和(2)得证得证.注意：定理逆命题不为真注意：定理逆命题不为真,即如果即如果f g:AC是单射是单射(或满射、或满射、双双射射)的的,不一定有不一定有f:AB 和和g:BC都是单射都是单射(或满射、双射或满射、双射)的的.定理定理8.3 设设f:AB,则则f

16、= f IB=IA f （证明略）（证明略） 20实例实例考虑集合考虑集合A=a1,a2,a3,B=b1,b2,b3,b4,C=c1,c2,c3.令令f=,g=,f g=,那么那么f:AB和和f g:AC是单射的是单射的,但但g:BC不是单射的不是单射的.考虑集合考虑集合A=a1,a2,a3,B=b1,b2,b3,C=c1,c2.令令f=,g=,f g=,那么那么g:BC 和和f g:AC是满射的是满射的,但但f:AB不是满射的不是满射的.21反函数反函数反函数存在的条件反函数存在的条件(1)任给函数任给函数F,它的逆它的逆F 1不一定是函数不一定是函数,只是一个二元关系只是一个二元关系.(2

17、)任给单射函数任给单射函数f:AB,则则f 1是函数是函数,且是从且是从ranf 到到A的双的双射函数射函数,但不一定是从但不一定是从B到到A的双射函数的双射函数(3)对于双射函数对于双射函数f:AB,f 1:BA是从是从B到到A的双射函数的双射函数.定理定理8.4设设f:AB是双射的是双射的,则则f 1:BA也是双射的也是双射的.证明思路：证明思路：先证明先证明f 1:BA，即，即f 1是函数，且是函数，且domf 1=B,ranf 1=A.再证明再证明f 1:BA的双射性质的双射性质.22证明证明证证因为因为f 是函数是函数,所以所以f 1是关系是关系,且且dom f 1=ranf =B,

18、ran f 1=domf =A对于任意的对于任意的xB =dom f 1,假设有假设有y1,y2A使得使得f 1f 1成立成立,则由逆的定义有则由逆的定义有ff根据根据f 的单射性可得的单射性可得y1=y2,从而证明了从而证明了f 1是函数，且是满射的是函数，且是满射的.若存在若存在x1,x2B使得使得f 1(x1)= f 1(x2)=y,从而有从而有f 1f 1ffx1=x2对于双射函数对于双射函数f:AB,称称f 1:BA是它的是它的反函数反函数.23反函数的性质反函数的性质定理定理8.5(1)设设f:AB是双射的是双射的,则则f 1 f =IB,f f 1=IA(2)对于双射函数对于双射

19、函数f:AA,有有f 1 f =f f 1=IA 证明思路：证明思路：根据定理可知根据定理可知f 1:BA也是双射的也是双射的,由合成基本定理可知由合成基本定理可知f 1 f:BB,f f 1:AA，且它们都是恒等函数，且它们都是恒等函数. 例例5设设 求求f g,g f.如果如果f 和和g 存在反函数存在反函数,求出它们的反函数求出它们的反函数.24解解f:RR不是双射的不是双射的,不存在反函数不存在反函数.g:RR是双射的是双射的,它的反函数是它的反函数是g 1:RR,g 1(x)=x 2求解求解258.3 双射函数与集合的基数双射函数与集合的基数主要内容主要内容l集合的等势及其性质集合的

20、等势及其性质l重要的等势或不等势的结果重要的等势或不等势的结果l集合的优势及其性质集合的优势及其性质l集合的基数集合的基数l可数集可数集26则则f 是是Z到到N的双射函数的双射函数.从而证明了从而证明了ZN.集合的等势集合的等势集合等势的实例集合等势的实例例例6(1)ZN.定义定义8.8设设A,B是集合是集合,如果存在着从如果存在着从A到到B的双射函数的双射函数,就就称称A和和B是是等势等势的的,记作记作AB.如果如果A不与不与B 等势等势,则记作则记作A B.27集合等势的实例集合等势的实例: NNNNNN.NN中所有的元素排成有序图形中所有的元素排成有序图形28-2/1-2/155-1/1

21、-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414PLAYNQ.双射函数双射函数f:NQ,其中其中f(n)是是n下方的有理数下方的有理数.集合等势的实例集合等势的实例: NQ29(6

22、)对任何任何a,bR,ab,0,1a,b，双射函数双射函数f:0,1a,b,f(x)=(b a)x+a类似地可以证明类似地可以证明,对任何对任何a,bR,ab,有有(0,1)(a,b).(4)(0,1)R.其中实数区间其中实数区间(0,1)=x|xR0x1.令令(5)0,1(0,1).其中其中(0,1)和和0,1分别为实数开区间和分别为实数开区间和闭区间闭区间.令令f:0,1(0,1)实数集合的等势实数集合的等势30实例实例例例7设设A为任意集合为任意集合,则则P(A)0,1A.证证如下构造从如下构造从P(A)到到0,1A 的函数的函数f:P(A)0,1A,f(A)= A, AP(A).其中其

23、中 A是集合是集合A的特征函数的特征函数.易证易证f 是单射的是单射的.对于任意的对于任意的g0,1A,那么有那么有g:A0,1.令令 B=x|xAg(x)=1则则B A,且且 B=g,即即 BP(A),f(B)=g.从而证明了从而证明了f 是满射是满射的的.由等势定义得由等势定义得P(A)0,1A.31等势的性质等势的性质定理定理8.6设设A, B,C是任意集合，是任意集合，(1)AA(2)若若AB，则，则BA(3) 若若AB，BC，则，则AC.证明思路：利用等势的等义证明思路：利用等势的等义.(1)IA是从是从A到到A的双射的双射(2)若若f:AB是双射，则是双射，则f 1:BA是从是从B

24、到到A的双射的双射.(3)若若f:AB，g:BC是双射，则是双射，则f g:AC是从是从A到到C的双射的双射32有关势的重要结果有关势的重要结果等势结果等势结果lNZQNNl任何实数区间都与实数集合任何实数区间都与实数集合R等势等势不等势的结果不等势的结果:定理定理8.7(康托定理康托定理)(1)N R； (2) 对任意集合对任意集合A都有都有A P(A)证明思路：证明思路：(1)只需证明任何函数只需证明任何函数f:N0,1都不是满射的都不是满射的.任取函数任取函数f:N0,1,列出列出f 的所有函数值，然后构造一个的所有函数值，然后构造一个0,1区间的小数区间的小数b，使得，使得b与所有的函

25、数值都不相等与所有的函数值都不相等.(2)任取函数任取函数f:AP(A)，构造，构造B P(A)，使得，使得B与与f 的任何函的任何函数值都不等数值都不等.33Cantor定理的证明定理的证明证证(1)规定规定0,1中数的表示中数的表示.对任意的对任意的x0,1,令令x =0.x1x2,0xi 9规定在规定在x 的表示式中不允许在某位后有无数个的表示式中不允许在某位后有无数个1的情况的情况.设设f:N0,1是任何函数，列出是任何函数，列出f 的所有函数值：的所有函数值：f(0)=0.a1(1)a2(1)f(1)=0.a1(2)a2(2) f(n 1)=0.a1(n)a2(n)令令y 的表示式为

26、的表示式为0.b1b2,并且满足并且满足bi ai(i),i=1,2,那么那么y 0,1,且且y与上面列出的任何函数值都不相等与上面列出的任何函数值都不相等.这就推出这就推出y ranf,即即f 不是满射的不是满射的.34(2)我们将证明任何函数我们将证明任何函数g:AP(A)都不是满射的都不是满射的.设设g:AP(A)是从是从A到到P(A)的函数的函数,如下构造集合如下构造集合B：B=x|xAx g(x)则则BP(A),但对任意但对任意xA都有都有 xB x g(x)从而证明了对任意的从而证明了对任意的xA都有都有Bg(x).即即B rang.注意：根据注意：根据Cantor定理可以知道定理

27、可以知道N P(N)，N 0,1N.Cantor定理的证明定理的证明35集合的优势集合的优势定义定义8.9(1)设设A,B是集合是集合,如果存在从如果存在从A到到B的单射函数的单射函数,就就称称B优势于优势于A,记作记作A B.如果如果B不是优势于不是优势于A,则记作则记作A B.(2)设设A,B是集合是集合,若若A B 且且A B,则称则称B 真优势于真优势于A,记记作作 A B.如果如果B 不是真优势于不是真优势于A,则记作则记作A B.实例实例N N,N R,A P(A),R NN R,A P(A),但但N N定理定理8.8设设A,B,C是任意的集合是任意的集合,则则(1)A A(2)若

28、若A B且且B A,则则AB(3)若若A B且且B C,则则A C36应用：证明等势应用：证明等势证证设设x 0,1),0.x1x2是是x 的二进制表示的二进制表示.规定表示式中规定表示式中不不允许出现连续无数个允许出现连续无数个1.对于对于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是：是：n01234567 tx(n)10110100tx0,1N,且对于且对于x,y0,1),xy,必有必有txty,即即f(x)f(y).这就证明了这就证明了f

29、:0,1)0,1N是单射的是单射的.例例8证明证明0,1N0,1).37考虑考虑t0,1N,其中其中 t(0)=0,t(n)=1,n=1,2,.按照按照f 的定义的定义,只有只有x =0.011才能满足才能满足f(x)=t.但根据规定但根据规定,这个数这个数x 记为记为0.100,所以根本不存在所以根本不存在x0,1),满足满足f(x)=t.定义函数定义函数g:0,1N0,1).g的映射法则恰好与的映射法则恰好与f 相反相反.即即 t0,1N, t：N0,1,g(t)=0.x1x2,其中其中xn+1=t(n).将将0.x1x2看作数看作数x 的十进制表示的十进制表示.这样就避免了形如这样就避免

30、了形如0.0111和和0.1000.在二进制表示中对应了同一个数的情在二进制表示中对应了同一个数的情况，从而保证了况，从而保证了g的单射性的单射性.根据定理有根据定理有0,1N0,1).再使用等势的传递性得再使用等势的传递性得0,1NR.构造另一个单射构造另一个单射38自然数的集合定义自然数的集合定义 定义定义8.10设设a为集合为集合,称称aa为为a的的后继后继,记作记作a+,即即a+=aa.如下定义自然数：如下定义自然数：0=1=0+=+=02=1+=+= =,=0,13=2+=,+=,=0,1,2 n=0,1,n 1自然数的相等与大小，即对任何自然数自然数的相等与大小，即对任何自然数 n

31、和和m，有有 m=n m n ， mn m n39有穷集和无穷集有穷集和无穷集定义定义8.11(1)一个集合是一个集合是有穷有穷的当且仅当它与某个自然数等势；的当且仅当它与某个自然数等势；(2)如果一个集合不是有穷的如果一个集合不是有穷的,就称作就称作无穷集无穷集.实例：实例：(1)a,b,c是有穷集是有穷集,因为因为3=0,1,2,且且a,b,c0,1,2=3(2)N和和R都是无穷集都是无穷集,因为没有自然数与因为没有自然数与N和和R等势等势利用自然数的性质可以证明：任何有穷集只与惟一的自然数利用自然数的性质可以证明：任何有穷集只与惟一的自然数等势等势.40集合基数的定义集合基数的定义定义定

32、义8.12(1)对于有穷集合对于有穷集合A,称与称与A等势的那个惟一的自然数为等势的那个惟一的自然数为A的的基基数数,记作记作cardA(也可以记作也可以记作|A|)cardA =n A n(2)自然数集合自然数集合N的基数记作的基数记作0,即即cardN =0(3)实数集实数集R的基数记作的基数记作,即即cardR =41基数的相等和大小基数的相等和大小定义定义8.13设设A,B为集合为集合,则则(1)cardA=cardB AB(2)cardAcardB A B(3)cardAcardB cardAcardBcardAcardB根据上一节关于势的讨论不难得到：根据上一节关于势的讨论不难得到

33、：cardZ =cardQ=cardNN =0cardP(N)=card2N =carda,b=card(c,d)=0cardAcardP(A)其中其中2N =0,1N42基数的大小基数的大小不存在最大的基数不存在最大的基数.将已知的基数按从小到大的顺序排列就将已知的基数按从小到大的顺序排列就得到：得到：0,1,2,n,0,其中：其中：0,1,2,n,是全体自然数是全体自然数,是有穷基数是有穷基数.0,是无穷基数是无穷基数,0是最小的无穷基数是最小的无穷基数,后面后面还还有更大的基数有更大的基数,如如cardP(R)等等.43可数集可数集定义定义8.14设设A为集合为集合,若若cardA0,则

34、称则称A为为可数集可数集或或可列集可列集.实例：实例：a,b,c,5,整数集整数集Z,有理数集有理数集Q,NN等都是可数集等都是可数集,实数集实数集R不是可数集不是可数集,与与R等势的集合也不是可数集等势的集合也不是可数集.对于任何的可数集对于任何的可数集,它的元素都可以排列成一个有序图形它的元素都可以排列成一个有序图形.换换句话说句话说,都可以找到一个都可以找到一个“数遍数遍”集合中全体元素的顺序集合中全体元素的顺序.可数集的性质：可数集的性质：l可数集的任何子集都是可数集可数集的任何子集都是可数集.l两个可数集的并是可数集两个可数集的并是可数集.l两个可数集的笛卡儿积是可数集两个可数集的笛

35、卡儿积是可数集.l可数个可数集的笛卡儿积仍是可数集可数个可数集的笛卡儿积仍是可数集.l无穷集无穷集A的幂集的幂集P(A)不是可数集不是可数集44实例实例解解(1)由由T=B,A,S,E,L知知cardT=5(2)由由B=,可知可知cardB=0.(3)由由|A|=4可知可知cardC=cardP(A)=|P(A)|=24=16.例例9求下列集合的基数求下列集合的基数(1)T=x |x是单词是单词“BASEBALL”中的字母中的字母(2)B=x |xRx2=92x=8(3)C=P(A),A=1,3,7,1145例例10设设A,B为集合为集合,且且cardA=0,cardB=n,n是自然数是自然数

36、,n0.求求cardAB.实例实例解解方法一方法一构造双射函数构造双射函数由由cardA=0,cardB=n,可知可知A,B都是可数集都是可数集.令令 A=a0,a1,a2,B=b0,b1,b2,bn 1对任意的对任意的,AB有有=i=kj=l 定义函数定义函数f :ABNf()=in+j,i=0,1,j=0,1,n 1易见易见f是是AB到到N的双射函数的双射函数,所以所以cardAB=card N=046方法二方法二直接使用可数集的性质求解直接使用可数集的性质求解.因为因为cardA=0,cardB=n,所以所以A,B都是可数集都是可数集.根据性质根据性质(3)可知可知AB也是可数集也是可数

37、集,所以所以cardAB0显然当显然当B时时,cardA cardAB,这就推出这就推出0 cardAB综合上述得到综合上述得到cardAB=0.实例实例47第八章第八章 习题课习题课主要内容主要内容l函数，函数，从从A到到B的函数的函数f:AB，BA，函数的像与完全原像，函数的像与完全原像l函数的性质：单射、满射、双射函数函数的性质：单射、满射、双射函数l重要函数：恒等函数、常函数、单调函数、集合的特征函重要函数：恒等函数、常函数、单调函数、集合的特征函数、自然映射数、自然映射l集合等势的定义与性质集合等势的定义与性质l集合优势的定义与性质集合优势的定义与性质l重要的集合等势以及优势的结果重

38、要的集合等势以及优势的结果l可数集与不可数集可数集与不可数集l集合基数的定义集合基数的定义48基本要求基本要求l给定给定f,A,B,判别判别f 是否为从是否为从A到到B的函数的函数l判别函数判别函数f:AB的性质（单射、满射、双射）的性质（单射、满射、双射）l熟练计算函数的值、像、复合以及反函数熟练计算函数的值、像、复合以及反函数l证明函数证明函数f:AB的性质（单射、满射、双射）的性质（单射、满射、双射）l给定集合给定集合A,B，构造双射函数，构造双射函数f:ABl能够证明两个集合等势能够证明两个集合等势l能够证明一个集合优势于另一个集合能够证明一个集合优势于另一个集合l知道什么是可数集与不

39、可数集知道什么是可数集与不可数集l会求一个简单集合的基数会求一个简单集合的基数49练习练习11给定给定A,B 和和f,判断是否构成函数判断是否构成函数f:AB.如果是如果是,说明该说明该函数是否为单射、满射、双射的函数是否为单射、满射、双射的.并根据要求进行计算并根据要求进行计算.(1)A=1,2,3,4,5,B=6,7,8,9,10, f=,.(2)A,B同同(1),f=,.(3)A,B同同(1),f=,.(4)A=B=R,f(x)=x3(5)A=B=R+,f(x)=x/(x2+1).(6)A=B=RR,f()=,令令 L=|x,yRy=x+1,计算计算 f(L).(7)A=NN,B=N,f

40、()=|x2 y2|.计算计算f(N0),f 1(0)50解解答解答(1)能构成能构成f:AB,f:AB既不是单射也不是满射既不是单射也不是满射,因为因为 f(3)=f(5)=9,且且7 ranf.(2)不构成不构成f:AB,因为因为f 不是函数不是函数.f 且且f,与与函函数定义矛盾数定义矛盾(3)不构成不构成f:AB,因为因为domf =1,2,3,4A(4)能构成能构成f:AB,且且f:AB是双射的是双射的(5)能构成能构成f:AB,f:AB既不是单射的也不是满射的既不是单射的也不是满射的.因为因为该该函数在函数在x=1取极大值取极大值f(1)=1/2.函数不是单调的函数不是单调的,且且

41、ranfR+.(6)能构成能构成f:AB,且且f:AB是双射的是双射的.f(L)=|xR=R 1(7)能构成能构成f:AB,f:AB既不是单射的也不是满射的既不是单射的也不是满射的.因为因为f()=f()=0,2 ranf.f(N0)=n2 02|nN=n2|nNf 1(0)=|nN51练习练习22.设设f1,f2,f3,f4 RR，且，且令令Ei 是由是由fi 导出的等价关系，导出的等价关系，i=1,2,3,4，即，即xEiy fi(x)=fi(y)(1)画出偏序集画出偏序集的哈斯图，其的哈斯图，其中中T 是加细关系：是加细关系： T x(x R/Eiy(y R/Ej x y)(2)gi:R

42、R/Ei 是自然映射，求是自然映射，求gi(0),i=1,2,3,4.(3)对每个对每个i,说明说明gi 的性质（单射、满射、双射）的性质（单射、满射、双射）.52(1)哈斯图如下哈斯图如下(2)g1(0)=x|x R x 0,g2(0)=0,g3(0)=Z,g4(0)=R(3)g1,g3,g4是满射的；是满射的；g2是双射的是双射的.解图1解答解答53练习练习33对于以下集合对于以下集合A和和B，构造从，构造从A到到B的双射函数的双射函数f:AB(1)A=1,2,3，B=a,b,c(2)A=(0,1)，B=(0,2)(3)A=x|x Zx0，B=N (4)A=R，B=R+解解(1)f=,(2

43、)f:AB,f(x)=2x(3)f:AB,f(x)= x 1(4)f:AB,f(x)=ex544.4.设 证明证明 f 既是满射的，也是单射的既是满射的，也是单射的. 证 任取任取 R R，存在，存在使得使得 练习练习4因此因此f 是满射的是满射的对于任意的对于任意的, R R,有有因此因此f 是单射的是单射的.55证明方法证明方法1.证明证明f:AB是满射的方法是满射的方法:任取任取y B,找到找到x (即给出即给出x的的表示表示)或者证明存在或者证明存在x A，使得，使得f(x)=y.2.证明证明f:AB是单射的方法是单射的方法方法一方法一 x1,x2 A, f(x1)=f(x2)x1=x

44、2推理前提推理前提推理过程推理过程推理结论推理结论方法二方法二 x1,x2 A, x1 x2f(x1) f(x2)推理前提推理前提推理过程推理过程推理结论推理结论3.证明证明f:AB不是满射的方法：不是满射的方法：找到找到y B,y ranf4.证明证明f:AB不是单射的方法：找到不是单射的方法：找到x1,x2 A,x1 x2,且且 f(x1)=f(x2)565.设设A,B为二集合为二集合,证明：如果证明：如果AB,则则P(A)P(B)练习练习5证证因为因为AB，存在双射函数，存在双射函数f:AB，反函数，反函数f 1:BA构造函数构造函数g:P(A)P(B), g(T)=f(T)， T A（

45、f(T)是是T在函数在函数f 的像）的像）证明证明g 的满射性的满射性.对于任何对于任何S B,存在存在f 1(S) A,且且g(f 1(S)=f f 1(S)=S证明证明g的单射性的单射性.g(T1)=g(T2)f(T1)=f(T2)f 1(f(T1)=f 1(f(T2)IA(T1)=IA(T2)T1=T2综合上述得到综合上述得到P(A)P(B).57证明集合证明集合A与与B等势的方法等势的方法方法一：直接构造从方法一：直接构造从A到到B的双射的双射,即定义一个从即定义一个从A到到B的函数的函数f:AB，证明证明f 的满射性，证明的满射性，证明f 的单射性的单射性方法二：利用定理方法二：利用

46、定理8.8，构造两个单射，构造两个单射f:AB 和和g:BA.即即定义函数定义函数f 和和g ，证明，证明f 和和g 的单射性的单射性方法三：利用等势的传递性方法三：利用等势的传递性方法四：直接计算方法四：直接计算A与与B的基数，得到的基数，得到cardA=cardB.注意：注意：l以上方法中最重要的是方法一以上方法中最重要的是方法一.l证明集合证明集合A与自然数集合与自然数集合N等势的通常方法是：找到一个等势的通常方法是：找到一个“数遍数遍”A中元素的顺序中元素的顺序.58练习练习66已知已知A=n7|nN,B=n109|nN,求下列各题：求下列各题：(1)CardA(2)CardB(3)c

47、ard(A B)(4)card(A B)解解(1)构造双射函数构造双射函数f:NA,f(n)=n7,因此因此cardA=0(2)构造双射函数构造双射函数g:NA,g(n)=n109,因此因此cardB=0(3)可数集的并仍旧是可数集，因此可数集的并仍旧是可数集，因此card(A B) 0,但是但是card(A B) cardA=0,从而得到从而得到card(A B)=0.(4)因为因为7与与109互素，互素，card(A B)=n7 109|n N，与与(1)类似得到类似得到card(A B)=0597.已知已知cardA=0,且且cardBcardA,求求card(A B)练习练习7解解由由A B A 得到得到card(A B) cardA,即即card(A B) 0由由cardBcardA 可知可知B 为有穷集，即存在自然数为有穷集，即存在自然数n使得使得cardB=n.假设假设card(A B)0，那么存在自然数，那么存在自然数m，使得，使得card(A B)=m从而得到从而得到cardA =card(A B) B) n+m，与与cardA=0矛盾矛盾.因此，因此，card(A B)=0.60