离散数学课件08函数

1、第8章 函数,离 散 数 学,本章说明,本章的主要内容 函数的定义 函数的性质 函数的逆 函数的合成 本章与后续各章的关系 是代数系统的基础,8.1 函数的定义与性质 8.2 函数的复合与反函数 8.3 一个电话系统的描述实例 本章小结 习题 作业,本章内容,8.1 函数的定义与性质,定义8.1 设F为二元关系，若xdom F，都存在唯一的yran F 使xFy成立，则称F为函数(function)(或称作映射(mapping)。 对于函数F，如果有 xFy，则记作yF(x)，并称y为F在x的值。,举例 判断下列关系是否为函数 F1,F2,是函数 不是函数,说明,函数是特殊的二元关系。 函数的

2、定义域为dom F，而不是它的真子集。 一个x只能对应唯一的y。,定义8.2 设 F,G 为函数，则 FG FGGF,由定义可知，两个函数F和G相等, 一定满足下面两个条件： （1）dom Fdom G （2）xdom Fdom G，都有 F(x)G(x),例如 函数F(x)(x21)/(x+1)，G(x)x1不相等, 因为 dom Fx|xRx -1 dom GR 显然， dom Fdom G，所以两个函数不相等。,函数相等,定义8.3 设A,B为集合，如果 f 为函数，dom fA，ran fB，则称 f 为从A到B的函数，记作 f：AB。 例如： f：NN，f(x)2x是从N到N的函数，

3、 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。,解答 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,例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)|

