半環上のフラクタル代数(6) - エレファント・コンピューティング調査報告

ブール代数(可補分配束)の非可換であるようなものを考えます。

自由モノイド

集合 $X$ で生成される自由モノイドを $X^*$ または $S(X)$ とします。 $S(X)$ は文字の集合 $X$ から作られる文字列全体の集合と見ることができます。空文字列が単位元となります。 $X$ の元を1つの文字からなる文字列と考えると、 $X \subseteq S(X)$ と考えることができます。

$f$ を $X$ からモノイド $M$ への写像 $f: X \to M$ とします。 $M$ の演算を $\times$ 、 $S(X)$ の演算(文字列の連結)を $*$ で表すことにします。 $S(X)$ は $x_1 * \cdots * x_n$ $(x_1,\cdots , x_n \in X)$ という形の列全体の集合となります。 $S(X)$ の元 $x_1 * \cdots * x_n$ に $M$ の元 $f(x_1) \times \cdots \times f(x_n)$ を対応させる写像は、モノイドの準同型 $f^*: S(X) \to M$ となります。

モノイド $M$ に対する $S(M)$ を考えます。 $M$ の演算を $\times$ 、 $S(M)$ の演算(文字列の連結)を $*$ で表すことにします。 $S(M)$ は $x_1 * \cdots * x_n$ $(x_1,\cdots , x_n \in M)$ という形の列全体の集合となります。

$S(M)$ の元 $x_1 * \cdots * x_n$ に $M$ の元 $x_1 \times \cdots \times x_n$ を対応させる写像は、 $S(M)$ から $M$ へのモノイドの準同型となります。

自由半環

集合 $X$ で生成される自由モノイドを $S(X)$ とします。この演算子を $\land$ と書くことにします。空文字列は単位元となります。これを $1$ と書きます。

$S(X)$ で生成される自由モノイドを $S^2(X)$ とします。この演算子を $\lor$ と書くことにします。空文字列は単位元となります。これを $0$ と書きます。

$\land$ は $\lor$ に優先されるものとします。

$S(X) \subseteq S^2(X)$ と考えます。 $S^2(X)$ に二項演算 $+$ (加法)と $\cdot$ (乗法)を定義します。 $\cdot$ は $+$ に優先されるものとします。

加法の定義

$u = u_1 \lor \cdots \lor u_k \in S^2(X)$ 、 $v = v_1 \lor \cdots \lor v_l \in S^2(X)$ に対して $u + v = u_1 \lor \cdots \lor u_k \lor v_1 \lor \cdots \lor v_l$ と定義します。

この加法は $\lor$ と同じなので、 $S^2(X)$ は $+$ (加法)に関してモノイドとなります。

乗法の定義

$x \in S^2(X)$ は
$\hspace{4em} \begin{eqnarray*} x & = & x_{11} \land x_{12} \land \cdots \land x_{1m_1} \\ & \lor & x_{21} \land x_{22} \land \cdots \land x_{2m_2} \\ & \lor & \\ & \vdots & \\ & \lor & x_{n1} \land x_{n2} \land \cdots \land x_{nm_n} \\ \end{eqnarray*}$
と表すことができます $(x_{ij} \in X)$ 。 $x$ に対して $f_x : S(X) \to S^2(X)$ を $y = y_1 \land \cdots \land y_k \in S(X)$ $(x_{ij} \in X)$ に対して
$\hspace{4em} \begin{eqnarray*} f_x(y) & = & x_{11} \land x_{12} \land \cdots \land x_{1m_1} \land y_1 \land \cdots \land y_k \\ & \lor & x_{21} \land x_{22} \land \cdots \land x_{2m_2} \land y_1 \land \cdots \land y_k \\ & \lor & \\ & \vdots & \\ & \lor & x_{n1} \land x_{n2} \land \cdots \land x_{nm_n} \land y_1 \land \cdots \land y_k \\ \end{eqnarray*}$
とすると、モノイドの準同型 $f_x^* : S^2(X) \to S^2(X)$ を定義することができます。 $S^2(X)$ の乗法を $x \cdot y = f_x^*(y)$ と定義します。

乗法の結合法則

上記のように $x \in S^2(X)$ からモノイドの準同型 $f_x^* : S^2(X) \to S^2(X)$ を定義することができます。 $S^2(X)$ から $S^2(X)$ へのモノイドの準同型全体の集合 $\operatorname{End} S^2(X)$ は写像の合成に関してモノイドとなります。 $\varphi : S^2(X) \to \operatorname{End} S^2(X)$ を $\varphi(x) = f_x^*$ とすると $\varphi(x \cdot y) = f_{x \cdot y}^* = f_{x}^* \circ f_{y}^*$ $(x, y \in S^2(X))$ となるのでモノイドの準同型となります。

$S(X)$ の単位元は空文字列なのですが空文字列は書き表しにくいのでこれを $1$ と書き、 $S(X) \subseteq S^2(X)$ と見ることにより $1 \in S^2(X)$ と考えます。
$\hspace{4em} \begin{eqnarray*} f_x(1) & = & x_{11} \land x_{12} \land \cdots \land x_{1m_1} \land 1 \\ & \lor & x_{21} \land x_{22} \land \cdots \land x_{2m_2} \land 1 \\ & \lor & \\ & \vdots & \\ & \lor & x_{n1} \land x_{n2} \land \cdots \land x_{nm_n} \land 1 \\ \end{eqnarray*}$
より $f_x(1) = x$ 、 $f_x^*(1) = x$ $(x \in S^*(X))$ となります。

