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

次に可換の場合を考えます。

モノイドから作られる半環(1)

$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$ で生成される自由可換モノイドとなります。

$M$ をモノイドとします。 $N(M)$ に加法( $+$ )と乗法( $\cdot$ )を定義します。乗法は加法に優先するものとします。以下に示すように $N(M)$ は半環となります。

加法の定義

$N(M)$ のモノイドとしての演算を加法とします。

すなわち $N(M)$ のモノイドとしての演算が $\lor$ であるとき、 $N(M)$ の加法の演算 $+$ を $u = u_1 \lor \cdots \lor u_l \in N(M)$ $(u_i \in M)$ と $v = v_1 \lor \cdots \lor v_m \in N(M)$ $(v_i \in M)$ に対して $u + v = u_1 \lor \cdots \lor u_l \lor v_1 \lor \cdots \lor v_m$ と定義します。

$(N(M), \lor)$ が可換モノイドであることから $N(M)$ は加法に関して可換モノイドとなります。

乗法の定義

モノイド $M$ の演算を $\land$ とします。 $\land$ は $+$ に優先するものとします。

$a_i$ 個の和 $u_i + \cdots + u_i$ を $a_i u_i$ と書くことにします。 $u \in N(M)$ は $u = a_1 u_1 + \cdots + a_l u_l$ $(a_i \in \mathbb{N}, u_i \in M)$ と順序を除いて一意的に表すことができます。

$u = a_1 u_1 + \cdots + a_l u_l \in N(M)$ $(a_i \in \mathbb{N}, u_i \in M)$ と $v = b_1 v_1 + \cdots + b_m v_m \in N(M)$ $(b_j \in \mathbb{N}, v_j \in M)$ に対して乗法を $\displaystyle u \cdot v = \sum_{i=1}^{l} \sum_{j=1}^{m} a_i b_j (u_i \land v_j)$ と定義することができます。

乗法の結合法則

$u = a_1 u_1 + \cdots + a_l u_l \in N(M)$ $(a_i \in \mathbb{N}, u_i \in M)$ 、 $v = b_1 v_1 + \cdots + b_m v_m \in N(M)$ $(b_j \in \mathbb{N}, v_j \in M)$ 、 $w = c_1 w_1 + \cdots + c_n w_n \in N(M)$ $(c_k \in \mathbb{N}, w_k \in M)$ に対して $\displaystyle (u \cdot v) \cdot w = u \cdot (v \cdot w) = \sum_{i=1}^{l} \sum_{j=1}^{m} \sum_{k=1}^{n} a_i b_j c_k (u_i \land v_j \land w_k)$ となるので乗法の結合法則が成り立ちます。

乗法の単位元

$M$ の単位元 $1$ を $1 \in N(M)$ と見ることができます。 $u = a_1 u_1 + \cdots + a_l u_l \in N(M)$ $(a_i \in \mathbb{N}, u_i \in M)$ に対して $u \cdot 1 = a_1 (u_1 \land 1) + \cdots + a_l (u_l \land 1) = a_1 u_1 + \cdots + a_l u_l = u$ 、 $1 \cdot u = a_1 (1 \land u_1) + \cdots + a_l (1 \land u_l) = a_1 u_1 + \cdots + a_l u_l = u$ となるので $1$ は $N(M)$ の乗法の単位元となります。

よって $N(M)$ は情報に関してモノイドとなります。

乗法の加法に対する分配法則

$u = a_1 u_1 + \cdots + a_l u_l \in N(M)$ $(a_i \in \mathbb{N}, u_i \in M)$ 、 $v = b_1 v_1 + \cdots + b_m v_m \in N(M)$ $(b_j \in \mathbb{N}, v_j \in M)$ 、 $w = c_1 w_1 + \cdots + c_n w_n \in N(M)$ $(c_k \in \mathbb{N}, w_k \in M)$ に対して
$\hspace{4em} \begin{eqnarray*} (u + v) \cdot w & = & \left( \sum_{i=1}^{l} a_i u_i + \sum_{j=1}^{m} b_j v_j \right) \cdot \left( \sum_{k=1}^{n} c_k w_k \right) \\ & = & \left( \sum_{i=1}^{l} a_i u_i \right) \cdot \left( \sum_{k=1}^{n} c_k w_k \right) + \left( \sum_{j=1}^{m} b_j v_j \right) \cdot \left( \sum_{k=1}^{n} c_k w_k \right) \\ & = & u \cdot w + v \cdot w \end{eqnarray*}$
$\hspace{4em} \begin{eqnarray*} u \cdot (v + w) & = & \left( \sum_{i=1}^{l} a_i u_i \right) \cdot \left( \sum_{j=1}^{m} b_j v_j + \sum_{k=1}^{n} c_k w_k \right) \\ & = & \left( \sum_{i=1}^{l} a_i u_i \right) \cdot \left( \sum_{j=1}^{m} b_j v_j \right) + \left( \sum_{i=1}^{l} a_i u_i \right) \cdot \left( \sum_{k=1}^{n} c_k w_k \right) \\ & = & u \cdot v + u \cdot w \end{eqnarray*}$
より乗法の加法に対する分配法則が成り立ちます。

よって $N(M)$ は半環となります。

集合 $X$ に対して $N(N(X))$ 、 $N(S(X))$ は半環となります。

モノイドから作られる半環(2)

$B$ を1つの元 $\varepsilon$ からなる集合 $E = \{ \varepsilon \}$ の冪集合 $B = \{ \varnothing , E \}$ とおきます。 $B$ は和集合関してモノイドとなります。

集合 $X$ に対して $F(X) = FM(X, B, \varnothing)$ は $f \in F(X)$ を $\{ x \in X \mid f(x) \ne \varnothing \}$ と同一視することにより $X$ の有限部分集合全体の集合と考えることができます。 $F(X)$ は集合 $X$ で生成される自由冪等可換モノイドとなります。

モノイド $M$ に対して $N(M)$ と同様に $F(M)$ に乗法を定義すると、 $F(M)$ は半環となります。

集合 $X$ に対して $F(F(X))$ は半環となります。