等价关系与等价类

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

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

2、集合A上的二元关系，上的二元关系， 如果对于任意如果对于任意x，y，zA， 每当每当 R且且 R，就有就有 R，称关系，称关系R在在A上是传递的。上是传递的。1R110M100001abc1RR1 是对称的。1R a,a,a,b ,b,a,c,c abc2R2R110M110001R2 是自反的、对称的、传递的。2R a,a,a,b ,b,a,b,b ,c,c 等价关系与等价类的基本概念等价关系与等价类的基本概念1等价关系的基本性质等价关系的基本性质2主要内容主要内容商集与集合的划分商集与集合的划分3 3一、定义一、定义定义定义1:设设R为定义在集合为定义在集合A上的一个关系，上的一个关系，若

3、若R是自反的，对称的和传递的是自反的，对称的和传递的，则称，则称R为集为集合合A上的等价关系。上的等价关系。例如例如n平面上三角形集合中，三角形的相似关平面上三角形集合中，三角形的相似关系；系；n同学集合同学集合A=a,b,c,d,e,f,g,A中的关系中的关系R：住在同一宿舍；：住在同一宿舍；n同性关系。同性关系。例例1 1 设设T T1 1，2 2，3 3，4 4，R R1 1，1 1，1 1，4 4，4 4，1 1， 4 4，4 4，2 2，2 2，2 2，3 3， 3 3，2 2，3 3，3 3。验证验证R R是集合是集合T T上的等价关系。上的等价关系。100101100110100

4、1RM轾犏犏犏=犏犏犏臌2100110011001011001100110011001100110100110011001RM轾轾轾犏犏犏犏犏犏犏犏犏=犏犏犏犏犏犏犏犏犏臌臌臌例例2 2 设设A = 1, 2, A = 1, 2, , 8 , , 8 , 如下定义如下定义A A上的关系上的关系R:R: R = | x, y A且且xy（mod3) 证明证明R为为A上的等价关系。上的等价关系。证明证明: xA , 因为x-x=0=03,所以R; x,yA, 若x-y=3t(t为整数）, 则有: y-x=-3t,即 R; x,y,zA, 若x-y=3t, y-z=3s, 则有: x-z=3(t+s