自由可換モノイド

同義語：free commutative monoid

概要

集合から関係式なしに作る可換モノイド

集合 $S$ の各元を生成元とし、可換モノイドの公理以外の関係式を一切課さないと 自由可換モノイド が得られる。具体的には、$S$ 上の有限台をもつ非負整数値関数全体
$$ \mathbb N^{(S)}=\bigoplus_{s\in S}\mathbb N $$
である。元 $a\in\mathbb N^{(S)}$ は、各生成元 $s$ を何回使うかを表す係数 $a(s)$ の族であり、形式和 $\sum_{s\in S}a(s)s$ とみなせる。
自由性とは、集合写像 $S\to P$ を任意の可換モノイド $P$ へただ一通り準同型として延長できることである。この普遍性により、具体的な関数表示に依存せず自由可換モノイドを特徴づけられる。基本事項は Gri01 Chapters I–II を参照。

構成と標準基底

有限台をもつ関数

集合 $S$ に対し、関数 $a:S\to\mathbb N$ の台を
$$ \operatorname{supp}(a)=\{s\in S\mid a(s)\ne0\} $$
と定める。$\operatorname{supp}(a)$ が有限集合であるとき、$a$ は有限台をもつという。

集合上の自由可換モノイド

集合 $S$ 上の 自由可換モノイド（free commutative monoid）を
$$ \mathbb N^{(S)}=\{a:S\to\mathbb N\mid\operatorname{supp}(a)\text{ は有限}\} $$
と定め、加法を点ごとの和 $(a+b)(s)=a(s)+b(s)$ とする。零元は定数零関数である。
各 $s\in S$ に対して
$$ \delta_s(t)= \begin{cases} 1&(t=s),\\ 0&(t\ne s) \end{cases} $$
と定める。写像 $\iota_S:S\to\mathbb N^{(S)}$、$s\mapsto\delta_s$ を標準基底の埋め込みという。

有限台という条件により、任意の $a\in\mathbb N^{(S)}$ は有限和
$$ a=\sum_{s\in\operatorname{supp}(a)}a(s)\delta_s $$
で表される。

標準基底表示の一意性

$a\in\mathbb N^{(S)}$ の標準基底による有限和表示は、零係数を除けば一意である。

有限集合 $F,G\subset S$ と正整数 $m_s,n_t$ により
$$ \sum_{s\in F}m_s\delta_s=\sum_{t\in G}n_t\delta_t $$
とする。両辺を任意の $u\in S$ で評価すると、左辺は $u\in F$ なら $m_u$、そうでなければ $0$ であり、右辺も同様である。したがって $u\in F$ と $u\in G$ は同値で、属する場合は $m_u=n_u$ である。よって $F=G$ かつ全係数が一致する。

自由性

自由可換モノイドの普遍性

集合 $S$、可換モノイド $P$、集合写像 $f:S\to P$ に対し、準同型 $\widetilde f:\mathbb N^{(S)}\to P$ で
$$ \widetilde f\circ\iota_S=f $$
を満たすものがただ一つ存在する。明示的には
$$ \widetilde f(a)=\sum_{s\in\operatorname{supp}(a)}a(s)f(s) $$
である。

$a$ の台は有限なので右辺は有限和として定義できる。$a,b\in\mathbb N^{(S)}$ に対して、可換性と結合律により
$$ \widetilde f(a+b) =\sum_{s\in S}(a(s)+b(s))f(s) =\widetilde f(a)+\widetilde f(b), $$
ここで和は $\operatorname{supp}(a)\cup\operatorname{supp}(b)$ 上だけ取ればよい。また $\widetilde f(0)=0$ なので、$\widetilde f$ は準同型である。$\delta_s$ の台は $\{s\}$ であるから $\widetilde f(\delta_s)=f(s)$ であり、延長条件を満たす。
一意性を示す。$g:\mathbb N^{(S)}\to P$ が $g(\delta_s)=f(s)$ を満たす準同型なら、標準基底表示から
$$ g(a)=g\!\left(\sum_s a(s)\delta_s\right) =\sum_s a(s)g(\delta_s) =\sum_s a(s)f(s) =\widetilde f(a). $$
したがって $g=\widetilde f$ である。

この全単射は
$$ \operatorname{Hom}_{\mathsf{CMon}}(\mathbb N^{(S)},P) \cong \operatorname{Hom}_{\mathsf{Set}}(S,U(P)) $$
と書ける。ここで $U:\mathsf{CMon}\to\mathsf{Set}$ は台集合を取る忘却関手である。

自由可換モノイド関手は忘却関手の左随伴

$F(S)=\mathbb N^{(S)}$ と置くと、$F:\mathsf{Set}\to\mathsf{CMon}$ は関手となり、忘却関手 $U:\mathsf{CMon}\to\mathsf{Set}$ の左随伴である。

集合写像 $u:S\to T$ に対し、$\iota_T\circ u:S\to\mathbb N^{(T)}$ を普遍性で延長した準同型を $F(u)$ と定める。明示的には
$$ F(u)(a)(t)=\sum_{\substack{s\in\operatorname{supp}(a)\\u(s)=t}}a(s). $$
和は有限である。恒等写像と合成について、$F(\operatorname{id}_S)$ と $\operatorname{id}_{F(S)}$、および $F(v\circ u)$ と $F(v)\circ F(u)$ はいずれも標準基底上で一致する。普遍性の一意性からそれぞれ等しいので $F$ は関手である。
前定理の全単射は、集合写像の合成とモノイド準同型の合成に対して両辺で同じ標準基底上の写像を与えるため $S$ と $P$ の双方について自然である。したがって $F\dashv U$ である。

階数と有限生成性

有限集合 $S=\{s_1,\ldots,s_r\}$ に対して、座標を並べることにより
$$ \mathbb N^{(S)}\cong\mathbb N^r $$
である。無限集合の場合にも各元は有限個の基底元しか使わないが、モノイド全体としては無限個の基底方向をもつ。

有限生成となるための条件

$\mathbb N^{(S)}$ が有限生成であることと、$S$ が有限集合であることは同値である。

$S$ が有限なら、標準基底 $\{\delta_s\mid s\in S\}$ が有限生成集合である。
逆に $\mathbb N^{(S)}$ が有限集合 $A$ で生成されるとする。各 $a\in A$ の台は有限なので
$$ T=\bigcup_{a\in A}\operatorname{supp}(a) $$
も有限である。$A$ の元の有限和の台はすべて $T$ に含まれるため、$\langle A\rangle\subseteq\mathbb N^{(T)}$ である。もし $s\in S\setminus T$ があれば $\delta_s\notin\langle A\rangle$ となり、$A$ が全体を生成することに反する。よって $S=T$ は有限である。

消去律・単元・冪等元

自由可換モノイド $\mathbb N^{(S)}$ は消去律を満たす。その単元と冪等元はいずれも零元だけである。

$a+c=b+c$ なら、各 $s\in S$ で自然数の消去律を用いて $a(s)=b(s)$ を得るため $a=b$ である。
$a+b=0$ なら、各座標で $a(s)+b(s)=0$ であり、非負整数なので $a(s)=b(s)=0$。したがって単元は零だけである。また $a+a=a$ なら各座標で $2a(s)=a(s)$ となり、$a(s)=0$。よって冪等元も零だけである。