$x, y, z \in S^2(X)$ に対して
$\varphi( (x \cdot y) \cdot z) = f_{(x \cdot y) \cdot z}^* = f_{x \cdot y}^* \circ f_{z}^* = (f_{x}^* \circ f_{y}^*) \circ f_{z}^*$
$\varphi( x \cdot (y \cdot z)) = f_{x \cdot (y \cdot z)}^* = f_{x}^* \circ f_{y \cdot z}^* = f_{x}^* \circ (f_{y}^* \circ f_{z}^*)$
$(x \cdot y) \cdot z = \varphi( (x \cdot y) \cdot z)(1) = f_{x}^* ( f_{y}^* ( f_{z}^* (1))) = \varphi( x \cdot (y \cdot z))(1) = x \cdot (y \cdot z)$
となるので乗法の結合法則が成り立ちます。

乗法の単位元

上に述べたように $f_x^*(1) = x$ $(x \in S^*(X))$ となります。

$f_1(y) = 1 \land y _i= y_i$ $(y_i \in S(X))$ より $f_1^*(y_1 \lor \cdots y_n) = y_1 \lor \cdots y_n$ $(y_1 \lor \cdots y_n \in S^2(X))$ となって $f_1^*(y) = y$ $(y \in S^*(X))$ となります。よって $x \cdot 1 = 1 \cdot x = x$ $(x \in S^*(X))$ となって $1$ は乗法の単位元となります。

分配法則

$f_x^*$ は準同型なので $f_x^*(y+z) = f_x^*(y) + f_x^*(z)$ より $x \cdot (y + z) = x \cdot z + x \cdot z$ $(x, y, z \in S^*(X))$ が成り立ちます。

$x, y \in S^2(X)$ とします。 $z_i \in S(X)$ とすると定義より $(x + y) \cdot z_i = x \cdot z_i + y \cdot z_i$ が成り立ちます。

$z = z_1 + \cdots + z_n \in S^2(X)$ $(z_i \in S(X))$ とします。 $(S^2(X), \lor)$ が可換モノイド(すなわち $(S^2(X), +)$ が可換モノイド)であるとすると
$\hspace{4em} \begin{eqnarray*} (x + y) \cdot z & = & (x + y) \cdot (z_1 + \cdots + z_n) \\ & = & (x + y) \cdot z_1 + \cdots + (x + y) \cdot z_n \\ & = & (x \cdot z_1 + y \cdot z_1) + \cdots + (x \cdot z_n + y \cdot z_n) \\ & = & (x \cdot z_1 + \cdots + x \cdot z_n) + (y \cdot z_1 + \cdots + y \cdot z_n) \\ & = & x \cdot z + y \cdot z \end{eqnarray*}$
が成り立ちます。

よって $(S^2(X), \lor)$ が可換モノイドならば、乗法の加法に対する分配法則が成り立ちます。よって $(S^2(X), \lor)$ が可換モノイドならば、 $S^2(X)$ は半環となります。

$(S^2(X), \lor)$ は可換ではないので以下では可換になるものについて考えます。

$X$ 、 $Y$ を集合、 $e$ を $Y$ の元とします。 $FM(X, Y, e)$ を $X$ から $Y$ への写像 $f$ で、 $f(x) \ne e$ となる $x \in X$ の個数が有限であるもの全体の集合とします。 $\mathbb{N}$ を自然数全体の集合とします。 $N(X) = FM(X, \mathbb{N}, 0)$ は $X$ で生成される自由可換モノイドとなります。 $S(X)$ の元に、その中に現れる文字 $x \in X$ にその文字の現れる個数を対応させる写像を対応させると、その写像は $S(X)$ から $N(X)$ へのモノイドの準同型となります。よって $N(S(X))$ は半環となります。

$X$ を集合、 $R$ を単位元を持つ自明ではない半環、 $f : X \to R$ とします。 $X \subseteq N(S(X))$ と考えることができます。 $g: N(S(X)) \to R$ を $g(0) = 0$ 、 $g(1) = 1$ 、
$\hspace{4em} \begin{eqnarray*} x & = & k_1 x_{11} x_{12} \cdots x_{1m_1} \\ & + & k_2 x_{21} x_{22} \cdots x_{2m_2} \\ & + & \\ & \vdots & \\ & + & k_n x_{n1} x_{n2} \cdots x_{nm_n} \in N(S(X)) \\ \end{eqnarray*}$
$(k_i \in \mathbb{N}, x_{ij} \in X)$ に対して
$\hspace{4em} \begin{eqnarray*} g(x) & = & k_1 f(x_{11}) f(x_{12}) \cdots f(x_{1m_1}) \\ & + & k_2 f(x_{21}) f(x_{22}) \cdots f(x_{2m_2}) \\ & + & \\ & \vdots & \\ & + & k_n f(x_{n1}) f(x_{n2}) \cdots f(x_{nm_n}) \in R \\ \end{eqnarray*}$
と定義することができます。 $g$ が加法を保存することは定義からわかります。 $u = u_1 \cdots u_l$ $(u_{i} \in X)$ に対して $g(xu) = g(x)g(u)$ であることは定義からわかります。 $y = y_1 + \cdots + y_r$ $(y_{i} \in S(X))$ に対して
$\hspace{4em} \begin{eqnarray*} g(xy) & = & g(x (y_1 + \cdots + y_r)) \\ & = & g(x y_1 + \cdots + x y_r ) \\ & = & g(x y_1) + \cdots + g(x y_r ) \\ & = & g(x) g(y_1) + \cdots + g(x) g( y_r ) \\ & = & g(x) (g(y_1) + \cdots + g( y_r )) \\ & = & g(x) g(y_1 + \cdots + y_r) \\ & = & g(x)g(y) \end{eqnarray*}$
が成り立つので $g$ が乗法を保存することがわかります。よって $g$ は半環の準同型になります。

よって $N(S(X))$ は $X$ で生成された自由半環となります。