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

ninglw@163.comDiscreteMathematics离散数学讲义（电子版）1DiscreteMathematics离散数学讲义（电子版）第四章

函数2第四章2第四章函数本章包括以下内容：4-1函数的概念4-2逆函数和复合函数4-4基数的概念4-5可数集与不可数集4-6基数的比较3第四章函数本章包括以下内容：4-1函数的概念3在这里把函数看作一种特殊关系。定义：设X，Y为任意两个集合，f是X到Y的关系，若对于每一个xX，有唯一的yY，使得〈x,y〉f，称关系f为函数（或映射），记作f：X

Y其中，x称为自变元，y称在f作用下x的象。〈x,y〉f也可记作y=f(x)，且记f(X)={f(x)|xX}4-1函数的概念注：函数与关系的区别（1）函数的定义域是X，而不能是X的某个真子集（2）一个xX只能对应唯一一个y4在这里把函数看作一种特殊关系。4-1函数的概念注：函数与关在〈x，y〉f中，f的前域即domf=X，f的值域ranfY，有时也记作Rf。Rf={y|(x)(xX)(yY)}集合Y称为f的共域，ranf称为函数的象集合。4-1函数的概念（续）定义：设函数f：AB，g：CD，如果A=C，B=D，且对所有xA和yC，有f(x)=g(x)，则称函数f和g相等，记作f=g注：XY的子集并不能都成为X到Y的函数。我们用YX表示从X到Y的所有函数的集合，当X和Y是无限集时也可用这个符号。5在〈x，y〉f中，f的前域即domf=X，f的值域ra定义：对于f：XY的映射中，如果ranf=Y，即Y的每一个元素是X中一个或多个元素的象点，则称这个映射为满射（或到上映射）。即对于任意yY，必存在xX使得f(x)=y成立。4-1函数的概念（续）定义：从X到Y的映射中，X中没有两个元素有相同的象，则称这个映射为入射。定义：从X到Y的映射，若既是满射，又是入射，则称这个映射为双射。6定义：对于f：XY的映射中，如果ranf=Y，即Y的4-1函数的概念（续）定理：设X，Y为有限集，若X和Y的元素个数相同，即|X|=|Y|，则f：XY是入射当且仅当它是满射。证明：若f是入射，则|X|=|f(X)|，由于f(X)Y，又因为|f(X)|=|Y|，而Y中的元素是有限的，因此f(X)=Y，即f是满射。若f是满射，则f(X)=Y，于是|X|=|Y|=|f(X)|。因为|X|=|f(X)|，且X是有限的，故f是一个入射。注：这个定理必须在有限集情况下才成立。74-1函数的概念（续）定理：设X，Y为有限集，若X和Y的元4-2逆函数和复合函数定理：设f：XY是双射函数，那么fc：Y

X也是双射函数。证明：设f={〈x,y〉|(xX)(yY)(f(x)=y)}fc={〈y,x〉|〈x,y〉f}因为f是满射，故对每一个yY，必存在〈x,y〉f，则〈y,x〉fc，即fc的前域为Y。又因为f是入射，对每一个yY，恰有一个xX，使得〈x,y〉f。因此仅有一个xX使得〈y,x〉fc，即y对应唯一的一个x，故fc是函数。又ranfc=domf=X，故fc是满射。若y1y2，有fc(y1)=fc(y2)，因为fc(y1)=x1，fc(y2)=x2，即x1=x2，故fc(y1)=fc(y2)，即y1=y2，得到矛盾。因此fc是双射函数。84-2逆函数和复合函数定理：设f：XY是双射函数，那4-2逆函数和复合函数（续）定义：设f：XY是一个双射函数，称YX的双射函数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：XY，g：WZ，若f(X)W，则gf={〈x,z〉|(xX)(zZ)(y)(yYy=f(x)z=g(y))}，称g在函数f的左边可复合。定义：设f：XY，g：YZ，则gf={〈x,z〉|(xX)(zZ)(y)(yYy=f(x)z=g(y))}，称为复合函数，或gf为g对f的左复合。94-2逆函数和复合函数（续）定义：设f：XY是一个双定理：两个函数的复合是一个函数。证明：设g：WZ，f：XY，为左复合，即f(X)W。4-2逆函数和复合函数（续）（1）对任意的xX，因为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〉，且z1z2，则在Y中必存在y1和y2，满足在f中有〈x,y1〉和〈x,y2〉，在g中有〈y1,z1〉和〈y2,z2〉，因为f是一个函数，故y1=y2。于是g中有〈y1,z1〉和〈y2,z2〉，但g是一个函数，故z1z2，即每个xX，只能有唯一的〈x,z〉gf。10定理：两个函数的复合是一个函数。证明：设g：WZ，f：X定理：令gf为复合函数。（1）若g和f为满射，则gf为满射。（2）若g和f为入射，则gf为入射。（2）若g和f为双射，则gf为双射。证明：（1）设f：XY，g：YZ，令z为Z的任意元素，因为g是满射，故必有某个元素y

