リンク集合

勝手に代数学シリーズが増えた。既にあるかもしれないし、そうでもないかもしれない。


定義. リンク集合

右(左)リンク集合 $A = (A, \cdot)$ は以下を満たす集合 $A$ と、リンク積 $\cdot : A \times A \rightarrow A$ のペアである。


$s, d, l$はそれぞれ"s"ource, "d"estination, "l"inkの略のつもり。 適当な元から、適当な別の元による操作で、他の全ての元にたどり着ける演算を持った集合。 FullyConnectedな〜とかそういう感じなので"リンク集合"。

閉じている(マグマである)ことはリンク積が演算なので自明だけど、右(左)リンク性と類似するのであえて書いた。


定義. バインド

右(左)リンク積の元 $a_i$ による右(左)バインド関数 $f_{a_i}$ とは

を満たす関数である。

バインド $B_A$ は、 $A$ からバインド関数への写像である。たとえば $B_A(a_i) = f_{a_i}$


バインドの情報から元のリンク演算を再現できるし、 またその逆も言えるため、バウンドを定めればリンク演算が、またその逆が一意に決定される。

ほぼ自明だけど以下の定理がなりたつ。

定理1. 任意の右(左)リンク集合のリンク積の右(左)バインド関数は全射

(proof)

右リンク集合についてのみ考える(左リンク集合は双対で自明)

任意のバインド関数 $f_{a_i}$ を考える。 このとき任意の $a_j \in A$ について $A$は右(左)リンクなので、ある $a_l \in A$ があり $$a_i \cdot a_l = a_j$$ となる。 したがって任意の $a_j \in A$ に対してある $a_l \in A$ があり $f_{a_i}(a_l) = a_j$ これが全射の定義だった。□

系1. 右(左)リンク集合が有限の $n$ 個ならば、そのリンク積の定め方は $n!n$ 種類である

各々のバウンド関数 $f$ は、定理1から全射。 また $f : A \rightarrow A$ であるため、$A$が有限から全単射でもある。 各々のバウンド関数の定め方は自由なので、対称群 $S_{n}$ の元と同数(=$n!$)ある。 今$A$のバインドは$n$タプルなので、結局リンク積は $n!n$ 個のバリエーションが存在する □