かじもとにっき

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

2項関係(3)

定義 関係の合成

R:X \to YかつS:Y \to Zの時、
R \circ S\mathop  = \limits^{def} \left\langle {\left\{ {\left\langle {x,y} \right\rangle ;\exists y.xRy \wedge ySz} \right\},X,Z} \right\rangle

{(R \circ S)_{xz}} \equiv \exists y.{R_{xy}} \wedge {S_{yz}}は行列の積{(AB)_{ik}} =\Sigma j.{A_{ij}} \cdot {B_{jk}}に似ている。

\circの優先順位は\cap\cupなどよりも高いことにする。

定義

R:X \to YかつS:Y \to Zの時、
S \bullet R\mathop  = \limits^{def} R \circ S
先の定義では一般的な関数の合成と順番が逆になるので、状況に応じて入れ替えることにする。

定理 単位元

R:X \to Yの時、
{{\rm I}_X} \circ R = R = R \circ {{\rm I}_Y}

定理 結合律

(R \circ S) \circ Q = R \circ (S \circ Q)

定理 Schröder律

\begin{array}{l}R \circ S \subseteq Q\\ \equiv \overline Q  \circ {S^T} \subseteq \overline R \\ \equiv {R^T} \circ \overline Q  \subseteq \overline S \end{array}
point-free reasoningに便利。

定理 Dedekind律

R \circ S \cap Q \subseteq (R \cap Q \circ {S^T}) \circ (S \cap {R^T} \circ Q)
point-free reasoningに便利。

定理 Tarski律

R \ne \emptyset  \Rightarrow \Omega  \circ R \circ \Omega  = \Omega

定理

R \circ \emptyset  = \emptyset  \circ R = \emptyset

定理

{(R \circ S)^T} = {S^T} \circ {R^T}

定理 分配律

R \circ (S \cup Q) = R \circ S \cup R \circ Q
(S \cup Q) \circ R = S \circ R \cup Q \circ R

定理 分配律

R \circ (S \cap Q) \subseteq R \circ S \cap R \circ Q
(S \cap Q) \circ R \subseteq S \circ R \cap Q \circ R
一般に逆は成り立たない。

定理

P \subseteq Q \wedge R \subseteq S \Rightarrow P \circ R \subseteq Q \circ S