离散数学08函数

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

2、 设设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 函数的定义域为函数的定义域为dom Fdom F，而不是它的真子集

3、。而不是它的真子集。q 一个一个x x只能对应唯一的只能对应唯一的y y。编辑ppt定义定义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不相等不相等, , 因为因为do

4、m Fdom F x| |xRRx -1-1 dom Gdom GR R显然，显然， dom Fdom Fdom Gdom G，所以两个函数不相等。所以两个函数不相等。函数相等函数相等编辑ppt 设设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 所有从所有从

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

6、合是空集时： A A且且B B，则，则B BA A 。 A A且且BB，则，则B BA AB B 。 AA且且B B，则则B BA AA A。编辑ppt 设函数设函数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) )为为

7、B B1 1在在 f 下的下的完完全原像全原像( (preimage) ) 。函数的像和完全原像函数的像和完全原像q 注意区别函数的值和像两个不同的概念。注意区别函数的值和像两个不同的概念。 函数值函数值f( (x)B)B，而函数的像而函数的像f(A(A1 1) ) B B。编辑ppt讨论讨论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

8、1)。一般来说，一般来说， f-1-1( (f( (A A1 1)A A1 1，但是但是A A1 1 f-1-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)的真子集。的真子集。编辑ppt例例8.38.3 设设f:NN:NN，且且 令令A A0,10,1，B B22，求求f(A)(A)

9、和和 f 1 1(B)(B)。 /2( )1xxf xxx若 为偶数若 为奇数解答解答 f(A)f(0, 1)f(0), f(1)0, 2 f 1(B) f 1(2)1, 4(因为因为 f(1)2, f(4)2)编辑ppt 设设f: :AB，（1 1）若若ran fB，则称则称f: :AB是是满射满射( (surjection) )的的。（2 2）若若 yran f 都存在都存在唯一的唯一的xA使得使得f(x)y，则称则称 f: :AB是是单射单射( (injection) )的的。（3 3）若若f 既是满射又是单射的既是满射又是单射的，则称则称f: :AB是是双射双射( (bijection

10、) )的的( (一一映像一一映像( (one-to-one mapping) ) ) 。 满射、入射、双射满射、入射、双射q 如果如果f:A:AB B是满射的，则对于任意的是满射的，则对于任意的yB B，都存在都存在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。编辑ppt不同类型的对应关系的示例不

11、同类型的对应关系的示例abc1234abc1234abc1234dabc1234dabc123d单射单射不是函数不是函数双射双射函数函数满射满射编辑ppt 判断下面函数是否为单射、满射、双射的，为什么判断下面函数是否为单射、满射、双射的，为什么? ? (1) 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+为正实数集。为正实数集。（1）f 在在x=1取得极大值取得极大值0。既不是单射也不是满射的既不是单射也不是

12、满射的。（2）f 是单调上升的，是单射的，但不满射是单调上升的，是单射的，但不满射。ran f=ln1, ln2, 。（3）f 是满射的，是满射的， 但不是单射的，例如但不是单射的，例如f(1.5)=f(1.2)=1。（4）f 是满射、单射、双射的，因为它是单调函数并且是满射、单射、双射的，因为它是单调函数并且ran f=R。（5）f 有极小值有极小值f(1)=2。 该函数既不是单射的，也不是满射的该函数既不是单射的，也不是满射的。分析分析实数集合上函数性质的判断方法实数集合上函数性质的判断方法编辑ppt 对于以下各题给定的对于以下各题给定的A, ,B和和 f，判断是否构成函数判断是否构成函数

13、f: :AB。如如果是，说明果是，说明 f:AB:AB是否为单射、满射和双射的，并根据要求是否为单射、满射和双射的，并根据要求进行计算。进行计算。(1)(1)A1,2,3,4,51,2,3,4,5，B6,7,8,9,106,7,8,9,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 。编辑ppt(3)

14、(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: :AB， 且且 f 是双射的是双射的 。(5)(5)ABR R+ +，f(x)x/(xx/(x2 2+1)+1)（ xRxR+ + ）能构成能构成f: :AB， 但但 f 既不是单射的也不是满射的。既不是单射的也不是满射的。因为该函数在因为该函数在 x1 取得极大值取得极大值 f(1)1/2，函数不是单调函数不是单调的，且的，且ran f RR+ +。编辑p

15、pt(6)(6)ABRR R，f () 令令L|x, ,yRRyx+1+1，计算计算 f( (L) )。能构成能构成 f: :AB，且且 f 是双射的是双射的。f( (L) )|+1)|xRR|+1,-1|xRRR R-1-1(7)(7)ANN，BN，f()|x|x2 2-y-y2 2| |计算计算f(N(N0),0),f-1-1(0)(0)。能构成能构成f: :AB， 但但 f 既不是单射也不是满射的。既不是单射也不是满射的。因为因为f()()f()()0 0，且且2 2 ran ran f。 f(N(N0)0) n2 2-0-02 2| |nNN n2 2| |nNNf-1-1(0)(0)

16、|nNN编辑ppt 对于给定的集合对于给定的集合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（4 4）A A /2,3/2,3 /2/2, B, B 1,11,1编辑ppt（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 ,。令令

17、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编辑ppt（2） A0,10,1, B1/4,1/21/4,1/2 令令f: AB, f(x)(x+1)/4。（3） AZ, BN 将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N N中元素对应：中元素对应：Z：0 1 1 22 33 N：0 12 3 4 5 6 则这种对应所表示的函数是：则这种对应所表示的函数是：20Z,( )210 xxfN f xxx：（4） A= /2,3 /2, B= 1,1 令令f: AB ，f(

18、x)sin x。 编辑ppt常用函数常用函数常函数和恒等函数常函数和恒等函数q 设设f：AB，如果存在如果存在cB，使得对所有的使得对所有的xA都有都有f(x)c，则称则称f：AB是是常函数常函数。q 设设f：AB，对所有的对所有的xA都有都有IA(x)x，称称IA为为A上的上的恒恒等函数等函数。编辑ppt常用函数常用函数单调递增函数单调递增函数q 设设， 为偏序集，为偏序集，f：AB，如果对任意的如果对任意的x1, x2A， x1x2，就有就有f(x1) f(x2)，则称则称f为为单调递增单调递增的；的；如果对任意的如果对任意的x1, x2A, x1x2, 就有就有f(x1) f(x2),

19、则称则称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是单调递增的是单调递增的, 但不是严格单调递增的。但不是严格单调递增的。编辑ppt常用函数常用函数特征函数特征函数q 设设A为集合，对于任意的为集合，对于任意的AA，A 的的特征函数特征函数 A : A

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

21、IA g(1)g(2)1,2, g(3)3 不同的等价关系确定不同的自然映射，其中恒等关系所确定不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射，的自然映射是双射， 而其他的自然映射一般来说只是满射。而其他的自然映射一般来说只是满射。编辑ppt定义在自然数集合上的计数函数定义在自然数集合上的计数函数q 对于给定规模为对于给定规模为n的输入，计算算法所做基本运算的次数，的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。将这个次数表示为输入规模的函数。排序和检索问题的基本运算是比较。排序和检索问题的基本运算是比较。矩阵乘法的基本运算是元素的相乘。矩阵乘法的基本

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

23、阶。阶可以是：。阶可以是：n，n2 2，n3 3，nlog log n，log log n，2 2n 编辑ppt定义在自然数集合上的计数函数定义在自然数集合上的计数函数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

24、( (n)。q 例如例如 f( (n) )1/2 1/2 n2 2-3-3n，则则 f( (n) )( (n2 2) ) g( (n) )6 6n3 3，则则 g( (n) )( (n3 3) )编辑ppt构造从构造从A A到到B B的双射函数的双射函数有穷集之间的构造有穷集之间的构造例例1 A=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,

25、 f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f7编辑ppt实数区间之间构造双射实数区间之间构造双射构造方法：直线方程构造方法：直线方程例例2 A=0,1 B=1/4,1/2构造双射构造双射 f : AB构造从构造从A A到到B B的双射函数的双射函数( (续续) )解解 令令 f : 0,11/4,1/2 f(x)=(x+1)/4 编辑pptA与自然数集合之间构造双射与自然数集合之间构造双射方法：将方法：将A中元素排成有序图形，然后从第一个元素开始中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应按照次序与自然数对应构造从

26、构造从A A到到B B的双射函数的双射函数( (续续) ) 01202)(,NZ:xxxxxff例例3 A=Z, B=N，构造双射，构造双射 f : AB将将Z中元素以下列顺序排列并与中元素以下列顺序排列并与N中元素对应：中元素对应：Z：0 11 22 33 N：0 1 2 3 4 5 6 则这种对应所表示的函数是：则这种对应所表示的函数是：编辑ppt8.2 8.2 函数的复合与反函数函数的复合与反函数q 函数的复合就是关系的右复合函数的复合就是关系的右复合，一切和关系右复合有关，一切和关系右复合有关的定理都适用于函数的复合。的定理都适用于函数的复合。本节重点考虑在复合中特本节重点考虑在复合中

27、特有的性质。有的性质。编辑ppt定理定理8.1(8.1(复合函数基本定理复合函数基本定理) ) 设设F, G是函数，则是函数，则F G 也是函数，且满足也是函数，且满足（1）dom (F G)x|xdom FF(x)dom G（2） xdom (F G)，有有F G(x)G(F(x)编辑ppt证明证明：先证明先证明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为函数）为函数）y1y

28、2 （G为函数）为函数） 所以所以F G为函数。为函数。编辑ppt任取任取x，(要证明要证明dom (F G)x|xdom FF(x)dom G) xdom (F G) t y(F G) t(xdom F tF(x) tdom G) xx|xdom F F(x)dom G所以（所以（1）得证。）得证。任取任取x， （要证明要证明 xdom (F G)，有有F G(x)G(F(x)） xdom F F(x)dom G F G F G xdom(F G) F G(x)G(F(x) 所以（所以（2）得证。）得证。编辑ppt推论推论1 设设F, G, H为函数，则为函数，则(F G) H和和F (G

29、H)都是函数，都是函数， 且且(F G) H=F (G H)证明证明：由定理：由定理8.18.1（复合函数基本定理）和定理（复合函数基本定理）和定理7.27.2（关系合成（关系合成具有结合性）得证。具有结合性）得证。编辑ppt推论推论2 2 设设f：AB，g：BC，则则f g：AC，且且 xA都有都有f g(x)=g(f(x)。证明证明：由定理：由定理8.1（复合函数基本定理）可知（复合函数基本定理）可知f g是函数，且是函数，且 dom (f g) x|xdom f f(x)dom g x|xA f(x)B A ran (f g) ran g C 因此因此 f g：AC，且且 xA有有 f

30、g(x)g(f(x)。编辑ppt 设设 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也也 是双射的。是双射的。函数的复合运算的性质函数的复合运算的性质该定理说明函数的复合能够保持函数单射、满射、双射的该定理说明函数的复合能够保持函数单射、满射、双射的性质。性质。编辑ppt(1)(1)如果如果f：AB，g：BC都是满射的，则都是满射的，

31、则f g：AC也也 是满射的。是满射的。证明：证明：任取任取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是满射的。是满射的。 编辑ppt(2)如果如果f：AB，g：BC都是单射的，则都是单射的，则f g：AC也是也是 单射的。单射的。证明证明：假设存在：假设存在x1, x2A使得使得 f g(x1)f g(x2)，由合成定理有由合成定理有 g(f(x1)=g(f(x2) 因为因为g：BC是

32、单射的，故是单射的，故f(x1)f(x2)。又由于又由于f：AB也是单射的，所以也是单射的，所以x1x2。所以，所以，fog：AC是单射的。是单射的。(3)如果如果f：AB， g：BC都是双射的，则都是双射的，则f g：AC也也 是双射的。是双射的。证明：由（证明：由（1）和（）和（2）得证。）得证。编辑pptq 考虑集合考虑集合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=

33、c1,c2。令令f, g ,则则f g,那么那么g: BC和和f g: AC是满射的，但是满射的，但f : AB不是满射的。不是满射的。 编辑ppt 设设 f：AB，则则 f f o IB IAof 证明证明 f o IB ：AB 和和 IAof ：AB任取任取， f f y B f IB f o IB所以，所以， f f o IB f o IB t( f IB ) f t=y f 所以，所以， f o IB f所以所以， f f o IB同理可证同理可证f IAof 编辑ppt什么样的函数什么样的函数 f：AB，它的逆它的逆f 1是从是从B到到A的函数呢？的函数呢？q 任给函数任给函数F,

34、它的逆它的逆F 1不一定是函数不一定是函数, 只是一个二元关系。只是一个二元关系。F ， F -1 ， q 任给单射函数任给单射函数f：AB, 则则f 1是函数是函数, 且是从且是从ran f到到A的双射的双射函数函数, 但不一定是从但不一定是从B到到A的双射函数。的双射函数。因为对于某些因为对于某些yBran f，f -1没有值与之对应。没有值与之对应。q 任给满射函数任给满射函数f：AB，则则f 1不一定是函数。不一定是函数。q 对于双射函数对于双射函数f：AB, f 1：BA是从是从B到到A的双射函数。的双射函数。 反函数反函数编辑ppt 设设f：AB是双射的，则是双射的，则f 1：BA

35、也是双射的。也是双射的。证明证明： 先证明先证明f- 1：BA是函数，且是函数，且dom f 1B，ran f 1A。 因为因为 f 是函数，所以是函数，所以 f 1 是关系，且是关系，且 dom f 1 ran f B , ran f 1dom f A， 对于任意的对于任意的xB dom f 1， 假设有假设有y1, y2A，使得使得f 1f 1成立，成立， 则由逆的定义有则由逆的定义有，ff。 根据根据 f 的单射性，可得的单射性，可得y1y2。 所以，所以，f- 1是函数。是函数。反函数存在的条件反函数存在的条件编辑ppt再证明再证明f- 1：BA的双射性质。的双射性质。 q （证明单射

36、（证明单射）若存在若存在x1, x2B，使得使得f 1 (x1)= f 1 (x2)=y， 从而有从而有f 1f 1 ff x1x2 （因为因为 f 是函数）是函数） 所以，所以， f- 1 是单射的。是单射的。q （证明满射（证明满射）对于任意的对于任意的 yA ，因为因为f 是双射的，是双射的， 所以必存在所以必存在 xB ，使得使得f，所以所以f 1， 所以，所以， f 1 是满射的。是满射的。 综上所述，综上所述， f 1 是双射函数。是双射函数。对于双射函数对于双射函数f：AB，称称f- 1：BA是它的反函数。是它的反函数。编辑ppt反函数的性质反函数的性质 设设f：AB是双射的，是

37、双射的， 则则f- 1 f = IB， f f- 1 = IA证明证明：根据定理可知：根据定理可知f- 1：BA也是双射的，也是双射的， 且且 f- 1 f：BB， f f- 1：AA。 任取任取 f 1 f t( f 1 f ) t( f f ) x=y x, y B IB所以，所以， f- 1 f IB IB xy x, y B t( f f ) t( f 1 f ) f- 1 f 所以，所以，IB f- 1 f 综上所述，综上所述， f- 1 f IB。同理可证同理可证 f f- 1 IA编辑ppt 设设 f：RR, g：RR 求求f g，g f。如果如果 f 和和 g 存在反函数，求出

38、它们的反函数。存在反函数，求出它们的反函数。解答解答23( )23( )2xxf xxg xx22:23( )03:(2)1( )21fg RRxxfg xxgfRRxxgf xxg：RR是双射的，它的是双射的，它的反函数是反函数是g 1：RR，g 1(x)=x 2 编辑ppt定义定义 设设A, BA, B是集合，如果存在着从是集合，如果存在着从A A到到B B的的双射函数双射函数，就称，就称A A和和B B是等势是等势（same cardinality）的的，记作，记作ABAB。 如果如果A A不与不与B B等势，则记作等势，则记作A BA B。双射函数与集合的基数集合的基数q通俗的说，集合

39、的势是量度集合所含元素多少的量。通俗的说，集合的势是量度集合所含元素多少的量。q集合的势越大，所含的元素越多。集合的势越大，所含的元素越多。编辑ppt（1）ZN。20:,( )210 xxfZNf xxx则则f是是Z到到N的双射函数。的双射函数。 从而证明了从而证明了ZN。等势集合的实例等势集合的实例(1)(1)编辑ppt等势集合的实例等势集合的实例(2)(2)（2） NNN。(1)():,(,)2mnmnfNNNfm nm 双射函数双射函数 编辑ppt等势集合的实例等势集合的实例(3)(3)（3 3）NQNQ。 把所有形式为把所有形式为p p/ /q q ( (p p, ,q q为整数且为整

40、数且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/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414以以0/10/1作为第一个数，按照箭头规定的顺序可

41、以作为第一个数，按照箭头规定的顺序可以“数遍数遍”表中表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。同一个有理数。编辑ppt等势集合的实例等势集合的实例(4)(4)（4）(0,1)R。 其中实数区间其中实数区间 (0,1)=x| xR0 x1。21:(0,1),( )tan2xfRf x令双射函数令双射函数则则 f 是是(0,1)到到R的双射函数。从而证明了的双射函数。从而证明了(0,1)R 。编辑ppt等势集合的实例等势集合的实例(5)(5)（5 5）0,1(0,1)。 其中其中(0,1)和和0,1分别为实数开区

42、间和闭区间。分别为实数开区间和闭区间。211/201/21( )1/21/2 ,1,2,.nnxxf xxnxx其它双射函数双射函数 f : 0,1(0,1)，n n3 32 22 21 12 21 12 21 12 21 110 02 22 21 12 21 12 2n n5 54 43 32 21 12 21 12 21 12 21 1 2 2编辑ppt等势集合的实例等势集合的实例(6)(6)（6 6）对任何）对任何a, bR，ab， 0,1a,b。 双射函数双射函数f：0,1a,b，f(x)(b a)x+a。编辑ppt例例 设设A为任意集合，则为任意集合，则P(A)0,1A。构造构造f：

43、P(A)0,1A， f(A )= A ， A P(A)。其中其中 A 是集合是集合A 的特征函数。的特征函数。(1)(1)易证易证 f 是单射的。是单射的。(2)(2)对于任意的对于任意的 g0,1A， 那么有那么有 g：A0,1。令令 B=x| xAg(x)=1 则则B A，且且 B=g，即即 BP(A)，使得使得f(B)=g。 所以所以 f 是满射的。是满射的。由等势定义得由等势定义得P(A)0,1A。例例证明证明复习复习编辑ppt定理定理 设设A，B，C是任意集合，是任意集合，（1）AA。（2）若若AB，则则BA。（3）若若AB，BC，则则AC。（1 1） IA是从是从A到到A的双射，因

44、此的双射，因此AA。（2） 假设假设AB ，存在，存在 f : : AB是双射，是双射，那么那么 f 1 : : BA是从是从B到到A的双射，所以的双射，所以BA。（3） 假设假设AB，BC，存在存在 f : :AB，g: :BC是双射，是双射，则则f g : : AC是从是从 A 到到 C 的双射。的双射。所以所以AC。等势的性质等势的性质证明证明编辑pptq N Z Q NNq R 0,1 (0,1)q 任何的实数区间（开区间、闭区间以及半开半闭的区间）任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合都与实数集合R R等势。等势。q 问题：问题：N N和和R R是否等势？是否

45、等势？若干等势集合若干等势集合编辑ppt（1）如果能证明）如果能证明N 0,1，就可以断定就可以断定N R。 只需证明任何函数只需证明任何函数f：N0,1都不是满射的。都不是满射的。 构造一个构造一个0,1区间的小数区间的小数b，使得使得b在在N中不存在原像。中不存在原像。（2）任取函数）任取函数f：AP(A)，构造构造BP(A)，使得使得B在在A中不存在中不存在原像。原像。或者使用反证法。或者使用反证法。定理定理 康托定理康托定理（1）N R。（2）对任意集合对任意集合A都有都有A P(A)。康托定理康托定理分析分析编辑ppt（1 1）首先规定）首先规定0,1中数的表示。中数的表示。 对任意

46、的对任意的x0,1，令令x = 0. .x1x2 , （0 xi 9） 注意：为了保证表示式的唯一性，如果遇到注意：为了保证表示式的唯一性，如果遇到0.249990.24999，则将，则将x x表表示为示为0.250000.25000。 设设 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与上面列出的任何一个函数值都不相等与

47、上面列出的任何一个函数值都不相等。即即f不是满射的。不是满射的。 所以所以，N R。康托定理康托定理编辑ppt康托定理康托定理q 假设假设A AP(A)，则必有函数则必有函数 f : AP(A)是双射函数。是双射函数。如下构造集合如下构造集合B：Bx| xAx f (x) 可知可知 BP(A)。于是存在唯一一个元素于是存在唯一一个元素bA，使得使得 f(b)B。若若bB，则由则由B的定义知，的定义知，b f (b)，即即 b B，矛盾矛盾。若若b B，则则b f (b)，于是由于是由B的定义知，的定义知， bB，矛盾。矛盾。编辑ppt（2 2）设）设g：AP(A)是从是从A到到P(A)的任意函

48、数，的任意函数， 如下构造集合如下构造集合B：Bx| xAx g(x) 则则BP(A)。 但是但是对任意对任意xA，都有都有xB x g(x) 所以，对任意的所以，对任意的xA都有都有Bg(x)，即即B ran ran g 即即P(A) 中存在元素中存在元素B，在在A中找不到原像。中找不到原像。 所以所以，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“更大更大”的集合。的集合

49、。 编辑ppt定义定义（1 1） 设设A, B是集合，如果存在从是集合，如果存在从A到到B的的单射单射函数，就称函数，就称B优优势于势于A，记作记作AB。 如果如果B不是优势于不是优势于A， 则记作则记作AB。（2 2）设设A, B是集合，若是集合，若AB且且A B，则称则称B真优势于真优势于A，记作记作AB。如果如果B不是真优势于不是真优势于A，则记作则记作AB。 例如：例如：N NN RA P(A)N RA P(A) R N N N优势优势RN编辑ppt定理定理 设设A, B, C是任意的集合，则是任意的集合，则（1）A A。（2）若若A B且且B A，则则AB。（3）若若A B且且B C

50、, 则则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 。优势的性质优势的性质q 该定理为证明集合之间的等势提供了有力的工具该定理为证明集合之间的等势提供了有力的工具。q 构造两个单射构造两个单射f：A AB B 和和 g g：B BA A函数容易集合等势函数容易集合等势。编辑ppt例题例题例题：例题：证明证明0,10,1与与(0,1)(0,1)等势。等势。证明：证明：构造两个

51、单射函数构造两个单射函数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编辑ppt证明证明 0,1N0,1)(1) 设设x 0,1)，0.x1x2是是x的的二进制表示二进制表示。 为了使表示唯一，规定表示式中不允许出现连续无数个为了使表示唯一，规定表示式中不允许出现连续无数个1。 例如例如 x111，1000。 对于对于x，如下定义如下定义f：0,1)0,1N，使得使得 f(x) = tx，且且tx：N0,1， tx(n) = xn+1，n = 0,1,2, 例如例如 x = 0.1011010

52、0，则对应于则对应于x的函数的函数tx是：是： n 0 1 2 3 4 5 6 7tx(n) 1 0 1 1 0 1 0 0 易见易见tx0,1N，且对于且对于x,y0,1)，xy，必有必有tx ty， 即即f(x) f(y)。 所以，所以，f：0,1)0,1N是单射的。是单射的。 编辑ppt(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

53、(t1111，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)编辑ppt总结总结q N Z Q NNq R a,b (c,d) 0,1N P(N)其中其中a,b，(c,d)代表任意的实数闭区间和开区间代表任意的实数闭区间和开区间。q 0,1A P(A)q N Rq A P(A)编辑ppt8.3.2 8.3.2 集合的基数集合

54、的基数 q 上一节我们只是抽象地讨论了集合的等势与优势。上一节我们只是抽象地讨论了集合的等势与优势。q 本节将进一步研究度量集合的势的方法。本节将进一步研究度量集合的势的方法。q 最简单的集合是有穷集。尽管前面已经多次用到最简单的集合是有穷集。尽管前面已经多次用到“有穷集有穷集”这一概念，当时只是直观地理解成含有有限多个元素的这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。问题我们需要先定义自然数和自然数集合。 编辑ppt8.10 8.10 设设a为为集合，

55、称集合，称aa 为为a的的后继后继，记作，记作a+，即即 a+=aa。 例例 考虑空集的一系列后继。考虑空集的一系列后继。 + = = + = += = ,= , + + =,+= ,= ,= , +, + 后继后继 q 前边的集合都是后边集合的元素。前边的集合都是后边集合的元素。q 前边的集合都是后边集合的子集。前边的集合都是后边集合的子集。编辑ppt利用后继的性质，可以考虑以构造性的方法用集合来给出自利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，然数的定义，即即 0=1=0+ 02=1+ ,0,132+,+, 0,1,2 n0, 1, , n 1自然数的定义自然数的定义

56、这种定义没有概括出自然数的共同特征。这种定义没有概括出自然数的共同特征。编辑ppt（1） 对任何自然数对任何自然数n，有有n n。（2） 对任何自然数对任何自然数n, m，若若m n，则则m n。（3） 对任何自然数对任何自然数n, m，若若mn，则则m n。（4） 对任何自然数对任何自然数n和和m，以下三个式子：以下三个式子： mn，m n， nm必成立其一且仅成立其一。必成立其一且仅成立其一。（5） 自然数的相等与大小顺序自然数的相等与大小顺序 对任何自然数对任何自然数m和和n，有有m = n m n m n mn 自然数的性质自然数的性质 编辑ppt定义定义 有穷集、无穷集有穷集、无穷集

57、（1 1）一个集合是）一个集合是有穷的有穷的当且仅当它与某个自然数等势；当且仅当它与某个自然数等势；（2 2）如果一个集合不是有穷的，就称作）如果一个集合不是有穷的，就称作无穷集无穷集。例如：例如：q a,b,c是有穷集，是有穷集， 因为因为30,1,2，且，且a,b,c0,1,23qN和和R都是无穷集，都是无穷集， 因为没有自然数与因为没有自然数与N和和R等势。等势。q任何有穷集只与唯一的自然数等势。任何有穷集只与唯一的自然数等势。有穷集和无穷集有穷集和无穷集 编辑ppt定义定义8.12 8.12 （1 1）对于有穷集合）对于有穷集合A，称与称与A等势的那个唯一的自然数为等势的那个唯一的自然

58、数为A的基的基数数，记作记作card A，即即 card A n A n （对于有穷集对于有穷集A， card A也可以记作也可以记作|A|）（2 2）自然数集合自然数集合N的基数记作的基数记作0，即，即card N =0（3 3）实数集实数集R的基数记作的基数记作（读作阿列夫），即（读作阿列夫），即card R =基数基数( (cardinality) ) 编辑ppt定义定义8.13 8.13 设设A, B为集合，则为集合，则（1）card Acard B AB（2）card Acard B A B（3）card A card B card Acard Bcard Acard B例如：例如：

59、q card Z card Q card NN 0q card P(N) card 2N card a,b card (c,d) q 0说明说明：集合的基数就是集合的势，基数越大，势就越大。：集合的基数就是集合的势，基数越大，势就越大。基数的相等和大小基数的相等和大小 编辑ppt关于基数的说明关于基数的说明 q 由于对任何集合由于对任何集合A都满足都满足A P(A)，所以有所以有 card A card P(A)，这说明这说明不存在最大的基数不存在最大的基数。q 将已知的基数按从小到大的顺序排列就得到：将已知的基数按从小到大的顺序排列就得到： 0, 1, 2, , n, , 0, , q 0,

60、 1, 2, n, 是全体自然数，是是全体自然数，是有穷基数有穷基数。q 0, , 是是无穷基数无穷基数。q 0是最小的无穷基数是最小的无穷基数，后面还有更大的基数，如后面还有更大的基数，如 card P(R)等。等。编辑ppt可数集可数集定义定义 设设A为集合，若为集合，若card A0，则称则称A为为可数集可数集(enumerable)或或可列集。可列集。例如：例如： q a,b,c、5、整数集整数集Z、有理数集有理数集Q、NN等都是可数集。等都是可数集。q 实数集实数集R不是可数集，与不是可数集，与R等势的集合也不是可数集。等势的集合也不是可数集。 对于任何的可数集，都可以找到一个对于任