かじもとにっき

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

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