资源描述：
《集合论与图论2.4.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2.6等价关系与划分*等价关系是一类重要的二元关系定义7.15:设R是非空集合A上的关系.如果R是自反的,对称的和传递的,则称R为A上的等价关系.若∈R,则称x等价于y,记作x≈y.例1:设A={1,2,…,8},定义A上的关系R:R={
2、x,y∈A∧x≡y(mod3)}证明:x∈A,有x≡x(mod3).x,y∈A,若x≡y(mod3),则有y≡x(mod3).x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3).关系图如下:(见图2.6.1)定义7.16:设R为非空集合A上的等价关系,x∈A,令[x]R={y
3、y∈A∧
4、xRy}.称[x]R为x关于R的等价类,简称为x的等价类,简记为[x]或.例如:例1中关系R的等价类有:[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}.*对上述等价关系的推广,可得整数集合Z上模n同余的等价关系.x∈Z,x=qn+r,0≤r≤n―1.*例如:n=3,x=8,8=2×3+2,r=2n=3,x=―8,―8=(―3)×3+1,r=1定义:x≈yx≡y(modn)该关系将Z中的数划分为等价类如下:余数为0的数,nz,z∈Z余数为1的数,nz+1,z∈Z…余数为n-1的数,nz+(n-1),z∈Z构成的等价类
5、:[i]={nz+i
6、z∈Z},i=0,1,2,…,n-1.*下面给出等价类的性质(对一般的等价类而言).定理7.14:设R为非空集合A上的等价关系,则(1)x∈A,[x]是A的非空子集;(2)x,y∈A,如果xRy,则[x]=[y];(3)x,y∈A,如果,则[x]与[y]不相交.(4)∪{[x]
7、x∈A}=A.证明:(1)由等价类的定义,有x∈A,xRx,故x∈[x],因而[x]≠φ.(2)任取z,则有z∈[x]xRzzRx(由对称性)又有zRx∧xRyzRy(由R的传递性)yRz(由对称性)从而证明了z∈[y],因而有[x][y].同理可证[y][x].因而有[x
8、]=[y].(3)假设[x]∩[y]≠φ,则存在z[x]∩[y],即有z∈[x]∧z∈[y].故∈R∧∈R,由对称性,∈R,再由传递性,有∈R,这与R矛盾.(4)先证∪{[x]
9、x∈A}A.任取y,y∈∪{[x]
10、x∈A}x(x∈A∧y∈[x])y∈A(因为[x]A)从而有∪{[x]
11、x∈A}A.再证:A∪{[x]
12、x∈A}.任取y,y∈Ay∈[y]∧y∈Ay∈∪{[x]
13、x∈A}.从而有A∪{[x]
14、x∈A}成立.综上所述,A=∪{[x]
15、x∈A}.*由非空集合A和A上的等价关系R可以构造一个新的集合—商集.定义7.1
16、7:设R是非空集合A上的一个等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记作A/R.即A/R={[x]R
17、x∈A}.例如:以例1中的集合A和关系R,得到商集:A/R={{1,4,7},{2,5,8},{3,6}}定义7.18:设A为非空集合,若A的子集族Π(ΠP(A))满足下面的条件:(1)φΠ;(2);(3)∪Π=A则称Π是A的一个划分,称Π中的元素为A的划分块.例2:设A={a,b,c,d},给出Π1,Π2,Π3,Π4,Π5,Π6如下:Π1={{a,b,c},{d}}Π2={{a,b},{c},{d}}Π3={{a},{a,b,c,d}}Π4={{a
18、,b},{c}}Π5={φ,{a,b},{c,d}}Π6={{a,{a,b}},{c,d}}.则Π1和Π2是A的划分,其它都不是A的划分.*设R是非空集合A上的一个等价关系,则商集A/R是A的一个划分.*反之,任给A的一个划分Π,定义A上的关系R如下:R={
19、x,y∈A∧x与y在Π的同一划分块中}.不难证明R是一个等价关系,且该等价关系所确定的商集就是Π.*A上的等价关系与A的划分是一一对应的.2.7偏序关系定义7.19:设R是非空集合A上的关系.如果R是自反的,反对称的和传递的,则称R为A上的偏序关系,记作≤.如果∈≤,则记为x≤y,读作x小于或等
20、于y.例如:集合A的幂集P(A)上是偏序关系.整数集上的≤也是偏序关系.*一般说来,全域关系EA不是A上的偏序关系.定义7.20:设R为非空集合A上的偏序关系,定义(1)(2)x,y∈A,x与y可比x≤y∨y≤x.*x
