离散数学讲义(第4章)课件.ppt

1、1离散数学讲义（电离散数学讲义（电子版）子版）2 3本章包括以下内容：4-1 函数的概念4-2 逆函数和复合函数4-4 基数的概念4-5 可数集与不可数集4-6 基数的比较4在这里把函数看作一种特殊关系。在这里把函数看作一种特殊关系。定义：定义：设X，Y为任意两个集合，f是X到Y的关系，若对于每一个xX，有唯一的yY，使得x,yf，称关系f为函数函数（或映射映射），记作f：X Y其中，x称为自变元，y称在f作用下x的象。x,yf也可记作y=f(x)，且记f(X)=f(x)|xX 4-1 函数的概念函数的概念注：注：函数与关系的区别（1）函数的定义域是X，而不能是X的某个真子集（2）一个xX只能

2、对应唯一一个y5在x，y f中，f的前域即dom f=X，f的值域ran f Y，有时也记作Rf。Rf=y|(x)(x X)(y Y)集合Y称为f的共域共域，ran f称为函数的象集合象集合。4-1 函数的概念函数的概念（续）（续）定义：定义：设函数f：A B，g：C D，如果A=C，B=D，且对所有x A和y C，有f(x)=g(x)，则称函数f和g相等相等，记作f=g注：注：X Y的子集并不能都成为X到Y的函数。我们用YX表示从X到Y的所有函数的集合，当X和Y是无限集时也可用这个符号。6定义：定义：对于f：X Y的映射中，如果ran f=Y，即Y的每一个元素是X中一个或多个元素的象点，则称

3、这个映射为满满射射（或到上映射到上映射）。即对于任意y Y，必存在x X使得f(x)=y成立。4-1 函数的概念函数的概念（续）（续）定义：定义：从X到Y的映射中，X中没有两个元素有相同的象，则称这个映射为入射入射。定义：定义：从X到Y的映射，若既是满射，又是入射，则称这个映射为双射双射。74-1 函数的概念函数的概念（续）（续）定理：定理：设X，Y为有限集，若X和Y的元素个数相同，即|X|=|Y|，则f：X Y是入射当且仅当它是满射。证明：若f是入射，则|X|=|f(X)|，由于f(X)Y，又因为|f(X)|=|Y|，而Y中的元素是有限的，因此f(X)=Y，即f是满射。若f是满射，则f(X)

4、=Y，于是|X|=|Y|=|f(X)|。因为|X|=|f(X)|，且X是有限的，故f是一个入射。注：注：这个定理必须在有限集情况下才成立。84-2 逆函数和复合函数逆函数和复合函数定理：定理：设f：X Y是双射函数，那么fc：Y X也是双射函数。证明：设f=x,y|(x X)(y Y)(f(x)=y)fc=y,x|x,yf因为f是满射，故对每一个y Y，必存在x,y f，则y,x fc，即fc的前域为Y。又因为f是入射，对每一个y Y，恰有一个x X，使得x,yf。因此仅有一个x X使得y,x fc，即y对应唯一的一个x，故fc是函数。又ran fc=dom f=X，故fc是满射。若y1y2，

