离散数学-等价关系与偏序关系.ppt

*离散数学集合论主要内容*/68集合代数二元关系函数集合的基本概念集合的运算有穷集合的计数集合恒等式有序对与笛卡儿积二元关系关系的运算关系的性质关系的闭包等价关系与划分偏序关系函数的定义与性质函数的复合与反函数双射函数与集合的基数§7.6等价关系与划分*/68例7.16设A={1,2…,8},定义A上的关系R如下:验证R是A上的等价关系.一.等价关系定义7.15设R为非空集合A上的关系.如果R是自反的,对称的和传递的,则称R为A上的等价关系.对等价关系R,若x,y?R,则称x等价于y,记为x～yorxRy.解:∵?x?A,有,故R是自反的.?x,y?A,若,则,故R是对称的.?x,y,z?A,若,则,故R是传递的.∴R是A上的一个等价关系.等价类*/68定义7.16设R为非空集合A上的等价关系,?x?A,令称?x?R为x在R下的等价类(简称为x的等价类),有时简记为?x?.x称为该等价类的代表元.注:一个等价类是A中在等价关系R下彼此等价的所有元素的集合,等价类中各元素的地位是平等的,每个元素都可以作为其所在等价类的代表元.例如,在上例中的等价关系R下,A中元素形成了三个等价类:?1?=?4?=?7?={1,4,7};?2?=?5?=?8?={2,5,8};?3?=?6?={3,6}.1,1,1,4,1,7,4,1,4,4,4,7,7,1,7,4,7,72,2,2,5,2,8,5,2,5,5,5,8,8,2,8,5,8,83,3,3,6,6,3,6,6等价类的性质*/68定理7.14设R为非空集合A上的等价关系,则（1）?x?A,?x?是A的非空子集.（2）?x,y?A,如果xRy,则?x?=?y?（3）?x,y?A,如果x与y不具有关系R,则?x?与?y?不相交.（4）∪{[x]|x∈A}=A证：(1)显然.(2)∵z??x??x,z?R?z,x?R（R是对称的）∴z,x?R∧x,y?R?z,y?R?y,z?R∴z??y?,从而?x???y?同理可得,?y???x?.故?x?=?y?等价类的性质/68∵∴再证∵∴因此(4)先证(3)反证法.假设?x?∩?y???,则存在z??x?∩?y?.因而z??x?且z??y?,即x,z?R∧y,z?R.根据R的对称性和传递性,必有x,y?R.这与前提条件矛盾.故原命题成立.商集与划分*/68定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素,形成的集合称为A关于R的商集,记为A/R,即:例如:例7.16中等价关系形成的商集为:A/R＝{{1,4,7},{2,5,8},{3,6}}定义7.18设A为非空集合,若A的子集族?(??P(A),是由A的一些子集形成的集合)满足下列条件:(1)????(2)?x?y(x,y??∧x≠y→x∩y=?)(3)?则称?是A的一个划分,而称?中的元素为A的划分块或类.?五.集合的划分等价关系与划分*/68例7.17设A={a,b,c,d},则?1={{a,b,c},{d}}和?2={{a,b},{c},{d}}都是A的划分,而?3={{a},{a,b,c,d}}和?4={?,{a,b},{c}}都不是A的划分.注:给定非空有限集A上的一个等价关系R,在R下彼此等价的元素构成的子集便形成了A的一个划分,它其实就是商集A/R,其每个类(等价块)就是R的一个等价类;反之,任给A的一个划分?,可定