离散数学-函数优秀PPT.ppt

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

1、1第四章第四章 函函 数数 本章探讨的函数，事实上就是关系，只不过本章探讨的函数，事实上就是关系，只不过它是一种特殊的关系。它对关系的概念作了两条它是一种特殊的关系。它对关系的概念作了两条限制，即要求由限制，即要求由A A到到B B的关系满足对于的关系满足对于A A中每一元素中每一元素a a，在，在B B中必需有一个元素且只能有一个元素与之中必需有一个元素且只能有一个元素与之对应。对应。由于函数也是关系，因此关系的全部性由于函数也是关系，因此关系的全部性质和运算对于函数均是成立的。但反过来，由于质和运算对于函数均是成立的。但反过来，由于函数是一种特殊的关系，因此它又有其自身特殊函数是一种特殊的

2、关系，因此它又有其自身特殊的一些性质。例如，逆函数、复合函数既是逆关的一些性质。例如，逆函数、复合函数既是逆关系和复合关系，但又有其不同于一般关系之处，系和复合关系，但又有其不同于一般关系之处，读者对这些必需有清晰的相识。读者对这些必需有清晰的相识。对函数的概念再作些限制，我们又可得对函数的概念再作些限制，我们又可得到内射、满射、双射三类特殊的函数。到内射、满射、双射三类特殊的函数。主要内容如下主要内容如下:函数函数 函数的复合运算函数的复合运算 逆函数逆函数 集合的基数集合的基数2函函 数数一、一、函数的概念函数的概念定定义义41设设有有集集合合A、B，f是是一一由由A到到B的的关关系系，假

3、假如如对对于于每每一一个个aA，均均存存在在唯唯一一的的bB，使使 得得 afb（或或(a，b)f），则则称称关关系系f是是由由A到到B的一个函数。记作的一个函数。记作f：AB。1.函数函数例例.设设A1,2,3,4,B=2,3,4,5,6,A到到B的的关关系系=(2,2),(2,4),(2,6),(3,3),(3,6),(4,4)3例例2对例对例1 1中关系中关系 的序偶进行调整或修改，使的序偶进行调整或修改，使 f f(1,2),(2,6),(3,6),(4,4)(1,2),(2,6),(3,6),(4,4)或或g=(1,3),(2,2),(3,6),(4,5)g=(1,3),(2,2),

4、(3,6),(4,5)若若f f是一由是一由A A到到B B的函数，且的函数，且(a,b)f(a,b)f，则常记，则常记作作f(a)=bf(a)=b。则则f f和和g g都是由都是由A A到到B B的函数。的函数。4.函数的定义域和值域函数的定义域和值域函数的定义域Df=A,而不会是A的真子集。函数的值域满足RfB.但对于函数f,常将Rf记作(A)。即(A)=Rf=b|bB且存在aA使f(a)=b例如例如例例2中中f(2)=6,f(4)=4,g(1)=3,g(3)=6Df=D=(A)=R=2,4,6g(A)=Rg=2,3,5,65.函数的相等函数的相等定定义义42设设f和和g都都是是由由集集合

5、合A到到B的的函函数数,假假如如对对于于全全部部的的aA,均均有有f(a)=g(a),则则称称函函数数f和和g相相等等,记作记作f=g。依据定义依据定义42，若在，若在A中有一个元素中有一个元素a，使得，使得f(a)g(a),则则fg。设设A A和和B B都都是是有有限限集集，A An n，B Bm m，设设A=aA=a1 1,a a2 2,a,an n,B=b,B=b1 1,b,b2 2,b,bm m。记记A A=f|f:AB,=f|f:AB,则则#(B#(BA A)=(#B)=(#B)#A#AA A中中n n个元素的取值方式是个元素的取值方式是 种种,因此因此由由A A到到B B的函数有的

6、函数有m m n n个个,6 例例3 3 设设A=a,b,c,B=1,2,A=a,b,c,B=1,2,构造出全部由构造出全部由A A到到B B的函数的函数,并验证并验证#(BA)=(#B)#A#(BA)=(#B)#A解解:由由A A到到B B的函数如下的函数如下:因此因此,#(B,#(BA A)=(#B)=(#B)#A#Af f5 5=(a,2),(b,1),(c,1)=(a,2),(b,1),(c,1)f f6 6=(a,2),(b,2),(c,1)=(a,2),(b,2),(c,1)f f7 7=(a,2),(b,1),(c,2)=(a,2),(b,1),(c,2)f f8 8=(a,2)

