有限生成モノイド
概要
有限生成モノイド（finitely generated monoid）とは、有限個の元の和で全要素を表せるモノイドである。可換の場合、これは有限階数の自由可換モノイド $\mathbb N^r$ の商であることと同値である。さらにRédeiの定理により、有限生成可換モノイドでは関係式も有限個に選べるため、有限表示をもつ。有限生成性は準同型像と有限直積で保たれる。
前提知識: 可換モノイド, モノイド準同型, 商モノイド, 多項式環
有限個の生成元で全体を記述する
以下では可換モノイドを加法記法で書き、単位元を $0$ とする。有限生成性は、無限個の元をもつモノイドであっても、有限個の基本的な元の和だけで全体を記述できるという条件である。
生成元が $p_1,\ldots,p_r$ なら、係数を並べた $\mathbb N^r$ から
$$
(a_1,\ldots,a_r)\longmapsto a_1p_1+\cdots+a_rp_r
$$
という全射が得られる。したがって有限生成可換モノイドは、有限階数の自由可換モノイド $\mathbb N^r$ の商として理解できる。有限生成可換モノイドが有限個の関係式でも記述できるというRédeiの定理が、この見方の重要な帰結である。基本事項とRédeiの定理については Gri01 を参照。
有限生成性
可換モノイド $P$ と部分集合 $S\subset P$ に対し、$S$ の元の有限和全体を $S$ が生成する部分モノイドといい、$\langle S\rangle$ と書く。空和は $0$ とする。
有限集合 $S\subset P$ で $P=\langle S\rangle$ となるものが存在するとき、$P$ を 有限生成モノイド（finitely generated monoid）という。
生成集合は一意とは限らず、冗長な生成元を加えてもよい。有限生成性は、生成集合そのものではなくモノイドの性質である。
可換モノイド $P$ に対し、次は同値である。
- $P$ は有限生成である。
- ある非負整数 $r$ と全射準同型 $\pi:\mathbb N^r\twoheadrightarrow P$ が存在する。
$P=\langle p_1,\ldots,p_r\rangle$ なら
$$
\pi(a_1,\ldots,a_r)=\sum_{i=1}^r a_ip_i
$$
と定める。この写像は加法と零元を保ち、生成性から全射である。$r=0$ の場合、$\mathbb N^0=\{0\}$ は零モノイドを表す。
逆に全射 $\pi:\mathbb N^r\to P$ があれば、$\mathbb N^r$ の標準基底を $e_1,\ldots,e_r$ として、任意の $p\in P$ は
$$
p=\pi(a_1,\ldots,a_r)=a_1\pi(e_1)+\cdots+a_r\pi(e_r)
$$
と書ける。したがって $P$ は有限集合 $\{\pi(e_1),\ldots,\pi(e_r)\}$ で生成される。
有限生成可換モノイドの準同型像は有限生成である。また、有限生成可換モノイド $P,Q$ の直積 $P\times Q$ も有限生成である。
$P=\langle p_1,\ldots,p_r\rangle$ とし、$f:P\to R$ を全射準同型とする。任意の $y\in R$ に対して $f(x)=y$ となる $x\in P$ を選べば、ある $a_i\in\mathbb N$ により
$$
y=f(x)=\sum_{i=1}^r a_i f(p_i)
$$
である。よって $R=\langle f(p_1),\ldots,f(p_r)\rangle$ である。
さらに $P=\langle p_1,\ldots,p_r\rangle$、$Q=\langle q_1,\ldots,q_s\rangle$ なら、$P\times Q$ は
$$
(p_1,0),\ldots,(p_r,0),(0,q_1),\ldots,(0,q_s)
$$
で生成される。実際、$(p,q)=(p,0)+(0,q)$ であり、各成分をそれぞれの生成元で表せばよい。
生成元と関係式
有限生成性だけでは、同じ元を表す係数ベクトルの関係が有限個で記述できるとは直ちには分からない。その関係を定式化する。
可換モノイド $M$ 上の同値関係 $\sim$ が 合同関係 であるとは、
$$
a\sim b\quad\Longrightarrow\quad a+c\sim b+c
$$
がすべての $a,b,c\in M$ について成り立つことをいう。
準同型 $f:M\to P$ の核合同関係を
$$
a\sim_f b\quad\Longleftrightarrow\quad f(a)=f(b)
$$
で定める。
可換モノイド $P$ が 有限表示 であるとは、ある $r,m\in\mathbb N$ と組
$$
(u_1,v_1),\ldots,(u_m,v_m)\in\mathbb N^r\times\mathbb N^r
$$
が存在し、$P$ がこれらの関係 $u_i=v_i$ で生成される合同関係による商
$$
P\cong\mathbb N^r/\!\sim
$$
と同型になることをいう。この表示を
$$
P=\langle e_1,\ldots,e_r\mid u_1=v_1,\ldots,u_m=v_m\rangle
$$
と書く。
「関係で生成される合同関係」は、指定した等式に、等式の向きの交換、推移、両辺への同じ元の加算を有限回適用して得られる最小の合同関係である。
有限表示可換モノイドは有限生成である。
$P\cong\mathbb N^r/\!\sim$ とする。商写像 $\mathbb N^r\twoheadrightarrow P$ は全射なので、自由可換モノイドによる特徴づけにより $P$ は有限生成である。具体的には、標準基底 $e_1,\ldots,e_r$ の像が $P$ を生成する。関係式が有限個であることは、この向きの含意には必要ない。
Rédeiの有限表示定理
一般の非可換モノイドでは、有限生成性から有限表示性は従わない。可換性を仮定すると事情が変わる。
有限生成可換モノイドは有限表示である。
$P$ を有限生成可換モノイドとする。自由可換モノイドによる特徴づけにより、ある全射
$$
\pi:\mathbb N^r\twoheadrightarrow P
$$
を取れる。体 $k$ を一つ固定し、対応するモノイド代数の準同型
$$
\Phi:k[x_1,\ldots,x_r]\longrightarrow k[P],
\qquad x^a\longmapsto t^{\pi(a)}
$$
を考える。ここで $a=(a_1,\ldots,a_r)$、$x^a=x_1^{a_1}\cdots x_r^{a_r}$ であり、$k[P]$ は記号 $t^p$ を基底にもつ $k$-ベクトル空間で、$t^pt^q=t^{p+q}$ と乗法を定めた代数である。
$\ker\Phi$ は、$\pi(a)=\pi(b)$ を満たす二項式 $x^a-x^b$ で生成される。実際、$f=\sum_a c_ax^a\in\ker\Phi$ なら、各 $p\in P$ について $\pi(a)=p$ となる項の係数和は零である。同じ $p$ に写る項から一つ $a_0$ を選べば、その部分和は
$$
\sum_{\substack{a\ne a_0\\\pi(a)=p}}c_a(x^a-x^{a_0})
$$
と書ける。これを有限個の $p$ について足せばよい。
Hilbert基底定理により多項式環 $k[x_1,\ldots,x_r]$ はNoether環である。したがって、上の二項式の族から有限個
$$
x^{u_1}-x^{v_1},\ldots,x^{u_m}-x^{v_m}
$$
を選んで $\ker\Phi$ を生成できる。Hilbert基底定理については DF04 Section 9.6 を参照。
これらの組 $(u_i,v_i)$ が生成する $\mathbb N^r$ 上の合同関係を $\approx$ とする。各組は $\pi(u_i)=\pi(v_i)$ を満たすので、$\approx$ は $\pi$ の核合同関係に含まれる。一方、商モノイド代数 $k[\mathbb N^r/\!\approx]$ の異なる基底元は $k$ 上で一次独立であるから、
$$
x^a-x^b=0\text{ in }k[\mathbb N^r/\!\approx]
\quad\Longleftrightarrow\quad a\approx b
$$
である。選んだ二項式が $\ker\Phi$ 全体を生成するため、$\pi(a)=\pi(b)$ なら $x^a-x^b$ はそれらの生成するイデアルに属し、商モノイド代数で零になる。よって $a\approx b$ である。
したがって $\approx$ は $\pi$ の核合同関係と一致し、
$$
P\cong\mathbb N^r/\!\approx
$$
は有限個の生成元と有限個の関係式による表示である。
証明の核心は、自由可換モノイド $\mathbb N^r$ のモノイド代数が有限変数多項式環になり、Hilbert基底定理を適用できることである。非可換モノイドの自由対象は語のモノイドであり、この議論はそのまま適用できない。実際、有限生成だが有限表示でない非可換モノイドが存在する。
例と反例
$\mathbb N^r$ は標準基底 $e_1,\ldots,e_r$ で生成される。関係式を一つも課さない表示をもつので、有限生成かつ有限表示である。$r=1$ の場合は加法モノイド $\mathbb N$ である。
$P=\{0,a\}$ に $a+a=a$ と定めると、$P=\langle a\rangle$ である。これは
$$
P\cong\langle a\mid 2a=a\rangle
$$
という有限表示をもつが、$a$ が冪等であるため自由可換モノイドではない。
自然数の加法モノイドの部分モノイド
$$
P=\langle2,3\rangle=\{2a+3b\mid a,b\in\mathbb N\}
$$
は有限生成だが自由でない。全射 $\mathbb N^2\to P$、$(a,b)\mapsto2a+3b$ の核合同関係は $(3,0)\sim(0,2)$ で生成されるので
$$
P\cong\langle x,y\mid3x=2y\rangle.
$$
実際、$2a+3b=2c+3d$ なら $2(a-c)=3(d-b)$ である。$2$ と $3$ が互いに素なので、ある整数 $k$ により $a-c=3k$、$d-b=2k$ となり、関係 $3x=2y$ を $|k|$ 回、適切な向きに適用して二つの係数ベクトルを結べる。
非負有理数の加法モノイド $\mathbb Q_{\ge0}$ は有限生成でない。有限集合 $S\subset\mathbb Q_{\ge0}$ を取ると、その全要素の分母を割り切る正整数 $N$ が存在し、$\langle S\rangle\subseteq\frac1N\mathbb N$ となる。しかし $1/(N+1)$ は $\frac1N\mathbb N$ に属さないため、$S$ は $\mathbb Q_{\ge0}$ 全体を生成しない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
