かじもとにっき

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

RDB(1)

定義 関係

有限集合Aを添字域とする集合族H = \left\langle {{H_a};a \in A} \right\rangleに対し、
B \subseteq (\Pi a \in A.{H_a}) = \left\{ {t:A \to ( \cup a \in A.{H_a});t:{\mathop{\rm mapping}\nolimits}  \wedge \forall a \in A.ta = {H_a}} \right\}
の時、組\left\langle {B,H} \right\rangleを関係*1と言う。
ここでBを関係の本体、Hを関係の見出し、Hの元を属性、Aの元を属性名と言う。

*1:A=\{0,1\}の時通常の2項関係とみなせる

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と同値だとわかる。

2項関係(19)

定理 shunting

R:{\mathop{\rm mapping}\nolimits}  \Rightarrow (P \circ R \subseteq Q \equiv P \subseteq Q \circ {R^T})
R:{\mathop{\rm mapping}\nolimits}  \Rightarrow ({R^T} \circ P \subseteq Q \equiv P \subseteq R \circ Q)
R:{\mathop{\rm bijective}\nolimits}  \Rightarrow (P \circ {R^T} \subseteq Q \equiv P \subseteq Q \circ R)
R:{\mathop{\rm bijective}\nolimits}  \Rightarrow (R \circ P \subseteq Q \equiv P \subseteq {R^T} \circ Q)

定理

P:{\mathop{\rm mapping}\nolimits}  \wedge Q:{\mathop{\rm mapping}\nolimits}  \Rightarrow (P \subseteq Q \circ R \equiv Q \subseteq P \circ {R^T})
P:{\mathop{\rm bijective}\nolimits}  \wedge Q:{\mathop{\rm bijective}\nolimits}  \Rightarrow (P \subseteq R \circ Q \equiv Q \subseteq {R^T} \circ P)

定理

R:{\mathop{\rm mapping}\nolimits}  \wedge S:{\mathop{\rm mapping}\nolimits}  \Rightarrow (R \subseteq S) = (R = S) = (S \subseteq R)
R:{\mathop{\rm bijective}\nolimits}  \wedge S:{\mathop{\rm bijective}\nolimits}  \Rightarrow (R \subseteq S) = (R = S) = (S \subseteq R)

2項関係(18)

定理

R:{\mathop{\rm univalent}\nolimits}  \Rightarrow R \circ \overline S  = R \circ \Omega  \cap \overline {R \circ S}。(再掲)
R:{\mathop{\rm univalent}\nolimits}  \Rightarrow \overline {R \circ S}  = \overline {R \circ \Omega }  \cup R \circ \overline S。(再掲)
R:{\mathop{\rm mapping}\nolimits}  \Rightarrow R \circ \overline S  = \overline {R \circ S}

定理

S:{\mathop{\rm injective}\nolimits}  \Rightarrow \overline R  \circ S = \Omega  \circ S \cap \overline {R \circ S}
S:{\mathop{\rm injective}\nolimits}  \Rightarrow \overline {R \circ S}  = \overline {\Omega  \circ S}  \cup \overline R  \circ S
S:{\mathop{\rm bijective}\nolimits}  \Rightarrow \overline R  \circ S = \overline {R \circ S}

2項関係(17)

定義 injective relation

\begin{array}{l}R:{\mathop{\rm injective}\nolimits} \\\mathop  \equiv \limits^{def} {R^T}:{\mathop{\rm univalent}\nolimits} \\ \equiv R \circ {R^T} \subseteq {\rm I}\\ \equiv \overline {\rm I}  \circ R \subseteq \overline R \end{array}

定義 surjective relation

\begin{array}{l}R:{\mathop{\rm surjective}\nolimits} \\\mathop  \equiv \limits^{def} {R^T}:{\mathop{\rm total}\nolimits} \\ \equiv \Omega  = \Omega  \circ R\\ \equiv {\rm I} \subseteq {R^T} \circ R\\ \equiv \overline R  \subseteq \overline {\rm I}  \circ R\end{array}

定理

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

定義 bijective relation

\begin{array}{l}R:{\mathop{\rm bijective}\nolimits} \\\mathop  \equiv \limits^{def} R:{\mathop{\rm injective}\nolimits}  \wedge R:{\mathop{\rm surjective}\nolimits} \\ \equiv \overline {\rm I}  \circ R = \overline R \end{array}

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

