かじもとにっき

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

2項関係(14)

定理

R:Z \to XS:Z \to Yx \in Xy \in Yの時、
x(R\backslash S)y \equiv \forall z \in Z.zRx \Rightarrow zSy

定理

R:X \to ZS:Y \to Zx \in Xy \in Yの時、
x(R/S)y \equiv \forall z \in Z.xRz \Leftarrow ySz

*1:ここでの\subseteqは関係ではなく集合に対するもの。さらにproper classを避ける為にAに限定した

2項関係(13)

定義 左除算

R:X \to YS:X \to Zの時、
R\backslash {\rm{S}}\mathop  = \limits^{def}  \cup \left\{ {X;R \circ X \subseteq S} \right\}

定理

R\backslash {\rm{S = }}\overline {{R^T} \circ \overline S }

証明

任意のXについて、
\begin{array}{l}R \circ X \subseteq S\\ \equiv {R^T} \circ \overline S  \subseteq \overline X \\ \equiv X \subseteq \overline {{R^T} \circ \overline S } \end{array}
なので、
 \cup \left\{ {X;R \circ X \subseteq S} \right\} \subseteq \overline {{R^T} \circ \overline S }

また、
\begin{array}{l}R \circ \overline {{R^T} \circ \overline S }  \subseteq S\\ \equiv {R^T} \circ \overline S  \subseteq {R^T} \circ \overline S \\ \equiv {\mathop{\rm true}\nolimits} \end{array}
より、
\overline {{R^T} \circ \overline S }  \in \left\{ {X;R \circ X \subseteq S} \right\}
よって\overline {{R^T} \circ \overline S }  \subseteq  \cup \left\{ {X;R \circ X \subseteq S} \right\}

定義 右除算*1

R:X \to ZS:Y \to Zの時、
R/{\rm{S}}\mathop  = \limits^{def}  \cup \left\{ {X;X \circ S \subseteq R} \right\}

定理

R/{\rm{S = }}\overline {\overline R  \circ {S^T}}

定理 分配律

R\backslash (P \cap Q) = (R\backslash P) \cap (R\backslash Q)
(P \cap Q)/R = (P/R) \cap (Q/R)

(P \cup Q)\backslash R = (P\backslash R) \cap (Q\backslash R)
P/(Q \cup R) = (P/Q) \cap (P/R)

定理

{(R\backslash {\rm{S)}}^T} = {S^T}/{R^T}
{(R/S)^T} = {S^T}\backslash {R^T}

定理

R \circ (R\backslash {\rm{S}}) \subseteq S
(R/{\rm{S}}) \circ S \subseteq R

S \subseteq R\backslash (R \circ S)
S \subseteq (S \circ R)/R

R \circ (R\backslash (R \circ S)) = R \circ S
((S \circ R)/R) \circ R = S \circ R

定理

P \circ Q \subseteq R \equiv Q \subseteq P\backslash R
P \circ Q \subseteq R \equiv P \subseteq R/Q

*1:商集合にはどんな記号を使おうか…

2項関係(12)

定理

{({R^+})^T} = {({R^T})^+}
{({R^*})^T} = {({R^T})^*}

定義 equivalence relation

R:{\mathop{\rm equivalence}\nolimits} \mathop  \equiv \limits^{def} R:{\mathop{\rm reflexive}\nolimits}  \wedge R:{\mathop{\rm transitive}\nolimits}  \wedge R:{\mathop{\rm symmetric}\nolimits}

定義 equivalence closure

{\mathop{\rm equiv}\nolimits} R\mathop  = \limits^{def}  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\}

定理

{\mathop{\rm equiv}\nolimits} R = {(R \cup {R^T})^*}

証明

R \subseteq R \cup {R^T} \subseteq {(R \cup {R^T})^*}
{(R \cup {R^T})^*}:{\mathop{\rm reflexive}\nolimits}  \wedge {(R \cup {R^T})^*}:{\mathop{\rm transitive}\nolimits}
{({(R \cup {R^T})^*})^T} = {({(R \cup {R^T})^T})^*} = {(R \cup {R^T})^*}より{(R \cup {R^T})^*}:{\mathop{\rm symmetric}\nolimits}
以上より{(R \cup {R^T})^*} \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\}
よって\cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\} \subseteq {(R \cup {R^T})^*}

任意のXについて、{R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} }を仮定すると、{R^T} \subseteq {X^T} = Xより、R \cup {R^T} \subseteq Xが得られる。
さらに{X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} }だから、{(R \cup {R^T})^*} \subseteq X
よって{(R \cup {R^T})^*} \subseteq  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm equivalence}\nolimits} } \right\}

2項関係(11)

定義 reflexive transitive closure*1

{R^*}\mathop  = \limits^{def}  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}

定理

\mathop {( \cup i}\limits_{i \ge 0} .{R^i}) = {\rm I} \cup {R^ + }

証明

\mathop {( \cup i}\limits_{i \ge 0} .{R^i}) = {R^0} \cup \mathop {( \cup i}\limits_{i \ge 1} .{R^i}) = {\rm I} \cup {R^ + }

