等價關系、等價類與劃分
文章目錄
- 等價關系、等價類與劃分
-
- 等價關系的定義
- 等價類
-
- 等價類的性質
- 集合的劃分
- 商集
- 等價關系與劃分的一一對應
等價關系的定義
定義：設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的下标)