2項関係(15)

定義 univalent relation*1

\begin{array}{l}R:{\mathop{\rm univalent}\nolimits} \\\mathop  \equiv \limits^{def} \forall x \in X.\forall y,z \in Y.xRy \wedge xRz \Rightarrow y = z\\ \equiv {R^T} \circ R \subseteq {\rm I}\\ \equiv R \circ \overline {\rm I}  \subseteq \overline R \end{array}

定理

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

証明

{R^T} \circ R \subseteq {\rm I}{S^T} \circ S \subseteq {\rm I}を仮定すると、
{(R \circ S)^T} \circ (R \circ S) = {S^T} \circ {R^T} \circ R \circ S \subseteq {S^T} \circ S \subseteq {\rm I}

定理

R \subseteq S \wedge S:{\mathop{\rm univalent}\nolimits}  \wedge R \circ \Omega  \supseteq S \circ \Omega  \Rightarrow R = S*2

証明

R \subseteq S{S^T} \circ S \subseteq {\rm I}S \circ \Omega  \subseteq R \circ \Omegaを仮定すると、
\begin{array}{l}S\\ = S \circ \Omega  \cap S\\ \subseteq R \circ \Omega  \cap S\\ \subseteq (R \cap S \circ \Omega ) \circ (\Omega  \cap {R^T} \circ S)\\ \subseteq R \circ {R^T} \circ S\\ \subseteq R \circ {S^T} \circ S\\ \subseteq R\end{array}

定理 分配律

R:{\mathop{\rm univalent}\nolimits}  \Rightarrow R \circ (P \cap Q) = R \circ P \cap R \circ Q

証明

{R^T} \circ R \subseteq {\rm I}と仮定すると、
\begin{array}{l}R \circ P \cap R \circ Q\\ \subseteq (R \cap R \circ Q \circ {P^T}) \circ (P \cap {R^T} \circ R \circ Q)\\ \subseteq R \circ (P \cap Q)\end{array}

定理

R \circ P \cap Q \subseteq (R \cap Q \circ {P^T}) \circ P
R \circ P \cap Q \subseteq R \circ (P \cap {R^T} \circ Q)

証明

どちらもDedekind律から直ちに出る。

定理

P:{\mathop{\rm univalent}\nolimits}  \Rightarrow R \circ P \cap Q = (R \cap Q \circ {P^T}) \circ P

定理

R:{\mathop{\rm univalent}\nolimits}  \Rightarrow R \circ \overline S  = R \circ \Omega  \cap \overline {R \circ S}

証明

{R^T} \circ R \subseteq {\rm I}と仮定。

\overline S  \subseteq \OmegaよりR \circ \overline S  \subseteq R \circ \Omega

\begin{array}{l}R \circ \overline S  \subseteq \overline {R \circ S} \\ \equiv {R^T} \circ R \circ S \subseteq S\\ \Leftarrow {R^T} \circ R \subseteq {\rm I} \wedge S \subseteq S\\ \equiv {\mathop{\rm true}\nolimits} \end{array}

よってR \circ \overline S  \subseteq R \circ \Omega  \cap \overline {R \circ S}

また、
\begin{array}{l}R \circ \Omega  \cap \overline {R \circ S}  \subseteq R \circ \overline S \\ \equiv \Omega  \subseteq \overline {R \circ \Omega }  \cup R \circ S \cup R \circ \overline S \\ \equiv \Omega  \subseteq \overline {R \circ \Omega }  \cup R \circ (S \cup \overline S )\\ \equiv \Omega  \subseteq \overline {R \circ \Omega }  \cup R \circ \Omega \\ \equiv \Omega  \subseteq \Omega \\ \equiv {\mathop{\rm true}\nolimits} \end{array}

定理

R:{\mathop{\rm univalent}\nolimits}  \Rightarrow \overline {R \circ S}  = \overline {R \circ \Omega }  \cup R \circ \overline S

*1:partial function

*2:R \circ \Omega  \supseteq S \circ \Omega  \equiv {\mathop{\rm def}\nolimits} R \supseteq {\mathop{\rm def}\nolimits} S