かじもとにっき

ゆるふわなおはなしをかきます

2項関係(12)

定理

{({R^+})^T} = {({R^T})^+}
{({R^*})^T} = {({R^T})^*}

定義 equivalence relation

R:{\mathop{\rm equivalence}\nolimits} \mathop  \equiv \limits^{def} R:{\mathop{\rm reflexive}\nolimits}  \wedge R:{\mathop{\rm transitive}\nolimits}  \wedge R:{\mathop{\rm symmetric}\nolimits}

定義 equivalence closure

{\mathop{\rm equiv}\nolimits} R\mathop  = \limits^{def}  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\}

定理

{\mathop{\rm equiv}\nolimits} R = {(R \cup {R^T})^*}

証明

R \subseteq R \cup {R^T} \subseteq {(R \cup {R^T})^*}
{(R \cup {R^T})^*}:{\mathop{\rm reflexive}\nolimits}  \wedge {(R \cup {R^T})^*}:{\mathop{\rm transitive}\nolimits}
{({(R \cup {R^T})^*})^T} = {({(R \cup {R^T})^T})^*} = {(R \cup {R^T})^*}より{(R \cup {R^T})^*}:{\mathop{\rm symmetric}\nolimits}
以上より{(R \cup {R^T})^*} \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\}
よって\cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\} \subseteq {(R \cup {R^T})^*}

任意のXについて、{R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} }を仮定すると、{R^T} \subseteq {X^T} = Xより、R \cup {R^T} \subseteq Xが得られる。
さらに{X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} }だから、{(R \cup {R^T})^*} \subseteq X
よって{(R \cup {R^T})^*} \subseteq  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\}