离散数学 - 等价关系与划分

(4)U[a] = AaeA对任意的xelal,必存在某个aEA,使得xE[al二 AaeA所以U[a]二 AaeA又对任意的xE A,有xE[x]≤U[a]aeA所以AcU[a]aeA因此有U[a]= AaeA

a A a A =  (4)[ ] x a a A x a A a A      对任意的 [ ],必存在某个 ,使得 [ ] a A a A   所以[ ]  a A x A x x a  又对任意的  ,有 [ ]  [ ]  a A A a  所以  [ ] a A a A =  因此有[ ]

、例： 设 A={1,2,3,4), R={(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(3,1),(4,2))为等价关系。，其等价类为[1]=[1,3][2]=[2,4][3]=[1,3][4]=[2,4]划分II={[1],[2]}前面是给定等价关系唯一确定划分，反过来，给定一个划分，也可唯一确定一个等价关系

• 例：设 A={1,2,3,4}，R={(1,1),(2,2), (3,3),(4,4),(1,3),(2,4),(3,1), (4,2)}为等价关 系。 • 其等价类为[1]={1,3} • [2]={2,4} • [3]={1,3} • [4]={2,4} • 划分={[1],[2]} • 前面是给定等价关系唯一确定划分，反 过来，给定一个划分，也可唯一确定一 个等价关系

·设非空集A上划分II={A,A2….,A,}，定义A上二元关系R：aRb当且仅当存在A，使得a,beA;o. 即R=(A,×A)U(A2xA2)U... U(A,×An)容易证明R是等价关系。定理2.14：集合A上的任一划分可以确定A上的一个等价关系R。·例：设A={a,b,c的一个划分II={{a,b},ic}由IⅡI确定A上的一个等价关系R：. R=((a,b)x(a,b))U (ic}x{c))=((a,a),(a,b),(b,a),(b,b), (c,c))

• 设非空集A上划分={A1 ,A2 ,.,An }，定义A 上二元关系R：aRb当且仅当存在Ai ,使得 a,bAi。 • 即R=(A1A1 )∪(A2A2 )∪.∪(AnAn ) • 容易证明R是等价关系。 • 定理2.14：集合A上的任一划分可以确定A 上的一个等价关系R。 • 例：设A={a,b,c}的一个划分={{a,b},{c}}, 由确定A上的一个等价关系R： • R=({a,b}{a,b})∪({c}{c})={(a,a),(a,b),(b,a) ,(b,b), (c,c)}

定理2.15：设R和R，是A上的等价关系，R,=R当且仅当A/R,=A/R2。·定理2.13和定理2.15说明集合A上的任一等价关系可以唯一地确定A的一个划分。定理2.14和定理2.15说明集合A的任一划分可以唯一地确定A上的一个等价关系。1集合A上给出一个划分和给出一个等价关系是没有什么实质区别的。设集合A上的等价关系为R，和R，它们通过并1和交运算而得到的关系是不是等价关系？·若是,其对应的划分与原来的两个划分有何联系

• 定理 2.15:设R1和R2是A上的等价关系,R1=R2 当且仅当A/R1=A/R2。 • 定理 2.13 和定理 2.15 说明集合A上的任一等 价关系可以唯一地确定A的一个划分。 • 定理2.14和定理 2.15说明集合A的任一划分 可以唯一地确定A上的一个等价关系。 • 集合A上给出一个划分和给出一个等价关系 是没有什么实质区别的。 • 设集合A上的等价关系为R1和R2 ,它们通过并 和交运算而得到的关系是不是等价关系? • 若是,其对应的划分与原来的两个划分有何联 系