第四章 4等价关系与等价类

13:1611离散数学(DiscreteMathematics)13:162等价关系等价类等价关系与划分小结4.7等价关系与等价类13:163一、等价关系定义4.7.1设R为集合A上的关系，如果R是自反的，对称的和可传递的，则称R是A上的等价关系。4.7等价关系与等价类(2)是对称矩阵关系图的特点：关系矩阵的特点：(1)每个结点都有自回路(1)对角线元素均为1(2)每对结点之间若有定向弧线，一定是成对出现的(3)若两个结点之间有路，则一定有一条长度为1的路13:1644.7等价关系与等价类设A={1,2,3}，R是集合A上的关系，R是否可传递？R不可传递13:165例2设A={a,b,c,d}，是A上的等价关系。例1设A是任意集合，则A上的恒等关系和全域关系UA均是A上的等价关系。4.7等价关系与等价类例3在整数集合Z上定义二元关系R如下：a,bZ，aRba与b的奇偶性相同则R是Z上的等价关系。例4在整数集合Z上定义二元关系R如下：a,bZ，aRb|a|=|b|则R是Z上的等价关系。例5同宿舍关系是等价关系例6同班关系是等价关系4.7等价关系与等价类例7同组关系是等价关系13:167例8设k为正整数(kZ+)，a,bZ，若存在整数m，使得则称R为Z上的模k等价关系（或模k同余关系）。4.7等价关系与等价类则称a与b是模k等价的（模k同余的），记为若记或13:1684.7等价关系与等价类证明：模k等价是任何集合AZ上的等价关系。证若A=，由例1知它是等价关系。若A≠，则(1)自反性：aA，因为a-a=0·k，所以a≡a(modk)。(2)对称性：a,bA，若a≡b(modk)，即存在某mZ，使a-b=mk，那么b-a=(-m)k，即b≡a(modk)。(3)传递性：a,b,cA，若a≡b(modk)，a≡b(modk)，即存在整数m,n，使a-b=mk，b-c=nk，那么a-c=(m+n)k，即a≡c(modk)。综上所述，模k等价是A上的等价关系。若a与b等价，则b与a也等价。定义4.7.2设R是集合A上的等价关系，若元素aRb，则称a与b等价（有时记为a～b）。二、等价类4.7等价关系与等价类定义4.7.3设R是集合A上的等价关系，对任意aA，令则称[a]R为元素a关于R的等价类，简称为a的等价类，简记为[a]R，即所有等价类的集合称为集合A关于R的商集，记作A/R，即。1.等价类的定义显然[a]RA。13:1610例9设A={a,b,c,d,f}，是A上的等价关系。4.7等价关系与等价类显然有R有三个不同的等价类，它们刚好构成了集合A的划分{[a]R，[c]R，[f]R}。同一个等价类中的任意两个元素是等价的，不同等价类中的元素不等价。13:1611显然有例10整数集Z关于模3同余关系，其等价类共有而{[0]3，[1]3，[2]3}恰好为整数集合Z的一个划分。4.7等价关系与等价类3个：同一个等价类中的任意两个元素是等价的，不同等价类中的元素不等价。13:16122.等价类的性质4.7等价关系与等价类定理4.7.1设R是集合A上的等价关系，任意a,b,c∈A(1)同一等价类中的元素，彼此有等价关系。即，必有。证明(1)设，由等价类定义知，由R的对称性有又由R的传递性得13:16132.等价类的性质4.7等价关系与等价类定理4.7.1设R是集合A上的等价关系，任意a,b,c∈A(1)同一等价类中的元素，彼此有等价关系。即，必有。(2)[a]R=[b]R当且仅当。证明(2)若[a]R=[b]R，因为a∈[a]R，故b∈[a]R，由等价类的定义有bRa，又R具有对称性，所以aRb。反之，若aRb，设即同理可证由此证得，若aRb，则[a]R=[b]R13:16142.等价类的性质4.7等价关系与等价类定理4.7.1设R是集合A上的等价关系，任意a,b,c∈A(3)当且仅当。证明(3)设﹤a,b﹥∉R，假设[a]R∩[b]R≠∅，则存在x∈[a]R∩[b]R，所以x∈[a]R∧[b]R，即﹤a,x﹥∈R,﹤b,x﹥∈R由R的对称性有﹤x,b﹥∈R由R的传递性得﹤a,b﹥∈R这与“﹤a,b﹥∉R”相矛盾，所以[a]R∩[b]R=∅。若[a]R∩[b]R=∅，假设﹤a,b﹥∈R，由等价类的定义知b∈[a]R又由bRb，有b∈[b]R，所以b∈[a]R∩[b]R，这与“[a]R∩[b]R=∅”矛盾，所以﹤a,b﹥∉R。13:16(5)A中任何元素a，a必属于且仅属于一个等价类。2.等价类的性质4.7等价关系与等价类定理4.7.1设R是集合A上的等价关系，任意a,b,c∈A(4)任意两个等价类，要么，要么证明(4)对于任意元素a，b，要么﹤a,b﹥∈R，要么﹤a,b﹥∉R，由(2)(3)知此结论成立。证明(5)A中任何元素a，由于aRa，所以，a∈[a]R，如果a∈[b]R，所以﹤a,b﹥∈R，由(2)得[a]R=[b]R，即a属于且仅属于一个等价类。。(1)同一等价类中的元素，彼此有等价关系。即，必有。(2)[a]R=[b]R当且仅当。(3)当且仅当。13:1616三、等价关系与划分4.7等价关系与等价类集合A上的等价关系与集合A上的划分具有一一对应关系定理4.7.2集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。(1)对每一元素a∈A，[a]R是A的非空子集。(3)对任意a,b∈A，不同的等价类是不相交的。证明(2)aA，因为a[a]R，所以，从而另一方面，[a]RA，从而。故可见商集满足划分的定义，所以就是A的划分。13:1617设A集合有一个划分S={S1,S2,…,Sr}，现定义一个关系R，aRb当且仅当a，b在同一分块中。可以证明这样 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 的关系R是一个等价关系。因为定理4.7.3集合A的一个划分确定A的元素间的一个等价关系。证明(1)a∈A，a与a在同一分块中，故必有aRa，即R是自反的。4.7等价关系与等价类(2)a,b∈A，若a与b在同一分块中，则b与a必在同一分块中，即aRbbRa，故R是对称的。(3)a,b,c∈A，若a与b在同一分块Si中，b与c在同一分块Sj中，因为Si∩Sj=∅（i≠j）即b属于且仅属于一个分块，故a与c必在同一分块中，故有即R是传递的。R满足上述三个条件，故R是等价关系，由R的定义可知，S就是A/R。13:1618由定理4.7.3可知：由集合A的划分S={A1,A2,…,Ar}所确定的A上的等价关系R为例11设A={a,b,c,d}，A上的两个划分分别为试分别求出这两个划分所确定的A的等价关系R1和R2。解且4.7等价关系与等价类13:1619定理4.7.4设R1和R2为非空集合A上的等价关系，则R1=R2，当且仅当。4.7等价关系与等价类证明若R1=R2，则aA，因为所以即13:1620定理4.7.4设R1和R2为非空集合A上的等价关系，则R1=R2，当且仅当。4.7等价关系与等价类证明反之，若故同理，从而证毕。13:1621例12设A={a,b,c}，求出A上所有的等价关系。解分成一个划分块的划分：分成两个划分块的划分：分成三个划分块的划分：4.7等价关系与等价类先求出A上有多少个不同的划分。共5个划分13:1622相对应的等价关系为：4.7等价关系与等价类当A为至多可数集时，全域关系诱导出A的最小化分。当A为至多可数集时，恒等关系诱导出A的最大划分。13:1623四、小结本结介绍了等价关系和等价类的概念，并研究了它们的特性。重点是等价类的性质、商集的概念、等价关系与划分之间的密切联系。4.7等价关系与等价类感谢谢谢，精品课件 资料 新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单 搜集