等价闭包

等价闭包
术语名称	等价闭包
英语名称	equivalence closure
别名	reflexive transitive symmetric closure

等价闭包(transitive closure)是指对集合上的一个二元关系，包含其的最小的等价关系。 它是自反闭包、对称闭包和传递闭包的复合。

定义

等价闭包
运算名称	等价闭包
运算符号	[math]\displaystyle{ \operatorname{eq}() }[/math],[math]\displaystyle{ \bullet^\equiv }[/math],[math]\displaystyle{ \bullet^\approx }[/math],[math]\displaystyle{ \bullet^e }[/math]
Latex	\operatorname{eq}, ^\equiv, ^\approx, ^e
运算对象	关系
运算元数	1
运算结果	关系
定义域	[math]\displaystyle{ \mathcal{P}(X\times X) }[/math]
陪域	[math]\displaystyle{ \mathcal{P}(X\times X) }[/math]

对集合 [math]\displaystyle{ X }[/math] 上的二元关系 [math]\displaystyle{ R }[/math] ，定义满足以下条件的所有关系 [math]\displaystyle{ S }[/math]：

• [math]\displaystyle{ S }[/math] 是等价关系；
• [math]\displaystyle{ S \supseteq R }[/math] 。

其中必有一个关系是其他所有关系的子集，称为关系 [math]\displaystyle{ R }[/math] 的等价闭包(quivalence closure)，记作 [math]\displaystyle{ \operatorname{e}(R) }[/math] 、 [math]\displaystyle{ R^\equiv }[/math] 、 [math]\displaystyle{ R^\approx }[/math] 或 [math]\displaystyle{ R^e }[/math]。

性质

• 基本性质
  • 计算： [math]\displaystyle{ \operatorname{eq}(R) = \operatorname{t}(\operatorname{s}(\operatorname{r}(R))) }[/math] 。
  • 等价闭包是包含 [math]\displaystyle{ R }[/math] 的最小等价关系。
  • 等价闭包运算的复合顺序：先取自反闭包，再取对称闭包，最后取传递闭包。自反的顺序不做要求，但对称闭包必须在传递闭包前进行。
  • 在有限集合上，等价闭包可在有限步内计算。
• 运算性质
  • 等价闭包运算是幂等的： [math]\displaystyle{ \operatorname{eq}(\operatorname{eq}(R)) = \operatorname{eq}(R) }[/math] 。
  • 等价闭包运算是单调的： 如果 [math]\displaystyle{ R \subseteq S }[/math] ，则 [math]\displaystyle{ \operatorname{eq}(R) \subseteq \operatorname{eq}(S) }[/math] 。
  • 等价闭包与并运算的关系： [math]\displaystyle{ \operatorname{eq}(R \cup S) \supseteq \operatorname{eq}(R) \cup \operatorname{eq}(S) }[/math] 。
• 特殊关系的等价闭包
  • 空关系的等价闭包是恒等关系： [math]\displaystyle{ \operatorname{eq}(\emptyset) = I_X }[/math] 。
  • 等价关系的等价闭包是其自身
  • 恒等关系是等价关系，故其等价闭包是其自身： [math]\displaystyle{ \operatorname{eq}(I_X) = I_X }[/math] 。
  • 全关系是等价关系，故其等价闭包是其自身： [math]\displaystyle{ \operatorname{eq}(X \times X) = X \times X }[/math] 。
• 表示
  • 等价闭包的关系矩阵是一个分块对角矩阵，只有主对角线上存在全 1 的子分块，每个这样的分块对应一个等价类。
  • 等价闭包的关系图，对应于将原关系图转换为无向图后按连通分量划分，每个连通分量通过原关系图添加自环、对称边和传递边成为一个完全图。

关系
定义属性	前域、后域、定义域 [math]\displaystyle{ \operatorname{dom} }[/math]、值域 [math]\displaystyle{ \operatorname{ran} }[/math]、域 [math]\displaystyle{ \operatorname{fld} }[/math]
特殊关系	空关系 [math]\displaystyle{ \varnothing }[/math]、恒等关系 [math]\displaystyle{ I }[/math]、全关系 [math]\displaystyle{ A\times B }[/math]
二元齐次关系类型	自反、反自反、对称、反对称、传递
运算	集合运算	交 [math]\displaystyle{ \cap }[/math]、并 [math]\displaystyle{ \cup }[/math]、补 [math]\displaystyle{ \bar{\bullet} }[/math]、差 [math]\displaystyle{ \setminus }[/math]
	类映射运算	转置/逆 [math]\displaystyle{ \bullet^\mathrm{T}/\bullet^{-1} }[/math]、复合 [math]\displaystyle{ \circ }[/math]（幂 [math]\displaystyle{ \bullet^n }[/math]）、限制 [math]\displaystyle{ \bullet_{|\bullet} }[/math]
	闭包运算	自反 [math]\displaystyle{ \operatorname{r}() }[/math]/[math]\displaystyle{ \bullet^= }[/math]、对称 [math]\displaystyle{ \operatorname{s}() }[/math]/[math]\displaystyle{ \bullet^\sim }[/math]、传递 [math]\displaystyle{ \operatorname{t}() }[/math]/[math]\displaystyle{ \bullet^+ }[/math]、自反传递 [math]\displaystyle{ \bullet^* }[/math]、等价 [math]\displaystyle{ \bullet^\equiv }[/math]