等价关系与等价类.ppt

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是自反的 对称的 传递的 主要内容 一 定义 定义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上的关系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 若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的商集 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 a A 中 a R A2 对任意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在同一个分块中 则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 R R1 R2 R3 例3A 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 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 x A aR1x x x A aR2x 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所以 R1a a R1 b a R1a c R2 b c R2 R2所以R1是R2的子集 同理可证R2也是R1的子集 所以R1 R2 定理4 设R1和R2为非空集合A上的等价关系 则R1 R2当且仅当A R1 A R2