Y，使得g(y)=z。又因为f是满射，故必有某个元素x

X，使得f(x)=y。故而gf(x)=g(f(x))=g(y)=z因此，Rgf=Z，gf是满射。4-2逆函数和复合函数（续）11定理：令gf为复合函数。证明：4-2逆函数和复合函数（2）设x1，x2为X的元素，假定x1

x2，因为f是入射，故f(x1)f(x2)。又因为g是入射，且f(x1)f(x2)，故g(f(x1))g(f(x2))，即x1x2gf(x1)gf(x2)，因此gf是入射。（3）因为g和f是双射，根据（1）（2），gf为满射和入射，则gf为双射。4-2逆函数和复合函数（续）例2：设R为实数集合，对xR，有f(x)=x+2，g(x)=x-2，h(x)=3x。求gf与h(gf)注：一般有h(gf)=(hg)f，即函数的复合是可结合的。因此可以将括号去掉。解：gf={〈x,x〉|xR}h(gf)={〈x,3x〉|xR}12（2）设x1，x2为X的元素，假定x1x2，因为f是入4-2逆函数和复合函数（续）定义：函数f：XY称作常函数，如果存在某个y0Y，对于每个xX，都有f(x)=y0，即f(X)={y0}。定理：若函数f：XY有逆函数f-1：YX，则f=fIx=Iyf。定理：若函数f：XY有逆函数f-1：YX，则f-1f=Ix，ff-1=Iy证明：f-1f与Ix的定义与均为X。因为f为一一对应的函数，因此f-1也为一一对应。若f：xf(x)，则f-1(f(x))=x，得到f-1f=Ix，故xXf-1f(x)=

f-1(f(x))=x定义：如果Ix={〈x,x〉|xX}，则称函数Ix：XX为恒等函数。134-2逆函数和复合函数（续）定义：函数f：XY称作常4-2逆函数和复合函数（续）定理：若f：XY是一一对应的函数，则(f-1)-1=f。证明：（1）因为f为一一对应的，因此f-1也为一一对应。则(f-1)-1也是一一对应的。显然domf=dom(f-1)-1=X。（2）xXf：xf(x)f-1：f(x)x(f-1)-1：xf(x)。得证(f-1)-1=f。144-2逆函数和复合函数（续）定理：若f：XY是一一对4-2逆函数和复合函数（续）定理：若函数f：XY，g：Y

