离散数学课件08函数.ppt

《离散数学课件08函数.ppt》由会员分享，可在线阅读，更多相关《离散数学课件08函数.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8 8章章 函数函数离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容函数的定义函数的定义函数的性质函数的性质函数的逆函数的逆函数的合成函数的合成q本章与后续各章的关系本章与后续各章的关系是代数系统的基础是代数系统的基础8.1 8.1 函数的定义与性质函数的定义与性质8.2 8.2 函数的复合与反函数函数的复合与反函数8.3 8.3 一个电话系统的描述实例一个电话系统的描述实例 本章小结本章小结 习题习题 作业作业本章内容本章内容本章内容本章内容8.1 8.1 8.1 8.1 函数的定义与性质函数的定义与性质函数

2、的定义与性质函数的定义与性质定义定义8.1 8.1 设设F F为二元关系，若为二元关系，若 xdom Fdom F，都存在都存在唯一的唯一的yran ran F使使xF Fy成立，则称成立，则称F F为为函数函数(function)(或称作或称作映映射射(mapping)。对于函数对于函数F F，如果有如果有 xF Fy，则记作则记作yF(F(x)，并称并称y为为F F在在x的的值值。举例举例 判断下列关系是否为函数判断下列关系是否为函数F F1 1x,F F2 2x,是函数是函数不是函数不是函数说明说明q函数是特殊的二元关系。函数是特殊的二元关系。q函数的定义域为函数的定义域为domdom

3、F F，而不是它的真子集。而不是它的真子集。q一个一个x x只能对应唯一的只能对应唯一的y y。定义定义8.2 8.2 设设 F,G F,G 为函数，则为函数，则 F FG G F F GGGG F F由定义可知，两个函数由定义可知，两个函数F F和和G G相等相等,一定满足下面两个条件：一定满足下面两个条件：（1 1）dom Fdom Fdom G dom G（2 2）xdom Fdom Fdom Gdom G，都有都有 F(F(x)G(G(x)例如例如 函数函数F(F(x)(x2 2 1)/(1)/(x+1)+1)，G(G(x)x 1 1不相等不相等,因因为为dom Fdom F x|xR

4、Rx-1-1 dom Gdom GR R显然，显然，dom Fdom Fdom Gdom G，所以两个函数不相等。所以两个函数不相等。函数相等函数相等函数相等函数相等定义定义8.38.3 设设A,BA,B为集合，如果为集合，如果 f 为函数，为函数，dom dom fA A，ran ran f B B，则称则称 f 为为从从A A到到B B的函数的函数，记作，记作 f：ABAB。例如：例如：f：NNNN，f(x)2x2x是从是从N N到到N N的函数，的函数，g：NNNN，g(x)2 2也是从也是从N N到到N N的函数。的函数。定义定义8.4 8.4 所有从所有从A A到到B B的函数的集合

5、记作的函数的集合记作B BA A，读作读作“B B上上A”A”，符号化表示为符号化表示为 B BA A f|f：AB AB。从从从从A A A A到到到到B B B B的函数的函数的函数的函数例例8.28.2 设设A A1,2,31,2,3，B Ba,ba,b，求求B BA A。解答解答BAf0,f1,f2,f3,f4,f5,f6,f7。其中其中f0,f1,f2,f3,f4,f5,f6,f7,例例例例8.28.28.28.2说明说明q若若|A|A|m，|B|B|n，且且m,n00，则则|B BA A|nm。q当当A A或或B B至少有一个集合是空集时：至少有一个集合是空集时：A A且且B B，

6、则，则B BA A 。A A且且BB，则，则B BA AB B 。AA且且B B，则则B BA AA A。定义定义8.58.5 设函数设函数f：ABAB，A A1 1 A A，B B1 1 B B。（1 1）令令f(A(A1 1)f(x)|)|xAA1 1，称称 f(A(A1 1)为为A A1 1在在f 下的像下的像(image)。特别地，当特别地，当A A1 1A A时，称时，称 f(A)(A)为函数的像为函数的像。（2 2）令令f 1 1(B(B1 1)x|xAAf(x)B)B1 1，称称f 1 1(B(B1 1)为为B B1 1在在 f 下的下的完完全原像全原像(preimage)。说明

7、说明函数的像和完全原像函数的像和完全原像函数的像和完全原像函数的像和完全原像q注意区别函数的值和像两个不同的概念。注意区别函数的值和像两个不同的概念。函数值函数值f(x)B)B，而函数的像而函数的像f(A(A1 1)B B。讨论讨论q设设 B B1 1 B B，显然显然B B1 1在在 f 下的原像下的原像 f-1-1(B(B1 1)是是A A的子集。的子集。q设设 A A1 1 A A，那么那么 f(A A1 1)B B。f(A A1 1)的完全原像就是的完全原像就是 f-1-1(f(A A1 1)。一般来说，一般来说，f-1-1(f(A A1 1)A A1 1，但是但是A A1 1 f-1

8、-1(f(A A1 1)。q例如函数例如函数 f:1,2,30,1:1,2,30,1，满足满足f(1)(1)f(2)(2)0 0，f(3)(3)1 1令令A A1 111，那么那么f-1-1(f(A A1 1)f-1-1(f(1)1)f-1-1(0)(0)1,21,2这时，这时，A A1 1是是f-1-1(f(A A1 1)的真子集。的真子集。例例8.38.3设设f:NN:NN，且且令令A A0,10,1，B B22，求求f(A)(A)和和 f 1 1(B)(B)。解答解答 f(A)f(0,1)f(0),f(1)0,2f 1(B)f 1(2)1,4(因为因为 f(1)2,f(4)2)例例例例8

9、.38.38.38.3定义定义8.68.6设设f:AB，（1 1）若若ranfB，则称则称f:AB是是满射满射(surjection)的的。（2 2）若若 yranf 都存在都存在唯一的唯一的xA使得使得f(x)y，则称则称 f:AB是是单射单射(injection)的的。（3 3）若若f 既是满射又是单射的既是满射又是单射的，则称则称f:AB是是双射双射(bijection)的的(一一映像一一映像(one-to-one mapping)。说明说明满射、入射、双射满射、入射、双射满射、入射、双射满射、入射、双射q如果如果f:A:AB B是满射的，则对于任意的是满射的，则对于任意的yB B，都存

10、在都存在xA A，使得使得f(x)y。q如果如果f:A:AB B是单射的，则对于是单射的，则对于x1 1、x2 2 A A且且x1 1x2 2，一定一定 有有f(x1 1)f(x2 2)。换句话说，如果对于换句话说，如果对于x1 1、x2 2 A A有有f(x1 1)f(x2 2)，则一定有则一定有x1 1x2 2。不同类型的对应关系的示例不同类型的对应关系的示例abc1234abc1234abc1234dabc1234dabc123d单射单射不是函数不是函数双射双射函数函数满射满射例例8.48.4判断下面函数是否为单射、满射、双射的，为什么判断下面函数是否为单射、满射、双射的，为什么?(1)

11、f：RR，f(x)=-x2+2x-1(2)f：Z+R，f(x)=ln x，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.48.48.48.4（1）f 在在x=1取得极大值取得极大值0。既不是单射也不是满射的既不是单射也不是满射的。（2）f 是单调上升的，是单射的，但不满射是单调上升的，是单射的，但不满射。ran f=ln1,ln2,。（3）f 是满射的，是满射的，但不是单射的，例如但不是单射的，例如f(1.5)=f(1.2)=1。（4）f 是满射、单射、双射的

12、，因为它是单调函数并且是满射、单射、双射的，因为它是单调函数并且ran f=R。（5）f 有极小值有极小值f(1)=2。该函数既不是单射的，也不是满射的该函数既不是单射的，也不是满射的。分析分析实数集合上函数性质的判断方法实数集合上函数性质的判断方法例例8.58.5例例8.58.5 对于以下各题给定的对于以下各题给定的A,B和和 f，判断是否构成函数判断是否构成函数f:AB。如果是，说明如果是，说明 f:AB:AB是否为单射、满射和双射的，并根据是否为单射、满射和双射的，并根据要求进行计算。要求进行计算。(1)(1)A1,2,3,4,51,2,3,4,5，B6,7,8,9,106,7,8,9,

13、10，f,能构成能构成f:AB，f 不是单射的，因为不是单射的，因为f(3)(3)f(5)(5)9,9,f 不是满射的，因为不是满射的，因为7 7 ran fran f。(2)2)A1,2,3,4,51,2,3,4,5，B6,7,8,9,106,7,8,9,10，f,不能构成不能构成f:AB，因为因为 1,7f 且且 1,9f。例例例例8.58.58.58.5(3)(3)A1,2,3,4,51,2,3,4,5，B6,7,8,9,106,7,8,9,10，f,不能构成不能构成f:AB，因为因为dom dom f1,2,3,41,2,3,4A。(4)(4)ABR R，f(x)x x能构成能构成f:

14、AB，且且f 是双射的是双射的。(5)(5)ABR R+，f(x)x/(xx/(x2 2+1)+1)（xRxR+）能构成能构成f:AB，但但f 既不是单射的也不是满射的。既不是单射的也不是满射的。因为该函数在因为该函数在x1取得极大值取得极大值f(1)1/2，函数不是单调函数不是单调的，且的，且ranfRR+。例例例例8.58.58.58.5(6)(6)ABRRR，f()令令L|x,yRRyx+1+1，计算计算 f(L)。能构成能构成 f:AB，且且f 是双射的是双射的。f(L)|+1)|xRR|+1,-1|xRRR-1R-1(7)(7)ANN，BN，f()|x|x2 2-y-y2 2|计算计

15、算f(N0),(N0),f-1-1(0)(0)。能构成能构成f:AB，但但f 既不是单射也不是满射的。既不是单射也不是满射的。因为因为f()()f()()0 0，且且2 2 ran ran f。f(N0)(N0)n2 2-0-02 2|nNN n2 2|nNNf-1-1(0)(0)|nNN例例8.68.6例例8.68.6 对于给定的集合对于给定的集合A A和和B B构造双射函数构造双射函数 f:AB:AB。（1 1）A AP P(1,2,3)(1,2,3),B,B0,10,11,2,31,2,3（2 2）A A0,10,1,B,B1/4,1/21/4,1/2（3 3）A AZ,BZ,BN N（

16、4 4）A A /2,3/2,3/2/2,B,B 1,11,1例例8.68.6的解答的解答（1）AP(1,2,3),B0,11,2,3 A,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.68.6的解答的解答（2）A0,10,1,B1/4,1/21/4,1/2令令f:AB,f(x)(x+1)/4。（3）AZ,BN将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N

17、N中元素对应：中元素对应：Z：0 11 22 33N：0123456则这种对应所表示的函数是：则这种对应所表示的函数是：（4）A=/2,3/2,B=1,1令令f:AB，f(x)sinx。常用函数常用函数常常函数和恒等函数函数和恒等函数q设设f：AB，如果存在如果存在cB，使得对所有的使得对所有的xA都有都有f(x)c，则称则称f：AB是是常函数常函数。q设设f：AB，对所有的对所有的xA都有都有IA(x)x，称称IA为为A上的上的恒恒等函数等函数。常用函数常用函数常用函数常用函数单调递增函数单调递增函数单调递增函数单调递增函数q设设，为偏序集为偏序集，f：AB，如果对任意的如果对任意的x1,x

18、2A，x1x2，就有就有f(x1)f(x2)，则称则称f为为单调递增单调递增的的；如果对任意的如果对任意的x1,x2A,x1x2,就有就有f(x1)f(x2),则称则称f为为严格严格单调递增单调递增的的。q类似的也可以定义单调递减和严格单调递减的函数类似的也可以定义单调递减和严格单调递减的函数。q举例举例：f:RR,f(x)x+1是严格单调递增的。是严格单调递增的。偏序集偏序集 ，R 为包含关系为包含关系，为为一般的小于等于关系。一般的小于等于关系。令令f：P(a,b)0,1，f()f(a)f(b)0，f(a,b)=1，f是单调递增的是单调递增的,但不是严格单调递增的但不是严格单调递增的。常用

19、函数常用函数特特征函数征函数q设设A为集合，对于任意的为集合，对于任意的A A，A 的的特征函数特征函数 A :A0,1定义为定义为1，aA 0，aA A A (a)q举例举例:A的每一个子集的每一个子集A 都对应于一个特征函数，不同的子都对应于一个特征函数，不同的子集对应于不同的特征函数。集对应于不同的特征函数。例如例如Aa,b,c,则有则有,，a,a,b,常用函数常用函数常用函数常用函数自自自自然映射然映射然映射然映射q设设R是是A上的等价关系，上的等价关系，令令 g：AA/Rg(a)=a，aA 称称g是从是从A到商集到商集A/R的的自然映射自然映射。q给定集合给定集合A和和A上的等价关系

20、上的等价关系R，就可以确定一个自然映射就可以确定一个自然映射g：AA/R。例如例如A1,2,3，R,IA g(1)g(2)1,2,g(3)3不同的等价关系确定不同的自然映射，其中恒等关系所确定不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射，的自然映射是双射，而其他的自然映射一般来说只是满射。而其他的自然映射一般来说只是满射。定定义在自然数集合上的计数函数义在自然数集合上的计数函数q对于给定规模为对于给定规模为n的输入，计算算法所做基本运算的次数，将的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。这个次数表示为输入规模的函数。排序和检索问题的基本运算是比

21、较。排序和检索问题的基本运算是比较。矩阵乘法的基本运算是元素的相乘。矩阵乘法的基本运算是元素的相乘。q估计算法在最坏情况下所做基本运算的次数记为估计算法在最坏情况下所做基本运算的次数记为W(W(n)。q估计算法在平均情况下所做基本运算的次数记为估计算法在平均情况下所做基本运算的次数记为A(A(n)。q设设f是定义在自然数集合上的函数，当是定义在自然数集合上的函数，当n变得很大时，变得很大时，函数值函数值f(n)的增长取决于函数的阶的增长取决于函数的阶。阶越高的函数，算法的复杂度。阶越高的函数，算法的复杂度就越高，同时意味着算法的效率越低。就越高，同时意味着算法的效率越低。q算法分析的主要工作就

22、是估计复杂度函数的阶算法分析的主要工作就是估计复杂度函数的阶。阶可以是：。阶可以是：n，n2 2，n3 3，nlog log n，log log n，2 2n 定定义在自然数集合上的计数函数义在自然数集合上的计数函数q若存在正数若存在正数c和和n0 0，使得对一切使得对一切nn0 0，有有00f(n)cg(n)，记记作作 f(n)O(g(n)。q若存在正数若存在正数c和和n0 0，使得对一切使得对一切nn0 0，有有00cg(n)f(n)，记记作作 f(n)(g(n)。q若若f(n)O(g(n)且且 f(n)(g(n)，则则f(n)(g(n)。q例如例如f(n)1/2 1/2 n2 2-3-3

23、n，则则 f(n)(n2 2)g(n)6 6n3 3，则则 g(n)(n3 3)构造从构造从A A到到B 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实数区间之间构造双射实数区间之间构造双射构造方法：直线方程构造方法：直线方程例

24、例2A=0,1B=1/4,1/2构造双射构造双射f:AB构造从构造从A A到到B B的双射函数的双射函数(续续)解解令令f:0,11/4,1/2 f(x)=(x+1)/4A与自然数集合之间构造双射与自然数集合之间构造双射方法：将方法：将A中元素排成有序图形，然后从第一个元素开始中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应按照次序与自然数对应构造从构造从A A到到B B的双射函数的双射函数(续续)例例3A=Z,B=N，构造双射，构造双射f:AB将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z：0 11 22 33N：0123456则这种对应所表示

25、的函数是：则这种对应所表示的函数是：8.2 8.2 函数的复合与反函数函数的复合与反函数q函数的复合就是关系的右复合函数的复合就是关系的右复合，一切和关系右复合有关的，一切和关系右复合有关的定理都适用于函数的复合。定理都适用于函数的复合。本节重点考虑在复合中特有的本节重点考虑在复合中特有的性质。性质。定理定理定理定理8.1(8.1(8.1(8.1(复合函数基本定理复合函数基本定理复合函数基本定理复合函数基本定理)定理定理8.18.1设设F,G是函数是函数，则则F G 也是函数，且满足也是函数，且满足（1）dom(F G)x|xdomFF(x)domG（2）xdom(F G)，有有F G(x)G

26、(F(x)证明证明：先证明先证明F G是函数是函数。因为因为F、G是关系是关系，所以所以F G也是关系也是关系。若对某个若对某个xdom(F G)，若有若有xF Gy1和和xF Gy2，则则 F G F G t1(F G)t2(F G)t1 t2(t1t2 GG)（F为函数为函数）y1y2（G为函数为函数）所以所以F G为函数为函数。定理定理定理定理8.18.18.18.1的证明的证明的证明的证明定理定理8.18.1的证明的证明任取任取x，(要证明要证明dom(F G)x|xdomFF(x)domG)xdom(F G)t y(F G)t(xdomF tF(x)tdomG)xx|xdomF F(

27、x)domG所以（所以（1）得证。）得证。任取任取x，（要证明要证明 xdom(F G)，有有F G(x)G(F(x)）xdomF F(x)domGF GF Gxdom(F G)F G(x)G(F(x)所以（所以（2）得证。）得证。推论推论1设设F,G,H为函数为函数，则则(F G)H和和F(G H)都是函数，都是函数，且且(F G)H=F(G H)证明证明：由定理：由定理8.18.1（复合函数基本定理）和定理（复合函数基本定理）和定理7.27.2（关系合成（关系合成具有结合性）得证。具有结合性）得证。定理定理定理定理8.18.18.18.1的推论的推论的推论的推论1 1 1 1推论推论2 2

28、设设f：AB，g：BC，则则f g：AC，且且 xA都有都有f g(x)=g(f(x)。证明证明：由定理由定理8.1（复合函数基本定理）可知（复合函数基本定理）可知f g是函数，且是函数，且 dom(f g)x|xdomf f(x)domgx|xA f(x)BA ran(f g)rang C 因此因此f g：AC，且且 xA有有f g(x)g(f(x)。定理定理定理定理8.18.18.18.1的推论的推论的推论的推论2 2 2 2定理定理8.28.2设设f：AB，g：BC。（1）如果如果f：AB，g：BC都是满射的，都是满射的，则则f g：AC 也是满射的也是满射的。（2）如果如果f：AB，g

29、：BC都是单射的，则都是单射的，则f g：AC也也是单射的。是单射的。（3）如果如果f：AB，g：BC都是双射的，则都是双射的，则f g：AC也也是双射的。是双射的。说明说明函数的复合运算的性质函数的复合运算的性质函数的复合运算的性质函数的复合运算的性质该定理说明函数的复合能够保持函数单射、满射、双射的该定理说明函数的复合能够保持函数单射、满射、双射的性质。性质。定理定理8.28.2的证明的证明(1)(1)如如果果f：AB，g：BC都都是是满满射射的的，则则f g：AC也也 是满射的。是满射的。证明：证明：任取任取cC，由由g：BC的满射性，所以的满射性，所以 bB使得使得g(b)=c。对于这

30、个对于这个b，由由f：AB的满射性，所以的满射性，所以 aA使得使得f(a)=b。由合成定理有由合成定理有 f g(a)g(f(a)g(b)c所以，所以，f g：AC是满射的。是满射的。定理定理8.28.2的证明的证明(2)如如果果f：AB，g：BC都都是是单单射射的的，则则f g：AC也也是是单射的单射的。证明证明：假设存在假设存在x1,x2A使得使得f g(x1)f g(x2)，由由合成定理有合成定理有 g(f(x1)=g(f(x2)因为因为g：BC是单射的，故是单射的，故f(x1)f(x2)。又由于又由于f：AB也是单射的，所以也是单射的，所以x1x2。所以，所以，fog：AC是单射的是

31、单射的。(3)如如果果f：AB，g：BC都都是是双双射射的的，则则f g：AC也也是双射的。是双射的。证明：由（证明：由（1）和（）和（2）得证。）得证。定理定理8.28.2之逆不为真之逆不为真q考虑集合考虑集合Aa1,a2,a3，Bb1,b2,b3,b4，Cc1,c2,c3。令令f,g,则则f g=,那么那么f:AB和和f g:AC都是单射的都是单射的，但但g:BC不是单射的不是单射的。q考虑集合考虑集合A=a1,a2,a3，B=b1,b2,b3，C=c1,c2。令令f,g,则则f g,那么那么g:BC和和f g:AC是满射的，但是满射的，但f:AB不是满射的。不是满射的。定理定理8.38.

32、3定理定理8.38.3设设f：AB，则则f f oIBIAof证明证明：由定理：由定理8.1的推论的推论2可知可知f oIB：AB和和IAof：AB任取任取，f f y Bf IBf oIB所以，所以，f f oIBf oIB t(f IB)f t=yf 所以所以，f oIB f所以所以，f f oIB同理可证同理可证f IAof什么样的函数什么样的函数f：AB，它的逆它的逆f 1是从是从B到到A的函数呢？的函数呢？q任给函数任给函数F,它的逆它的逆F 1不一定是函数不一定是函数,只是一个二元关系。只是一个二元关系。F，F-1，q任任给给单单射射函函数数f：AB,则则f 1是是函函数数,且且是

33、是从从ranf到到A的的双双射射函数函数,但不一定是从但不一定是从B到到A的双射函数。的双射函数。因为对于某些因为对于某些yBranf，f-1没有值与之对应。没有值与之对应。q任给满射函数任给满射函数f：AB，则则f 1不一定是函数。不一定是函数。q对于双射函数对于双射函数f：AB,f 1：BA是从是从B到到A的双射函数。的双射函数。反函数反函数反函数反函数定理定理8.48.4设设f：AB是双射的，则是双射的，则f 1：BA也是双射的。也是双射的。证明证明：先证明先证明f-1：BA是函数，且是函数，且domf 1B，ranf 1A。因为因为f 是函数，所以是函数，所以f 1是关系，且是关系，且

34、domf 1ranfB,ranf 1domfA，对于任意的对于任意的xB domf 1，假设有假设有y1,y2A，使得使得f 1f 1成立，成立，则由逆的定义有则由逆的定义有，ff。根据根据f 的单射性，可得的单射性，可得y1y2。所以，所以，f-1是函数。是函数。反函数存在的条件反函数存在的条件反函数存在的条件反函数存在的条件再证明再证明f-1：BA的双射性质。的双射性质。q（证明单射（证明单射）若存在若存在x1,x2B，使得使得f 1(x1)=f 1(x2)=y，从而有从而有f 1f 1ff x1x2（因为因为f 是函数）是函数）所以，所以，f-1是单射的。是单射的。q（证明满射（证明满射

35、）对于任意的对于任意的yA，因为因为f 是双射的是双射的，所以必存在所以必存在xB，使得使得f，所以所以f 1，所以，所以，f 1是满射的。是满射的。综上所述，综上所述，f 1是双射函数。是双射函数。说明说明定理定理定理定理8.48.48.48.4的证明的证明的证明的证明对于双射函数对于双射函数f：AB，称称f-1：BA是它的反函数。是它的反函数。反函数的性质反函数的性质定理定理8.58.5设设f：AB是双射的，是双射的，则则f-1 f=IB，f f-1=IA证明证明：根据定理可知：根据定理可知f-1：BA也是双射的，也是双射的，且且f-1 f：BB，f f-1：AA。任取任取 f 1 f t

36、(f 1 f)t(f f)x=y x,y B IB所以，所以，f-1 f IB IBxy x,y B t(f f)t(f 1 f)f-1 f 所以，所以，IB f-1 f 综上所述，综上所述，f-1 f IB。同理可证同理可证f f-1IA例例8.88.8例例8.88.8设设f：RR,g：RR 求求f g，g f。如果如果f 和和g 存在反函数，求出它们的反函数存在反函数，求出它们的反函数。解答解答g：RR是双射的，它的是双射的，它的反函数是反函数是g 1：RR，g 1(x)=x 2定义定义8.88.8 设设A,BA,B是集合，如果存在着从是集合，如果存在着从A A到到B B的的双射函数双射函

37、数，就，就称称A A和和B B是等势是等势（samecardinality）的的，记作，记作ABAB。如果如果A A不与不与B B等势，则记作等势，则记作A BA B。8.38.3双射函数与双射函数与集合的基数集合的基数集合的基数集合的基数q通俗的说，集合的势是量度集合所含元素多少的量。通俗的说，集合的势是量度集合所含元素多少的量。q集合的势越大，所含的元素越多。集合的势越大，所含的元素越多。（1）ZN。则则f是是Z到到N的双射函数。的双射函数。从而证明了从而证明了ZN。等势集合的实例等势集合的实例等势集合的实例等势集合的实例(1)(1)(1)(1)等势集合的实例等势集合的实例(2)(2)（2

38、）NNN。双射函数双射函数等势集合的实例等势集合的实例(3)(3)（3 3）NQNQ。把所有形式为把所有形式为p p/q q(p p,q q为整数且为整数且q q0)0)的数排成一张表。的数排成一张表。-2/1-2/155-1/1-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/

39、41515-3/4-3/416162/42/43/43/413130/40/41/41/41414以以0/10/1作为第一个数，按照箭头规定的顺序可以作为第一个数，按照箭头规定的顺序可以“数遍数遍”表中表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。同一个有理数。等势集合的实例等势集合的实例(4)(4)（4）(0,1)R。其中实数区间其中实数区间(0,1)=x|xR0 x1。令双射函数令双射函数则则f 是是(0,1)到到R的双射函数。从而证明了的双射函数。从而证明了(0,1)R。等势集合的实例等势集合的实例(5)(5

40、)（5 5）0,1(0,1)。其中其中(0,1)和和0,1分别为实数开区间和闭区分别为实数开区间和闭区间。间。双射函数双射函数f:0,1(0,1)，2 2等势集合的实例等势集合的实例(6)(6)（6 6）对任何）对任何a,bR，ab，0,1a,b。双射函数双射函数f：0,1a,b，f(x)(b a)x+a。例例8.108.10设设A为任意集合，则为任意集合，则P(A)0,1A。构造构造f：P(A)0,1A，f(A)=A ，A P(A)。其中其中 A 是集合是集合A 的特征函数的特征函数。(1)(1)易证易证f 是单射的是单射的。(2)(2)对于任意的对于任意的g0,1A，那么有那么有g：A0,

41、1。令令 B=x|xAg(x)=1则则B A，且且 B=g，即即 BP(A)，使得使得f(B)=g。所以所以f 是满射的。是满射的。由等势定义得由等势定义得P(A)0,1A。例例例例8.108.108.108.10证明证明复习复习定理定理8.68.6 设设A，B，C是任意集合，是任意集合，（1）AA。（2）若若AB，则则BA。（3）若若AB，BC，则则AC。（1 1）IA是从是从A到到A的双射，因此的双射，因此AA。（2）假设假设AB，存在，存在f:AB是双射，是双射，那么那么f 1:BA是从是从B到到A的双射，所以的双射，所以BA。（3）假设假设AB，BC，存在存在 f:AB，g:BC是双射

42、，是双射，则则f g:AC是从是从A 到到C 的双射的双射。所以所以AC。等势的性质等势的性质等势的性质等势的性质证明证明q N Z Q NNq R 0,1(0,1)q任何的实数区间（开区间、闭区间以及半开半闭的区间）任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合都与实数集合R R等势。等势。q问题：问题：N N和和R R是否等势？是否等势？若干等势集合若干等势集合若干等势集合若干等势集合（1）如果能证明）如果能证明N0,1，就可以断定就可以断定NR。只需证明任何函数只需证明任何函数f：N0,1都不是满射的。都不是满射的。构造一个构造一个0,1区间的小数区间的小数b，使得使得b

43、在在N中不存在原像。中不存在原像。（2）任取函数）任取函数f：AP(A)，构造构造BP(A)，使得使得B在在A中不存在原中不存在原像。像。或者使用反证法。或者使用反证法。定理定理8.78.7康托定理康托定理（1）N R。（2）对任意集合对任意集合A都有都有A P(A)。康托定理康托定理康托定理康托定理分析分析（1 1）首先规定）首先规定0,1中数的表示。中数的表示。对任意的对任意的x0,1，令令x=0.x1x2,（0 xi 9）注意：为了保证表示式的唯一性，如果遇到注意：为了保证表示式的唯一性，如果遇到0.249990.24999，则将，则将x x表表示为示为0.250000.25000。设设

44、 f:N0,1是从是从N到到0,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的表示式为的表示式为0.b1b2，并且满足并且满足bi ai(i)，i=1,2,，则则y0,1，但但y与上面列出的任何一个函数值都不相等与上面列出的任何一个函数值都不相等。即即f不是满射的。不是满射的。所以所以，N R。康托定理康托定理康托定理康托定理康托定理康托定理q假设假设A AP(A)，则必有函数则必有函数f:AP(A)是双射函数。是双射函数。如下构造集合如下构造集合B：Bx|xA

45、x f(x)可知可知BP(A)。于是存在唯一一个元素于是存在唯一一个元素bA，使得使得f(b)B。若若bB，则由则由B的定义知，的定义知，b f(b)，即即b B，矛盾矛盾。若若b B，则则b f(b)，于是由于是由B的定义知，的定义知，bB，矛盾。矛盾。（2 2）设）设g：AP(A)是从是从A到到P(A)的任意函数，的任意函数，如下构造集合如下构造集合B：Bx|xAx g(x)则则BP(A)。但是但是对任意对任意xA，都有都有xB x g(x)所以，对任意的所以，对任意的xA都有都有Bg(x)，即即B ran ran g 即即P(A)中存在元素中存在元素B，在在A中找不到原像。中找不到原像。

46、所以所以，g不是满射的。不是满射的。所以所以，A P(A)。说明说明康托定理康托定理康托定理康托定理q根据这个定理可以知道根据这个定理可以知道N P(N)。q综合前面的结果，可知综合前面的结果，可知N 0,1N。q实际上，实际上，P(N)P(N)，0,10,1N N和和R R都是比都是比N“N“更大更大”的集合。的集合。定义定义8.98.9（1 1）设设A,B是集合，如果存在从是集合，如果存在从A到到B的的单射单射函数，就称函数，就称B优优势于势于A，记作记作AB。如果如果B不是优势于不是优势于A，则记作则记作AB。（2 2）设设A,B是集合，若是集合，若AB且且A B，则称则称B真优势于真优

47、势于A，记作记作AB。如果如果B不是真优势于不是真优势于A，则记作则记作AB。例如：例如：N NN RA P(A)N RA P(A)R NN N优势优势优势优势RN定理定理8.88.8 设设A,B,C是任意的集合，则是任意的集合，则（1）A A。（2）若若A B且且B A，则则AB。（3）若若A B且且B C,则则A C。证明：证明：（1 1）IA是是A到到A的单射的单射，因此因此A A。（2 2）证明略。）证明略。（3 3）假设）假设A B且且B C，那么存在单射，那么存在单射 f:AB:AB，g:BC:BC，于是于是 f g：AC也是单射的，因此也是单射的，因此A C。优势的性质优势的性质

48、优势的性质优势的性质说明说明q该定理为证明集合之间的等势提供了有力的工具该定理为证明集合之间的等势提供了有力的工具。q构造两个单射构造两个单射f：A AB B 和和 g g：B BA A函数容易集合等势函数容易集合等势。例题例题例题：例题：证明证明0,10,1与与(0,1)(0,1)等势。等势。证明：证明：构造两个单射函数构造两个单射函数f:(0,1)0,1:(0,1)0,1，f(x)xg:0,1(0,1):0,1(0,1)，g(x)x/2+1/4/2+1/4证明证明 0,1N0,1)(1)设设x 0,1)，0.x1x2是是x的的二进制表示二进制表示。为了使表示唯一，规定表示式中不允许出现连续

49、无数个为了使表示唯一，规定表示式中不允许出现连续无数个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是是：n 01234567tx(n)10110100易见易见tx0,1N，且对于且对于x,y0,1)，xy，必有必有tx ty，即即f(x)f(y)。所以所以，f：0,1)0,1N是单射的。是单射的。(2)定义函数定义函数g：0,1N0,1)。g的映射法则恰好与的映射

50、法则恰好与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,10,1N N0,1)0,1)总结总结qN Z Q