等价关系和划分
等价关系和等价类
集合 X X X上自反、对称且传递的关系称为 X X X上的等价关系。
设 R R R是 X X X上的等价关系， x ∈ X x\in X x∈X，定义 X X X的子集
[ x ] R = { y ∣ y ∈ X , 且 y R x } [x]_R=\{y|y\in X,且yRx\} [x]R?={
y∣y∈X,且yRx}
称 [ x ] R [x]_R [x]R?为 x x x（关于 R R R）的等价类， x x x为等价类 [ x ] R [x]_R [x]R?的代表元。
也就是说， x ( ∈ X ) x(\in X) x(∈X)的等价类 [ x ] R [x]_R [x]R?由 X X X中所有与 x x x等价的元素组成。
性质
-
[ x ] R ≠ ? [x]_R\ne\empty [x]R???=?
-
若 ( x , y ) ∈ R (x,y)\in R (x,y)∈R，则 [ x ] R = [ y ] R [x]_R=[y]_R [x]R?=[y]R?
x , y x,y x,y同样具有关系 R R R
- 任意等价类中的任意一个元素都可以作为该等价类的代表元
-
若 ( x , y ) ? R (x,y)\notin R (x,y)∈/?R，则 [ x ] R ∩ [ y ] R = ? [x]_R\cap [y]_R=\empty [x]R?∩[y]R?=?
- 任意两个等价类要么相等要么没有公共元素
- 等价类是由所有那些相互等价的元素组成的，且其外的元素都不与其中的元素等价
-
? z ∈ X [ z ] R = X \bigcup_{z\in X}[z]_R=X ?z∈X?[z]R?=X
证明
-
R 自 反 ? x R x ? x ∈ [ x ] R R自反\Rightarrow xRx\Rightarrow x\in [x]_R R自反?xRx?x∈[x]R?.
-
? z ∈ [ x ] R ? z R x ∧ x R y ? z R y ? z ∈ [ y ] R \forall z\in[x]_R\Rightarrow zRx\wedge xRy\Rightarrow zRy\Rightarrow z\in[y]_R ?z∈[x]R??zRx∧xRy?zRy?z∈[y]R?，所以 [ x ] R ∈ [ y ] R [x]_R\in[y]_R [x]R?∈[y]R??，反之同理.
-
利用反证法，假设 ? z ∈ [ x ] R ∧ [ y ] R \exist z\in[x]_R\wedge[y]_R ?z∈[x]R?∧[y]R?，则 z R x ∧ z R y ? x R z ∧ z R y ? x R y zRx\wedge zRy\Rightarrow xRz\wedge zRy\Rightarrow xRy zRx∧zRy?xRz∧zRy?xRy，与前提矛盾，假设不成立.
-
推导如下
X = ? { { x } ∣ x ∈ X } ? ? { [ x ] R ∣ x ∈ X } ? ? { X ∣ x ∈ X } = X \begin{aligned} X &= \bigcup\{\{x\}|x\in X\} \\ &\subseteq \bigcup\{[x]_R|x\in X\} \\ &\subseteq \bigcup\{X|x\in X\} \\ &= X \end{aligned} X?=?{ { x}∣x∈X}??{ [x]R?∣x∈X}??{ X∣x∈X}=X?
商集
X X X上关于 R R R的所有等价类组成的集合称为 X X X关于 R R R的商集，记为 X / R X/R X/R，即
X / R = { [ x ] R ∣ x ∈ X } X/R=\{[x]_R|x\in X\} X/R={
[x]R?∣x∈X}
特殊的等价关系
全关系
X / E X = { { x 1 , x 2 , ? , x n } } X/E_X=\{\{x_1,x_2,\cdots,x_n\}\} X/EX?={ { x1?,x2?,?,xn?}}
恒等关系
X / I X = { { x 1 } , { x 2 } , ? , { x n } } X/I_X=\{\{x_1\},\{x_2\},\cdots,\{x_n\}\} X/IX?={ { x1?},{ x2?},?,{ xn?}}
R i j R_{ij} Rij?
记 R i j = I X ∪ { ( x i , x j ) , ( x j , x i ) } , x i , x j ∈ X , i ≠ j R_{ij}=I_X\cup \{(x_i,x_j),(x_j,x_i)\},x_i,x_j\in X,i\neq j Rij?=IX?∪{
(xi?,xj?),(xj?,xi?)},xi?,xj?∈X,i??=j，则
X / R i j = X / I A ∪ { { x i , x j } } ? { { x i } , { x j } } = { { x 1 } , ? , { x i ? 1 } , { x i + 1 } , ? , { x j ? 1 } , { x j + 1 } , ? , { x n } , { x i , x j } } \begin{aligned} X/R_{ij} &= X/I_A\cup \{\{x_i,x_j\}\}-\{\{x_i\},\{x_j\}\} \\ &= \{\{x_1\},\cdots,\{x_{i-1}\},\{x_{i+1}\},\cdots,\{x_{j-1}\},\{x_{j+1}\},\cdots,\{x_n\},\{x_i,x_j\}\} \end{aligned} X/Rij??=X/IA?∪{
{
xi?,xj?}}?{
{
xi?},{
xj?}}={
{
x1?},?,{
xi?1?},{
xi+1?},?,{
xj?1?},{
xj+1?},?,{
xn?},{
xi?,xj?}}?
即除了 { x i , x j } \{x_i,x_j\} {
xi?,xj?}外，其他元素只和自身为等价类
应用
由等价关系求划分块
X = { a , b , c } X=\{a,b,c\} X={
a,b,c}上全体等价关系共有5种，
R 1 = I X , R 2 = E X , R 3 = I X ∪ { ( b , c ) , ( c , b ) } R 4 = I X ∪ { ( a , c ) , ( c , a ) } , R 5 = I X ∪ { ( a , b ) , ( b , a ) } R_1=I_X,R_2=E_X,R_3=I_X\cup\{(b,c),(c,b)\} \\ R_4=I_X\cup\{(a,c),(c,a)\},R_5=I_X\cup\{(a,b),(b,a)\} R1?=IX?,R2?=EX?,R3?=IX?∪{
(b,c),(c,b)}R4?=IX?∪{
(a,c),(c,a)},R5?=IX?∪{
(a,b),(b,a)}
相应导出的商集
X / R 1 = { { a } , { b } , { c } } , X / R 2 = { { a , b , c } } , X / R 3 = { { a } , { b , c } } X / R 4 = { { a , c } , { b } } , X / R 5 = { { a , b } , { c } } X/R_1=\{\{a\},\{b\},\{c\}\},X/R_2=\{\{a,b,c\}\},X/R_3=\{\{a\},\{b,c\}\} \\ X/R_4=\{\{a,c\},\{b\}\},X/R_5=\{\{a,b\},\{c\}\} X/R1?={
{
a},{
b},{
c}},X/R2?={
{
a,b,c}},X/R3?={
{
a},{
b,c}}X/R4?={
{
a,c},{
b}},X/R5?={
{
a,b},{
c}}
空关系不是 X X X上的等价关系（非自反）
划分
设 π \pi π是集合 X X X的非空子集的集合（ π ? P ( X ) \pi\subseteq P(X) π?P(X) ），满足
-
? A , B ∈ π , A = B 或 A ∩ B = ? \forall A,B\in \pi,A=B或A\cap B=\empty ?A,B∈π,A=B或A∩B=?
-
? A ∈ π A = X \bigcup_{A\in\pi} A=X ?A∈π?A=X
则称 π \pi π是 X X X的划分， π \pi π中的元素称为该划分的划分块。
划分和等价关系
等价关系和划分可以相互导出。
性质
-
设 R R R是 X X X上的等价关系，那么商集 X / R X/R X/R是 X X X的划分
记由 R R R导出的划分 X / R X/R X/R为 π R \pi_R πR?
-
设 π \pi π是集合 X X X的划分，则关系
R = { ( x , y ) ∣ x , y 同 属 于 π 的 一 个 划 分 块 } R=\{(x,y)|x,y同属于\pi的一个划分块\} R={ (x,y)∣x,y同属于π的一个划分块}
则 R R R是 X X X上的等价关系。这样导出的 R R R记为 R π R_{\pi} Rπ?
推论
R = R π R , π = π R π R=R_{\pi_R},\quad \pi=\pi_{R_{\pi}} R=RπR??,π=πRπ??
所以本质上，等价关系和划分描述的是同一件事情的两个方面。
证明
π R = X / R ; R π R = { ( x , y ) ∣ x , y ∈ [ u ] R } ? ( x , y ) ∈ R \pi_R=X/R;R_{\pi_R}=\{(x,y)|x,y\in[u]_R\}\Rightarrow (x,y)\in R πR?=X/R;RπR??={ (x,y)∣x,y∈[u]R?}?(x,y)∈R
由划分求等价关系
沿用[应用](# 应用)的例子，先求出划分，再还原等价关系。