4、xA1，称 f(A1)为A1在f 下的像(image)。 特别地，当A1A时，称 f(A)为函数的像。 （2）令f 1(B1)x|xAf(x)B1，称f 1(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，但是A1 f-1(f(A1)。 例如函数 f:1,2,30,1，满足 f(1)f(2)

5、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, 2 f 1(B) f 1(2)1, 4(因为 f(1)2, f(4)2),例8.3,定义8.6 设f:AB， （1）若ran fB，则称f:AB是满射(surjection)的。 （2）若yran f 都存在唯一的xA使得f(x)y，则称 f:AB是单射(injection)的。 （3）若f 既是满射又是单射的，则称f:AB是双射(bije

6、ction)的(一一映像(one-to-one mapping) 。,说明,满射、入射、双射,如果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)=ln x，Z+为正整数集(3) f：RZ，f(x)=x (4) f：RR，f(x)=

7、2x+1(5) f：R+R+，f(x)=(x2+1)/x，其中R+为正实数集。,例8.4,（1）f 在x=1取得极大值0。既不是单射也不是满射的。 （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。 该函数既不是单射的，也不是满射的。,分析,实数集合上函数性质的判断方法,例8.5,例8.5 对于以下各题给定的A,B和 f，判断是否构成函数f:AB。如果是，说明 f:AB是否为单射、满射和双射

8、的，并根据要求进行计算。 (1)A1,2,3,4,5，B6,7,8,9,10， f, 能构成f:AB， f 不是单射的，因为f(3)f(5)9, f 不是满射的，因为7ran f。 (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，因为dom f1,2,3,4A。 (4)ABR，f(x)x 能构成f:AB， 且 f 是双射的 。 (5)ABR+，f(x)x/(x2+1)（xR+ ） 能构成f:AB， 但 f 既不是单射的也不是满射的。 因为该函数在 x1 取得极

9、大值 f(1)1/2，函数不是单调的，且ran f R+。,例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，且2ran f。 f(N0)n2-02|nNn2|nN f-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）

10、A/2,3/2, B1,1,例8.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.6的解答,（2） A0,1, B1/4,1/2 令f: AB, f(x)(x+1)/4。 （3） AZ, BN 将Z中元素以下列顺序排列并与N中元素对应：Z：01 1 22

11、33 N：0 12 3 4 5 6 则这种对应所表示的函数是：,（4） A=/2,3/2, B=1,1 令f: AB ，f(x)sin x。,常用函数常函数和恒等函数,设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为严格单调递增的。 类似的也可以定义单调递减和严格单调递减的函数。

12、 举例：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/R g(a)=a，aA 称g是从A到商集A/R的自然映射。,给定集合A和A上的等价关系R，就可以确定一个自然映

13、射g：AA/R。 例如A1,2,3，R,IA g(1)g(2)1,2, g(3)3 不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射， 而其他的自然映射一般来说只是满射。,定义在自然数集合上的计数函数,对于给定规模为n的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。 排序和检索问题的基本运算是比较。 矩阵乘法的基本运算是元素的相乘。 估计算法在最坏情况下所做基本运算的次数记为W(n)。 估计算法在平均情况下所做基本运算的次数记为A(n)。 设f是定义在自然数集合上的函数，当n变得很大时，函数值f(n)的增长取决于函数的阶。阶越高的函数，算法的复杂度就越高

14、，同时意味着算法的效率越低。 算法分析的主要工作就是估计复杂度函数的阶。阶可以是： n，n2，n3，nlog n，log n，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/2 n2-3n，则 f(n)(n2) g(n)6n3，则 g(n)(n3),构造从A到B的双射函数,有穷集之间的构造 例1 A=P(1,2,3), B=0,11,2,

15、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,实数区间之间构造双射 构造方法：直线方程 例2 A=0,1 B=1/4,1/2构造双射 f : AB,构造从A到B的双射函数(续),解 令 f : 0,11/4,1/2 f(x)=(x+1)/4,A与自然数集合之间构造双射 方法：将

16、A中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应,构造从A到B的双射函数(续),例3 A=Z, B=N，构造双射 f : AB,将Z中元素以下列顺序排列并与N中元素对应：Z：011 2233 N：0 1 2 3 4 5 6 则这种对应所表示的函数是：,8.2 函数的复合与反函数,函数的复合就是关系的右复合，一切和关系右复合有关的定理都适用于函数的复合。本节重点考虑在复合中特有的性质。,定理8.1(复合函数基本定理),定理8.1 设F, G是函数，则FG 也是函数，且满足 （1）dom (FG)x|xdom FF(x)dom G （2）xdom (FG)，有FG(x)G(F(x)

17、,证明： 先证明FG是函数。 因为F、G是关系，所以FG也是关系。 若对某个xdom (FG)，若有xFGy1和 xFGy2， 则 FG FG t1(FG)t2(FG) t1t2(t1t2GG) （F为函数） y1y2 （G为函数） 所以FG为函数。,定理8.1的证明,定理8.1的证明,任取x，(要证明dom (FG)x|xdom FF(x)dom G) xdom (FG) ty(F G) t(xdom F tF(x) tdom G) xx|xdom F F(x)dom G 所以（1）得证。 任取x， （要证明xdom (FG)，有FG(x)G(F(x)） xdom F F(x)dom G F

18、 G FG xdom(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|xdom f f(x)dom g x|xA f(x)B A ran (fg) ran g C 因此 fg：AC，且xA有 fg(x)g(f(x)。,定理8.1的推论2,定

19、理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

20、)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: A

21、C都是单射的，但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，则 f f o IB IAof 证明：由定理8.1的推论2可知 f o IB ：AB 和 IAof ：AB 任取，,f f yB 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,什么样的函数 f：AB，它的逆f 1是从B到A的函数呢

22、？ 任给函数F, 它的逆F 1不一定是函数, 只是一个二元关系。 F， F -1， 任给单射函数f：AB, 则f 1是函数, 且是从ran f到A的双射函数, 但不一定是从B到A的双射函数。 因为对于某些yBran f，f -1没有值与之对应。 任给满射函数f：AB，则f 1不一定是函数。 对于双射函数f：AB, f 1：BA是从B到A的双射函数。,反函数,定理8.4 设f：AB是双射的，则f 1：BA也是双射的。 证明： 先证明f- 1：BA是函数，且dom f 1B，ran f 1A。 因为 f 是函数，所以 f 1 是关系，且 dom f 1 ran f B , ran f 1dom f

23、 A， 对于任意的xB dom f 1， 假设有y1, y2A，使得f 1f 1成立， 则由逆的定义有，ff。 根据 f 的单射性，可得y1y2。 所以，f- 1是函数。,反函数存在的条件,再证明f- 1：BA的双射性质。 （证明单射）若存在x1, x2B，使得f 1 (x1)= f 1 (x2)=y， 从而有f 1f 1 ff x1x2 （因为 f 是函数） 所以， f- 1 是单射的。 （证明满射）对于任意的 yA ，因为f 是双射的， 所以必存在 xB ，使得f，所以f 1， 所以， f 1 是满射的。 综上所述， f 1 是双射函数。,说明,定理8.4的证明,对于双射函数f：AB，称f

24、- 1：BA是它的反函数。,反函数的性质,定理8.5 设f：AB是双射的， 则f- 1f = IB， f f-1 = IA 证明：根据定理可知f- 1：BA也是双射的， 且 f- 1f：BB， f f- 1：AA。 任取, f 1f t( f 1 f ) t( f f ) x=y x, y B IB 所以， f- 1f IB, IB xy x, y B t( f f ) t( f 1 f ) f- 1f 所以，IB f- 1f,综上所述， f- 1f IB。同理可证 f f-1 IA,例8.8,例8.8 设 f：RR, g：RR 求fg，gf。如果 f 和 g 存在反函数，求出它们的反函数。

25、解答,g：RR是双射的，它的反函数是g1：RR，g1(x)=x2,定义8.8 设A, B是集合，如果存在着从A到B的双射函数，就称A和B是等势（same cardinality）的，记作AB。 如果A不与B等势，则记作A B。,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

26、,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 。,等

27、势集合的实例(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

28、(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。,等势的性质,证明,N Z Q NN R 0,1 (0,1) 任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合R等势。 问题：N和R是否等势？,若干等势集合,（1）如果能证明N 0,1，就可

29、以断定N R。 只需证明任何函数f：N0,1都不是满射的。 构造一个0,1区间的小数b，使得b在N中不存在原像。 （2）任取函数f：AP(A)，构造BP(A)，使得B在A中不存在原像。 或者使用反证法。,定理8.7 康托定理 （1）N R。 （2）对任意集合A都有A P(A)。,康托定理,分析,（1）首先规定0,1中数的表示。 对任意的x0,1，令x = 0.x1x2 , （0 xi 9） 注意：为了保证表示式的唯一性，如果遇到0.24999，则将x表示为0.25000。 设 f:N0,1是从N到0,1的任何一个函数。f的所有函数值为： f(0)=0.a1(1)a2(1) f(1)=0.a1(

30、2)a2(2) f(n1)=0.a1(n)a2(n) 令y的表示式为0.b1b2，并且满足bi ai(i)，i=1,2,， 则y0,1， 但y与上面列出的任何一个函数值都不相等。 即f不是满射的。 所以，N R。,康托定理,康托定理,假设AP(A)，则必有函数 f : AP(A)是双射函数。 如下构造集合B： Bx| xAx f (x) 可知 BP(A)。 于是存在唯一一个元素bA，使得 f(b)B。 若bB，则由B的定义知，b f (b)，即 bB，矛盾。 若bB，则b f (b)，于是由B的定义知， bB，矛盾。,（2）设g：AP(A)是从A到P(A)的任意函数， 如下构造集合B： Bx|

31、 xAxg(x) 则BP(A)。 但是对任意xA，都有xB xg(x) 所以，对任意的xA都有Bg(x)，即Bran g 即P(A) 中存在元素B，在A中找不到原像。 所以，g不是满射的。 所以， A P(A)。,说明,康托定理,定义8.9 （1） 设A, B是集合，如果存在从A到B的单射函数，就称B优势于A，记作AB。 如果B不是优势于A， 则记作AB。 （2）设A, B是集合，若AB且A B，则称B真优势于A，记作AB。如果B不是真优势于A，则记作AB。 例如：,N N N R A P(A),N R A P(A),R N N N,优势,定理8.8 设A, B, C是任意的集合，则 （1）A

32、 A。 （2）若A B且B A，则AB。 （3）若A B且B C, 则A C 。 证明： （1）IA是A到A的单射，因此A A。 （2）证明略。 （3）假设A B且B C，那么存在单射 f:AB，g:BC， 于是 fg：AC也是单射的，因此A C 。,优势的性质,说明,该定理为证明集合之间的等势提供了有力的工具。 构造两个单射f：AB 和 g：BA函数容易集合等势。,例题,例题：证明0,1与(0,1)等势。 证明：构造两个单射函数 f: (0,1)0,1，f(x)x g: 0,1(0,1)，g(x)x/2+1/4,证明 0,1N0,1),(1) 设x0,1)，0.x1x2是x的二进制表示。 为

33、了使表示唯一，规定表示式中不允许出现连续无数个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 0 1 2 3 4 5 6 7 tx(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是单射的。,(2) 定义函数g：0,1N0,1)。 g的映射法则恰好与 f 相反， 即 t0,1N

34、，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),总结,N Z Q NN R a,b (c,d) 0,1N P(N) 其中a,b，(c,d)代表任意的实数闭区间和开区间。 0,1A P(A) N R A P(A),8.3.2 集合的基数

35、,上一节我们只是抽象地讨论了集合的等势与优势。 本节将进一步研究度量集合的势的方法。 最简单的集合是有穷集。尽管前面已经多次用到“有穷集”这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。,定义9.38.10 设a为集合，称aa为a的后继，记作a+，即 a+=aa。,例 考虑空集的一系列后继。,+ = =,+ = + = = , = , +,+ =,+ = , = , = , +, + ,后继,说明,前边的集合都是后边集合的元素。 前边的集合都是后边集合的子集。,利用后继的性质，可以考虑以构造性的方法用集合来

36、给出自然数的定义，即 0= 1=0+ 0 2=1+ ,0,1 32+,+, 0,1,2 n0, 1, , n1 ,说明,自然数的定义,这种定义没有概括出自然数的共同特征。,（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,自然数的性质,定义8.11 有穷集、无穷集 （1）一个集合是有穷的当且仅当它与某个自然数等势； （2）如果一个集合不是有

37、穷的，就称作无穷集。 例如： a,b,c是有穷集， 因为30,1,2，且a,b,c0,1,23 N和R都是无穷集， 因为没有自然数与N和R等势。,任何有穷集只与唯一的自然数等势。,说明,有穷集和无穷集,定义8.12 （1）对于有穷集合A，称与A等势的那个唯一的自然数为A的基数，记作card A，即 card A n A n （对于有穷集A， card A也可以记作|A|） （2）自然数集合N的基数记作0，即 card N =0 （3）实数集R的基数记作（读作阿列夫），即 card R =,基数(cardinality),定义8.13 设A, B为集合，则 （1）card Acard B AB

38、（2）card Acard B A B （3）card A card B card Acard Bcard Acard B 例如： card Z card Q card NN 0 card P(N) card 2N card a,b card (c,d) 0 说明：集合的基数就是集合的势，基数越大，势就越大。,基数的相等和大小,关于基数的说明,由于对任何集合A都满足A P(A)，所以有 card A card P(A)，这说明不存在最大的基数。 将已知的基数按从小到大的顺序排列就得到： 0, 1, 2, , n, , 0, , 0, 1, 2, n, 是全体自然数，是有穷基数。 0, , 是无

39、穷基数。 0是最小的无穷基数，后面还有更大的基数，如 card P(R)等。,可数集,定义8.14 设A为集合，若card A0，则称A为可数集(enumerable)或可列集。 例如： a,b,c、5、整数集Z、有理数集Q、NN等都是可数集。 实数集R不是可数集，与R等势的集合也不是可数集。,对于任何的可数集，都可以找到一个“数遍”集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。,说明,（1）可数集的任何子集都是可数集。 一个集合的无限子集若不可数，则该集合也不可数。 （2）两个可数集的并是可数集。 （3）两个可数集的笛卡儿积是可数集。 （4）可数个可数集的

40、笛卡儿积仍是可数集。 （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知，card T5。 （2）由B可知，card B0。 （3）由|A|4可知，card Ccard P(A)|P(A)|2416。,解答,例8.11,方法一 由card A0，card Bn，可知A, B都是可数集。 令A=a0,a1 , a2 , ，B=b0 , b1 , b2 , , bn1。 对任意的， A

41、B，有 i kj l 定义函数 f：ABNf()in+j, i0,1, j0,1,n1 由于 f 是AB到N的双射函数，所以card ABcard N。,例8.12,解答,例8.12 设A, B为集合，且card A0， card Bn，n是自然数，n0。求card AB。,例8.12,方法二 因为card A0，card Bn，所以A, B都是可数集。 根据性质（3）可知，AB也是可数集，所以，card AB0 当B时，card Acard AB， 这就推出 0card AB 综合所述，card AB 0,本章主要内容,函数的基本概念与性质（单射，满射，双射）。 函数的合成与反函数。,本章主

42、要内容（续）,集合等势的定义 等势的性质 集合优势的定义 优势的性质 重要的集合等势以及优势的结果 可数集与不可数集 集合的基数,本章学习要求,掌握函数、A到B的函数、集合在函数下的像、集合在函数下的完全原像的概念及表示法；当A与B都是有穷集时，会求A到B的函数的个数。 掌握A到B的函数是单射、满射、和双射的定义及证明方法。 掌握常函数、恒等函数、单调函数、特征函数、自然映射等概念。 掌握合成函数的主要性质和求合成函数的方法。 掌握反函数的概念及主要性质。,本章学习要求（续）,能够证明两个集合等势。 能够证明一个集合优势于另一个集合。 知道什么是可数集与不可数集。 会求一个简单集合的基数。,对

43、于任意的, 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的双射

44、。令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的基数，得到card A card B。 证明集合A与自然数集合N等势的方法 找到一个“数遍”A中元素的顺序。,例题选讲,1已知An7|nN，B n109|n N ，求下列各题： （1）card A（2）card B （3）card (AB)（4）card (AB),（1）构造双射函数 f：NA， f(n)=n7 ，因此 card A0。 （2）构造双射函数 g：NA，