5、有fc(y1)=fc(y2)，因为fc(y1)=x1，fc(y2)=x2，即x1=x2，故 fc(y1)=fc(y2)，即y1=y2，得到矛盾。因此fc是双射函数。94-2 逆函数和复合函数逆函数和复合函数（续）（续）定义：定义：设f：X Y是一个双射函数，称Y X的双射函数fc为f的逆函数逆函数，记作f-1。例1：设X=1,2,3，Y=p,q，Z=a,b，f=1,p,2,p,3,q，g=p,b,q,b，则gf=1,b,2,b,3,b定义：定义：设f：X Y，g：W Z，若f(X)W，则gf=x,z|(xX)(zZ)(y)(yY y=f(x)z=g(y)，称g在函数f的左边可复合左边可复合。定

6、义：定义：设f：X Y，g：Y Z，则gf=x,z|(xX)(zZ)(y)(yYy=f(x)z=g(y)，称为复合函数复合函数，或gf为g对f的左复合左复合。10定理：定理：两个函数的复合是一个函数。证明：设g：WZ，f：XY，为左复合，即f(X)W。4-2 逆函数和复合函数逆函数和复合函数（续）（续）（1）对任意的x X，因为f为函数，则必有唯一序偶x,y使得y=f(x)成立。而f(x)f(X)，即f(x)W，又因为g是函数，故必有唯一的序偶y,z使得z=g(y)成立，根据复合定义，x,z gf，即X中每个x对应Z中某个z。（2）假设gf中包含序偶x,z1和x,z2，且z1 z2，则在Y中必

7、存在y1和y2，满足在f中有x,y1和x,y2，在g中有y1,z1和y2,z2，因为f是一个函数，故y1=y2。于是g中有y1,z1和y2,z2，但g是一个函数，故z1 z2，即每个x X，只能有唯一的x,z gf。11定理：定理：令g f为复合函数。（1）若g和f为满射，则g f为满射。（2）若g和f为入射，则g f为入射。（2）若g和f为双射，则g f为双射。证明：（1）设f：XY，g：YZ，令z为Z的任意元素，因为g是满射，故必有某个元素y Y，使得g(y)=z。又因为f是满射，故必有某个元素x X，使得f(x)=y。故而g f(x)=g(f(x)=g(y)=z因此，Rgf=Z，g f是

8、满射。4-2 逆函数和复合函数逆函数和复合函数（续）（续）12（2）设x1，x2为X的元素，假定x1 x2，因为f是入射，故f(x1)f(x2)。又因为g是入射，且f(x1)f(x2)，故g(f(x1)g(f(x2)，即x1x2 gf(x1)gf(x2)，因此gf是入射。（3）因为g和f是双射，根据（1）（2），g f为满射和入射，则g f为双射。4-2 逆函数和复合函数逆函数和复合函数（续）（续）例2：设R为实数集合，对x R，有f(x)=x+2，g(x)=x-2，h(x)=3x。求g f与h (g f)注：注：一般有h (g f)=(h g)f，即函数的复合是可结合的。因此可以将括号去掉。

9、解：gf=x,x|x Rh (g f)=x,3x|x R134-2 逆函数和复合函数逆函数和复合函数（续）（续）定义：定义：函数f：X Y称作常函数常函数，如果存在某个y0 Y，对于每个x X，都有f(x)=y0，即f(X)=y0。定理：定理：若函数f：X Y有逆函数f-1：Y X，则f=f Ix=Iy f。定理：定理：若函数f：X Y有逆函数f-1：Y X，则f-1f=Ix，ff-1=Iy证明：f-1f与Ix的定义与均为X。因为f为一一对应的函数，因此f-1也为一一对应。若f：x f(x)，则f-1(f(x)=x，得到f-1f=Ix，故x X f-1f(x)=f-1(f(x)=x定义：定义：

10、如果Ix=x,x|xX，则称函数Ix：X X为恒恒等函数等函数。144-2 逆函数和复合函数逆函数和复合函数（续）（续）定理：定理：若f：X Y是一一对应的函数，则(f-1)-1=f。证明：（1）因为f为一一对应的，因此f-1也为一一对应。则(f-1)-1也是一一对应的。显然dom f=dom(f-1)-1=X。（2）x X f：x f(x)f-1：f(x)x (f-1)-1：x f(x)。得证(f-1)-1=f。154-2 逆函数和复合函数逆函数和复合函数（续）（续）定理：定理：若函数f：X Y，g：Y X均为一一对应的函数，则(g f)-1=f-1g-1证明：（1）因为f，g为一一对应的函

11、数，因此f-1，g-1存在，且f-1：Y X，g-1：Z Y，所以f-1g-1：Z X。又，f，g为双射，故g f为双射，因此(g f)-1存在且(g f)-1：Z X。dom(f-1g-1)=dom(g f)-1=Z（2）对任意z Z 存在唯一y Y，使得g(y)=z 存在唯一x X，使得f(x)=z，故(f-1g-1)(z)=(f-1(g-1(z)=f-1(y)=x。但(g f)(x)=g(f(x)=g(y)=z，故(g f)-1(z)=x，因此对任意z Z，有(g f)-1(z)=(f-1g-1)(z)。可知(g f)-1=(f-1g-1)。164-4 基数的概念基数的概念定义：定义：给

12、定集合A的后继集后继集定义为集合：A+=A A若A为空集，则后继集为+，(+)+，(+)+)+，这些集合可写成如下形式：，并可简化成，,，,，若命名集合=0，则+=0+=1；1+=,=2；2+=,=3；这样就得到了自然数集合0,1,2,3,17Peano公理：公理：（1）0N，（其中0=）（2）如果0N，则n+N（其中n+=nn）（3）如果一个子集S N具有性质：（a）0S （b）如果nS，有n+S 则S=N注：注：4-4 基数的概念基数的概念（续）（续）1）性质（3）称极小性质，指明了自然数系统的最小性。即自然数系统是满足公理（1）（2）的最小集合。2）自然数也可不从0开始，只需定义=1即可

13、。18定义：定义：给定两个集合P与Q，如果我们对P中每个不同元素，与Q中每个不同元素，可以分别两两成对，那么我们说P的元素与Q的元素间存在着一一对应一一对应。4-4 基数的概念基数的概念（续）（续）例如：2,4,6,2n,与1,3,5,2n-1,之间存在着一一对应。定义：定义：当且仅当集合A的元素与集合B的元素之间存在着一一对应，集合A与集合B称为是等势的等势的（同浓的同浓的）。例1：验证自然数集合N与非负偶数集合M是等势的。证明：因为N与M的元素之间可作一一对应的映射，即f(n)=2例2：设P为实数集合，S是P的子集，即SP，且S=x|(xP)(0 x1)证明S P。证明：令f：PS，f(x

14、)=tg-1x/p+1/2(-x)显然f的值域是S，且f是双射函数。194-4 基数的概念基数的概念（续）（续）定理：定理：在集合族上等势关系是一个等价关系。证明：设集合族为Sa）对任意的A S，必有A Ab）若A,B S，如果A B，必有B Ac）若A,B,C S，如果A B，B C，则有A C定义：定义：如果有一个从集合0,1,n-1到A的双射函数，那么称集合A是有限的；如果集合A不是有限的有限的，则它是无无限的限的。定理：定理：自然数集合N是无限的。证明：设n是N的任意元素，f是任意的从0,1,n-1到N的函数。设k=1+maxf(0),f(1),f(n-1)，那么k N，但对每一个x

15、0,1,n-1，有f(x)k。因此f不能是满射函数，即f也不是双射函数。因为n和f都是任意的，故N是无限的。204-4 基数的概念基数的概念（续）（续）定义：定义：所有与集合A等势的集合所组成的集合，叫做集合A的基数基数。例如：A=a,b,c，B=,，C=桌子，灯泡，教室，A B C，即KA=KB=KC=A,B,C,。注：注：（1）可见，有限集合的基数就是其元素的个数，记为KA（2）有限集合的基数就是其元素的个数。约定：空集的基数为0。（3）如果两个集合能够建立双射函数，则两个集合元素间一一对应，该两个集合具有相同的基数。214-4 基数的概念基数的概念（续）（续）例例3：证明区间0,1与(0

16、,1)基数相同。1(0)211()12()0,1ffnnnf xxxA证明：设集合A=0,1,1/2,1/n,，A 0,1定义f：0,1 (0,1)使得则f是双射。224-5 可数集与不可数集可数集与不可数集定义：定义：与自然数集合等势的任意集合称为可数的，可数集合的基数用（阿列夫）表示。A等势的集合所组成的集合，叫做集合A的基数基数。例如：A=1,4,9,16,n2,，B=1,8,27,64,n3,，C=3,12,27,3n2,，D=1,1/2,1/3,1/n,有限集和可数集统称为至多可数集至多可数集。定 理：定 理：A 为 可 数 集 的 充 分 必 要 条 件 是 可 以 排 列 成A=

17、a1,a2,an,的形式。证明：若A可排成上述形式，则将A的元素an与足标n对应，就得到A与N之间的一一对应，故A是可数集。反之，若A为可数集，那么在A与N之间存在一种一一对应关系f，由f得到n的对应元素an，即A可写为a1,a2,an,的形式。234-5 可数集与不可数集可数集与不可数集（续）（续）定理：定理：任意无限集必含有可数子集。证明：设A为无限集，从A中取出一个元素a1，因为A是无限的，所以从A-a1中可取元素a2，继而可从A-a1,a2中取一元素a3，如此继续，可得到可数子集A。定理：定理：任意无限集必与其某一真子集等势。证明：设M为无限集，则含有可数子集A=a1,a2,，设M-A

18、=B，我们定义集合M到其真子集的映像：f：M M-a1使得f(an)=an+1(n=1,2,)且对于任意bB，有f(b)=b，这个f是双射的。244-5 可数集与不可数集可数集与不可数集（续）（续）定理：定理：可数集的任何无限子集是可数的。证明：设A为可数集，B A为一无限子集，将A的元素排成a1,a2,an,，从a1开始，向后检查，不断删去不在B中的元素，则得到新的一列与自然数一一对应：ai1,ai2,ain,，故B是可数的。定理：定理：可数个两两不相交的可数集合的并集，仍然是一可数集。证明：设可数个可数集表示为：S1=a11,a12,a1n,；S2=a21,a22,a2n,；令S=S1 S

19、2 ，并排列为a11,a21,a12,a13,a31,a41,可与自然数一一对应。254-5 可数集与不可数集可数集与不可数集（续）（续）定理：定理：自然数集为N，则N N是可数集。证明：构造函数f：N N N，f(m,n)=(m+n)(m+n+1)/2+m，可证f是个双射函数（详见课本）。得证N N为可数集。定理：定理：有理数全体组成的集合是可数集。证明：设已知N N可数，在N N中删去所有m和n不互质的序偶m,n得到S N N，S=m,n|mN,nN,且m,n互质，则是可数的。令g：S Q+，g(m,n)=m/n（其中m，n互质），因为g是双射，故 是可数集。又Q+Q-，故Q=Q+Q-0是

20、可数集。264-5 可数集与不可数集可数集与不可数集（续）（续）定理：定理：全体实数构成的集合R是不可数的。证明：因为f：(0,1)R是双射，令S=x|x R,0 x1若S是不可数集，则R也是不可数集。（反证）假设S可数，则S可表示为S1,S2,，其中，Si是(0,1)间的任意实数。设Si=0.y1y2y3，其中yi 0,1,2,9，则可设S1=0.a11a12a1n；S2=0.a21a22a2n；构造一个实数r=0.b1b2b3，使bj=1，若ajj1；bj=2，若ajj=1。则r与所列实数全不相同，即r S，得到矛盾。因此S是不可数的，即R是不可数的。274-6 基数的比较基数的比较定义：

21、定义：若从集合A到集合B存在一个入射，则称A的基数不不大于大于B的基数，记作KA KB。若从A到B存在入射但不存在双射，则称A的基数小于小于B的基数，记作KA KB。Zermelo定理：定理：令A和B是任意集合，则以下三条中恰有一条成立。1）KA KB2）KB KA3）KA=KBCantor-Schroder-Bernstein定理：定理：设A和B是集合，如果KA KB，KB KA，则KB=KA。284-6 基数的比较基数的比较（续）（续）例1：证明0,1与(0,1)有相同的基数。例2：设A=N，B=(0,1)，KA=0，KB=，求证KA B=证明：作入射函数f：(0,1)0,1，f(x)=x

22、；g：0,1 (0,1)，g(x)=x/2+1/4得证。证明：定义入射函数f：A B x|x R+，f(n,x)=n+x又KR+=，所以KA B 。定义入射函数g：(0,1)A B，g(x)=0,x故 KA B。因此，KA B=29定理：定理：设A是有限集合，则KA 0 证明：设KA=n，则A 0,1,2,n-1。定义入射函数f：0,1,2,n-1 N，f(x)=x，f是入射函数，故KA KN。又已知N到A之间不存在双射函数，故KA KN，因此KA KN，即KA 0。作映射g：N 0,1，g(n)=1/(n+1)，g是入射函数。故0 。又N与0,1间不能一一对应，故0 。因此0 4-6 基数的

23、比较基数的比较（续）（续）定理：定理：若A是无限集合，则0 KA证明：因为A为无限集，故A必包含一个可数无限子集A。定义入射函数f：A A，f(x)=x，故KA KA。又KA=0，故0 KA。连续统假设：连续统假设：假定是大于0的最小基数，即不存在任何基数KS，使得故0 KS 。30Cantor定理：定理：设M是一个集合，T=P(M)，则KMKT证明：4-6 基数的比较基数的比较（续）（续）1）作入射函数f：M P(M)，f(a)=a，故KM KT2）（反证法）若KM=KT，则必有双射j：M T。对任意m M，必有T中唯一的j(m)与之对应。若m j(m)，称m为M的内部元素，否则称m为M的外部元素。设S=x|x M,x j(m)，即S为M的外部元素集合。则S M，故S T。因为j是双射函数，故又一个元素b S使j(b)=S。若b S，因为j(b)=S，此时b为M的内部元素，得到矛盾；若b S，因为j(b)=S，此时b为M的外部元素，得到矛盾。因此 KM KT，得到KM KT