离散数学(3.10等价关系和等价类)

1离散数学(DiscreteMathematics)张捷第三章集合与关系（SetsandRelations)3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(CompatibilityRelations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)3.2序偶与笛卡尔积(OrderedPairs&CartesianProduct)3.3关系(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)BABA3.8等价关系与等价类(EquivalenceRelations&Equivalenceclasses)3.8.1等价关系的定义(TheDefinitionofEquivalenceRelation)3.8.2等价类的性质(ThePropertiesofEquivalenceclass)3.8.3等价关系与划分(EquivalenceRelations&Partitions)第三章集合与关系(Sets&Relations)3.8.1等价关系的定义(TheDefinitionofEquivalenceRelation)1.等价关系定义3.8.1集合A上的关系ρ，如果它是自反的，对称的，且可传递的，则称ρ是A上的等价关系。例如数的相等关系是任何数集上的等价关系。又例如一群人的集合中姓氏相同的关系也是等价关系。但父子关系不是等价关系，因为它不可传递。例1设A是任意集合，则A上的恒等关系和全域关系UA均是A上的等价关系。例2设，A上的关系ρ是A上的等价关系。例3设m为大于等于2的正整数，整数集Z上的同余关系则ρ是集合Z上的等价关系，称为Z上的模m同余关系。有时写成},,,{dcbaA},,,,,,,,,,,,,,,{ddcddcccbbabbaaa},,,,{Zkbakmbaba)}(mod,,,{mbaZbaba或2.元素a与b等价设ρ是集合A上的等价关系，若元素aρb，则称a与b等价，或称b与a等价。},,,{整除余数相同被和mbaZbaba3.等价类定义3.8.2设ρ是集合A上的等价关系，则A中等价于元素a的所有元素组成的集合称为a生成的等价类，用表示，即][a}|{][baAbba且a称为等价类的代表元素。][a显然有例4对于例2中的ρ来说},{][},,{][babbaa},{][},,{][dcddcc例5整数集Z关于模3同余关系ρ的等价类共有三个：},,3,,6,3,0,3,6,,3,{]0[1nnZ},,13,,7,4,1,2,5,,13,{]1[2nnZ},,23,,8,5,2,1,4,,23,{]2[3nnZ]3[]0[]3[]6[]1[]4[]2[]5[而恰好为Z的一个划分。]2[]1[321,,ZZZ1.对任意,3.8.2等价类的性质(ThePropertiesofEquivalenceclass)因为对于任意的a∈A,有aρa，所以。2.对任意的a,b∈A有aρb当且仅当。由ρ的对称性有xρa，证明“”若，则aρx，又由aρb及ρ的传递性有xρb，因此Aa][a][aa][][ba][ax][bx故。][][ba类似地可以证明由上得][][ab][][ba3.8.2等价类的性质(ThePropertiesofEquivalenceclass)2.对任意的a,b∈A有aρb当且仅当ρρ[b][a]证明(续)“”由，知因此有aρb.][][abb][][ba与相矛盾。][][ba3.对任意a,b∈A，若，则.ba证明（用反证法）假设,则A中至少有一元素因此且，即xρa，且xρb,于是由aρx,xρb，得aρb，故][][ba][][bax][ax][bxba][][ba例6设A={a,b,c,d}，A上的关系ρ是A上的等价关系同一个等价类中元素均相互等价。不同等价类中的元素互不等价。},,,,,,,,,,,,,,,,,,,{ddacbcabbbcccacbbaaa},,{][][][cbacba}{][dd3.8.3等价关系与划分(EquivalenceRelations&Partitions)集合A上的等价关系与集合A上的划分具有一一对应关系.定理3.8.1设ρ是集合A上的一个等价关系，则集合A中所有元素产生的等价类的集合是A的一个划分。（1）对每一元素a∈A，是A的非空子集。（2）对任意a,b∈A，或者与是A的同一子集或者}|]{[AaaAa][][a][b][][ba（3）对所有的元素的等价类求并集，显然有.AaAa][另一方面，对任一，而][,xxAx有Aaax][][所以，因此，故。Aaax][AaaA][AaAa][A定义3.8.3设ρ是集合A上的等价关系,其所有不同等价类的全体所组成的A的划分称为A关于ρ的商集，记作。例如在集合A={a,b,c,d}上，例2中A关于等价关系ρ的商集为例5中Z关于模3同余关系ρ的商集为例6中A关于等价关系ρ的商集为}][,]{[}}{},,,{{/dbdcbaA/A}][,]{[}},{},,{{/cadcbaA}]2[,]1[,]0{[/A定理3.8.2设是集合A的一个划分，则存在A上的一个等价关系ρ，使得S是A关于ρ的商集。证明：在集合A上定义一个关系ρ，对于任意的a,b∈A，当且仅当a与b在同一分划块中时，有aρb。对任意a∈A，a与a在同一分划块中，所以有aρa，即ρ自反。又对任意的a,b∈A,若a与b在同一分划块中，则b与a在同一分划块中.即,若aρb,则bρa,因此ρ是对称的.对于任意a,b,c∈A，若a与b在同一分划块中，b与c在同一分划块中，因为，所以a与c也在同一分划块中，此即,若aρb，bρc，则必有aρc，因此ρ是可传递的。},,,{21rAAAS)(jiAAji由定理3.8.2可知:由集合A的划分所确定的A上的等价关系ρ为},,,{21rAAASrrAAAAAA2211例7设A={a,b,c,d}，A上的划分试求出等价关系和，使得和的等价类分别是和的分划块。解定义A上等价关系则定义A上的等价关系则}}{},,{},{{1dcbaS}}{},{},{},{{2dcbaS12121S2S},,,,,,,,,,,{1ddccbccbbbaa}}{},,{},{{/11dcbaSA},,,,,,,{2ddccbbaa}}{},{},{},{{/22dcbaSA例8设A={a,b,c}，求出A上所有的等价关系。解先求出A上有多少个不同的分划。•分成一个分划块的分划•分成两个分划块的分划•分成三个分划块的分划}},,{{1cbaS}},{},{{2cbaS}},{},{{4bacS}},{},{{3cabS}}{},{},{{5cbaScab},,,,,,,,,{2ccbccbbbaa因此，A上有5个不同的分划，如下图所示记与分划相对应的等价关系为abcabcbacacb54321SSSSSiSiAUccbcaccbbbabcabaaa},,,,,,,,,,,,,,,,,{1},,,,,,,,,{3ccaccaaabb},,,,,,,,,{4bbabbaaaccAIccbbaa},,,,,{5第三章集合与关系(Sets&Relations)小结:本结介绍了等价关系和等价类的概念，并研究了它们的特性。重点是等价类的性质、商集的概念、等价关系与划分之间的密切联系。Pg134(2),(3),(6).