かじもとにっき

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

2項関係(6)

定義 symmetric relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm symmetric}\nolimits} \\\mathop  \equiv \limits^{def} \forall x,y \in X.xRy \Rightarrow yRx\\ \equiv {R^T} \subseteq R\\ \equiv {R^T} = R\end{array}

定義 asymmetric relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm asymmetric}\nolimits} \\\mathop  \equiv \limits^{def} \forall x,y \in X.xRy \Rightarrow y\not Rx\\ \equiv {R^T} \subseteq \overline R \\ \equiv {R^T} \cap R \subseteq \emptyset \\ \equiv {R^T} \cap R = \emptyset \end{array}

定義 antisymmetric relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm antisymmetric}\nolimits} \\\mathop  \equiv \limits^{def} \forall x,y \in X.xRy \wedge yRx \Rightarrow x = y\\ \equiv {R^T} \cap R \subseteq {\rm I}\\ \equiv {R^T} \subseteq \overline R  \cup {\rm I}\end{array}

用語

R:X \to Xのようにdomainとcodomainが等しい2項関係を(X上の)homogeneous relationやendorelationとも言う。

定理

あらゆるendorelationはsymmetricな部分とasymmetricな部分に分割できる。

証明

endorelation Rに対し、
R = R \cap \Omega  = R \cap ({R^T} \cup \overline {{R^T}} ) = (R \cap {R^T}) \cup (R \cap \overline {{R^T}} )
であり、
(R \cap {R^T}) \cap (R \cap \overline {{R^T}} ) = \emptyset
なので、\left\{ {R \cap {R^T},R \cap \overline {{R^T}} } \right\}Rの分割である。
さらに、{(R \cap {R^T})^T} = R \cap {R^T}よりR \cap {R^T}:{\mathop{\rm symmetric}\nolimits}
また、{(R \cap \overline {{R^T}} )^T} \cap (R \cap \overline {{R^T}} ) = \emptyset よりR \cap \overline {{R^T}} :{\mathop{\rm asymmetric}\nolimits}

定義 symmetric closure

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

定理

{\mathop{\rm symm}\nolimits} R = R \cup {R^T}

証明

任意のXについて、
\begin{array}{l}X \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm symmetric}\nolimits} } \right\}\\ \equiv R \subseteq X \wedge X:{\mathop{\rm symmetric}\nolimits} \\ \equiv R \subseteq X \wedge X = {X^T}\\ \Rightarrow R \subseteq X \wedge {R^T} \subseteq X \wedge X = {X^T}\\ \Rightarrow R \cup {R^T} \subseteq X\end{array}
なので、
R \cup {R^T} \subseteq  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm symmetric}\nolimits} } \right\}

また、R \subseteq R \cup {R^T}{(R \cup {R^T})^T} = R \cup {R^T}よりR \cup {R^T} \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm symmetric}\nolimits} } \right\}
よって、
\cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm symmetric}\nolimits} } \right\} \subseteq R \cup {R^T}\