定理

R \subseteq S \Rightarrow {R^ + } \subseteq {S^ + }

証明

R \subseteq Sを仮定。
\mathop {( \cup i}\limits_{i \ge 1} .{R^i}) \subseteq \mathop {( \cup i}\limits_{i \ge 1} .{S^i})を示すには、\mathop {\forall i}\limits_{i \ge 1} .{R^i} \subseteq \mathop { \cup j}\limits_{j \ge 1} .{S^j}を示せば良い。

基底ケース。
\mathop {( \cup j}\limits_{j \ge 1} .{S^j}) = \mathop {S \cup ( \cup j}\limits_{j \ge 2} .{S^j}) \supseteq S \supseteq {R^1}

帰納ケース。
{R^i} \subseteq \mathop { \cup j}\limits_{j \ge 1} .{S^j}を仮定すると、
\begin{array}{l}{R^{i + 1}}\\ = {R^i} \circ R\\ \subseteq (\mathop { \cup j}\limits_{j \ge 1} .{S^j}) \circ S\\ = \mathop { \cup j}\limits_{j \ge 1} .{S^{j + 1}}\\ = \mathop { \cup j}\limits_{j \ge 2} .{S^j}\\ \subseteq \mathop {( \cup j}\limits_{j \ge 2} .{S^j}) \cup {S^1}\\ = \mathop { \cup j}\limits_{j \ge 1} .{S^j}\end{array}

定理

{R^*} = {\rm I} \cup {R^ + }\

証明

R \subseteq {R^ + } \subseteq {\rm I} \cup {R^ + }
{\rm I} \subseteq {\rm I} \cup {R^ + }より({\rm I} \cup {R^ + }):{\mathop{\rm reflexive}\nolimits}
({\rm I} \cup {R^ + }) \circ ({\rm I} \cup {R^ + }) = {\rm I} \cup {R^ + } \cup {R^ + } \circ {R^ + } \subseteq {\rm I} \cup {R^ + }より({\rm I} \cup {R^ + }):{\mathop{\rm transitive}\nolimits}
よって{\rm I} \cup {R^ + } \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}
よって\cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} } \right\} \subseteq {\rm I} \cup {R^ + }

R \subseteq X{\rm I} \subseteq XX = {X^ + }を満たす任意のXについて、{\rm I} \cup {R^ + } \subseteq X \cup {X^ + } = X
よって\forall X \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}.{\rm I} \cup {R^ + } \subseteq X
よって{\rm I} \cup {R^ + } \subseteq  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm reflexive}\nolimits}  \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}

定理

{R^ + } = R \circ {R^*}

証明

R \circ {R^*} = R \circ \mathop {( \cup i}\limits_{i \ge 0} .{R^i}) = \mathop {( \cup i}\limits_{i \ge 0} .{R^{i + 1}}) = \mathop {( \cup i}\limits_{i \ge 1} .{R^i}) = {R^ + }

*1:Rを含む最小のpreorder

2項関係(10)

定理*1

endorelation Rに対し、
\mathop {(\cup i}\limits_{i \ge 1} .{R^i}):{\mathop{\rm transitive}\nolimits}

証明は前回を参照。

定義 transitive closure

{R^ + }\mathop  = \limits^{def}  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}

定理

{R^ + } = \mathop {\cup i}\limits_{i \ge 1} .{R^i}

証明

R \subseteq \mathop {\cup i}\limits_{i \ge 1} .{R^i}\mathop {(\cup i}\limits_{i \ge 1} .{R^i}):{\mathop{\rm transitive}\nolimits} が共に成り立つので、\mathop {\cup i}\limits_{i \ge 1} .{R^i} \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}
よって\cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm transitive}\nolimits} } \right\} \subseteq \mathop {\cup i}\limits_{i \ge 1} .{R^i}

{R \subseteq X \wedge X:{\mathop{\rm transitive}\nolimits} }を満たす任意のXについて、\mathop {\forall i}\limits_{i \ge 1} .{R^i} \subseteq Xを数学的帰納法により容易に示せる。
よって任意のX \in \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}について\mathop {( \cup i}\limits_{i \ge 1} .{R^i}) \subseteq X
よって\mathop {( \cup i}\limits_{i \ge 1} .{R^i}) \subseteq  \cap \left\{ {X;R \subseteq X \wedge X:{\mathop{\rm transitive}\nolimits} } \right\}

*1:先にこの定理を証明しておけば良かった

2項関係(9)

定義*1 transitive relation

R:X \to Xの時、

\begin{array}{l}R:{\mathop{\rm transitive}\nolimits} \\\mathop  \equiv \limits^{def} \forall x,y,z \in X.xRy \wedge yRz \Rightarrow xRz\\ \equiv R \circ R \subseteq R\\ \equiv R = \mathop {\cup i}\limits_{i \ge 1} .{R^i}\\ \equiv R \supseteq \mathop {\cup i}\limits_{i \ge 1} .{R^i}\end{array}

