集合论总复习、习题(精品)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,集合论总复习,习题,第二十一讲,1,作业讲评,P86 3-1.(9),设某集合有,101,个元素，试问：,a),可构成多少个子集？,b),其中有多少个子集元素为奇数？,c),是否有,102,个元素的子集？,解：,a),可构成,2,101,个子集,b),有,2,100,个子集元素为奇数,c),不能有,102,个元素的子集,2,(10),设,S = a,1, a,2, ., a,8,由,B,17,和,B,31,所表示的,S,的子集各是什么,?,应如何表示子集,a,1, a,8, ,a,2, a,6,a,7,和,a,3, a,8, a,7,?,B,17,= B,00010001,= a,4, a,8,B,31,= B,00011111,= a,4, a,5, a,6, a,7, a,8,a,1, a,8, = B,10000001,= B,129,a,3, a,7,a,8, = B,00100011,= B,35,a,2, a,6,a,7, = B,01000110,= B,70,作业讲评,P86 3-1.(10),解：,S,有,2,8,= 256,个不同的子集,可表示为,B0, B1, B2, B3, , B255,二进制,下标有,8,位,.,3,a),证明,(1) A(B,C) = (AB),(AC),证明,: (AB),(AC),= (AB) (AC)(AC)(AB),= (AB)(AC)(AC)(AB),=,(AB)C)(AC)B),= A(BC)(CB),= A(,B,C,),作业讲评,P95 3-2.(11),4,作业讲评,P95 3-2.(11),a),证明,(1) A(B,C) = (AB),(AC),证明,: (AB),(AC),= (AB),(AC)(AC),(AB),=,(A(B,C)(A(C,B),= A(,(B C)(C B),),= A(,B,C,),注意：,A(BC),(AB)(AC),5,(2),A(B,C) = (AB),(AC),不一定成立。,证明,:,设,A = 2, 3, B = 1, 4, 7, C = 3, 5,则,B,C = 1, 3, 4, 5, 7,所以,A(B,C) = 1, 2, 3, 4, 5, 7,但,AB = 1, 2, 3, 4, 7,AC = 2, 3, 5,故,(,AB),(AC) = 1, 4, 5, 7,因此,A(B,C) = (AB),(AC),不一定成立。,作业讲评,6,作业讲评,P105 3-4.(3),c),(A,B), (,C,D,) = (A,C),(B, D,),解,:,不成立。,设,A=B,，,C,和,D, ,则左边,=,，,右边,7,作业讲评,P105 3-4.(3),e),证明,(1) ( A,B ),C = (A,C),(B,C),证明,:,对于任意的,(A,B),C,x,(A,B) y,C,(,x,A,x,B,), (,x,A,x,B,) y,C,(,x,Ax,B),y,C) (,x,Ax,B,) y,C),(,(A,C,),(B,C) ),(,(A,C,),(B,C) ),(A,C,)(B,C) ),8,作业讲评,P105 3-4.(3),e),证明,(1) ( A,B ),C = (A,C),(B,C),证明,: ( A,B ),C = (A-B)(B-A),C,=,(A-B),C) (B-A),C),= ( (A,C) -(B,C) ) ( (B,C )-,(A,C) ),= (A,C),(B,C),注意：,A,(B * C) = (A,B) * (A,C),(B * C),A = (B,A) * (C,A),*,代表, ,或,运算,9,作业讲评,P105 3-4. (5),(5),证明 若,X,Y = X,Z,，且,X, ,则,Y=Z,证明：,1,) Y= ,则,X,Y=,故,X,Z =,Z =,，,Y=Z,y ,Z, Y,Z,同理,Y,Z,Y,=,Z,2),Y, ,任意,y,Y,， 令,xX,，,由已知有, ,X,Y= X,Z,10,作业讲评,(5),证明 若,X,Y = X,Z,，且,X, ,则,Y=Z,证明：,X,Y = X,Z,且,X, ,X,Y,X,Z,且,X,Z,X,Y,Y,Z,且,Y,Z,Y,=,Z,(1)A,B,的充分必要条件是,A,C,B,C;,(2) A,B,的充分必要条件是,C,A,C,B,C,是,非空,集合,。,11,作业讲评,补充题,90,名学生，,55,人参加数学小组，,44,人参加语文小组，,33,人参加体育小组。,36,人参加数学和语文小组，,29,人参加数学和体育小组，,25,人参加语文和体育小组。问多少人,3,个小组都没有参加？,1.,|AB| |A| + |B|,2.,|AB| ,min(|A,|, |B|),3.,|A B| |A| |B|,4.,|A,B| = |A| + |B| 2|AB|,12,作业讲评,P113 3-6.(3),举出,A=1,2,3,上的关系,R,的例子，使它有以下性质：,a),既是对称又是反对称的,b),既不是对称又不是反对称的,c) R,是可传递的,解,: a) R, I,A,，,如,R = ,b),部分对称,如,R=, , ,c) R=, , , ,13,作业讲评,P113 3-6. (6),(6),设,R,是,X,上的自反关系。,证明,R,是对称和传递的,当且仅当,a,b,和,在,R,中时，则有,在,R,之中。,任意元素,a,b,c,若,aRb,由自反性得有,aRa,于是有,bRa,故,R,是对称的；,若有,aRb,且,bRc,由对称性得到,bRa,于是有,bRa,且,bRc,故有,aRc,故,R,传递,14,作业讲评,P113 3-6. (6),(6),设,R,是,X,上的自反关系。,证明,R,是对称和传递的,当且仅当,a,b,和,在,R,中时，则有,在,R,之中。,必要性,：,因为,R,为,X,上的等价关系，,所以具有自反性、对称性和传递性。,对于集合,X,上的任意元素,a,b,c,，,若,aRb,且,aRc,由对称性得：,bRa,，,再由传递性得,bRc,。,15,作业讲评,P119 3-7. (3),令,S S,，存在,y,使,S,且,S,S,是传递的,S,S S S,设,S,为,X,上的关系，证明,S,是自反的和传递的，则 ，其逆为真吗？,令,S,，,由自反性知,S, S S,S S S,其逆不真。例如,X=1,，,2,，,3,，,S=,，,，,S S = S,但,S,不是自反的。,16,作业讲评,A relation R on a set A is called circular if,aRb,and,bRc,imply,cRa,. Show that R is reflexive and circular if and only if it is an equivalence relation.,必要性：,R,是自反和循环的,R,是等价关系,令,R,R,是循环的,R,R,对称,令, ,R,，,R,是对称的,R,R,传递,R,是自反的,R,R,是循环的,R,集合,A,上的关系,R,，如果,aRb,且,bRc,蕴含,cRa,，那么就称,R,是,循环的,。,证明：,R,是自反和循环的,当且仅当,R,是等价关系,17,作业讲评,A relation R on a set A is called circular if,aRb,and,bRc,imply,cRa,. Show that R is reflexive and circular if and only if it is an equivalence relation.,充分性,令, ,R,，,R,是对称的,R,R,循环,R,是等价关系,R,是自反,传递,对称的,R,是传递的,R,R,是,等价关系,R,是,自反和循环的,18,作业讲评,Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if,a+d,=,b+c,.,(1) Show that R is an equivalence relation.,(2) Compute A/R,即证：,R,是自反，对称，传递的,a,b,S,，则,A,a+b,=,b+a,R,自反,令,R,，即,a+d,=,b+c,a+f,=,b+e,R,R,传递, c + b= d + a,R,对称,R,令,R,，,R,即,a+d,=,b+c,，,c+f,=,d+e,R,19,作业讲评,Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if,a+d,=,b+c,.,(1) Show that R is an equivalence relation.,(2) Compute A/R,A=,R=, , , , , , , , , , , , , , ,，, , ,20,作业讲评,Let S = 1,2,3,4 and let A = SS. Define the following relation R on A: R if and only if,a+d,=,b+c,.,(1) Show that R is an equivalence relation.,(2) Compute A/R,A/R=, , ,A=, , , , ,21,作业讲评,P146 3-12 (6),(6),设集合,P=x,1, x,2, x,3, x,4, x,5,上的偏序关系如图所示。,找出,P,的最大,(,小,),元素，极大,(,小,),元素。,找出子集,x,2, x,3, x,4,x,3, x,4, x,5,x,1, x,2, x,3,的上,(,下,)(,确,),界,最大元素,x,1,无最小元素,x,5,x,1,x,2,x,3,x,4,极大元素,x,1,极小元素,x,4, x,5,集合,上界,下界,上确界,下确界,x,2, x,3, x,4,x,1,x,4,x,1,x,4,x,3, x,4, x,5,x,1,x,3,无,x,3,无,x,1, x,2, x,3,x,1,x,4,x,1,x,4,22,作业讲评,P146 3-12 (7),(7),下图给出了集合,1,2,3,4,上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。,1,2,4,3,(a),先去环,再去掉传递,最后调整位置,1,2,3,4,(a),23,作业讲评,P146 3-12 (7),(7),下图给出了集合,1,2,3,4,上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。,1,2,3,4,(c),先去环,再去掉传递,最后调整位置,4,2,1,3,24,作业讲评,补充题,设,f,g,h,是实数集,R,上的函数，,f(x)=x+2, g(x)=x-2, h(x)=3x,，求,fg,、,ff,、,gf,、,gg,、,fh,、,hg,、,hfg,fg,(x),= x ff,(x),= x+4,gf,(x),= x gg,(x),= x-4,fh,(x),= 3x+2 hg,(x),= 3x-6,hfg,(x),= h,(x),= 3x,25,作业讲评,P151 4-2.(6),(6),设,A,和,B,是有穷集合，有多少不同入射函数和多少不同的双射函数。,入射,: X,中没有两个元素有相同的象,(1),f: A,B,为入射,必须有,|A|,|B|,即,m,n,设,|A| = m,，,|B| = n,B,中任意选出,m,个元素的任一全排列即为所求,.,满射,: Y,中每一个元素是,X,中的一个或多个元素的象点。,(2),f: A,B,为双射,必须有,|A|,=,|B|,即,m,=,n,所以，共有,m!,个。,26,集合是什么,集合是不能精确定义的基本概念,。,如何,理解,集合：,由共同性质的一些对象汇集而成的整体 。,集合可以是,有限集,，也可以是,无限集,集合的表示方法：,枚举法,叙述法,（列判别条件）,一般用,大写字母,表示集合，用,小写字母,表示元素,见 课本,P82,27,集合与元素的关系,集合与元素的关系：,xA,或,xA,集合元素可以是,离散型,数据（如整型、逻辑型、枚举型等），也可以是,非离散型,数据（如实型）。,有限集一定是离散型数据,，无限集可能是离散型，也可能是非离散型的数据。,本书中默认：,自然数集从,0,开始,（见,P94,，,习题,(3),中对自然数,N,的子集,C,的定义）,28,集合的概念,子集,：,(,x)(x,x,),（,B,包含,A,）,真子集,：,(,x)(x,x,)(x) (xBxA),空集,：不包含任何元素的集合, = x | p(x)p(x),，,p(x),为任何谓词,全集,：,E = x | p(x)p(x),，,p(x),为任何谓词,29,集合的相等,集合,A,、,B,相等,：,A = B, A , B,的元素完全相同,A B,且,B A, ( x ,若,xA,，则,xB ),且,( x ,若,xB,，则,xA ),集合,A,、,B,不等,：,AB, A , B,的元素不完全相同,（,不是完全不同,！,), not (A B),或,not (B A ), ( x , xA,且,x B ),或,( x , xB,且,x A ),30,幂 集,幂集,的概念：,给定集合,A,，,由集合,A,的所有子集,为元素组成的集合，称为,集合,A,的幂集,，记为,P(A),。,若,|A| = n,，,则,|P(A)| = 2,n,如何证明,?,注意,P(,)=,区别：,但, ,。,A=B P(A) = P(B),AB P(A) P(B),31,证明,A,B,当且仅当,P(A),P(B),充分性,:,对,任意,x,A,x,P(A,),x,P(B,),x,B,所以,A,B,必要性,:,对,任意,x,P(A,),x,A,x,B,x,P(B,),所以,P(A),P(B),32,集合之间的关系,子集,：,A,包含,B B,包含于,A,真子集,：,相等,：,A,、,B,的元素完全相同,不等,：,A,、,B,的元素不完全相同,从属,：,（,一个集合是另外一个集合的元素）,33,空集的性质,空集是一切集合的子集。,空集是惟一的。,空集是任何集合的幂集的元素。,空集的幂集不是空集。,34,空集,例题,例,判断下列命题的真假,:,(1),(2),(3),(4),(2),为假,;,其余均为真。,35,集合运算的性质,交换律,AB = BA,AB = BA,AB = BA,结合律,(AB)C = A(BC),(AB)C = A(BC),(AB)C = A(BC),注意：,AB BA,(AB)C A(BC),36,集合运算的性质,分配律,（注意证明方法是典型的，见,P89,，,P91,）,A(BC) = ( AB)(AC),A(BC) = ( AB)(AC),A(BC)= (AB)(AC),P91,定理,但：,A(BC)(AB)(AC),例：,B =,A , C =,时,A(BC) = ( AB)(AC),但：,A(BC)(AB)(AC),例：,B = C , A ,时,37,集合运算的性质,摩根律,(AB) =,A,B,(AB) =,A,B,A (BC) = (A B)(A C),A (BC) = (A B)(A C),吸收律,A(AB) = A = A(AB),其他,AB A AB,AB B AB,38,证明集合相等的方法,往证,A=B,方法一,：,证明：,AB,且,BA,（,P91,定理,3-2.5,的证明方法）,方法二,：,证明满足,A,元素的条件逻辑等价于满足,B,元素的条件,（,P91,定理,3-2.4,的证明方法）,方法三,：,使用集合运算的性质,（,P91,定理,3-2.6,的证明方法）,39,证明集合不等的方法,往证,A B,：,方法一,：,举反例,AB ( x , xA,且,x B ),或,( x , xB,且,x A ),方法二,：,说明（或证明）一个是空集（或全集），另一个不是,方法三,：,画文氏图示意,40,证明集合是空集的方法,方法一,：,其逻辑判断条件是永假,方法二,：,用反证法：设,aA,，,引出矛盾的结果（见,P95,习题,(10)a),的证明）,方法三,：,利用等式，例如：,AA=,41,包含排斥原理,AB=A+B-AB,ABC=A+B+C,-AB-AC-BC,+ABC,见,P96-99,例题,1,、,2,、,3,42,定义序偶,序偶：有序的偶对,序偶与集合的区别：有序,/,无序,若,xy,，,则,，,但,x,y=y,x,序偶与集合的统一：, = x,x,y,序偶相等的定义：,=,x=u,且,y=v,43,集合的笛卡儿乘积,集合,A,、,B,的笛卡儿乘积,A,B =,(x,A),(y,B),见课本,P102,例题,1,44,笛卡儿乘积的性质,AB BA,ABC = (AB)C A(BC),A,n,= AAA (n个A),ABAB,A,n,A,n,A A ,45,笛卡儿乘积的定理,以下定理均可从序偶、集合相等的定义证明：,A(BC)(AB)(AC),(BC)A(B A)(CA),A(BC)(AB)(AC),(BC)A(B A)(CA),若,C ,，,则,AB (AC) (BC) (CA CB),非空集合,A,B,C,D,AB CD A C,且,B D,46,关系的定义,关系,是两个集合的笛卡儿乘积的子集。,本质上,关系,R,是序偶的集合,：,若,R,则记为,xRy,若,R,则记为,xRy,集合,A,到,集合,B,的关系,：,AB,的子集,集合,A,上,的关系,：,AA,的子集,见课本,P106,例题,1,、,2,、,3,47,特殊的关系,恒等关系,I,A, ,x,xxA,是,A,上的关系,全域关系,：,R,AB,空关系,：,R,定理,：,A,到,B,的两个关系的交、并、差、补仍是,A,到,B,的关系,48,关系的表示,集合法,：,列举集合的所有元素（序偶）或判别条件,叙述法,：,叙述关系定义的判别条件；,P107,例,4,矩阵法,：,A,到,B,的关系用,|A|,行,|B|,列的,0,、,1,矩阵表示,图,：,A,到,B,的关系,：用有向偶图表示（点表示集合元素，弧表示序偶）,A,上的关系,： 用有向图表示（点表示集合元素，弧表示序偶）,49,关系的性质,讨论非空集合,A,上,的关系,R,（即,RAA,）,自反性,： ,aA, a, aR,关系图,中每个点都有环,关系矩阵,是对角线元素全部为,1,反自反性,：,aA, a, aR,关系图,中每个点都没环,关系矩阵,是对角线元素全部为,0,50,关系的性质,对称性,： ,a, b A,若,a, bR,，,则,b, aR,关系图,中任意两个不同的点之间要么没有边，要么有双向边；,关系矩阵,是对称矩阵,反对称性,：若,ab,，则,a,bR,或,b,aR,；,或者：,a,bA,若,a,bR,且,b,aR,则,a=b,；,关系图,任意两个不同的点之间要么没有边，要么只有单向边。,关系矩阵,呢？,51,关系的性质,传递性,：,a,b,cA,若,a,bR,且,b,cR,，,则,a,cR,关系图,中任意两个点之间若经过第三点有路接通，则必有直达边,;,关系矩阵,较复杂,52,定义复合关系,设,R,是,A,到,B,的关系，,S,是,B,到,C,的关系，则,R,S,称为,R,和,S,的,复合关系,，表示为,R,S = | xAzC,(,y,)(yBRS),R,表示关系时，,R,n,表示,n,个关系,R,的复合,复合关系是,不可交换的,（没有公共域）,复合关系是,可结合的,。,53,定义逆关系,设,R,是,A,到,B,的关系,， 将,R,中每一序偶元素顺序互换，得到的集合称为关系,R,的,逆关系,，,(,inverse relation),表示为,R,c,= | R,可见，,R,c,是,B,到,A,的关系,。,逆关系保持了关系的性质,：,即保持了原关系的自反性、反自反性、对称性、反对称性、传递性（若原关系有这些性质的话）。见课本,P119,习题（,5,）,54,有关定理,证明两个关系相等，实质上是证明两个集合（元素是序偶）相等,(R,1,R,2,),c,= R,1,c,R,2,c,(R,1,R,2,),c,= R,1,c,R,2,c,(R,1,-R,2,),c,= R,1,c,-R,2,c,(AB),c,= BA,( R,1,R,2,),c,= R,2,c,R,1,c,(R,1,R,2,),R,3,= R,1,(R,2 ,R,3,),R,是对称的 ,R=,R,c,R,是反对称的 ,RR,c,I,x,55,逆关系的性质,逆关系的矩阵,：,原关系矩阵转置之后得到逆关系的矩阵,逆关系的图,：,把弧的方向反转，得到逆关系的图,逆关系,保留了原来关系的自反、反自反、对称、反对称、传递等性质。,56,关系运算后性质的保持,关系运算后性质的保持,运算,性质,自反性,反自反性,对称性,反对称性,传递性,RS,RS,R S,R,c,R S,57,关系的闭包,关系,R,的自反（对称、传递）闭包：,是指包含,R,的、而且是自反的、最小的自反（对称、传递）关系,严格的定义：见课本,P119,如果,R,本身是自反的（对称的、传递的），则其自反的（对称的、传递的）闭包就是,R,自反闭包：,reflexive closure,对称闭包,：,symmetric closure,传递闭包：,transitive closure,58,闭包的讨论,自反闭包,r R RI,x,（,R,是集合,X,上的关系）,对称闭包,s R ,RR,c,传递闭包,t (R) = RR,2,R,n,若,|X| = n,，,则只需前,m,个（,m n,）,关系的并,rs,R ,sr,(R),rt,R ,tr,(R),ts,R ,st,(R),Warshall,算法的实质：简化矩阵运算，此处不要求，“数据结构”课程再讲。,59,定义集合的划分与覆盖,A,为,非空集合，,S=S1,S2,Sm,，,其中,（,1,）,SiA,，,Si(i,=1,2,m),（,2,）,S1S2,Sm,=A,（,3,）当,ij,时，,SiSj,=,S,是,A,的覆盖,S,是,A,的划分,定义的另一种描述：,若把集合,A,分成若干个叫做分块的,非空,子集，使得,A,中每一个元素,至少属于,一个分块，则这些分块的全体叫,A,的一个,覆盖,；若,A,中每一个元素,属于且只属,于一个分块，则这些分块的全体叫,A,的一个,划分,（或分划）。,60,习题解答,P130,习题,(5),(1) (A,i,B),= (A,1,A,2, ,A,k,),B,= A,B,i=1,k,(2) (A,i,B) ,(,A,j,B),= A,i,A,j,B,= ,61,定义等价关系,R,是集合,A,上,的关系，满足自反、对称、传递，则,R,是,A,上的等价关系。,见课本,P131,例题,1,、例题,2,注意：,许多这类题目：给出某些性质，判别是否等价关系,62,定义等价类,R,是,A,上的等价关系，则,等价类 ,a,R, xxA,且,aRx,等价类的性质： ,a, bA,1,） ,a,R,且,a,R, A,2,） ,a, bR a,R, b,R,3,） ,a, bR a,R,b,R,=,4,） ,a,R,aA,是的一个划分，记为（商集）,63,划分和等价关系,1,） 等价关系 ,-,划分,（,P133,定理,3-10.2,，,3-10.3,）,2,）,R,1,=R,2, A/R,1,= A/R,2,（,P134,定理,3-10.4,）,决定,64,定义偏序关系,非空集合,A,上的关系,R,，,满足,自反,、,反对称,、,传递,的性质，称,R,是,A,上的一个,偏序关系,，记为 ：,序偶,A,称作,偏序集,。,见课本,P140,例题,1,、例题,2,65,定义“盖住”,在偏序集中的两个元素,x,和,y,满足以下条件：,x y,xy,x, y,之间没有,z,，使,x z,且,z y,则称,y,盖住,x,见课本,P140,例题,3,对于给定的偏序集,A,，其,盖住关系是确定的、唯一的。,66,哈斯图,Hasse,diagram,回顾：偏序关系的关系图的特点？,哈斯图,：,关系图的简化（省略了自反性、传递性）,使用了“盖住”的性质，作图规则如下：,1,）每个元素用一个小圆点表示；,2,）若元素,y,盖住,元素,x,，则,y,画在,x,上方，并用,直线连接,；,3,）若,x y,且,xy,，则,y,画在,x,之上；若无关系，则两个点可画在同一水平，也可一上一下。,67,作业讲评,P146 3-12 (7),(7),下图给出了集合,1,2,3,4,上的四个偏序关系图,画出它们的哈斯图，并说明哪个是全序关系，哪个是良序关系。,1,2,3,4,(c),先去环,再去掉传递,最后调整位置,4,2,1,3,68,定义链、反链,的,子集,称为：,链,：偏序集的每两个元素都有关系；,(,哈斯图中某条链上的点集,),反链,：偏序集的每两个元素都没有关系,(,哈斯图中若干个没关系的点的集合,),单个元素的子集，既是链，又是反链,（注意：这是约定，不能证明）,问：是否存在非链、非反链的关系？,答：是。如集合,2,3,4,上的整除关系,69,线序关系,在偏序集,A,中，如果,A,是一个链，则称,A,为,全序集合,或,线序集合,，二元关系,称为,全序关系,或,线序关系,。,全序关系 线序关系 哈斯图是一条“链”,全序关系,A,中，,x,yA,，,xy,和,yx,至少有一个成立。,A,上的线序关系 ,A,上的偏序关系,A,上的偏序关系 ,A,上的关系,A,上的关系 ,AA,70,AA,A,上的关系,A,上的偏序关系,A,上的等价关系,线序关系,恒等关系的子集,单个元素,各概念的相互关系,71,极大元 最大元,A,是,偏序集合，且,B,是,A,的子集，对于,B,中的某个元素,b,，若,B,中,没有其他元素,x,，,满足,bx,，则称,b,是,B,的,极大元,。,A,是偏序集合，且,B,是,A,的子集，对于,B,中的某个元素,b,，,若对于,B,中,每个元素,x,，,满足,xb,，,则称,b,是,B,的,最大元,。,72,上界、上确界,A,是,偏序集合，且,B,是,A,的子集，对于,A,中的某个元素,a,，若,对于,B,中,每个元素,x,，,满足,xa,，则称,a,是,B,的,上界,。,注意：上界,不一定,是集合内的点；,A,是偏序集合，且,B,是,A,的子集，,a,是,B,的某一上界，对于,B,中,所有上界,y,，,满足,ay,，,则称,a,是,B,的,最小上界，,或,上确界,。,注意：上确界,不一定,是集合内的点；,73,良序,偏序集合的每个非空子集存在最小元素，则称为,良序集,。,良序集合一定是全序集合（,P145,定理,12.1),良序 线序 偏序 关系 笛卡尔乘积,有限的全序集合一定是良序集合,(P145,定理,12.2),无限的全序集合不一定是良序集合,（例如正实数集合上的小于关系，开区间子集没最小元素,）,74,定义函数,函数,（也叫,映射,mapping,）,的定义：,f,是集合,X,到集合,Y,的一个关系，对于,每一个,xX,，,有,惟一,的,yY,，,使得,f,，称,关系,f,为函数，记为：,f : XY,或,XY y,记为,f(x),f,函数与关系的区别,:,定义域是整个集合,X,；,一个,a X,只能对应于惟一的一个,yY,，,使,f(x) = y,；,可见,:,函数 关系 笛卡尔乘积,75,解,(1) R,1,不是函数,因为元素,a,有,两个不同的像,(2) R,2,不是函数,因为,A,中元素,c,没有像,。,(3) R,3,是函数,函数的定义允许,多个元素共有一个像,例 题,设,A = a, b, c, B = 0, 1,判别下列二元关系中哪个是函数？,(1) R1 = ,a, 0, ,a, 1, b, 0, c, 1,。,(2) R2 = a, 0, b, 1,。,(3) R 3= a, 0, b,1, c,1,。,76,例 题,证明,因为任一函数,f,是由,A,中,n,个元素的取值所,唯一确定,的, A,中的任一元素,a, f,在,a,处的取值都有,m,种可能,所以,A,到,B,可以定义,mm,m =,m,n,=,|B|,|A|,个不同的函数,。,设,| A | = n, | B | = m,，,X,到,Y,有多少个不同,的函数？,77,习题解答,P151 4-1 (2),令,f : AB,，,已知,CA,，,证明：,f(A)-f(C) f(A-C),证明：,任意,y ,f(A)-f(C,), x A,f(x,)=y,对于,zC,，,y f(z),，,即,x z,因此,x A-C,故,y = f(x) ,f(A,-C),于是有：,f(A)-f(C) f(A-C),78,习题解答,P151 4-1 (3),假设,f,和,g,是函数，且有,f,g,和,dom,g,dom,f,，,证明,f = g,。,证明,：,g,，有,a ,dom,g ,dom,f,故,a ,dom,f,，,有, f g,，,即, g,由于,g,是函数，因此,a,有惟一像点，,于是有：, = ,= , f,因此,g f,已知,f,g,，,得到,f = g,79,习题解答,P151 4-1 (3),假设,f,和,g,是函数，且有,f,g,和,dom,g,dom,f,，,证明,f = g,。,证明,：用反证法：,设,f g,，,由已知,fg,得, g,，,但, f,由, g,，得,a ,dom,g ,dom,f,故,a ,dom,f,，,有, f g,，,即, g,，,由于,g,是函数，因此,a,有惟一像点，,于是有：, = ,= , f,与题设矛盾。,因此,f = g,80,满射,、,入射,(,单射,),、,双射,函数,f : XY,满射,：,yY,，,xX,，,使得,f(x)=y,；,入射,：,x1,x2X,，,x1x2 f(x1)f(x2),；,双射,：既是入射又是满射，也叫,一一对应,81,入射,入射,入射,入射,82,逆函数,inverse function,问：函数的逆关系一定是函数吗？,答：,只有双射才有逆函数,双射函数,f : XY,逆函数,f,1,: YX,(f,1,),1,= f,反函数,即逆函数,83,复合函数,composite function,函数,f : XY,，,g : WZ,若,f ( X ) W,，,则：,g f,= | xXzZ,(y)(yYy=f(x)z=g(y) ,称,函数,g,在函数,f,的左边可复合,。,设,R,是,A,到,B,的关系，,S,是,B,到,C,的关系，则,R,S,称为,R,和,S,的,复合关系,，表示为,R,S = | xAzC,(,y,)(yBRS),比较复合关系：,84,1.,证明,:,任意集合,A,、,B, P(A)P(B)= (AB),2.,证明,:,任意集合,A,、,B, P(A)P(B) P(AB),3.,任意集合,A,、,B, P(A-B),是否等于,P(A)-P(B),？,4.,对任意集合,A,、,B,、,C,已知,AC BC, A-C B-C,证明,: A B,（提示：参考课本,P89,例题,2,结论）,补充习题,85,补充习题,5. R1,、,R2,是非空集合,A,上,的等价关系。,问：,R1R2,、,R1R2,还是,A,上的等价关系吗？,6.,画出,54,因子集合上整除关系的哈斯图；,画出,1,2,3,4,6,9,12,18,36,上整除关系的哈斯图,7.,下列关系中哪些能够构成函数？,1),、,f = | x,yR,且,x = y,2,2),、,g = | x,yN,且,y,为小于,x,的素数个数,3),、,f = | x,yN,且,x+y10 ,4),、,g = | x,yR,且,y = x,2,86,补充习题,证明： 对任意集合,A,、,B,，,P(A)P(B) = P(AB),证明： 对任意集合,A,、,B,，,P(A)P(B) P(AB),对任意集合,A,、,B,，,P(A-B),是否等于,P(A)-P(B),？,87,证明,P(AB),= P(A)P(B),证明：,对,任意,x,P(AB),x,AB,x,A x,B,x,P(A,) ,x,P(B,),x,P(A)P(B),所以,P(AB) = P(A)P(B),88,证明,对任意,x,P(A)P(B),x,P(A)x,P(B),x,Ax,B,x,AB,x,P(AB),所以,P(A)P(B),P(AB),；,当,A,B,时, P(A),P(B),；,AB = B, P(A)P(B),= P(AB),证明,P(A)P(B),P(AB),89,补充习题,对任意集合,A,、,B,、,C,，,已知,AC BC,，,A-C B-C,证明：,A B,提示：参考课本,P89,例题,2,结论,90,补充习题,R1,、,R2,是非空集合,A,上的,等价关系，,问：,R1R2,、,R1R2,还是,A,上的等价关系吗？,R1R2,还是,A,上的等价关系，因为交运算依然保持了其自反,对称,传递性。,R1R2,不是,A,上的等价关系，不一定传递,91,补充习题,画出,54,因子集合上整除关系的哈斯图；,画出,1,2,3,4,6,9,12,18,36,上整除关系的哈斯图,12,18,6,1,4,2,9,3,36,92,补充习题,下列关系中哪些能够构成函数？,1,、,f = | x,yR,且,x = y,2,2,、,g = | x,yN,且,y,为小于,x,的素数个数,3,、,f = | x,yN,且,x+y10 ,4,、,g = | x,yR,且,y = x,2,解,1. f,不能构成函数,存在,x,在,Y,上有两个元素与之对应,2. g,构成函数,3.,由于,f,仅涉及,N,中的元素,0, 1, 2, 9,，而,其它元素没有像,所以,f,不是,N,上的函数。,4. g,构成函数,93,