7、,(b,2),(c,2)=(a,2),(b,2),(c,2)所以所以#(B#(BA A)=8)=8。f f1 1=(a,1),(b,1),(c,1)=(a,1),(b,1),(c,1)f f2 2=(a,1),(b,2),(c,1)=(a,1),(b,2),(c,1)f f3 3=(a,1),(b,1),(c,2)=(a,1),(b,1),(c,2)f f4 4=(a,1),(b,2),(c,2)=(a,1),(b,2),(c,2)7二、几种特殊的函数二、几种特殊的函数定义43设f是一由A到B的函数,（1）若当aiaj时，有f(ai)f(aj),(或者说当f(ai)f(aj)时,有ai=aj)

8、则称f是由A到B的内射。（2）若对随意bB，必存在aA，使f(a)=b，则称f是A到B的满射。（3）若f既是内射，又是满射，则称f是由A到B的双射。8（a a）是内射，但不是满射；）是内射，但不是满射；（b b）是满射）是满射,但不是内射；但不是内射；（c c）既不是内射，也不是满射；）既不是内射，也不是满射；(d(d）既是内射，又是满射，因此是双射。）既是内射，又是满射，因此是双射。例例4 49练习练习 4 41 1 .设设A A1,2,3,4,5,1,2,3,4,5,B=6,7,8,9,10,B=6,7,8,9,10,推断下列由推断下列由A A到到B B的的关系哪些是函数关系哪些是函数,哪

9、些不是函数。在相应哪些不是函数。在相应的括号中键入的括号中键入“Y”“Y”或或“N”“N”。(1)f1(1)f1(1,10),(2,9),(3,8),(4,(1,10),(2,9),(3,8),(4,7),(5,6)7),(5,6)（）(2)f2(2)f2(3,6),(1,8),(2,6),(4,(3,6),(1,8),(2,6),(4,7)7)（）(3)f3(3)f3(3,6),(2,9),(1,9),(4,(3,6),(2,9),(1,9),(4,9),(5,9)9),(5,9)（）(4)f4(4)f4(2,9),(3,8),(1,7),(2,(2,9),(3,8),(1,7),(2,6)

10、,(4,7),(5,10)6),(4,7),(5,10)（）YNYN10(1)(2)(3)(4).对下列每一函数，确定是否内射，是否对下列每一函数，确定是否内射，是否满射，是否双射。分别将满射，是否双射。分别将“内内”、“满满”或或“双双”填入相应的括号内。填入相应的括号内。(）（）（）（）满满满满双双内内11函数的复合运算函数的复合运算 由由A A到到B B的函数事实上也是一个由的函数事实上也是一个由A A到到B B的关系的关系,因此对函数可以进行关系的复合因此对函数可以进行关系的复合运算运算,而且我们发觉所得的复合关系也仍而且我们发觉所得的复合关系也仍旧是一个函数旧是一个函数,因此因此,我

11、们引进复合函数的我们引进复合函数的概念。概念。一、复合函数一、复合函数 定定定定义义义义4 44 4 设设设设有有有有函函函函数数数数f f：AABB和和和和g g：BCBC，f f和和和和g g的的的的复复复复合合合合函函函函数数数数是是是是一一一一个个个个由由由由A A到到到到C C的的的的函函函函数数数数，记记记记为为为为gfgf。定定定定义义义义为为为为：对对对对于于于于任任任任一一一一a aA A，(gf)(a)=g(f(a)(gf)(a)=g(f(a)。即即即即假假假假如如如如集集集集合合合合B B中中中中的的的的元元元元素素素素b b是是是是a a在在在在f f作作作作用用用用下

12、下下下的的的的像像像像，且且且且集集集集合合合合C C中中中中的的的的元元元元素素素素c c是是是是b b在在在在g g作作作作用用用用下下下下的的的的像像像像，那那那那么么么么就就就就是是是是a a在函数在函数在函数在函数gfgf作用下的像。作用下的像。作用下的像。作用下的像。12例例1 1 设集合设集合=a=a1 1,a,a2 2,a,a3,3,a a4 4,B=b,B=b1 1,b,b2 2,b,b3 3,b,b4 4,b,b5 5,C Ccc1 1,c,c2 2,c,c3 3,c,c4 4 函数函数f:ABf:AB和和g:BCg:BC，分别定义为，分别定义为 f=(a f=(a1 1,

13、b,b2 2),(a),(a2 2,b,b2 2),(a),(a3 3,b,b3 3),(a),(a4 4,b,b4 4),),g=(b g=(b1 1,c,c1 1),(b),(b2 2,c,c2 2),(b),(b3 3,c,c1 1),(b),(b4 4,c,c3 3),(b),(b5 5,c,c3 3),因此因此gf=(agf=(a1 1,c,c2 2),(a),(a2 2,c,c2 2),(a),(a3 3,c,c1 1),(a),(a4 4,c,c3 3)复复合合函函数数gfgf就就是是复复合合关关系系fgfg。要要留留意意的的是是为为了了便便利利，当当将将其其看看作作复复合合函函

14、数数时时，在在其其表表示示记记号号中中颠颠倒倒f f和和g g的的位位置置而写成而写成gfgf。13二、函数复合运算的性质二、函数复合运算的性质定理定理41设设f f是一个由集合是一个由集合A A到到B B的函数，的函数，I IA A和和I IB B分别是分别是A A和和B B上的恒等函数，则有上的恒等函数，则有fIfIA A=I=IB Bfff f。例例2 2设设A Aa,b,c,d,B=1,2,3,a,b,c,d,B=1,2,3,函数函数f:ABf:AB定义为定义为f=(a,1),(b,3),(c,2),(d,2)f=(a,1),(b,3),(c,2),(d,2)则则fIfIA AI IB

15、 Bfff f。I IA AI IB BffI IA AI IB Bff14 定理定理4 42 2设有函数设有函数 f f：ABAB，g g：BCBC和和 h h：CDCD，则有，则有 h(gf)h(gf)(hg)f(hg)f ggf fhghg15例例3 3设有函数设有函数f,g,h,均是由实数集均是由实数集R到到R的函数的函数,且且f(x)=x+3,g(x)=2x+1,h(x)x/2求复合函数求复合函数h(gf),(hg)f。解解:所求的复合函数都是由所求的复合函数都是由R到到R的函数的函数由上可知由上可知 h(gf)=(hg)f h(gf)=(hg)f16 设有函数设有函数f f1 1：

16、A A1 1AA2 2,f,f2 2：A A2 2AA3 3,，f fn n：A An nA A n n1 1,则不加括号的表达式则不加括号的表达式f fn nffn-1n-1 f f1 1 唯一地表示一个由唯一地表示一个由A A1 1到到A An+1n+1的函数。的函数。若有函数若有函数f:AA,f:AA,则对任意正整数则对任意正整数n n，唯一地表示一个由唯一地表示一个由A A到到A A的函数，并将其简记为的函数，并将其简记为 .17f(1)=2,f(2)=3,f(3)=4,f（4）=1f2(1)=(ff)(1)=f(f(1)=f(2)=3f2(2)=4,f2(3)=1,f2(4)=2f3

17、(1)=(ff2)(1)=f(f2(1)=f(3)=4 类似地类似地f3(2)=1,f3(3)=2,f3(4)=3f4(1)=(ff3)(1)=f(f3(1)=f(4)=1 类似地类似地f4(2)=2,f4(3)=3,f4(4)=4 因此因此f4=IA，f5=IAf=f,f6=f2,f7=f3,故故f4n=IA，f4n1=f,f4n2=f2,f4n3=f3,即对随意正整数即对随意正整数n n，f4nf4ni=fi i=fi（i i1,2,3,41,2,3,4）例例4设设A A1,2,3,4,1,2,3,4,定义函数定义函数 f f：AA,AA,为为 f f(1,2),(2,3),(3,4),(

18、4,1)(1,2),(2,3),(3,4),(4,1)，试求，试求 解解 对任意正整数对任意正整数n,n,都是由都是由A A到到A A的函数，的函数，类似的类似的f8=IA，f9=IAf=f,f10=f2,f11=f318三、三、三、三、复合函数的性质复合函数的性质复合函数的性质复合函数的性质 定理定理定理定理4 433设有函数设有函数设有函数设有函数f f：ABgABg：BCBC(1(1）假如）假如）假如）假如f f和和和和g g都是内射，则都是内射，则都是内射，则都是内射，则gfgf也是内射也是内射也是内射也是内射;（2 2）假如）假如）假如）假如f f和和和和g g都是满射，则都是满射，

19、则都是满射，则都是满射，则gfgf也是满射也是满射也是满射也是满射;（3 3）假如）假如）假如）假如f f和和和和g g都是双射，由都是双射，由都是双射，由都是双射，由gfgf也是双射。也是双射。也是双射。也是双射。此即此即 gf(a gf(ai i)gf(a gf(aj j)，故，故gfgf是内射是内射证明：证明：(1)(1)ggf f19 对于对于b,b,又必存在又必存在aA,aA,使得使得f(a)=b,f(a)=b,(3)(3)由由(1)(1)和和(2)(2)知知gfgf必是双射。必是双射。(2)(2)对于集合对于集合C C中任一元素中任一元素c c，必存，必存在在bB bB，使得，使得

20、g(b)=cg(b)=c。cba由由c c的任意性得的任意性得gfgf是满射。是满射。于是有于是有gf(a)=g(f(a)=g(b)=c,gf(a)=g(f(a)=g(b)=c,20 例例例例55设有函数设有函数设有函数设有函数f f：IIII和和和和g g：IIII（I I是整数集）是整数集）是整数集）是整数集）f(x)=x3f(x)=x32,g(x)=x2,g(x)=x1 1试推断试推断试推断试推断f,g,gff,g,gf是否内射是否内射是否内射是否内射,满射或双射。满射或双射。满射或双射。满射或双射。解解 （1 1）f f是内射，是内射，因为当因为当x1x2时，时，x132x232f不是

21、满射，例如不是满射，例如8I,但但8没有像源。没有像源。（2 2）g g是内射，是内射，因为当因为当x x1 1xx2 2 时，时，x x1 11 x1 x2 21 1gg是满射，因为对随意是满射，因为对随意y yI I，有，有f(yf(y1)=y1)=y。gf是内射，是内射，gf不是满射不是满射。(3(3）gf(x)=g(f(x)=g(xgf(x)=g(f(x)=g(x3 32)=x2)=x3 32 21=x1=x3 31 121定定理理44 44 设设有有函函数数f f：AB AB 和和g g：BCBC (1)(1)假假如如gfgf是是内内射射，则则f f是是内内射；射；(2)(2)假假如

22、如gfgf是是满满射射，则则g g是是满满射；射；(3)(3)假假如如gfgf是是双双射射，则则f f是是内内射而射而g g是满射。是满射。证明证明 （1 1）反证法）反证法 假设假设f f不是内射不是内射,则则gf(ai)=g(f(ai)=g(b)=cgf(ai)=g(f(ai)=g(b)=c gf(aj)=g(f(aj)=g(b)=c gf(aj)=g(f(aj)=g(b)=c gf(ai)=gf(aj)gf(ai)=gf(aj)这与这与gf gf 是内射相冲突。是内射相冲突。则存在元素则存在元素a ai i,a,aj j A,a A,ai i a aj j,但但f(af(ai i)=f(

23、a)=f(aj j),),gfgf令令f(af(ai i)=f(a)=f(aj j)=b,)=b,且令且令g(b)=c,g(b)=c,c c22(2)2)因为因为gf gf 是满射，所以对任一元素是满射，所以对任一元素cCcC，必存在元素必存在元素aAaA，使得，使得gf(a)=c gf(a)=c，而而 gf(a)=g(f(a)=c,gf(a)=g(f(a)=c,(3)(3)由结论由结论(1)(1)和和(2)(2)干脆推得。干脆推得。令令b=f(a)b=f(a)，则，则g(b)=c,g(b)=c,由由c c的随意性的随意性,知知g g是满射。是满射。留意：当留意：当gf gf 是内射时，是内射

24、时，g g可能不是可能不是内射，内射，例如例如23当当gf gf 是满射，是满射，f f可能不是满射可能不是满射.当当gf gf 是双射时，是双射时，f f可能不是满射，可能不是满射，g g可能不是内射可能不是内射.例如例如例如例如24例例6 6 设设有有函函数数f f：RRRR和和g g：RRRR，定义为，定义为 f(x)=x2 f(x)=x22,g(x)=x2,g(x)=x4 4 试推断试推断f f是否内射？是否内射？gfgf是否内射。是否内射。解解 （1 1）f f不是内射。不是内射。因为因为3 3 3,3,但但f(3)=f(f(3)=f(3)=73)=7(2)gf(2)gf不是内射不是

25、内射gf(x）g(f(x)=g(x22)=x224x22。gf(3)=gf(3)=11。25例如例如 f(1,2,3,4,5)=2,3,5 f(1,2,3,4,5)=2,3,5 若将若将f(s)f(s)表示为表示为S SP P,即即f(s)=Sf(s)=SP P因此因此f2(s)=。f3(s)=。2.设有函数设有函数f:II，定义为，定义为f(i)=2i+1,则复合函数则复合函数f2(i)=_f3(i)=_ S SP P S SP P f(f(i)=f(2i+1)=2(2i+1)+1=4i+3f(f(i)=f(2i+1)=2(2i+1)+1=4i+3 f(f(f2(i)=f(4i+3)=2(4

26、i+3)+1=8i+7(i)=f(4i+3)=2(4i+3)+1=8i+7练习练习421.1.设有函数设有函数f f：2 2N N 2 2N N，对于给定的，对于给定的s2s2N N（或（或s s）f(s)=n|nSP (N f(s)=n|nSP (N表示正整数集表示正整数集,P,P表示素数集表示素数集)26f f是函数是函数,但但 不是函数不是函数 f=(a,1),(b,3),(c,2)f=(a,1),(b,3),(c,2)，f f的逆关系的逆关系 =(1,a),(3,b),(2,c)=(1,a),(3,b),(2,c)逆函数逆函数例例1 1 设有函数设有函数f:ABf:AB，如下图所示，如

27、下图所示27例例2 2 设有函数设有函数f f：ABAB，如下图所示：，如下图所示：f f是函数是函数,但逆关系但逆关系 不是函数不是函数 f=(a,1),(b,2),(c,2),(d,3)f=(a,1),(b,2),(c,2),(d,3)，f f的逆的逆关系关系 =(1,a),(2,b),(2,c),(3,d)=(1,a),(2,b),(2,c),(3,d)28一、逆函数的定义一、逆函数的定义定义定义4 4设函数设函数f f：ABAB是一个双射，定义函是一个双射，定义函数数g g：BABA，使得对于每一个元素，使得对于每一个元素bBbB，g(b)=a,g(b)=a,其中其中a a是是使得使得

28、f(a)=bf(a)=b的的A A中的元素中的元素,称称g g为为f f的逆函数的逆函数,记作记作f f-1-1,并称并称f f是可逆的。是可逆的。由定义由定义4 45 5，若函数，若函数f f使使f(a)=bf(a)=b，则逆函数，则逆函数f f-1-1使使f f11(b)=a,(b)=a,即若即若(a,b)f,(a,b)f,则则(b,a)f(b,a)f-1-1 。因此逆函数因此逆函数f f-1-1就是就是f f的逆关系。的逆关系。f f的逆关系的逆关系 =(2,a),(3,b),(4,c),(1,d)=(2,a),(3,b),(4,c),(1,d)显然是一个函数。显然是一个函数。例如例如

29、下图给出一双射函数下图给出一双射函数f f，如图所示，如图所示29f f的逆函数的逆函数f f-1-1：R R0R0R00 例例3 3设有函数设有函数f f：R R0R0R0,0,定义为定义为f(r)=f(r)=当当r r1 1 r r2 2时时,所以所以f f是内射。是内射。对任意对任意rRrR0,0,有有 所以所以f f是满射。故是满射。故f f是双射。是双射。对对任任意意rRrR0 0 f f11(r)=(r)=。30又又由由逆逆函函数数定定义义，f f-1-1(b(b1 1)=)=a a1 1 ,f f-1-1(b(b2 2)=a)=a2 2因此因此f f-1-1(b1)f f-1-1

30、(b2)这说明这说明f f-1-1是内射。是内射。(2)f(2)f-1-1是满射。是满射。于是有于是有f-1(b)=a,f-1(b)=a,由由a a 的随意性的随意性,f-1,f-1是满射。是满射。二、逆函数有关的一些性质二、逆函数有关的一些性质定理定理4 4设设f f：ABAB是双射，则逆函数是双射，则逆函数f f-1-1：BABA也是双射。也是双射。证明证明(1)f(1)f是内射。是内射。设设b b1 1,b,b2 2BB，b b1 1bb2 2 ，b b1 1b b2 2因为因为f f是满射，所以在是满射，所以在A A中必有元素中必有元素a a1 1,a a2 2 ，使得，使得f(af(

31、a1 1)=b)=b11,f(a,f(a2 2)=b)=b2 2a1a1a2a2且由函数定义中像的唯一性，有且由函数定义中像的唯一性，有 a a1 1aa2 2 。任取任取aA,aA,由由f f的定义的定义,必有必有bB,bB,使使f(a)=b,f(a)=b,a ab b31定理定理4 46 6 设函数设函数f:ABf:AB是双射，是双射，则则(f(f-1-1)-1-1=f=f。于是于是f(a)=(f-1)-1(a),由由a的随意性知的随意性知f=(f-1)-1。证明证明 由定理由定理3 35 5，f f-1-1是一个由是一个由B B到到A A的的双射，因此双射，因此f f-1-1存在逆函数存

32、在逆函数(f(f-1-1)-1-1：AB.AB.对任一对任一aAaA，设，设f(a)=b,f(a)=b,a ab ba a 则则f-1(b)=a,b b因此因此(f-1)-1(a)b，32于是于是f f-1-1 f(a)f(a)f f-1-1(f(a)(f(a)f f-1-1(b)=a(b)=a。定理定理4-74-7 如果函数如果函数f f：ABAB是可逆的，是可逆的，则有则有对于任一元素对于任一元素aAaA，设，设f(a)=b,f(a)=b,a ab b则则f f-1-1(b)=a(b)=aa a由由a a的任意性的任意性,。证明证明由复合函数定义，由复合函数定义，是一由是一由A A到到A

33、A的函数。的函数。33 证明证明因为因为gfgfI IA A，所以，所以gfgf是内射，于是是内射，于是f f是内射。是内射。因为因为fgIB，所以，所以fg是满射，于是是满射，于是f是满射。是满射。因此因此f是双射，存在逆函数是双射，存在逆函数f-1：BA又又 f-1(fg)=(f-1f)g=IAg=g，另一方面另一方面f f-1-1(fg)=f-1IB=f-1。故有故有g=f-1 定定理理4 48 8设设有有函函数数f f：ABAB，若若有有函函数数g g：BABA，使得使得gfgfI IA A，fgfgI IB B，则有，则有g gf f-1-1。g g f ff f g g34练习练习

34、 4 43 31 1填空：填空：设设A=a,A=a,b,b,c,c,d,B=1,d,B=1,2,2,3,3,4,4,和和均均是是由由到到的的函函数数,这这些些函函数数的的值值域域分分别别为为 f(f()=1,2,4,)=1,2,4,()=1,3,h()=1,3,h()=)=这三个函数中这三个函数中,有逆函数。有逆函数。h h推推断断以以下下函函数数是是否否有有逆逆函函数数，在在相相应应的的括括号号中键入中键入“”或或“”。(1)f:I,f(i)=3i()(2)g:RR,f(r)=3r()N NY Y353 3对对下下列列论论断断作作出出推推断断，在在相相应应括括号号内内填填入入“Y”“Y”或或

35、“N”“N”(1)(1)设设集集合合=a1,a2,an=a1,a2,an=1,1,则则由由A A到到B B至至少少存存在在一一个个双双射射函函数数f:f:B.B.()()(2)2)设集合设集合=a1,a2,an=1,m,则由到至少存在一个内射函数：则由到至少存在一个内射函数：.()()(3)(3)设设集集合合=a=a1 1,a a2 2,a an n=1,m,n,n,则到至少存在一个满射函数则到至少存在一个满射函数：.()()Y Y N NN N36集合的基数集合的基数一一.集合的同基集合的同基 定义定义4-4-设有集合，假如存在一个双射设有集合，假如存在一个双射函数：函数：，则称与同基（有相

36、同的基数），则称与同基（有相同的基数）。或称与等势。记作。或称与等势。记作。集合间的同基关系具有以下三条性质：集合间的同基关系具有以下三条性质：(1)(1)自反性：对于随意集合，自反性：对于随意集合，。(2)(2)对称性对称性:对于随意集合、对于随意集合、,若若，则必有，则必有。(3)(3)可传递性：对于随意集合可传递性：对于随意集合,和和,若若,则则CC。定义定义4假如集合与集合假如集合与集合,(为某一正整数为某一正整数)同基同基,则称为有限集则称为有限集,且且#=.#=0,也是有限集也是有限集,不是有限集的集合称为无限集。不是有限集的集合称为无限集。37二二.可数集可数集 定定义义4 4

37、假假如如集集合合，则则称称是是可可数数集集，假假如如是是无无限限集集，但但不不是是可可数数集集，则称是不行数集。则称是不行数集。例例 设设|,即即,10,10,定义函数：定义函数：,对随意对随意,()=2)=2,10 12 10 12 ,=,因此因此是可数集。是可数集。38 是一双射，所以，即是一双射，所以，即，是可数集。是可数集。全部正有理数的集合，全部负有理数的集合全部正有理数的集合，全部负有理数的集合和全部有理数的集合都是可数集。和全部有理数的集合都是可数集。可可数数集集的的基基数数记记作作“0 0”。读读作作“阿阿列列夫夫零零”。因此因此N NN N2 2I IQ Q0 0-对应关系的

38、函数表达式如下：对应关系的函数表达式如下：例例 整数集是可数集。整数集是可数集。在整数集和正整数集之间可定义在整数集和正整数集之间可定义元素的对应关系如下：元素的对应关系如下：39三、不行数集三、不行数集例例集合集合|,是不行数集。是不行数集。例例实数集是不行数集实数集是不行数集是一个双射是一个双射,因此因此,将集合将集合的基的基数记作数记作“1 1”，读作，读作“阿列夫壹阿列夫壹”。于是。于是 1 1。证明证明定义函数：定义函数：40练习练习 4 44 4 推断下列论断是否正确，在相应的括号内键推断下列论断是否正确，在相应的括号内键入入“”或或“”。(1)(1)=2=2|是可数集。是可数集。

39、()()(2)(2)=2=2|是可数集。是可数集。()()(3)(3)=2=2|是可数集。是可数集。()()(4)(4)=2=2|,是可数集。是可数集。()()Y YY YN NN N 41例例 题题1 1关系关系 的素数的个数的素数的个数 是否函数？是否函数？解解 因为小于因为小于1 1和小于和小于2 2的素数的个数为的素数的个数为0 0，所以当，所以当n n1 1=1=1和和n n1 1=2=2时在时在 N N 中没有象，中没有象，因此不能构成函数。因此不能构成函数。422.下下列列函函数数中中，确确定定哪哪些些是是内内射射，哪哪些些是是满满射射，哪些是双射哪些是双射?(1)解解:（1 1

40、）因为）因为 因此因此 不是内射。不是内射。显然对于任意的显然对于任意的 均有均有 所以对于任意的所以对于任意的 就就是是说说，当当 时时，y y在在R R中中无无像像源源，因因此此 不是满射，由此可知不是满射，由此可知 也不是双射。也不是双射。43解：解：对任意对任意若若，则，则而而有有 因此因此 不是内射。不是内射。又又 但不存在但不存在 和和 ，使，使得得 而而 ,即即 中没有像源，所以中没有像源，所以 也不是满射，因此也不是满射，因此 不是双不是双射。射。44 既是内射又满射，因此既是内射又满射，因此 是一个双射是一个双射.表表示示 被被7 7除除后后的的非非负负余余数数，于是按照函数

41、于是按照函数 的定义的定义解解45 3 3设设 ，定义，定义函函数数 ，使得，使得 ，而且是双射。求，而且是双射。求 以及以及 。能否找到一个。能否找到一个双射双射 ，使出，使出 ，但，但？解：解：定义函数定义函数 ，显然显然 ，且且f f是双射。是双射。可以找到可以找到函函数，数，但，（即）。但，（即）。46 4 4设有函数设有函数 和和 ，使得，使得 是一个内射，且是一个内射，且 是满射。证明是满射。证明 是一个内射。举是一个内射。举出一个例子说明，若出一个例子说明，若 不是满射，则不是满射，则 不一定是内不一定是内射。射。证明：证明：任取任取 ，并设，并设 ，b b1b b2 因为因为 是是满射，所以必有满射，所以必有 ,使得使得 .a a1a a247 因为因为 是内射，所以由是内射，所以由 可知可知 ，此即此即 ，故，故 是射。是射。b b1b b2a a1 a a2又又因为因为是由是由B到到C的函数，所以有的函数，所以有，使，使得得，c c1c c2由于由于 ，根据函数的定义必有，根据函数的定义必有，于是于是48 下图中的例子可说明当下图中的例子可说明当 不是不是满射时，满射时，不一定是内射。不一定是内射。