传递闭包
| 传递闭包 | |
|---|---|
| 术语名称 | 传递闭包 |
| 英语名称 | transitive closure |
传递闭包(transitive closure)是指对集合上的一个二元关系，包含其的最小的传递关系。
定义
| 传递闭包 | |
|---|---|
| 运算名称 | 传递闭包 |
| 运算符号 | [math]\displaystyle{ \operatorname{t}() }[/math] |
| Latex | \operatorname{t}
|
| 运算对象 | 关系 |
| 运算元数 | 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] 的传递闭包(transitive closure)，记作 [math]\displaystyle{ \operatorname{t}(R) }[/math] 或 [math]\displaystyle{ R^+ }[/math]。
性质
可证明，集合 [math]\displaystyle{ X }[/math] 上关系的传递闭包是这一关系与其自身任意次复合（即其任意次幂）的并，即 [math]\displaystyle{ \operatorname{t}(R) = R \cup R^2 \cup R^3 \cup \dots = \bigcup_{i=1}^\infty R^i }[/math] 。
对称关系的对称闭包是其自身。