查看“︁幂（关系）”︁的源代码

[[分类:关系]]{{DEFAULTSORT:mi4}}
{{#seo:
|keywords=关系的幂, 幂关系
|description=本文介绍关系幂的概念、定义及其基本性质，包括关系自我复合的运算规则、零指数幂的定义以及关系幂与传递闭包的联系。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2023-04-22
}}
{{InfoBox
|name=幂
|eng_name=power
}}
关系的'''幂'''('''power''' of relations)指一个[[关系]]自我[[复合（关系）|复合]]多次构成的关系。

== 定义 ==

{{Operation
|name=幂关系
|symbol=<math>\bullet^n</math>
|latex=^
|operand=关系,自然数
|result=关系
|domain=<math>\mathcal{P}(X \times X) \times \mathbb{N}</math>
|codomain=<math>\mathcal{P}(X \times X)</math>
}}
对集合 <math>X</math> 上的二元关系 <math>R</math> ，记 <math>R^1 = R </math> 并递推地记 <math>R^{n+1} = R \circ R^{n}</math>，称为 <math>R</math> 的'''幂'''('''power''')。

由于复合的结合性，幂定义成 <math>R^{n+1} = R^{n} \circ R</math> 也是相同的。

注意：由于复合会限制前后域之前的关系，自身复合需要前后域相同。

=== 零指数 ===

定义 <math>R^0 = I_X</math> 为恒等映射。
由于复合运算要求前一个关系的后域与后一个关系的前域匹配，一般要求 <math>R</math> 是齐次二元关系。

但也有人不限制齐次关系，此时可以定义为 <math>I_{\operatorname{fld}(R)}</math>。
也有人在可逆的情况下定义，不总有这样的定义。

=== 负指数 ===

[[逆关系]]经常也写成指数形式的 <math>R^{-1}</math> ，但逆关系不是逆元，不允许通过负指数的形式表达，因此一般不允许使用负指数幂。

== 性质 ==
* 表示
** <math>R^n</math> 的关系矩阵是 R 的关系矩阵的 n 次布尔幂（使用[[逻辑与]]和[[逻辑或]]的矩阵幂）
** 在关系图中，<math>(a,b) \in R^n</math> 当且仅当存在从 a 到 b 的长度为 n 的路径
* 幂的指数法则
** <math>R^m \circ R^n = R^{m+n}</math>（对任意非负整数 m, n）
** <math>(R^m)^n = R^{mn}</math>（对任意非负整数 m, n）
* 幂的单调性
** 如果 <math>R \subseteq S</math>，则 <math>R^n \subseteq S^n</math>（对任意非负整数 n）
** 如果 R 是[[自反关系]]，则 <math>R^n \subseteq R^{n+1}</math>（对任意非负整数 n）
* 与传递闭包的关系：
** 关系 R 的[[传递闭包]]等于 <math>R^+ = \bigcup_{n=1}^\infty R^n</math>
** 关系 R 的[[自反传递闭包]]等于 <math>R^* = \bigcup_{n=0}^\infty R^n = R^0 \cup R^+</math>
* 稳定性：
** 存在最小正整数 k（称为 R 的指数）和周期 d，使得对所有 <math>n \geq k</math>，有 <math>R^{n+d} = R^n</math>
** 特别地，对于有限集合，关系幂序列最终会进入周期循环
* 特殊关系的幂：
** 如果 R 是[[自反关系]]，则所有 <math>R^n</math> 也是自反关系
** 如果 R 是[[对称关系]]，则所有 <math>R^n</math> 也是对称关系
** 如果 R 是[[传递关系]]，则 <math>R^n \subseteq R</math>（对所有正整数 n）
** 如果 R 是[[等价关系]]，则 <math>R^n = R</math>（对所有正整数 n）
** 如果 R 是[[偏序关系]]，则 <math>R^n \subseteq R</math>（对所有正整数 n）


{{关系}}