かじもとにっき

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

2項関係(1)

しばらく関係と関数の計算についてひたすら調べるブログになります。

定義 2項関係

集合X、集合Y、及びそれらの直積の部分集合G\subseteq X \times Yが与えられたとき、3つ組R=\left\langle {G,X,Y} \right\rangleX \times Y上の2項関係と言う。このとき、XRのdomain、YRのcodomain、GRのグラフと言い、XRのdomainでありYRのcodomainであることをR:X \to Yと書く。
\left\langle {x,y} \right\rangle  \in GxRyR_{xy}などと書く。
また、{\mathop{\rm dom}\nolimits} R=X{\mathop{\rm cod}\nolimits} R=Y\Gamma R=Gとする。
Y=Xの時、Rを単にX上の2項関係と言う。

定義 2項関係上の演算

R:X \to YかつS:X \to Yの時、以下を定義できる。

合併 R \cup S = \left\langle {\left\{ {\left\langle {x,y} \right\rangle  \in X \times Y;xRy \vee xSy} \right\},X,Y} \right\rangle
共通部分 R \cap S = \left\langle {\left\{ {\left\langle {x,y} \right\rangle  \in X \times Y;xRy \wedge xSy} \right\},X,Y} \right\rangle
補関係 \bar R = \left\langle {\left\{ {\left\langle {x,y} \right\rangle  \in X \times Y;x\not Ry} \right\},X,Y} \right\rangle
普遍関係 {\Omega _{X,Y}} = \left\langle {X \times Y,X,Y} \right\rangle
空関係 {\emptyset _{X,Y}} = \left\langle {\{ \} ,X,Y} \right\rangle
恒等関係 {{\rm I}_X} = \left\langle {\left\{ {\left\langle {x,x} \right\rangle  \in X \times X;x \in X} \right\},X,X} \right\rangle

空関係等の添字は文脈から明らかな場合省略する。

定理

対称律 R \cup S = S \cup R,R \cap S = S \cap R
結合律 R \cup (S \cup T) = (S \cup R) \cup T,R \cap (S \cap T) = (S \cap R) \cap T
吸収律 R \cup (R \cap T) = R,R \cap (R \cup T) = R
分配律 R \cup (S \cap T) = (R \cup S) \cap (R \cup T),R \cap (S \cup T) = (R \cap S) \cup (R \cap T)
De Morgan律 \overline {R \cup S}  = \overline R  \cap \overline S ,\overline {R \cap S}  = \overline R  \cup \overline S
二重否定 \overline{\overline R}  = R
排中律 R \cup \overline R  = {\Omega _{{\mathop{\rm dom}\nolimits} R,{\mathop{\rm cod}\nolimits} R}}
矛盾律 R \cap \overline R  = {\emptyset _{{\mathop{\rm dom}\nolimits} R,{\mathop{\rm cod}\nolimits} R}}

等が明らかに成り立つ。