かじもとにっき

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

2項関係(16)

定義 total relation

R:X \to Yの時、

\begin{array}{l}R:{\mathop{\rm total}\nolimits} \\\mathop  \equiv \limits^{def} \forall x \in X.\exists y \in Y.xRy\\ \equiv \Omega  = R \circ \Omega \\ \equiv {\rm I} \subseteq R \circ {R^T}\\ \equiv \overline R  \subseteq R \circ \overline {\rm I} \end{array}

証明

\Omega  = R \circ \Omega  \equiv {\rm I} \subseteq R \circ {R^T}について。
\Omega  = R \circ \Omegaと仮定すると、
{\rm I} = \Omega  \cap {\rm I} = R \circ \Omega  \cap {\rm I} \subseteq (R \cap {\rm I} \circ {\Omega ^T}) \circ (\Omega  \cap {R^T} \circ {\rm I}) = R \circ {R^T}
一方、{\rm I} \subseteq R \circ {R^T}を仮定すると、
\Omega  = {\rm I} \circ \Omega  \subseteq R \circ {R^T} \circ \Omega  \subseteq R \circ \Omega

\overline R  \subseteq R \circ \overline {\rm I}  \equiv \Omega  = R \circ \Omegaについて。
\overline R  \subseteq R \circ \overline {\rm I}  \equiv \Omega  = R \cup R \circ \overline {\rm I}
ここで、R \cup R \circ \overline {\rm I}  = R \circ ({\rm I} \cup \overline {\rm I} ) = R \circ \Omega

定理

R:{\mathop{\rm total}\nolimits} iff 任意の関係Sに対し、S \circ R = \emptysetならばS = \emptyset

証明

R:{\mathop{\rm total}\nolimits}と仮定。
任意のSに対して、

\begin{array}{l}S \circ R = \emptyset \\ \equiv \Omega  \circ {R^T} = \overline S \\ \equiv R \circ \Omega  = \overline {{S^T}} \\ \equiv \Omega  = \overline {{S^T}} \\ \equiv \Omega  \subseteq \overline {{S^T}} \\ \equiv S \subseteq \emptyset \end{array}

逆に、任意の関係Sに対し、S \circ R = \emptysetならばS = \emptysetと仮定すると、

\begin{array}{l}{\mathop{\rm true}\nolimits} \\ \equiv R \circ \Omega  \subseteq R \circ \Omega \\ \equiv \Omega  \circ {R^T} \subseteq {(R \circ \Omega )^T}\\ \equiv \overline {{{(R \circ \Omega )}^T}}  \circ R \subseteq \emptyset \\ \Rightarrow \overline {{{(R \circ \Omega )}^T}}  \subseteq \emptyset \\ \equiv \Omega  \subseteq {(R \circ \Omega )^T}\\ \equiv \Omega  \subseteq R \circ \Omega \end{array}

定理

R:{\mathop{\rm total}\nolimits}  \wedge S:{\mathop{\rm total}\nolimits}  \Rightarrow (R \circ S):{\mathop{\rm total}\nolimits}

定義 mapping relation*1

\begin{array}{l}R:{\mathop{\rm mapping}\nolimits} \\\mathop  \equiv \limits^{def} R:{\mathop{\rm univalent}\nolimits}  \wedge R:{\mathop{\rm total}\nolimits} \\ \equiv R \circ \overline {\rm I}  = \overline R \end{array}

定理

R:{\mathop{\rm mapping}\nolimits}  \wedge S:{\mathop{\rm mapping}\nolimits}  \Rightarrow (R \circ S):{\mathop{\rm mapping}\nolimits}

*1:total function