等价关系、等价类与划分
文章目录
- 等价关系、等价类与划分
-
- 等价关系的定义
- 等价类
-
- 等价类的性质
- 集合的划分
- 商集
- 等价关系与划分的一一对应
等价关系的定义
定义：设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一 个等价关系，若<x,y> ∈R ，称x等价于y，记作x~y。
（即R同时满足自反性、对称性、传递性，则R为A上的等价关系）
例1：
设A={1,2...,8}，如下定义A上的关系R：
R={<x,y>|x,y≡∈A∧x≡y(mod3)}, 其中x≡y(mod3)叫做x与y模3相等（即x除以3的余数与y除以3的余数相等）
R={ <1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<8,8>, <1,4>,<1,7>,<4,1>,<4,7>,<7,1>,<7,4>,<2,5>,<2,8>,<5,2>,<5,8>,<8,2>,<8,5>,<3,6>,<6,3>}
因为∀x∈A,有x≡x(mod3)
∀x,y∈A,有x≡y(mod3),则有y≡x(mod3)
∀x,y,z∈A,有x≡y(mod3),y≡z(mod3)则有x≡z(mod3)
同时满足自反性、对称性、传递性，所以R为A上的等价关系
以下为R的关系图
例2：
设S={a,b,c},定义S上的关系R=Is∪{<a,b>,<b,a>}，R是否是S上的等价关系？（注：Is中的s为I的下标）
正确答案：是
等价类
定义：设R为非空集合A上的等价关系, ∀x∈A，令[x]R = { y | y∈A∧xRy }
称 [x]R 为 x 关于R 的等价类, 简称为 x 的等价类, 简记为[x]。
例3：
求例1中等价关系的等价类。
等价类：
[1]=[4]=[7]={1,4,7}
[2]=[5]=[8]={2,5,8}
[3]=[6]={3,6}
等价类的性质
设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
例4：
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}
例5：
设S={a,b,c}，定义S上的等价关系R=Is∪{<a,b>,<b,a>}，
则[a]=？[b]=？[c]=？
[a]={a,b}
[b]={a,b}
[c]={c}
集合的划分
定义 设A为非空集合, 若A的子集族π(π ⊆ P(A)) 满足下面条件：
(1) Ø ∉ π
(2) ∀x∀y (x,y∈π∧x≠y→x∩y= Ø)
(3) ∪π=A
称π是A的一个划分, 称π中的元素为A的划分块。
例6：
设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的划分。
商集
定义：设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R | x∈A }
例7：
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：
设S={a,b,c}，定义S上的等价关系R=Is∪{<a,b>,<b,a>}，
则S/R=？
正确答案：{{a,b},{c}}
等价关系与划分的一一对应
商集 A/R 就是 A 的一个划分；
例如： A={1,2,…,8},A关于模3等价关系R的商集为：
A/R = { {1,4,7}, {2,5,8}, {3,6} }，它就是Ａ的一个划分
不同的商集对应于不同的划分；
任给 A 的一个划分π, 如下定义 A 上的关系 R：
R = {<x,y> | x,y∈A∧x 与 y 在π的同一划分块中}，则 R 为 A上的等价关系, 且该等价关系确定的商集是π。
例9：
求出A＝{1,2,3}上所有的等价关系
求解思路：先求出A的所有划分, 然后根据划分写出对应的等价关系。(如下图)
π1对应于全域关系 EA
π2对应等价关系 R2={<2,3>,<3,2>}∪IA
π3对应等价关系 R3 ={<1,3>,<3,1>}∪IA
π4对应等价关系 R4={<1,2>,<2,1>}∪IA
π5 对应于恒等关系 IA
(注：以上所出现的IA，A为I的下标)