証明

R \circ R \subseteq R \equiv R = \mathop {\cup i}\limits_{i \ge 1} .{R^i}を証明する。

まず左辺\Rightarrow右辺を示す為に、R \circ R \subseteq Rを仮定する。
R = {R^1} \subseteq \mathop {\cup i}\limits_{i \ge 1} .{R^i}
一方、\mathop {(\cup i}\limits_{i \ge 1} .{R^i}) \subseteq Rを示すには、任意のi \ge 1に対して{R^i} \subseteq Rを言えば良い。
{R^1} \subseteq Rは明らか。
{R^i} \subseteq Rが成り立つと仮定すると、
{R^{i + 1}} = {R^i} \circ R \subseteq R \circ R \subseteq R

次に右辺\Rightarrow左辺を示す為に、R = \mathop {\cup i}\limits_{i \ge 1} .{R^i}を仮定する。
任意のx,y \in Xについて、
\begin{array}{l}x(R \circ R)y\\ \equiv x( (\mathop {\cup i}\limits_{i \ge 1} .{R^i}) \circ (\mathop {\cup i}\limits_{i \ge 1} .{R^i}) )y\\ \equiv x(\mathop {\cup i}\limits_{i \ge 1} .\mathop {\cup j}\limits_{j \ge 1} .{R^i} \circ {R^j})y\\ \equiv \mathop {\exists i,j}\limits_{i \ge 1 \wedge j \ge 1} .x{R^{i + j}}y\\ \Rightarrow \mathop {\exists i,j}\limits_{i + j \ge 2} .x{R^{i + j}}y\\ \Rightarrow \mathop {\exists i,j}\limits_{i + j \ge 1} .x{R^{i + j}}y\\ \equiv \mathop {\exists i,j,k}\limits_{k \ge 1 \wedge k = i + j} .x{R^k}y\\ \Rightarrow \mathop {\exists k}\limits_{k \ge 1} .x{R^k}y\\ \equiv x(\mathop {\cup i}\limits_{i \ge 1} .{R^i})y\\ \equiv xRy\end{array}

定理

{\rm I}:{\mathop{\rm coreflexive}\nolimits}

定理

R \subseteq R \circ {R^T} \circ R\

証明

\begin{array}{l}R\\ = (R \circ {\rm I}) \cap R\\ \subseteq (R \cap R \circ {{\rm I}^T}) \circ ({\rm I} \cap {R^T} \circ R)\\ = R \circ ({\rm I} \cap {R^T} \circ R)\\ \subseteq R \circ {R^T} \circ R\end{array}

定理

R:{\mathop{\rm coreflexive}\nolimits}  \Rightarrow R:{\mathop{\rm symmetric}\nolimits}  \wedge R:{\mathop{\rm transitive}\nolimits}

証明

R:{\mathop{\rm coreflexive}\nolimits}と仮定。(これはR \subseteq {\rm I}と同値)

R \subseteq R \circ {R^T} \circ R \subseteq {\rm I} \circ {R^T} \circ {\rm I} = {R^T}よりR:{\mathop{\rm symmetric}\nolimits}
R \circ R \subseteq R \circ {\rm I} = RよりR:{\mathop{\rm transitive}\nolimits}

定理

R:{\mathop{\rm symmetric}\nolimits}  \wedge S:{\mathop{\rm symmetric}\nolimits}  \Rightarrow (R \cap S):{\mathop{\rm symmetric}\nolimits}

証明

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

*1:定義と定理と書いた方が良いだろうか

2項関係(8)

定義 関係の羃乗

任意の自然数nに対し、endorelation Rn回合成R^nを以下のように定義する。
{R^0} = {\rm I}
{R^{n + 1}} = {R^n} \circ R\;\;\;(n \ge 0)

定理

Xが有限でそのcardinalityがnとすると、R:X \to Xのとき、

\mathop {\exists i,j}\limits_{0 \le i < j \le {2^{{n^2}}}} .{R^i} = {R^j}\

証明

X \times Xのcardinalityはn^2なのでX上の異なるendorelationは全部で2^{{n^2}}個ある。
しかし、列\left\langle {{R^0},{R^1}, \ldots ,{R^{{2^{{n^2}}}}}} \right\rangleは全部で2^{{n^2}}+1個の要素を持っているので、それらのうち少なくとも2つは等しい。

定理

{R^m} \circ {R^n} = {R^{m + n}}\;\;\;(m \ge 0,n \ge 0)
{({R^m})^n} = {R^{m \cdot n}}\;\;\;(m \ge 0,n \ge 0)

定理

R:X \to XXが有限とする。{R^i} = {R^j}かつ0 \le i < jの時、

{R^{i + k}} = {R^{j + k}}\;\;\;(k \ge 0)
{R^i} = {R^{i + k \cdot (j - i)}}\;\;\;(k \ge 0)

要するに有限の関係の合成の列は一定の周期で繰り返し続けるということ。