文档介绍：等价关系与偏序关系
等价关系的定义与实例
等价类及其性质
商集与集合的划分
等价关系与划分的一一对应
偏序关系
偏序集与哈斯图
偏序集中的特定元素
1
等价关系的定义与实例
定义设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系.
设 R 是一个等价关系, 若<x,y>∈R, 称 x 等价于y, 记做 x~y. 
实例设 A={1,2,…,8}, 如下定义A上的关系 R: R = { <x,y> | x,y∈A∧x≡y(mod 3) } 其中 x≡y(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等.
2
等价关系的验证
验证模 3 相等关系 R 为 A上的等价关系, 因为 x∈A, 有x ≡ x(mod 3) x, y∈A, 若 x ≡ y(mod 3), 则有 y ≡ x(mod 3) x, y, z∈A, 若x ≡ y(mod 3), y ≡ z(mod 3),
则有 x≡z(mod 3)
自反性、对称性、传递性得到验证
3
A上模3等价关系的关系图
设 A={1,2,…,8}, R={ <x,y>| x,y∈A∧x≡y(mod 3) }
4
等价类
定义设R为非空集合A上的等价关系, x∈A,令 [x]R = { y | y∈A∧xRy }
称[x]R 为 x 关于R 的等价类, 简称为 x 的等价类, 简
记为[x].
实例 A={ 1, 2, …, 8 }上模 3 等价关系的等价类: [1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6}
5
等价类的性质
定理1 设R是非空集合A上的等价关系, 则 (1) x∈A, [x] 是A的非空子集. (2) x, y∈A, 如果 x R y, 则[x]=[y]. (3) x, y∈A, 如果 x y, 则[x]与[y]不交. (4) ∪{ [x] | x∈A}=A,即所有等价类的并集就是A.
6
实例
A={ 1, 2, …, 8 }上模 3 等价关系的等价类: [1]=[4]=[7]={1,4,7},
[2]=[5]=[8]={2,5,8},
[3]=[6]={3,6}
以上3 类两两不交,
{1,4,7}{2,5,8}{3,6} = {1,2, …,8}
7
商集
定义设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R | x∈A }
实例 A={1,2,…,8},A关于模3等价关系R的商集为 A/R = { {1,4,7}, {2,5,8}, {3,6} } A关于恒等关系和全域关系的商集为:
A/IA = { {1},{2}, …,{8}}
A/EA = { {1, 2, …,8} }
8
集合的划分
定义设A为非空集合, 若A的子集族π(πP(A)) 满足下面条件:
(1) π
(2) xy (x,y∈π∧x≠y→x∩y=) (3) ∪π=A 则称π是A的一个划分, 称π中的元素为A的划分块.
9
例题
例1 设A={a, b, c, d},
给定π1,π2,π3,π4,π5,π6如下:
π1= { {a, b, c}, {d} }, π2= { {a, b}, {c}, {d} } π3= { {a}, {a, b, c, d} }, π4= { {a, b}, {c} } π5= { ,{a, b}, {c, d} }, π6= { {a, {a}}, {b, c, d} }
则π1和π2 是A的划分, 其他都不是 A 的划分.
为什么?
10