幂（关系）
| 幂 | |
|---|---|
| 术语名称 | 幂 |
| 英语名称 | power |
关系的幂(power of relations)指一个关系自我复合多次构成的关系。
定义
| 幂关系 | |
|---|---|
| 运算名称 | 幂关系 |
| 运算符号 | [math]\displaystyle{ \bullet^n }[/math] |
| Latex | ^
|
| 运算对象 | 关系, 自然数 |
| 运算元数 | 2 |
| 运算结果 | 关系 |
| 定义域 | [math]\displaystyle{ \mathcal{P}(X \times X) \times \mathbb{N} }[/math] |
| 陪域 | [math]\displaystyle{ \mathcal{P}(X \times X) }[/math] |
对集合 [math]\displaystyle{ X }[/math] 上的二元关系 [math]\displaystyle{ R }[/math] ，记 [math]\displaystyle{ R^1 = R }[/math] 并递推地记 [math]\displaystyle{ R^{n+1} = R \circ R^{n} }[/math]，称为 [math]\displaystyle{ R }[/math] 的幂(power)。
由于复合的结合性，幂定义成 [math]\displaystyle{ R^{n+1} = R^{n} \circ R }[/math] 也是相同的。
注意：由于复合会限制前后域之前的关系，自身复合需要前后域相同。
零指数
定义 [math]\displaystyle{ R^0 = I_X }[/math] 为恒等映射。 由于复合运算要求前一个关系的后域与后一个关系的前域匹配，一般要求 [math]\displaystyle{ R }[/math] 是齐次二元关系。
但也有人不限制齐次关系，此时可以定义为 [math]\displaystyle{ I_{\operatorname{fld}(R)} }[/math]。 也有人在可逆的情况下定义，不总有这样的定义。
负指数
逆关系经常也写成指数形式的 [math]\displaystyle{ R^{-1} }[/math] ，但逆关系不是逆元，不允许通过负指数的形式表达，因此一般不允许使用负指数幂。
性质
- 表示
- 幂的指数法则
- [math]\displaystyle{ R^m \circ R^n = R^{m+n} }[/math]（对任意非负整数 m, n）
- [math]\displaystyle{ (R^m)^n = R^{mn} }[/math]（对任意非负整数 m, n）
- 幂的单调性
- 如果 [math]\displaystyle{ R \subseteq S }[/math]，则 [math]\displaystyle{ R^n \subseteq S^n }[/math]（对任意非负整数 n）
- 如果 R 是自反关系，则 [math]\displaystyle{ R^n \subseteq R^{n+1} }[/math]（对任意非负整数 n）
- 与传递闭包的关系：
- 稳定性：
- 存在最小正整数 k（称为 R 的指数）和周期 d，使得对所有 [math]\displaystyle{ n \geq k }[/math]，有 [math]\displaystyle{ R^{n+d} = R^n }[/math]
- 特别地，对于有限集合，关系幂序列最终会进入周期循环
- 特殊关系的幂：
- 如果 R 是自反关系，则所有 [math]\displaystyle{ R^n }[/math] 也是自反关系
- 如果 R 是对称关系，则所有 [math]\displaystyle{ R^n }[/math] 也是对称关系
- 如果 R 是传递关系，则 [math]\displaystyle{ R^n \subseteq R }[/math]（对所有正整数 n）
- 如果 R 是等价关系，则 [math]\displaystyle{ R^n = R }[/math]（对所有正整数 n）
- 如果 R 是偏序关系，则 [math]\displaystyle{ R^n \subseteq R }[/math]（对所有正整数 n）