かじもとにっき

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

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:定義と定理と書いた方が良いだろうか