かじもとにっき

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

2項関係(7)

ここでのconnexという用語の定義はGunther Schmidtに倣っておりwikipediaのものとは異なる。

定義 semi-connex*1 relation

R:X \to Xの時、

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

定義 connex*2 relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm connex}\nolimits} \\\mathop  \equiv \limits^{def} \forall x,y \in X.x\not Ry \Rightarrow yRx\\ \equiv \Omega  \subseteq R \cup {R^T}\\ \equiv \overline R :{\mathop{\rm asymmetric}\nolimits} \end{array}

*1:weak-trichotomous

*2:comparable

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}\

2項関係(5)

定義 reflexive relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm reflexive}\nolimits} \\\mathop  \equiv \limits^{def} \forall x \in X.xRx\\ \equiv {\rm I} \subseteq R\end{array}

定義 irreflexive relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm irreflexive}\nolimits} \\\mathop  \equiv \limits^{def} \forall x \in X.x\not Rx\\ \equiv R \subseteq \overline {\rm I} \end{array}

定義 coreflexive relation

R:X \to Xの時、

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

定義 reflexive closure

R:X \to Xの時、
{\mathop{\rm refl}\nolimits} R\mathop  = \limits^{def}  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits} } \right\}

定理

{\mathop{\rm refl}\nolimits} R = R \cup {\rm I}

証明

\begin{array}{l}R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits} \\ \equiv R \subseteq X \wedge {\rm I} \subseteq X\\ \Rightarrow R \cup {\rm I} \subseteq X\end{array}
なので、{R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits} }を満たす任意のXに対してR \cup {\rm I} \subseteq X
よってR \cup {\rm I} \subseteq  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits} } \right\}
また、R \subseteq R \cup {\rm I}{\rm I} \subseteq R \cup {\rm I}よりR \cup {\rm I} \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits} } \right\}
よって\cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits} } \right\} \subseteq R \cup {\rm I}

2項関係(4)

定義 domain of definition

R:X \to Yの時、
{\mathop{\rm def}\nolimits} R\mathop  = \limits^{def} \left\{ {x \in X;\exists y.xRy} \right\}

プログラミングにおいてpartialityは重要なので、domainとdomain of definitionを明確に区別することにする

定義 image

R:X \to Yの時、
{\mathop{\rm img}\nolimits} R\mathop  = \limits^{def} \left\{ {y \in Y;\exists x.xRy} \right\}

定理

{\mathop{\rm def}\nolimits} {R^T} = {\mathop{\rm img}\nolimits} R
{\mathop{\rm img}\nolimits} {R^T} = {\mathop{\rm def}\nolimits} R
\Gamma R \subseteq {\mathop{\rm def}\nolimits} R \times {\mathop{\rm img}\nolimits} R \subseteq {\mathop{\rm dom}\nolimits} R \times {\mathop{\rm cod}\nolimits} R
等が成り立つ。

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

2項関係(2)

定義 部分関係

R:X \to YかつS:X \to Yの時、
\begin{array}{l}R \subseteq S\\\mathop  \equiv \limits^{def} \forall x \in X,y \in Y.xRy \Rightarrow xSy\\ \equiv \overline R  \cup S = \Omega \\ \equiv R \cap \overline S  = \emptyset \\ \equiv R \cup S = S\\ \equiv R \cap S = R\end{array}

定義 転置関係*1

R:X \to Yの時、
{R^T}\mathop  = \limits^{def} \left\langle {\left\{ {\left\langle {y,x} \right\rangle ;xRy} \right\},Y,X} \right\rangle

定理

{({R^T})^T} = R
{\overline R ^T} = \overline {{R^T}}
{(R \cup S)^T} = {R^T} \cup {S^T}
{(R \cap S)^T} = {R^T} \cap {S^T}
{{\rm I}_X}^T = {{\rm I}_X}
{\Omega _{X,Y}}^T = {\Omega _{Y,X}}
{\emptyset _{X,Y}}^T = {\emptyset _{Y,X}}
R \subseteq S \equiv {R^T} \subseteq {S^T}

*1:反対関係、逆関係などとも言うが、一般にR \circ {R^T} = {\rm I}は成り立たないので逆関係という言い方はあまり好きじゃない

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}}

等が明らかに成り立つ。