かじもとにっき

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

2項関係(20)

定理

R:{\mathop{\rm asymmetric}\nolimits}  \Rightarrow R:{\mathop{\rm irreflexive}\nolimits}

証明

{R^T} \subseteq \overline Rと仮定する。

\begin{array}{l}{R^T} \subseteq \overline R \\ \equiv {R^T} \circ {\rm I} \subseteq \overline R \\ \equiv R \circ R \subseteq \overline {\rm I} \end{array}
よりR \cap R \circ R \subseteq \overline {\rm I}

また、
\begin{array}{l}{\rm I} \cap R\\ = R \circ {\rm I} \cap {\rm I}\\ \subseteq (R \cap {\rm I} \circ {{\rm I}^T}) \circ ({\rm I} \cap {R^T} \circ {\rm I})\\ \subseteq R \circ ({R^T} \circ {\rm I} \cap {\rm I})\\ \subseteq R \circ ({R^T} \cap {\rm I} \circ {{\rm I}^T}) \circ ({\rm I} \cap R \circ {\rm I})\\ \subseteq R \circ {\rm I} \circ R\\ = R \circ R\end{array}
であり、
{\rm I} \cap R \subseteq R \circ R \equiv R \cap \overline {R \circ R}  \subseteq \overline {\rm I}

以上より、
R = R \cap (R \circ R \cup \overline {R \circ R} ) = (R \cap R \circ R) \cup (R \cap \overline {R \circ R} ) \subseteq \overline {\rm I}

定理

R:{\mathop{\rm asymmetric}\nolimits}  \equiv R:{\mathop{\rm antisymmetric}\nolimits}  \wedge R:{\mathop{\rm irreflexive}\nolimits}

証明

R:{\mathop{\rm asymmetric}\nolimits}と仮定すると、R \cap {R^T} \subseteq \emptyset  \subseteq {\rm I}と先の定理を合わせてR:{\mathop{\rm antisymmetric}\nolimits}  \wedge R:{\mathop{\rm irreflexive}\nolimits}が成り立つ。
逆に、R \cap {R^T} \subseteq {\rm I}R \subseteq \overline {\rm I}を仮定すると、対偶と推移律によりR:{\mathop{\rm asymmetric}\nolimits}が成り立つ。

定義

\begin{array}{l}R:{\mathop{\rm preorder}\nolimits} \\\mathop  \equiv \limits^{def} R:{\mathop{\rm transitive}\nolimits}  \wedge R:{\mathop{\rm reflexive}\nolimits} \\ \equiv R \circ R \subseteq R \wedge {\rm I} \subseteq R\\ \equiv R \circ R = R \wedge {\rm I} \subseteq R\end{array}

定義

\begin{array}{l}R:{\mathop{\rm order}\nolimits} \\\mathop  \equiv \limits^{def} R:{\mathop{\rm preorder}\nolimits}  \wedge R:{\mathop{\rm antisymmetric}\nolimits} \\ \equiv R \circ R \subseteq R \wedge {\rm I} \subseteq R \wedge R \cap {R^T} \subseteq {\rm I}\end{array}

定義

\begin{array}{l}R:{\mathop{\rm strictorder}\nolimits} \\\mathop  \equiv \limits^{def} R:{\mathop{\rm transitive}\nolimits}  \wedge R:{\mathop{\rm asymmetric}\nolimits} \\ \equiv R \circ R \subseteq R \wedge R \cap {R^T} \subseteq \emptyset \\ \equiv R \circ R \subseteq R \wedge {R^T} \subseteq \overline R \\ \equiv R \circ R \subseteq R \wedge R \subseteq \overline {\rm I} \\ \equiv R:{\mathop{\rm transitive}\nolimits}  \wedge R:{\mathop{\rm irreflexive}\nolimits} \end{array}

証明

R \circ R \subseteq R \wedge {R^T} \subseteq \overline R  \equiv R \circ R \subseteq R \wedge R \subseteq \overline {\rm I}を示す。

R \circ R \subseteq R \wedge {R^T} \subseteq \overline R  \Rightarrow R \circ R \subseteq R \wedge R \subseteq \overline {\rm I}は先の定理から明らか。
逆に、R \circ R \subseteq R \wedge R \subseteq \overline {\rm I}を仮定すると、推移律からR \circ R \subseteq \overline {\rm I}であり、Schröder律によって直ちにこれが{R^T} \subseteq \overline Rと同値だとわかる。