かじもとにっき

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

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:先にこの定理を証明しておけば良かった