离散数论-函数.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2001.10,*,函 数,离 散 数 学,函 数,李 舟 军,主要内容,1.,部分函数,2.,函数的合成,3.逆函数,4.特征函数,5.基数,6.基数算术,2001.10,2,函 数,函数（映射）：一个集合和另外一个集合之间的联系。,一个集合中的每个元素都对应有另一个集合中,唯一,的一个元素。,函数是一种 特殊的关系,2001.10,3,函 数,3.1 部 分 函 数,2001.10,4,函 数,部分函数,目的：,理解各种部分函数、限制和延拓的概念；掌握根据部分函数概念进行证明的方法；,重点：,各种部分函数的概念、基于概念的证明方法；,难点：,各种部分函数概念的理解。,2001.10,5,函 数,部分函数,如果从集合,X,到集合,Y,的二元关系,f,是“,单值,”的，,即,f,满足以下条件：,若,x，y,1,f,且,x，y,2,f，,则,y,1,=y,2,。,就称,f,为从,X,到,Y,的,部分函数,。,当,x，yf,时，称,y,为,f,在,x,处的值，记为,y=f(x)。,2001.10,6,函 数,定义域、值域,部分函数,f,的定义域,dom,f：,dom,f =xx X,且有,y Y,使,y=f(x),f,若,x,dom,f，,就称,f,在,x,处有定义，记为“,f(x)”；,否则称,f,在,x,处无定义，记为“,f(x)”，,显然,dom,f,X。,部分函数,f,的值域,ran f：,ran f =yy Y,且有,x X,使,f(x)=y,f,显然,ran f,Y。,2001.10,7,函 数,例子,exp =|x,R,arcsin,=|x，y,R,且,sin y=x,不是部分函数,2001.10,8,函 数,特殊的部分函数,设,f,为从集合,X,到集合,Y,的,部分函数,。,若,dom,f=X，,则称,f,为从,X,到,Y,的,全函数,，简称,f,为,从,X,到,Y,的（,全,）函数，记为,X Y,或,f：XY。,若,dom,f,X，,则称,f,为从,X,到,Y,的,严格,部分函数。,若,ran f=Y，,则称,f,为从,X,到,Y,上,的部分函数。,若,ran f,Y，,则称,f,为从,X,到,Y,内,的部分函数。,若对任意的,x,1,，x,2,dom,f，,当,x,1,x,2,时 皆有,f(x,1,)f(x,2,)，,则称,f,为从,X,到,Y,的,1-1,部分函数。,（即，,当,f(x,1,)=f(x,2,),时 皆有,x,1,=x,2,）,2001.10,9,函 数,f,=,|,x,R,例子,R,到,R,内 1-1（全）函数,2001.10,10,函 数,象、原象,设,f,为从集合,X,到集合,Y,的,部分,函数，,A,X,且,B,Y。,令,f A =y,有,x A,使,y=f(x),f,1,B =x,有,y B,使,f(x)=y,称,f A,为,A,在,f,下的,象,，,f,1,B,为,B,在,f,下的,原象,。,即，,f A =f(x)x A,且,f(x),f,1,B =xx X,使,f(x),且,f(x),B,2001.10,11,函 数,限制、延拓,设,f,为从集合,X,到集合,Y,的部分函数且,A,X。,定义,f,在,A,上的,限制,f,A,为从,A,到,Y,的部分函数，并且,f,A=f (AY),也称,f,为,f,A,到,X,上的,延拓,。,2001.10,12,函 数,定理3.1.1,设,f,为从集合,X,到集合,Y,的部分函数。,若,A,1,A,2,X，,则,f A,1,f A,2,；,若,B,1,B,2,Y，,则,f,1,B,1,f,1,B,2,；,若,A,dom,f，,则,A,f,1,f A；,若,B,ran f，,则,B=f f,1,B。,2001.10,13,函 数,证明：,i),和,ii),显然，只证,iii),和,iv),若,x A，,因为,A,dom,f，,所以,f(x),且,f(x)f A，,所以,x f,1,f A 。,若,yB，,则,yran f（,因为,B,ran f）。,因此，有,xX,使,y=f(x)。,从而得,xf,1,B。,这表明,yf f,1,B 。,另一方面，若,yf f,1,B，,则有,xf,1,B,使,f(x)=y，,所以,y B。,2001.10,14,函 数,定理3.1.2,设,f,为从集合,X,到集合,Y,的部分函数，,(,X)，,(Y)。,f,=,f AA,；,若,，则,f,f AA,；,f,1,=f,1,B B,；,若,，,则,f,1,=,f,1,BB,。,2001.10,15,函 数,证明：,只证,iv)，,其它的证明与此类似。,若,B,，,则由,B,得：,f,1,f,1,B,从而得：,f,1,f,1,BB,；,另一方面，任取,x f,1,BB,，,若,B,，,则,x f,1,B，,即,f(x)B。,因此：,f(x),，,即,x f,1,。,故有：,f,1,BB,f,1,。,2001.10,16,函 数,定理3.1.3,若,f,为从集合,X,到集合,Y,的部分函数且,A,X，,则,dom,(f,A)=A,dom,f，,ran(f,A)=,f,若,A,dom,f,，,则,f,A,是全函数。,2001.10,17,函 数,A,到,B,的全函数集,设,A,和,B,为任意二集合，记,B,A,=ff：AB。,（f,为,A,到,B,的全函数）,2001.10,18,函 数,例子,设,A,为任意集合，,B,为任意,非空,集合。,因为存在唯一的一个从,到,A,的函数，所以,A,=,；,因为不存在从,B,到,的函数，所以,B,=,。,？,是否存在从,B,到,的,部分,函数？,2001.10,19,函 数,定理1.1.4,设,A,和,B,都是有限集，则,n(B,A,)=(n(B),n(A),。,证明：,对,n(A),用归纳法。,2001.10,20,函 数,作业,习题3.1,5.,6.,7.,8.,2001.10,21,函 数,3.2 函数的合成,2001.10,22,函 数,函数的合成,目的：,理解函数合成的概念；了解函数合成与关系合成的区别和联系；掌握满射、内射、双射和逆的证明和书中的相关定理；,重点：,函数合成与关系合成的区别和联系、满射、内射和双射的相关性质和证明思路；,难点：,满射、内射和双射的证明。,2001.10,23,函 数,关系的合成,函数的合成,2001.10,24,函 数,定理3.2.1,设,f,为从,X,到,Y,的部分函数，,g,为从,Y,到,Z,的部分函数，则合成关系,f,o,g,为从,X,到,Z,的部分函数。,证明：,若,x，z,2,x，z,1,f,o,g，,则有,y,1,y,2,Y,使,x，y,1,，x，y,2,f,且,y,1,，z,1,，y,2,，z,2,g。,因为,f,是部分函数，所以,y,1,=y,2,。,但,g,也是部分函数，所以又有,z,1,=z,2,，,这表明,f,o,g,是一个从,X,到,Z,的部分函数。,2001.10,25,函 数,合成,设,f,为从,X,到,Y,的部分函数，,g,为从,Y,到,Z,的部分函数，则称合成关系,f,o,g,为,f,与,g,的,合成函数,，并用,g,o,f,表示。,2001.10,26,函 数,*合成函数,g,o,f,与合成关系,f,o,g,表示同一个集合。,这种差异是历史形成的，具有其方便之处：,(,g,o,f,)(x)=g(f(x),当,f,o,g,时，必有,y,Y,使,f,且,g。,2001.10,27,函 数,定理3.2.2,设,f,为从,X,到,Y,的部分函数，,g,为从,Y,到,Z,的部分 函数。,dom,(,g,o,f,)=f,1,dom,g,且,ran(,g,o,f,)=g ran f 。,若,f,和,g,都是全函数，则,g,o,f,也是全函数。,证明：,参见,P62,2001.10,28,函 数,定理3.2.3,设,f,是从,X,到,Y,的部分函数，,g,是,Y,到,Z,的部分函数，,h,是,Z,到,W,的部分函数，则,h,o,(g,o,f)=(h,o,g),o,f。,（,这是定理2.4.1中,vii),的特例）,2001.10,29,函 数,恒等函数,集合,A,上的,恒等函数,：,II,A,=,x，x,x,A ,。,2001.10,30,函 数,定理3.2.4,设,f,是从,X,到,Y,的部分函数，则,f,o,II,X,=f=II,Y,o,f,。,2001.10,31,函 数,内射、满射和双射,设,f：XY，,若,ran f=Y，,则称,f,为,满射,。,若,f,是1-1的，则称,f,为,内射,。,若,f,既是满射，又是内射，则称,f,为,双射,。,2001.10,32,函 数,设,R,为集合,A,上的,等价,关系，则,x，x,R,x A,是从,A,到,A,/,R,的满射，并称,为,自然映射,。,例子,2001.10,33,函 数,设,f：X Y,和,g：Y Z,若,f,和,g,都是满射，则,g,o,f,也是满射；,若,f,和,g,都是内射，则,g,o,f,也是内射；,若,f,和,g,都是双射，则,g,o,f,也是双射。,定理3.2.5,2001.10,34,函 数,证明：,i)ran(g,o,f),|,定理3.2.2,g ran f,|f,满射,g Y,|g,满射,Z,2001.10,35,函 数,ii),若,x,1,，x,2,X,且,x,1,x,2,f,内射,f(x,1,),f(x,2,),g,内射,g(f(x,1,),g(f(x,2,),即(,g,o,f)(x,1,),(g,o,f)(x,2,),故,g,o,f,为内射,2001.10,36,函 数,设,f：X Y,和,g：Y Z,若,g,o,f,是满射，则,g,是满射；,若,g,o,f,是内射，则,f,是内射；,若,g,o,f,是双射，则,g,是满射且,f,是内射。,规则：,左,满 右内,定理3.2.6,2001.10,37,函 数,证明：,i),显然,ran g,Z,又：,ran f,Y,g ran f,g Y,=,ran g,而：,g ran f =ran(g,o,f)（,定理3.2.2）,且,：ran(g,o,f)=Z （g,o,f,满射）,所以：,Z,ran g,因此：,Z=ran g，,即,g,为满射。,2001.10,38,函 数,ii),反证法。,假设,f,不是内射，则有,x,1,x,2,X,且,x,1,x,2,使,f(x,1,)=f(x,2,)。,因此 (,g,o,f)(x,1,)=g(f(x,1,)=g(f(x,2,)=(g,o,f)(x,2,)，,这与,g,o,f,为内射矛盾。,所以假设不成立，即,f,为内射。,2001.10,39,函 数,作业,习题3.2,3.,a)、c)、e),5.,6.,9.,2001.10,40,函 数,3,.3 逆 函 数,2001.10,41,函 数,逆函数,目的：,了解逆函数的概念；掌握函数逆的证明及相关定理；,重点：,函数逆的相关性质和证明思路；,难点：,函数逆的相关证明。,2001.10,42,函 数,关系的合成,函数的合成，那么,关系的逆,函数的逆？,2001.10,43,函 数,例子,设,f：,I,I,，f =|i,I,则,f,1,=,|i,N,（,关系的逆）,显然，,f,1,，,所以，关系,f,1,不是部分函数。,故 不能把,逆函数,直接定义为,逆关系,。,2001.10,44,函 数,左逆、右逆、逆,设,X,和,Y,为二集合且,f：X Y。,若有,g：Y X,使,g,o,f=II,X,，,则称,f,为左可逆的，并称,g,为,f,的一个左逆函数，简称,左逆,。,若有,g：Y X,使,f,o,g=II,Y,，,则称,f,为右可逆的，并称,g,为,f,的一个右逆函数，简称,右逆,。,若有,g：Y X,使,g,o,f =II,X,且,f,o,g=II,Y,，,则称,f,为,可逆的，并称,g,为,f,的一个逆函数，简称,逆,。,2001.10,45,函 数,一个函数的左逆、右逆和逆不一定存在。即使存在，也不一定唯一。,2001.10,46,函 数,定理3.3.1,设,X,和,Y,为二集合 且,X,，,则,f：X Y,为左可逆的,iff,f,为内射。,证明思路：,2001.10,47,函 数,证明：,若,f,为左可逆的，则有,g：YX,使,g,o,f =II,X,从而由定理3.2.6 的,ii),知道，,f,为内射。,反之，若,f,为内射，则,f,的逆关系,f,1,是从,Y,到,X,的部分函数。因为,X,，,故有,a X。,令,g =f,1,(Y ran f)a,则,g,为从,Y,到,X,的函数 且,g,o,f =II,X,，,这表明,g,是,f,的一个 左逆，即,f,为左可逆的。,2001.10,48,函 数,定理3.3.2,设,X,和,Y,为二集合，则,f：X Y,为右可逆的,iff,f,为满射。,证明：,）,若,f,为右可逆的，则有,g：Y X,使,f,o,g=II,Y,，,从而由定理3.2.6 的,i),知道，,f,为满射。,）,另一方面，设,f,为满射。,i),当,X=,时，因,f,为满射，则,Y=ran f=,，,此时定理显然成立。,ii),当,X,时，因,f,为函数，则,Y,。,对每个,y Y，,令：,S,y,=xxX,且,f(x)=y,则,S,y,y Y,就是,X,的一个划分。对每个,y Y，,都任意取定,S,y,中,唯一的一个元素,x,y,，,显然,f(,x,y,)=y。,并令,g =y，,x,y,y Y,则,g,显然是一个从,Y,到,X,的全函数 且,f,o,g =II,Y,。,这表明,g,是,f,的一个右逆，即,f,为右可逆的。,2001.10,49,函 数,定理3.3.3,设,X,和,Y,为二集合，若,f：XY,既是左可逆的，又是右可逆的，则,f,是可逆的，且,f,的左逆和右逆都等于,f,的唯一逆。,证明：,设,g,1,o,f=II,X,，f,o,g,2,=II,Y,。,则,g,1,=g,1,o,II,Y,=g,1,o,(f,o,g,2,)=(g,1,o,f),o,g,2,=II,X,o,g,2,=g,2,令,g=g,1,，,则,g,即为,f,的逆。,唯一性的证明 类似。,2001.10,50,函 数,逆函数,设,X,和,Y,为二集合。若,f,：,X,Y,为可逆的，,则,f,的,逆函数,用,f,1,表示。,2001.10,51,函 数,定理3.3.4,若,X,和,Y,为二集合 且,f：X Y，,则下列条件等价：,f,是双射；,f,既是左可逆的，又是右可逆的；,f,是可逆的；,f,的逆关系,f,-1,即为,f,的逆函数。,2001.10,52,函 数,证明：,i)ii)iv),（,定理3.3.1+3.3.2）,（定理3.3.3）,（定理3.3.1+3.3.2）,ii)iii)i),iii),iv),f,是可逆的,f,-1,o,f=II,X,，f,o,f,-1,=II,Y,。（f,-1,为,f,的逆函数）,f,为双射,f,-1,（,逆关系）是函数且为,f,的一个逆,又,f,的逆函数唯一,f,-1,（,逆关系）即为,f,-1,（,逆函数）,2001.10,53,函 数,定理3.3.5,若,f：X Y,和,g：Y Z,都是可逆的，则,g,o,f,也是可逆的，,且(,g,o,f),-1,=f,-1,o,g,-1,。,证明：,(,g,o,f),o,(f,-1,o,g,1,)=g,o,(f,o,f,1,),o,g,-1,=g,o,II,Y,o,g,1,=g,o,g,1,=II,Z,同理(,f,-1,o,g,1,),o,(g,o,f)=II,X,故,g,o,f,是可逆的，并且(,g,o,f),-1,=f,-1,o,g,-1,。,2001.10,54,函 数,作业,习题3.3,3.,4.,5.,2001.10,55,函 数,3.4 特征函数,2001.10,56,函 数,特征函数,目的：,理解特征函数的概念；掌握利用特征函数证明集合关系的方法；,重点：,利用特征函数证明集合关系的方法。,2001.10,57,函 数,特征函数：确定集合和集合之间的关系的函数。,2001.10,58,函 数,特征函数,设,U,为全集，,A,U，,A,为如下定义的从,U,到 0，1 的函数：,A,(,x,)=,称,A,为集合,A,的特征函数。,2001.10,59,函 数,记号,设,f，g：X,R。,f g：,x X，f(x)g(x),f+g：X R，,xX，(f+g)(x)=f(x)+g(x),f,g：X R，,xX，(f,g)(x)=f(x),g(x),f*g：X R，,xX，(f*g)(x)=f(x)*g(x),2001.10,60,函 数,0：,U,0,1|x,U,1：U,0,1|x,U,特征函数的一些重要性质：参见,P68,2001.10,61,函 数,例子,试证明：(,AB)=AB。,证明：,(,AB),=1-,AB,=1-,A,-,B,+,A,*,B,AB,=,A,*,B,=(1-,A,)*(1-,B,)=1-,A,-,B,+,A,*,B,所以,(,AB),=,AB,从而(,AB)=AB,2001.10,62,函 数,作业,习题3.4,1.,8),10),2.,a),c),2001.10,63,函 数,3.5 基 数,2001.10,64,函 数,基数,目的：,理解基数的概念；掌握抽屉原则的运用方法、基数和可列集的证明；,重点：,抽屉原则的运用方法、基数和可列集的证明；,难点：,抽屉原则的运用方法、基数和可列集的证明。,2001.10,65,函 数,比较两个集合的大小：,1 计数法：先数出它们的元素个数，再加以比较。,2 愚人比宝法：每次各取一，看哪个最后取完。,对无限集，方法 1 失效。,什么叫做数一个集合中元素个数？,在该集合与某个自然数之间建立一个双射。,2001.10,66,函 数,等势,设,A,和,B,为二集合，若存在从,A,到,B,的双射，,则称,A,和,B,对等,，或称,A,和,B,等势,，记为,A B。,2001.10,67,函 数,有限集、无限集,设,A,是集合，如果存在,n,N,使,A,n,，,则称,A,为,有限集,，否则称,A,为,无限集,。,2001.10,68,函 数,定理3.5.1,（鸽笼原理、抽屉原理）,任何,有限集,都不能与它的,真子集,对等。,这个定理也叫,抽屉原理,，可通俗表述为：,“如果把,n+1,本书放进,n,个抽屉里，至少在一个抽屉里有两本或两本以上的书。”,2001.10,69,函 数,用途,：解决组合数学中的问题。,2001.10,70,函 数,例子,把,s,个元素分成,t,个组，当不能均匀分放时，必有一个组其元素个数要超出“平均数”。,形式地叙述为：,定理,：,s,（,s,1,）,个元素分成,t,个组，那么,必,存在一个组至少含有,s/t,（,这里,为“上整数”记号）个元素。,2001.10,71,函 数,证明：,反证法,假设每个组至多含有（,s/t-1）,个元素，则,t,个组共有,t（s/t-1）,元素。,因为,s/t s/t(s/t)+1，,所以有,t（s/t-1）,k,j,，,则有,k,i,/,k,j,=2,ai,aj,为正整数，因此,k,i,是,k,j,的倍数。,2001.10,74,函 数,抽屉原则对于无限集并不成立。,例：如果,a，b,R,，a b，,则(,a，b),R,。（,构造法）,证：定义,f：(a，b),R,如下：,x(a，b)，,令,f(x)=,tg,(x-(a+b)2)(b-a),，,（-/2,/2）,显然，,f,是双射，所以(,a，b),R,。,*,任何无限集都如此，这正是无限集与有限集之间的,本质区别,，也可以把它作为无限集的定义。,2001.10,75,函 数,集合的基数,我们现在拓广集合中含有的元素个数这一概念，引进集合的,基数,的概念。,A：(A)（，card(A),或,A）,显然，每个,有限集,都与唯一的,自然数,对等,。,设,n,N,，,若,A n，,则令#(,A)=n。,对于无限集的基数，我们规定特殊的记号，例如令,#(,N,)=,0,是希伯来语的第一个字母，念作阿列夫。,2001.10,76,函 数,设,A,和,B,为二集合。,如果,AB，,就称,A,和,B,的基数,相等,，记为#(,A)=#(B)。,如果存在从,A,到,B,的,内射,，就称,A,的基数,小于等于,B,的基数，记为#(,A)#(B)，,或称,B,的基数,大于等于,A,的基数，记为#(,B)#(A)。,如果#(,A)#(B),且#(,A)#(B)，,就称,A,的基数,小于,B,的基数，记为#(,A)#(A)。,基数相等和大小顺序,2001.10,77,函 数,设,A,和,B,为任意两个集合，则,#(,A)#(B),和#(,B)#(A),二者之中至少有一个成立。,（证明要用,选择公理,）,任何两个基数都可以比较大小,2001.10,78,函 数,设,A、B,和,C,为三集合。则有,#(,A)=#(A)；,若#(,A)=#(B)，,则#(,B)=#(A)；,若#(,A)=#(B),且#(,B)=#(C)，,则#(,A)=#(C)。,基数的相等关系“,=,”是等价关系,2001.10,79,函 数,设,A，B,和,C,为三集合，则有,#(,A)#(A)；,若#(,A)#(B),且#(,B)#(A)，,则#(,A)=#(B)；,若#(,A)#(B),且#(,B)#(C)，,则#(,A)#(C)。,基数的小于等于关系“”是半序,2001.10,80,函 数,与,N,对等的集合称为,可列集,或,可数集,。,可列集,2001.10,81,函 数,以下三个条件等价。,A,为无限集；,A,有可列子集；,A,有与它对等的真子集。,定理3.5.5,2001.10,82,函 数,i),ii),设,A,为无限集，取,a,0,，对每个,nN，,若,a,0,a,1,a,n,A，,必有,a,n+1,A,且,a,n+1,a,0,a,1,a,n,。,因此，,B=,a,i,i N,即为,A,的可列子集。,ii),iii)（,构造法）设,B,是,A,的可列子集。因为,BN，,故有双射,f：N B。,取,C=A-f(0)，,并令,g：A C,使得,显然，,g：AC,是双射。所以,A,与它的真子集,C,对等。,iii),i),抽屉原则加反证法。,2001.10,83,函 数,#(,B),#(A),iff,存在从,A,到,B,的满射。,证明：,i),设,f：AB,为满射，则,f,有右逆,g：BA,使得,f,o,g=II,B,，,因为,II,B,是内射，所以,g,是内射，故#(,B)#(A)。,ii),若#(,B)#(A)，,则有内射,g：BA，g,有左逆,f：AB,使得,f,o,g=II,B,。,因为,II,B,是满射，所以,f,是满射。,定理3.5.6,2001.10,84,函 数,对每个集合,A,，,皆有,#(,A)#,(A),。,定理3.5.7,（,基数的个数也是无限的，且无最大者,）,证明,：,i),定义,g：A,(A),为,g(a)=a,显然,g,是,内射,，所以#(,A)#,(A)。,ii),用反证法来 证明#(,A)#,(A),2001.10,85,函 数,假设#(,A)=#,(A)，,则有双射,f：A,(A)。,令,B =aa A,且,a,f(a),则,B,(A)。,因,f,为双射，故有,tA,使,f(t)=B,。,（1）若,tB，,按,B,的定义，,t,f(t)，,即,t,B；,（2）若,t,B，,即,t,f(t)。,而按,B,的定义，,tB。,总之，,tB,当且仅当,t,B。,这是一个矛盾。,故假设有误，所以必有#(,A)#(,(A)。,由,i),和,ii),知，#(,A)#,(A)。,2001.10,86,函 数,#,(,N,),记为,2001.10,87,函 数,例：证明#(,R,)=,。,为此只需证明,#,(,N,),=,#,(,0，1 ),例：,N,N,是可列集。,构造法。定义,：,N,N,N,为,(,n,m)=(n+m)(n+m+1)/2+n,例：#(,R,R,)=,例子,2001.10,88,函 数,作业,习题3.5,1.,b)，c)，d),4.,6.,7.,8.b),9.,2001.10,89,函 数,3.6 基 数 算 术,2001.10,90,函 数,基数算术,目的：,掌握基数算术；,重点：,基数算术；,难点：,基数算术中构造性的证明；,2001.10,91,函 数,无穷基数、有穷基数、和、积、幂,定义3.6.1,无限集的基数称为,无穷基数,，有限集的基数称为,有穷基数,。,定义3.6.2,（和、积、幂）略,2001.10,92,函 数,定理3.6.1 3.6.3,定理3.6.1,i),和、积交换律,ii),和、积结合律,iii),积对和的分配律,iv),v)vi),幂运算,定理3.6.2,（0、1的和、积、幂）,定理3.6.3,设,为无穷基数，,为基数且,0。,=,max(,，,)；,=max(,，,)。,2001.10,93,函 数,作业,习题3.6,4.,2001.10,94,函 数,