在數學中，對於集合X上的二元關係R，其自反閉包為X上包含R的最小的自反關係。
例如，若取集合X為數的集合，並定義X上的二元關係R，滿足x R y \iff x ，則R的自反閉包為關係R'，滿足x R' y \iff x \le y。
定義
給定集合X上的二元關係R，其自反閉包R^{=}的定義為關係R與恆等關係I_X的聯集，形式語言寫作：
:R^{=} = R \cup I_X。
其中恆等關係被定義為
:I_X = \{(x, x):x \in X\}，
或更嚴格的形式語言寫作
:I_X = \{i \in X \times X \mid (\exists x \in X)[i = (x, x)]\}。
這裡(x, x)表示一個有序對。
證明
給定集合X上的二元關係R，其自反閉包R^{=}滿足以下性質：
- 包含性：R \subseteq R^{=}。
{{Math proof|
對於任意r \in R，有(r \in R) \lor (r \in I_X)，故r \in R \cup I_X = R^{=}。即R \subseteq R^{=}。
}}
- 自反性：(\forall x \in X)(x R^{=} x)。
{{Math proof|
對於任意x \in X，有(x, x) \in I_X，又因為I_X \subseteq R^{=}，故(x, x) \in R^{=}。即(\forall x \in X)(x R^{=} x)。
}}
- 最小性：對任意X上的自反關係S，若R \subseteq S，則R^{=} \subseteq S。
{{Math proof|
根據S的假設，有(\forall r \in R)(r \in S)和(\forall x \in X)[(x, x) \in S]，
更進一步的，有(\forall i \in I_X)(i \in S)。
此時，將條件合併有(\forall s)[(s \in R) \lor (s \in I_X) \implies s \in S] \iff (\forall s)(s \in R^{=} \implies s \in S)，即R^{=} \subseteq S。
}}
性質
記謂詞\operatorname{Refl}_X(Q)表示Q為集合X上的自反關係，即\operatorname{Refl}_X(Q) \iff (\forall x \in X)[(x, x) \in Q]。則自反閉包具備以下性質：
- \operatorname{Refl}_X(R) \iff I_X \subseteq R。
- \operatorname{Refl}_X(R) \iff R = R^{=}。
- R \subseteq X \times X \implies (R^{=})^{=} = R^{=}。
- 對集合X上的關係R和S，R \subseteq S \implies R^{=} \subseteq S^{=}。
参見
- 传递闭包
- 对称闭包
参考资料
- Franz Baader and Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1998, p. 8
评论 (0)