等价关系与等价类.ppt

《等价关系与等价类.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3-10等价关系与等价类离散数学复习自反性（reflexive）定义：设R为定义在集合A上的二元关系，如果对于每个x∈A，都有∈R,即xRx，则称二元关系R是自反的。对称性（symmetric）定义：设R为定义在集合A上的二元关系，如果对于每个x，y∈A，每当∈R，就有∈R，则称集合A上关系R是对称的。传递性（transitive）定义:设R为定义在集合A上的二元关系，如果对于任意x，y，z∈A，每当∈R且∈R，就有∈R，称关系R在A上是传递的。R1是对称的。R2是自反

2、的、对称的、传递的。等价关系与等价类的基本概念1等价关系的基本性质2主要内容商集与集合的划分33一、定义定义1:设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为集合A上的等价关系。例如平面上三角形集合中，三角形的相似关系；同学集合A={a,b,c,d,e,f,g},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上的关

3、系R:R={

4、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,若x-y=3t,y-z=3s,则有:x-z=3(t+s),即∈R.关系图如下图所示.等价类定义2：设R为集合A上的等价关系，对任意a∈A，集合[a]R={x

5、x∈A,∈R}称为元素a关于R的等价类。例2可求出三个不同的等价类[1]R=[4]R=[7]R={1,4,7}[2]

6、R=[5]R=[8]R={2,5,8}[3]R=[6]R={3,6}定义3:集合A上的等价关系R，其等价类集合{[a]R

7、a∈A}称作A关于R的商集(quotientset)。记作A/R(1)a∈[a]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/R1、A/R={[a]R

8、a∈A}中,　∪[a]R=A2、对任意

9、a∈A，都有aRa，即a∈[a]R，即A中的每一个元素都属于一个分块。3、A的每个元素只能属于一个分块反证设a∈[b]R，a∈[c]R,且[b]R≠[c]R，则bRa,cRa成立，所以有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在同

10、一个分块中，则b与a在同一个分块中，即若aRb，有bRa，故R是对称的。③、a与b在同一个分块中，b与c在同一个分块中，而由划分的定义b只能属于且属于一个分块，故a与c必在同一分块中，即若有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}={

11、}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〉,〈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}

12、×{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

13、a∈A}，A/R2＝{[a]R2

14、a∈A}R1＝R2，