第4章 集合论基础

第四章二元关系与函数4.1集合的笛卡尔积与二元关系有序对（序偶）由两个元素x和y按一定的顺序排列的二元组叫做一个有序对,记作x,y。例如：1,2,a,b。有序数对具有以下特点：.,,两个有序对相等，.2.,,时，yx1.vyuxvuyxxyyx且当且仅当，即当有序n元组一个有序n元组（n2)是一个有序对，其中第一个元素是一个有序n-1元组，一个n元有序组记作在数学中有许多量是一有序n元组的形式表示的，例如，n维向量等.,,,,1121xxxxxxnnn笛卡尔积设A,B为集合，用A中元素为第一元素，B中元素为第二元素，构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作AxB，符号化表示为：由排列组合的知识，若A有m个元素，B有n个元素，则AxB有mn个元素。}.|,{ByAxyxBA笛卡儿积的性质（1）1：若A，B中有一个是空集，则他们的笛卡儿积是空集，即2：当A，B，C都不是空集的时候，上式说明结合律改变了有序对的顺序性，所以笛卡儿积不适合结合律。3：当AB且A，B都不是空集时有：上式说明笛卡尔积运算不适合交换律。AB)()(CBACBAABBA笛卡儿积的性质（2）4：笛卡尔积运算对运算满足分配律，即思考：集合元素的无序性，与有序对的有序性以及无序性和有序性构成的笛卡尔积，他们的区别和联系。or).()()();()()();()()();()()(ACABACBCABACBAACABACBCABACBA笛卡儿积的例题例4.2：设A，B，C，D为任意集合，判断下列等式是否成立，说明了什么？)()()()(:4)()()()(:3)()()()(:2)()()()(:1DBCADCBADBCADCBADBCADCBADBCADCBAn阶笛卡尔积设是集合（n2orn=2)，它们的n阶笛卡尔积，记作其中：当时，它们的n阶笛卡尔积可简记为：AAAn21}.,|,{11121AxAxxxAAAnnnnAnnAAA,,,21nAAA21二元关系（1）如果一个集合为空或它的元素都是有序对，则称这个集合是一个二元关系，一般记作R。对于二元关系R，如果则记作xRy；如果则记作xRy。Ryx,Ryx,/二元关系（2）设A，B为集合，AxB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，则叫做A上的二元关系。常见的二元关系：空关系，全域关系，恒等关系小于等于关系，整除关系等。EAIALADA}|,|,{},|,{yxAyxyxyxAyxyxDLAA二元关系例题例4.4}.,,},{,},{,{b}{b},,{a}{a},,A,,{b},,{a},,,{R}.{b}{a},b},{a,,{P(A)则有：y}xP(A)yx,|yx,{)A(PRb},{a,A设AAAbAa上的包含关系是关系矩阵(1)nnnnnnjijinrrrrrrrrrRRARxxxxxxx212222111211ijij21)(,则n),1,2,j(i,,0,1},,,,{A设rr若若令上的关系，是关系矩阵(2)A={1,2,3,4}，上的关系R={1,1,1,2,2,3,2,4,4,2},的矩阵表示为：0010000011000011关系图4.2关系的运算定义域，值域，域定义域domR,值域ranR,域fldR,)},(|{RyxyxdomR)},(|{RyxxyranRranRdomRfldR定义域，值域，域图解的方法表示关系。（教材P86）关系的逆与合成F的逆记作F与G的合成记作}.|,{1yFxyxFF1GF)}.(|,{zFyxGzzyxGF逆与合成的例题例4.6设F，G为N上的关系，求，。F1GF}yNyx,|yx,{GF}2,4,2,4,1,1,1,1{},|,{}1,|,{G}yNyx,|yx,{F1)(x2212，xFxyNyxxyxyNyxyx关系运算的性质(1)FFFFFFranFF11-11-1-1.4))(3.,.21.1G)G(HG(HGdomFranFdom)(关系运算的性质(1)FHFGFH)(G8.FHFGFH)(G7.G)(FG)F(H)(GF6.G)(FG)F(H)(GF.5幂运算设R为A上的关系，n为自然数，R的幂运算：由上面的定义可推出：1n,.2}|,{.11n0RRRRnAxxxRRRRRRR0100R即：幂运算例题（矩阵方法）例4.8RRRRRdccbabbaRdcbaARRRR32100000000010100101000010000101001000001000010100100000100001010010,1000010000100001},,,,,,,{},,,,{则幂运算的性质设R为A上的关系，m,n为自然数，则下面的等式成立：RRRnmnnmn)R(Rm2.1.m4.3关系的性质自反性反自反性对称性反对称性传递性定义关系矩阵主对角元全为1。主对角元全为0。矩阵为对称矩阵。如r(i,j)=1且i，j不等则r(j,i)=0.关系图每个顶点都有环。每个顶点都没有环。无单边。无双边。有边x-y,有边y-z,则有x-zIRARR1IRRA1RRRRIA关系性质的例题(1)例4.9判断下列关系图的性质：关系性质的例题(1)图1的关系在{1,2,3}上的对称的，图上无单边，既不是自反，也不时反自反有的定点有环有的没环，它也没有传递性。图2的关系是反自反的无顶点有环，反对称得全为单边，而且是传递的。图3的关系是自反的，反对称得，但不是传递的（自证）。原有性质及运算自反性反自反性对称性反对称性传递性1111111111111000111010000RR21RR21RR21R1RR214.4关系的闭包对于某关系，添加最少的有序对，使之具有某种性质（自反性，对称性或传递性），即得到相应性质的闭包（自反闭包，对称闭包或传递闭包）。因为关系闭包具有某些特别的性质，在解决问题时很实用，所以要学习关系闭包。关系闭包定义设R是非空集合A上的关系，R的自反闭包（对称闭包或传递闭包）是A上的关系（1）：是自反的（对称的或传递的）。（2）：（3）：对A上任意包含R的自反关系(对称或传递性关系）都有。自反闭包r(R),对称闭包s(R),传递闭包t(R).R'R'RR'R''RR'''关系闭包的构造（1）设R为非空集合上的关系，则有RRRRRRRsRRRr3210)(.3)(.2)(.1t关系闭包的构造（1）MMM32t'srtsrMMMMEMMMMM则有：,,关系闭包的矩阵为关系闭包构造例题例4.10设A={a,b,c,d},R={a,b,b,a,b,c,c,d},求r(R),s(R),t(R)。（对于有限集A，R的不同幂只有有限种。）4.5等价关系和偏序关系等价关系设R为非空集合A上的关系，如果R是自反的，对称的和传递的，则称R为A上的等价关系。y.~x则记作R,yx,A,yx,对任何等价关系如果等价关系例题例4.11对模3的等价关系推广，对于任意的正整数n可以定义Z上的模n等价关系。6.~38,~5~27~4~1AR3y-x3)y(modx},y(mod3)xAyx,|yx,{R8},,,2,1{，其中：上的等价关系。为验证不难整除，可以被的含义是其中A等价类（1）设R是非空集合A上的等价关系，对任意的，令则称为x关于R的等价类，简称为x的等价类，记作[x],其中x为代表元。Ax},|{][xRyAyyxR][xR等价类（2）在例4.11中有[1]=[4]=[7]={1，4，7}，[2]=[5]=[8]={2，5，8},[3]=[6]={3，6}。在Z上模n等价关系有，共有n个等价类[i]={n*k+i|k为整数},i=0,1,2,……等价关系的性质设R为非空集合A上的等价关系，有Ayx,.][(4);[y][x]yRx(3)[y][x]xRy,(2)]x[,]x[)1(AxAxA，则若；则若；且商集设R为非空集合上的等价关系，以R的不相交的等价类为元素的集合叫A在R下的商集，记作A/R，即：在例4.11中，A在R下的商集为:A/R={{1，4，7}，{2，5，8}，{3，6}}。A}.x|{/][xRRA商集例题例4.131.非空集合A上的全域关系是A上的等价关系，对A中任意的x有[x]=A,商集2.非空集合A上的恒等关系是A上的等价关系，对A中任意的x有[x]={x},商集3.在整数集合Z上的模n等价关系。EAIAA}.x|}{{/xIAA}.{/AEAA划分）（书上的划分是一一对应的。与集合非空集合上的等价关系中的元素为划分块。的一个划分，且称为则称，中所有元素的并集等于）（中任意两个元素不交，）（，）（满足以下条件：）（的子集族一个是非空集合，如果存在设97321)(PAAAAPAA划分例题(1)例4.15设A={1,2,3},求出Ａ上所有的等价关系。对Ａ的三种划分：1有一个划分块；2,3,4有两个划分块；5有三个划分块。划分例题(２).}3,3,2,2,1,1{;}1,2,2,1{;}1,3,3,1{;}2,3,3,2{;}3,2,3,1,2,3,2,1,1,3,1,2{IIIIIR54321AAAAAARRRRE偏序关系（一种顺序含义）设Ｒ为非空集合Ａ上的关系，如果Ｒ是自反的，反对称的和传递的，则称Ｒ为Ａ上的偏序关系，简称偏序，记作：如果x,y属于，即xy.注：这里的x,y不一定是数，xy,是排序的概念。偏序集－个集合Ａ与Ａ上的偏序关系Ｒ一起叫做偏序集，记作A,R。。，则称使得且不存在且即如果的，是与成立，则称或者如果为偏序集，对于任意的设xyyzxAzyxyxyxyxxyyxAyxA盖住可比),(,,,,全序集设A,为偏序集，如果对于A中任意的x,y都可比，则称为Ａ上的全序关系，且称A,为全序集。全序集的意义：在集合Ａ上存在关系Ｒ能够对Ａ中的元素进行一个排序。全序集的哈斯图是一条直线，所以全序集也称为线序集。哈斯图连一条线。之间和，则在盖住从底向上排列，如果按它们在偏序中的次序的一个元素，结点位置中图，每个结点表示哈斯图就是简化的关系yxxyA偏序集的哈斯图例4.16画出{1,2,…,12},Ｒ整除的哈斯图。偏序集中的特征元素注：有限集合，极大、小必存在，最大、小不一定存在（如果存在则唯一）。的极大元；是成立，则称使得若的极小元；是成立，则称使得若的最大元；是成立，则称使得若的最小元；是成立，则称使得若为偏序集，设ByxyBxxByByyxBxxByByyxBxxByByxyBxxByABA)(,)4()(,)3()(