論理計算と随伴関手(5) - エレファント・コンピューティング調査報告

集合 $S$ の1個以上有限個の元からなる集合の全体を $FPS(S)$ とおきます。 $FPS(S)$ は和集合を演算とすることにより集合 $S$ によって自由生成された自由冪等可換半群と考えることができます。

集合 $S$ によって自由生成された自由半群 $G=FSG(S)$ (演算を $xy$ のように書くことにします)とし、 $G$ によって自由生成された自由冪等可換半群 $R=FPS(G)$ (演算を $+$ とします)を考えます。 $R$ に積を $(x_1 + x_2 + \cdots + x_m)(y_1 + y_2 + \cdots + y_n) = \sum_{i=1}^m \sum_{j=1}^n x_i y_j$ によって定義することができ、 $R$ は冪等可換半環になります。

集合 $\{e\}$ によって自由生成された自由半群 $FSG(\{e\})$ は $\{e\}$ の元からなる1個以上有限個の文字列の全体として定義することができます(演算を $+$ と書きます)。 $\mathrm{N}_1 = FSG(\{e\})$ とおきます。 $n$ 個の $e$ の和からなる $e+\cdots+e$ を $[n]$ と書くことにします。 $\mathrm{N}_1 = \{ [1], [2], \cdots \}$ となります。
$[m+1] + [n] = [m] + [1] + [n] = [m] + [n+1]$
が成り立つことからこれを繰り返すことにより
$[m] + [n] = [n] + [m]$
$[m] + [n] = [m+n]$
が成り立ちます。 $\mathrm{N}_1$ は可換となります。 $\mathrm{N}_1$ は1以上の自然数全体からなる可換半群と同型となります。

$\mathrm{N}_1$ に以下のように帰納的に積を定義します。
$[m] [1] = [m]$
$[m] + [n+1] = [m] [n] +[m]$
この定義から
$[m] [n] = [n] [m]$
$[m] [n] = [mn]$
が成り立ちます。 $\mathrm{N}_1$ は積に関して可換となります。
$[m] ([n] + [r]) = [m] [n] + [m] [r]$
$([m] + [n]) [r] = [m] [r] + [n] [r]$
も成り立ちます。 $\mathrm{N}_1$ は半環となります。