かじもとにっき

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

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)

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