等价关系与等价类

《等价关系与等价类》由会员分享，可在线阅读，更多相关《等价关系与等价类（24页珍藏版）》请在装配图网上搜索。

1、,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,3-10 等价关系与等价类,,离散数学,复习,自反性,（ reflexive ）,,,定义：,设R为定义在集合A上的二元关系，如果,,对于每个x∈A，,都有,∈,R,,即xRx，则称二元关系R是自反的。,,对称性（ symmetric ）,定义：,设R为定义在集合A上的二元关系，如果对于每个x，y∈A，,每当∈R，就有∈R,，则称集合A上关系R是对称的。,,,

2、传递性,（ transitive ）,定义:,设R为定义在集合A上的二元关系， 如果对于任意x，y，z∈A，,,,每当 ∈ R且 ∈R，,就有, ∈ R,，称关系R在A上是传递的。,,,,,,,,,R,1,是对称的。,,,,,,,,,,R,2,是自反的、对称的、传递的。,,,,,等价关系与等价类的基本概念,1,,,,等价关系的基本性质,2,主要内容,商集与集合的划分,3,,,,3,一、定义,,定义1:,设R为定义在集合A上的一个关系，,若R是自反的，对称的和传递的,，则称R为集合A上的等价关系。,,例如,平面上三角形集合中，三角形的相似关系；,,同学集合A={a,b,c,d,e,f,g}

3、,A中的关系R：住在同一宿舍；,,同性关系。,,例1 设T＝｛1，2，3，4｝，,R＝｛＜1，1＞，＜1，4＞，＜4，1＞，,,＜4，4＞，＜2，2＞，＜2，3＞，,,＜3，2＞，＜3，3＞｝。,,验证R是集合T上的等价关系。,,,,例2 设A = { 1, 2,,…,, 8 }, 如下定义A上的关系R:,,,,R = { | x, y,,A且x≡y（mod3) },,证明R为A上的等价关系。,证明:,,,,,x,,A , 因为x-x=0=0,×,3,所以∈R;,,,,x,y,,A, 若x-y=3t(t为整数）, 则有: y-x=-3t,即 ∈R;,,,,x,y,z,,A, 若

4、x-y=3t, y-z=3s, 则有:,,x-z=3(t+s),即 ∈R.,,,关系图如下图所示.,,等价类,定义2：,设R为集合A上的等价关系，对任意a∈A，集合,,[a],R,={x|x ∈ A,∈R},,称为元素a关于R的等价类。,,例2可求出三个不同的等价类,[1],R,=[4],R,=[7],R,={1,4,7},,[2],R,=[5],R,=[8],R,={2,,5,,8},,[3],R,=[6],R,={3,6},,定义3:,集合A上的等价关系R，其等价类集合{[a],R,|a ∈ A}称作A关于R的,商集(,quotient set),,。记作A/R,,,(1) a ∈[a],

5、R,,,,(2),定理1:,设给定集合A上的等价关系R，对于a,b∈A，若∈R,iff [a],R,=[b],R,。,,,,,,,,,二、性质,,,(3)设R为集合A上的等价关系，则任意a,b ∈ A,若,,R,则,,证明,设集合A上的一个等价关系R，则[a],R,是A的一个子集，则所有这样的子集可做成商集A/R,,1、A/R={[a],R,|a,,∈A}中,　∪[a],R,=A,,2、 对任意a ∈A，都有aRa，即a∈[a],R，,即A中的每一个元素都属于一个分块。,,3、A的每个元素只能属于一个分块,,反证设a∈[b],R,，a∈[c],R,,且[b],R,≠ [c],R，,则bRa,c

6、Ra成立，所以有aRc,所以bRc，即[b],R,＝ [c],R,,所以A/R是A上对应于R的一个划分。,定理2：,集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。,三 商集与集合的划分,证明：,,设集合A的一个划分S＝｛S1,S2…Sm｝，现定义一个关系：aRb当且仅当a,b在同一个分块中。则R是一个等价关系。,,①,、a与a在同一个分块中，则有aRa ，即自反性,,②,、 a与b在同一个分块中，则b与a在同一个分块中，即若aRb，有bRa，故R是对称的。,,③,、 a与b在同一个分块中， b与c在同一个分块中，而由划分的定义b只能属于且属于一个分块，故a与c必在同一分块中，

7、即若有aRb,bRc则必有aRc，即传递性成立。,,所以R是一个等价关系。S＝A/R,定理3,集合A的一个划分确定A的元素间的一个等价关系。,说明,等价关系,——,等价类,——,商集,——,划分,,A上的等价关系与A的划分是一一对应的。,,R1＝{a,b},x,{a,b}={},,R2={c},x,{c}={},,R3= {d,e}x{d,e}={},,R=R1∪R2∪R3,,例3　A={a,b,c,d,e}，,,S＝{{a,b},{c},{d,e}}，求由S确定的R,。,例4设A={a,b,c,d,e},R={〈a,a〉,〈a,b〉,〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉

8、,〈c,a〉,〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉},其有向图如图所示,,则R诱导的划分S={{a,b,c},{d,e}}.反之,若A的划分S={{a,b,c},{d,e}},则所诱导的等价关系R={a,b,c}×{a,b,c}∪{d,e}×{d,e}={〈a,a〉,〈a,b〉,〈a,c〉,〈b,b〉,〈b,a〉,〈b,c〉,〈c,c〉,〈c,a〉,〈c,b〉,〈d,d〉,〈d,e〉,〈e,e〉,〈e,d〉},,,证明,,必要性：A/R1＝{[a],R1,|a ∈ A}，A/R2 ＝{[a],R2,|a ∈ A},,R1＝R2，对任意a ∈ A, 有[a],R1,＝{x|

9、x ∈ A,aR,1,x}={x|x ∈ A,aR,2,x}= [a],R2,,所以有{[a],R1,|a ∈ A}＝{[a],R2,|a ∈ A}即有A/R1=A/R2,,充分性：反之设{[a],R1,|a ∈ A}＝{[a],R2,|a ∈ A},,对任意[a],R1,∈ A/R1则有[c],R2,∈ A/R2,使得[a],R1,＝[c],R2,所以,, ∈R1 a ∈ [a],R1,∧b ∈ [a],R1,a ∈ [c],R2,∧b ∈ [c],R2,→ ∈R2,,所以R1是R2的子集，同理可证R2也是R1的子集。,,所以R1＝R2,,定理4：设R1和R2为非空集合A上的等价,,关系，则R1=R2当且仅当A/R1=A/R2。,,