X均为一一对应的函数，则(g

f)-1=f-1g-1证明：（1）因为f，g为一一对应的函数，因此f-1，g-1存在，且f-1：YX，g-1：ZY，所以f-1g-1：ZX。又，f，g为双射，故gf为双射，因此(gf)-1存在且(gf)-1：ZX。dom(f-1g-1)=dom(gf)-1=Z（2）对任意zZ存在唯一yY，使得g(y)=z存在唯一xX，使得f(x)=z，故(f-1g-1)(z)=(f-1(g-1(z))=f-1(y)=x。但(gf)(x)=g(f(x))=g(y)=z，故(gf)-1(z)=x，因此对任意zZ，有(gf)-1(z)=(f-1g-1)(z)。可知(gf)-1=(f-1g-1)。154-2逆函数和复合函数（续）定理：若函数f：XY，g4-4基数的概念定义：给定集合A的后继集定义为集合：A+=A∪{A}若A为空集，则后继集为+，(+)+，((+)+)+，…这些集合可写成如下形式：∪{}，∪{}∪{∪{}}，∪{}∪{∪{}∪{∪{}}}，…并可简化成{}，{,{}}，{,{},{,{}}，…若命名集合=0，则+=0+={}=1；1+={,{}}=2；2+={,{},{,{}}=3；…这样就得到了自然数集合{0,1,2,3,…}164-4基数的概念定义：给定集合A的后继集定义为集合：若A为Peano公理：（1）0N，（其中0=）（2）如果0N，则n+N（其中n+=n∪{n}）（3）如果一个子集SN具有性质：（a）0S（b）如果nS，有n+S则S=N注：4-4基数的概念（续）1）性质（3）称极小性质，指明了自然数系统的最小性。即自然数系统是满足公理（1）（2）的最小集合。2）自然数也可不从0开始，只需定义=1即可。17Peano公理：注：4-4基数的概念（续）1）性质（3）称定义：给定两个集合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<x<1)}证明SP。证明：令f：PS，f(x)=tg-1x/p+1/2(-∞<x<∞)显然f的值域是S，且f是双射函数。18定义：给定两个集合P与Q，如果我们对P中每个不同元素，与Q中4-4基数的概念（续）定理：在集合族上等势关系是一个等价关系。证明：设集合族为Sa）对任意的AS，必有AAb）若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+max{f(0),f(1),…,f(n-1)}，那么kN，但对每一个x{0,1,…,n-1}，有f(x)k。因此f不能是满射函数，即f也不是双射函数。因为n和f都是任意的，故N是无限的。194-4基数的概念（续）定理：在集合族上等势关系是一个等价关4-4基数的概念（续）定义：所有与集合A等势的集合所组成的集合，叫做集合A的基数。例如：A={a,b,c}，B={{,{},{,{}}}，C={桌子，灯泡，教室}，…，ABC，即K[A]=K[B]=K[C]={A,B,C,…}。注：（1）可见，有限集合的基数就是其元素的个数，记为K[A]（2）有限集合的基数就是其元素的个数。约定：空集的基数为0。（3）如果两个集合能够建立双射函数，则两个集合元素间一一对应，该两个集合具有相同的基数。204-4基数的概念（续）定义：所有与集合A等势的集合所组成的4-4基数的概念（续）例3：证明区间[0,1]与(0,1)基数相同。证明：设集合A={0,1,1/2,…,1/n,…}，A[0,1]定义f：[0,1](0,1)使得则f是双射。214-4基数的概念（续）例3：证明区间[0,1]与(0,1)4-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={a1,a2,…,an,…}的形式。证明：若A可排成上述形式，则将A的元素an与足标n对应，就得到A与N之间的一一对应，故A是可数集。反之，若A为可数集，那么在A与N之间存在一种一一对应关系f，由f得到n的对应元素an，即A可写为{a1,a2,…,an,…}的形式。224-5可数集与不可数集定义：与自然数集合等势的任意集合称为4-5可数集与不可数集（续）定理：任意无限集必含有可数子集。证明：设A为无限集，从A中取出一个元素a1，因为A是无限的，所以从A-{a1}中可取元素a2，继而可从A-{a1,a2}中取一元素a3，如此继续，可得到可数子集A。定理：任意无限集必与其某一真子集等势。证明：设M为无限集，则含有可数子集A={a1,a2,…}，设M-A=B，我们定义集合M到其真子集的映像：f：MM-{a1}使得f(an)=an+1(n=1,2,…)且对于任意bB，有f(b)=b，这个f是双射的。234-5可数集与不可数集（续）定理：任意无限集必含有可数子集4-5可数集与不可数集（续）定理：可数集的任何无限子集是可数的。证明：设A为可数集，BA为一无限子集，将A的元素排成a1,a2,…,an,…，从a1开始，向后检查，不断删去不在B中的元素，则得到新的一列与自然数一一对应：ai1,ai2,…,ain,…，故B是可数的。定理：可数个两两不相交的可数集合的并集，仍然是一可数集。证明：设可数个可数集表示为：S1={a11,a12,…,a1n,…}；S2={a21,a22,…,a2n,…}；…令S=S1∪

S2∪…，并排列为{a11,a21,a12,a13,a31,a41,…}可与自然数一一对应。244-5可数集与不可数集（续）定理：可数集的任何无限子集是可4-5可数集与不可数集（续）定理：自然数集为N，则NN是可数集。证明：构造函数f：NNN，f(m,n)=(m+n)(m+n+1)/2+m，可证f是个双射函数（详见课本）。得证NN为可数集。定理：有理数全体组成的集合是可数集。证明：设已知NN可数，在NN中删去所有m和n不互质的序偶〈m,n〉得到SNN，S={〈m,n〉|mN,nN,且m,n互质}，则是可数的。令g：SQ+，g(〈m,n〉)=m/n（其中m，n互质），因为g是双射，故是可数集。又Q+Q-，故Q=Q+∪Q-∪{0}是可数集。254-5可数集与不可数集（续）定理：自然数集为N，则N4-5可数集与不可数集（续）定理：全体实数构成的集合R是不可数的。证明：因为f：(0,1)R是双射，令S={x|xR,0<x<1}若S是不可数集，则R也是不可数集。（反证）假设S可数，则S可表示为{S1,S2,…}，其中，Si是(0,1)间的任意实数。设Si=0.y1y2y3…，其中yi{0,1,2,…,9}，则可设S1=0.a11a12…a1n…；S2=0.a21a22…a2n…；…构造一个实数r=0.b1b2b3…，使bj=1，若ajj1；bj=2，若ajj=1。则r与所列实数全不相同，即rS，得到矛盾。因此S是不可数的，即R是不可数的。264-5可数集与不可数集（续）定理：全体实数构成的集合R是不4-6基数的比较定义：若从集合A到集合B存在一个入射，则称A的基数不大于B的基数，记作K[A]K[B]。若从A到B存在入射但不存在双射，则称A的基数小于B的基数，记作K[A]<K[B]。Zermelo定理：令A和B是任意集合，则以下三条中恰有一条成立。1）K[A]<K[B]2）K[B]<K[A]3）K[A]=K[B]Cantor-Schroder-Bernstein定理：设A和B是集合，如果K[A]K[B]，K[B]K[A]，则K[B]=K[A]。274-6基数的比较定义：若从集合A到集合B存在一个入射，则称4-6基数的比较（续）例1：证明[0,1]与(0,1)有相同的基数。例2：设A=N，B=(0,1)，K[A]=0，K[B]=，求证K[AB]=证明：作入射函数f：(0,1)[0,1]，f(x)=x；g：[0,1](0,1)，g(x)=x/2+1/4得证。证明：定义入射函数f：AB{x|xR+}，f(n,x)=n+x又K[R+]=，所以K[AB]。定义入射函数g：(0,1)

AB，g(x)=〈0,x〉故

K[AB]。因此，K[AB]=284-6基数的比较（续）例1：证明[0,1]与(0,1)有相定理：设A是有限集合，则K[A]<0<证明：设K[A]=n，则A{0,1,2,…,n-1}。定义入射函数f：{0,1,2,…,n-1}

N，f(x)=x，f是入射函数，故K[A]K[N]。又已知N到A之间不存在双射函数，故K[A]K[N]，因此K[A]<K[N]，即K[A]<0。作映射g：N[0,1]，g(n)=1/(n+1)，g是入射函数。故0<。又N与[0,1]间不能一一对应，故0

。因此0

<

4-6基数的比较（续）定理：若A是无限集合，则0

K[A]证明：因为A为无限集，故A必包含一个可数无限子集A’。定义入射函数f：A’

A，f(x)=x，故K[A’]K[A]。又K[A’]=0，故0

K[A]。连续统假设：假定是大于0的最小基数，即不存在任何基数K[S]，使得故0

K[S]。29定理：设A是有限集合，则K[A]<0<证明：设K[Cantor定理：设M是一个集合，T=P(M)，则K[M]<K[T]证明：4-6基数的比较（续）1）作入射函数f：MP(M)，f(a)={a}，故K[M]K[T]2）（反证法）若K[M]=K[T]，则必有双射j：MT。对任意mM，必有T中唯一的j(m)与之对应。若mj(m)，称m为M的内部元素，否则称m为M的外部元素。设S={x|xM,xj(m)}，即S为M的外部元素集合。则SM，故ST。因为j是双射函数，故又一个元素bS使j(b)=S。若bS，因为j(b)=S，此时b为M的内部元素，得到矛盾；若bS，因为j(b)=S，此时b为M的外部元素，得到矛盾。因此K[M]K[T]，得到K[M]<K[T]30Cantor定理：设M是一个集合，T=P(M)，则K[M]<ninglw@163.comDiscreteMathematics离散数学讲义（电子版）31DiscreteMathematics离散数学讲义（电子版）第四章

函数32第四章2第四章函数本章包括以下内容：4-1函数的概念4-2逆函数和复合函数4-4基数的概念4-5可数集与不可数集4-6基数的比较33第四章函数本章包括以下内容：4-1函数的概念3在这里把函数看作一种特殊关系。定义：设X，Y为任意两个集合，f是X到Y的关系，若对于每一个xX，有唯一的yY，使得〈x,y〉f，称关系f为函数（或映射），记作f：X

Y其中，x称为自变元，y称在f作用下x的象。〈x,y〉f也可记作y=f(x)，且记f(X)={f(x)|xX}4-1函数的概念注：函数与关系的区别（1）函数的定义域是X，而不能是X的某个真子集（2）一个xX只能对应唯一一个y34在这里把函数看作一种特殊关系。4-1函数的概念注：函数与关在〈x，y〉f中，f的前域即domf=X，f的值域ranfY，有时也记作Rf。Rf={y|(x)(xX)(yY)}集合Y称为f的共域，ranf称为函数的象集合。4-1函数的概念（续）定义：设函数f：AB，g：CD，如果A=C，B=D，且对所有xA和yC，有f(x)=g(x)，则称函数f和g相等，记作f=g注：XY的子集并不能都成为X到Y的函数。我们用YX表示从X到Y的所有函数的集合，当X和Y是无限集时也可用这个符号。35在〈x，y〉f中，f的前域即domf=X，f的值域ra定义：对于f：XY的映射中，如果ranf=Y，即Y的每一个元素是X中一个或多个元素的象点，则称这个映射为满射（或到上映射）。即对于任意yY，必存在xX使得f(x)=y成立。4-1函数的概念（续）定义：从X到Y的映射中，X中没有两个元素有相同的象，则称这个映射为入射。定义：从X到Y的映射，若既是满射，又是入射，则称这个映射为双射。36定义：对于f：XY的映射中，如果ranf=Y，即Y的4-1函数的概念（续）定理：设X，Y为有限集，若X和Y的元素个数相同，即|X|=|Y|，则f：XY是入射当且仅当它是满射。证明：若f是入射，则|X|=|f(X)|，由于f(X)Y，又因为|f(X)|=|Y|，而Y中的元素是有限的，因此f(X)=Y，即f是满射。若f是满射，则f(X)=Y，于是|X|=|Y|=|f(X)|。因为|X|=|f(X)|，且X是有限的，故f是一个入射。注：这个定理必须在有限集情况下才成立。374-1函数的概念（续）定理：设X，Y为有限集，若X和Y的元4-2逆函数和复合函数定理：设f：XY是双射函数，那么fc：Y

X也是双射函数。证明：设f={〈x,y〉|(xX)(yY)(f(x)=y)}fc={〈y,x〉|〈x,y〉f}因为f是满射，故对每一个yY，必存在〈x,y〉f，则〈y,x〉fc，即fc的前域为Y。又因为f是入射，对每一个yY，恰有一个xX，使得〈x,y〉f。因此仅有一个xX使得〈y,x〉fc，即y对应唯一的一个x，故fc是函数。又ranfc=domf=X，故fc是满射。若y1y2，有fc(y1)=fc(y2)，因为fc(y1)=x1，fc(y2)=x2，即x1=x2，故fc(y1)=fc(y2)，即y1=y2，得到矛盾。因此fc是双射函数。384-2逆函数和复合函数定理：设f：XY是双射函数，那4-2逆函数和复合函数（续）定义：设f：XY是一个双射函数，称YX的双射函数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：XY，g：WZ，若f(X)W，则gf={〈x,z〉|(xX)(zZ)(y)(yYy=f(x)z=g(y))}，称g在函数f的左边可复合。定义：设f：XY，g：YZ，则gf={〈x,z〉|(xX)(zZ)(y)(yYy=f(x)z=g(y))}，称为复合函数，或gf为g对f的左复合。394-2逆函数和复合函数（续）定义：设f：XY是一个双定理：两个函数的复合是一个函数。证明：设g：WZ，f：XY，为左复合，即f(X)W。4-2逆函数和复合函数（续）（1）对任意的xX，因为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〉，且z1z2，则在Y中必存在y1和y2，满足在f中有〈x,y1〉和〈x,y2〉，在g中有〈y1,z1〉和〈y2,z2〉，因为f是一个函数，故y1=y2。于是g中有〈y1,z1〉和〈y2,z2〉，但g是一个函数，故z1z2，即每个xX，只能有唯一的〈x,z〉gf。40定理：两个函数的复合是一个函数。证明：设g：WZ，f：X定理：令gf为复合函数。（1）若g和f为满射，则gf为满射。（2）若g和f为入射，则gf为入射。（2）若g和f为双射，则gf为双射。证明：（1）设f：XY，g：YZ，令z为Z的任意元素，因为g是满射，故必有某个元素y

Y，使得g(y)=z。又因为f是满射，故必有某个元素x

X，使得f(x)=y。故而gf(x)=g(f(x))=g(y)=z因此，Rgf=Z，gf是满射。4-2逆函数和复合函数（续）41定理：令gf为复合函数。证明：4-2逆函数和复合函数（2）设x1，x2为X的元素，假定x1

x2，因为f是入射，故f(x1)f(x2)。又因为g是入射，且f(x1)f(x2)，故g(f(x1))g(f(x2))，即x1x2gf(x1)gf(x2)，因此gf是入射。（3）因为g和f是双射，根据（1）（2），gf为满射和入射，则gf为双射。4-2逆函数和复合函数（续）例2：设R为实数集合，对xR，有f(x)=x+2，g(x)=x-2，h(x)=3x。求gf与h(gf)注：一般有h(gf)=(hg)f，即函数的复合是可结合的。因此可以将括号去掉。解：gf={〈x,x〉|xR}h(gf)={〈x,3x〉|xR}42（2）设x1，x2为X的元素，假定x1x2，因为f是入4-2逆函数和复合函数（续）定义：函数f：XY称作常函数，如果存在某个y0Y，对于每个xX，都有f(x)=y0，即f(X)={y0}。定理：若函数f：XY有逆函数f-1：YX，则f=fIx=Iyf。定理：若函数f：XY有逆函数f-1：YX，则f-1f=Ix，ff-1=Iy证明：f-1f与Ix的定义与均为X。因为f为一一对应的函数，因此f-1也为一一对应。若f：xf(x)，则f-1(f(x))=x，得到f-1f=Ix，故xXf-1f(x)=

f-1(f(x))=x定义：如果Ix={〈x,x〉|xX}，则称函数Ix：XX为恒等函数。434-2逆函数和复合函数（续）定义：函数f：XY称作常4-2逆函数和复合函数（续）定理：若f：XY是一一对应的函数，则(f-1)-1=f。证明：（1）因为f为一一对应的，因此f-1也为一一对应。则(f-1)-1也是一一对应的。显然domf=dom(f-1)-1=X。（2）xXf：xf(x)f-1：f(x)x(f-1)-1：xf(x)。得证(f-1)-1=f。444-2逆函数和复合函数（续）定理：若f：XY是一一对4-2逆函数和复合函数（续）定理：若函数f：XY，g：Y

X均为一一对应的函数，则(g

f)-1=f-1g-1证明：（1）因为f，g为一一对应的函数，因此f-1，g-1存在，且f-1：YX，g-1：ZY，所以f-1g-1：ZX。又，f，g为双射，故gf为双射，因此(gf)-1存在且(gf)-1：ZX。dom(f-1g-1)=dom(gf)-1=Z（2）对任意zZ存在唯一yY，使得g(y)=z存在唯一xX，使得f(x)=z，故(f-1g-1)(z)=(f-1(g-1(z))=f-1(y)=x。但(gf)(x)=g(f(x))=g(y)=z，故(gf)-1(z)=x，因此对任意zZ，有(gf)-1(z)=(f-1g-1)(z)。可知(gf)-1=(f-1g-1)。454-2逆函数和复合函数（续）定理：若函数f：XY，g4-4基数的概念定义：给定集合A的后继集定义为集合：A+=A∪{A}若A为空集，则后继集为+，(+)+，((+)+)+，…这些集合可写成如下形式：∪{}，∪{}∪{∪{}}，∪{}∪{∪{}∪{∪{}}}，…并可简化成{}，{,{}}，{,{},{,{}}，…若命名集合=0，则+=0+={}=1；1+={,{}}=2；2+={,{},{,{}}=3；…这样就得到了自然数集合{0,1,2,3,…}464-4基数的概念定义：给定集合A的后继集定义为集合：若A为Peano公理：（1）0N，（其中0=）（2）如果0N，则n+N（其中n+=n∪{n}）（3）如果一个子集SN具有性质：（a）0S（b）如果nS，有n+S则S=N注：4-4基数的概念（续）1）性质（3）称极小性质，指明了自然数系统的最小性。即自然数系统是满足公理（1）（2）的最小集合。2）自然数也可不从0开始，只需定义=1即可。47Peano公理：注：4-4基数的概念（续）1）性质（3）称定义：给定两个集合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<x<1)}证明SP。证明：令f：PS，f(x)=tg-1x/p+1/2(-∞<x<∞)显然f的值域是S，且f是双射函数。48定义：给定两个集合P与Q，如果我们对P中每个不同元素，与Q中4-4基数的概念（续）定理：在集合族上等势关系是一个等价关系。证明：设集合族为Sa）对任意的AS，必有AAb）若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+max{f(0),f(1),…,f(n-1)}，那么kN，但对每一个x{0,1,…,n-1}，有f(x)k。因此f不能是满射函数，即f也不是双射函数。因为n和f都是任意的，故N是无限的。494-4基数的概念（续）定理：在集合族上等势关系是一个等价关4-4基数的概念（续）定义：所有与集合A等势的集合所组成的集合，叫做集合A的基数。例如：A={a,b,c}，B={{,{},{,{}}}，C={桌子，灯泡，教室}，…，ABC，即K[A]=K[B]=K[C]={A,B,C,…}。注：（1）可见，有限集合的基数就是其元素的个数，记为K[A]（2）有限集合的基数就是其元素的个数。约定：空集的基数为0。（3）如果两个集合能够建立双射函数，则两个集合元素间一一对应，该两个集合具有相同的基数。504-4基数的概念（续）定义：所有与集合A等势的集合所组成的4-4基数的概念（续）例3：证明区间[0,1]与(0,1)基数相同。证明：设集合A={0,1,1/2,…,1/n,…}，A[0,1]定义f：[0,1](0,1)使得则f是双射。514-4基数的概念（续）例3：证明区间[0,1]与(0,1)4-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={a1,a2,…,an,…}的形式。证明：若A可排成上述形式，则将A的元素an与足标n对应，就得到A与N之间的一一对应，故A是可数集。反之，若A为可数集，那么在A与N之间存在一种一一对应关系f，由f得到n的对应元素an，即A可写为{a1,a2,…,an,…}的形式。524-5可数集与不可数集定义：与自然数集合等势的任意集合称为4-5可数集与不可数集（续）定理：任意无限集必含有可数子集。证明：设A为无限集，从A中取出一个元素a1，因为A是无限的，所以从A-{a1}中可取元素a2，继而可从A-{a1,a2}中取一元素a3，如此继续，可得到可数子集A。定理：任意无限集必与其某一真子集等势。证明：设M为无限集，则含有可数子集A={a1,a2,…}，设M-A=B，我们定义集合M到其真子集的映像：f：MM-{a1}使得f(an)=an+1(n=1,2,…)且对于任意bB，有f(b)=b，这个f是双射的。534-5可数集与不可数集（续）定理：任意无限集必含有可数子集4-5可数集与不可数集（续）定理：可数集的任何无限子集是可数的。证明：设A为可数集，BA为一无限子集，将A的元素排成a1,a2,…,an,…，从a1开始，向后检查，不断删去不在B中的元素，则得到新的一列与自然数一一对应：ai1,ai2,…,ain,…，故B是可数的。定理：可数个两两不相交的可数集合的并集，仍然是一可数集。证明：设可数个可数集表示为：S1={a11,a12,…,a1n,…}；S2={a21,a22,…,a2n,…}；…令S=S1∪

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