可換モノイド(commutative monoid)とは、結合的かつ可換な二項演算と単位元を備えた集合である。加法記法では単位元を $0$ と書き、自然数の加法や集合の合併が基本例となる。群とは異なり逆元を仮定せず、部分モノイド、生成系、単元、消去律、冪等元、合同関係、群化などを通じて構造を調べる。$a+c=b$ となる $c$ があるとき $a\preceq b$ とする代数的前順序は、消去的で単元が $0$ だけなら半順序になり、すべての元が冪等なら上限を和とする半束の順序になる。有限な消去的可換モノイドはアーベル群である。
可換モノイド(commutative monoid)は、結合的で可換な加法と零元を備えた集合である。自然数の加法、非負実数の加法、可換環のイデアル全体の積、集合の合併など、多くの「足し合わせる」操作が可換モノイドをなす。
群との違いは、各元の逆元を仮定しないことである。たとえば $\mathbb N$ は加法について可換モノイドだが、正の自然数の加法逆元を含まないため群ではない。この弱い構造の中で、生成、関係式、群化、単元、消去律、冪等元を調べるのが可換モノイド論の出発点である。可換な演算とモノイドの定義は Bou89 Ch. I, §1, no. 5, Definition 8(p. 7)と §2, no. 1, Definition 2(p. 12)にあり、$\mathbb N$ の加法と乗法が可換モノイドであることは同 §2, no. 1, Examples(p. 13)に挙がっている。
加法の記号を使うのは、演算の順序を気にせずに足し合わせられることを強調するためである。可換モノイドの「大きさの比べ方」(代数的前順序)、冪等な元だけからなる場合(半束)、有限の場合の振る舞いは、群にはない可換モノイド特有の現象であり、本記事の後半で扱う。
集合 $M$、二項演算 $+:M\times M\to M$、元 $0\in M$ の組 $(M,+,0)$ が モノイド であるとは、任意の $a,b,c\in M$ について
$$
(a+b)+c=a+(b+c),
\qquad
a+0=0+a=a
$$
が成り立つことをいう。
モノイド $(M,+,0)$ が 可換モノイド であるとは、さらに任意の $a,b\in M$ について
$$
a+b=b+a
$$
が成り立つことをいう。
本記事では可換モノイドを加法記法で書く。乗法記法を用いる文献では演算を積、単位元を $1$ と書くこともある。
可換モノイド $M,N$ の間の写像 $f:M\to N$ が 可換モノイド準同型 であるとは
$$
f(0_M)=0_N,
\qquad
f(a+b)=f(a)+f(b)
$$
をすべての $a,b\in M$ について満たすことをいう。
可換モノイドを対象、可換モノイド準同型を射とする圏を $\mathsf{CMon}$ と書く。一般の非可換モノイドの圏 $\mathsf{Mon}$ と区別する。
$x\in M$ と $n\in\mathbb N$ に対し、$nx$ を
$$
0x=0,
\qquad
(n+1)x=nx+x
$$
によって帰納的に定める。
任意の $m,n\in\mathbb N$ と $x,y\in M$ について
$$
(m+n)x=mx+nx,
\qquad
n(x+y)=nx+ny,
\qquad
(mn)x=m(nx)
$$
が成り立つ。
最初の等式は $n$ に関する帰納法で示す。$n=0$ の場合は単位律である。$n$ について成り立つなら
$$
(m+n+1)x=(m+n)x+x=mx+(nx+x)=mx+(n+1)x
$$
である。
二つ目も $n$ に関する帰納法で示せる。$n=0$ は明らかで、帰納法の仮定と可換律から
$$
(n+1)(x+y)=n(x+y)+x+y=(nx+x)+(ny+y)
$$
を得る。三つ目は $m$ に関する帰納法と最初の等式から従う。$\blacksquare$
この法則により、有限族 $x_1,\ldots,x_r\in M$ と係数 $n_1,\ldots,n_r\in\mathbb N$ に対する有限和 $\sum_i n_ix_i$ を括弧や順序に依存せず扱える。
可換モノイド $M$ の部分集合 $N\subset M$ が 部分モノイド であるとは、$0\in N$ であり、任意の $x,y\in N$ について $x+y\in N$ となることをいう。
$M$ の部分モノイドの族 $\{N_\lambda\}_{\lambda\in\Lambda}$ の交わり
$$
\bigcap_{\lambda\in\Lambda}N_\lambda
$$
は $M$ の部分モノイドである。
各 $N_\lambda$ は $0$ を含むので、交わりも $0$ を含む。$x,y$ が交わりに属するなら、すべての $\lambda$ について $x,y\in N_\lambda$ である。各 $N_\lambda$ は加法で閉じているから $x+y\in N_\lambda$ であり、したがって $x+y$ は交わりに属する。$\blacksquare$
部分集合 $X\subset M$ を含むすべての部分モノイドの交わりを、$X$ が 生成する部分モノイド といい、$\langle X\rangle$ と書く。$\langle X\rangle=M$ のとき $X$ を $M$ の生成系という。
部分集合 $X\subset M$ に対し、
$$
\langle X\rangle
=
\left\{
\sum_{i=1}^{r}n_ix_i
\;\middle|\;
r\in\mathbb N,\ x_i\in X,\ n_i\in\mathbb N
\right\}
$$
である。$r=0$ の空和は $0$ とする。
右辺を $S$ とする。空和により $0\in S$ であり、二つの有限和を連結すれば再び有限和になるので $S$ は部分モノイドである。また各 $x\in X$ は $1x$ と書けるため $X\subset S$ である。したがって $\langle X\rangle$ の最小性から $\langle X\rangle\subset S$ である。
逆に、$X$ を含む任意の部分モノイドは自然数倍と有限和について閉じているので $S$ を含む。これを特に $\langle X\rangle$ に適用すると $S\subset\langle X\rangle$ である。よって両者は等しい。$\blacksquare$
有限集合 $X\subset M$ で $\langle X\rangle=M$ となるものが存在するとき、$M$ は 有限生成 であるという。
有限生成性と有限表示性の詳しい関係は 有限生成モノイド と 可換モノイドの表示 で扱う。
元 $u\in M$ が 単元 または可逆元であるとは、ある $v\in M$ が存在して $u+v=0$ となることをいう。この $v$ を $u$ の逆元という。
単元の逆元は一意である。単元全体 $M^\times$ は $M$ の部分モノイドであり、加法についてアーベル群をなす。
$u+v=0=u+w$ とする。可換律と結合律により
$$
v=v+0=v+(u+w)=(v+u)+w=0+w=w
$$
だから逆元は一意である。
$0$ は自分自身を逆元にもつ。$u,v$ が単元で逆元をそれぞれ $u',v'$ とすれば
$$
(u+v)+(u'+v')=(u+u')+(v+v')=0
$$
なので $u+v$ も単元である。よって $M^\times$ は部分モノイドで、そのすべての元が逆元をもつからアーベル群である。$\blacksquare$
すべての元が単元である可換モノイドは、ちょうどアーベル群である。
可換モノイド $M$ が 消去的 であるとは
$$
a+x=b+x\quad\Longrightarrow\quad a=b
$$
がすべての $a,b,x\in M$ について成り立つことをいう。
消去律は、自然写像 $M\to M^{\mathrm{gp}}$ が単射になるための必要十分条件である。詳しくは 可換モノイドの群化 を参照。
元 $e\in M$ が 冪等元 であるとは $e+e=e$ を満たすことをいう。
消去的可換モノイドでは、冪等元は $0$ だけである。実際、$e+e=e+0$ から $e=0$ を得る。逆は成り立たず、非消去的でも非零冪等元をもたない可換モノイドがある(ex-commutative-monoid-doubled-one)。
可換モノイド準同型 $f:M\to N$ について、部分モノイド $A\subset M$ の像 $f(A)$ は $N$ の部分モノイドである。また部分モノイド $B\subset N$ の逆像 $f^{-1}(B)$ は $M$ の部分モノイドである。
$0_N=f(0_M)\in f(A)$ であり、$f(a),f(a')\in f(A)$ なら
$$
f(a)+f(a')=f(a+a')\in f(A)
$$
なので像は部分モノイドである。
$0_N\in B$ かつ $f(0_M)=0_N$ だから $0_M\in f^{-1}(B)$ である。$x,y\in f^{-1}(B)$ なら $f(x),f(y)\in B$ であり、
$$
f(x+y)=f(x)+f(y)\in B
$$
なので $x+y\in f^{-1}(B)$ である。$\blacksquare$
準同型によって同一視される元の対は 可換モノイドの合同関係 をなし、その商と像のあいだには準同型定理(商から像への同型)が成り立つ。
可換モノイドでは、「足して届くかどうか」で元を比べることができる。$\mathbb N$ ではこれがふつうの大小になる。
可換モノイド $M$ の元 $a,b$ について、ある $c\in M$ で $a+c=b$ となるとき $a\preceq b$ と書く。$\preceq$ を $M$ の代数的前順序(algebraic preorder)という。
可換モノイド $M$ の代数的前順序 $\preceq$ について次が成り立つ。
3 の二つの仮定はどちらも外せない。$\mathbb Z$ は消去的だが単元が $0$ だけでなく、任意の $a,b$ について $a+(b-a)=b$ なので $a\preceq b$ かつ $b\preceq a$ となり、反対称律が成り立たない。消去律を外した反例は次の例である。
三元集合 $M=\{0,e,g\}$ に、$0$ を零元とし
$$
e+e=e,\qquad e+g=g+e=g,\qquad g+g=e
$$
と定めた演算を入れる。これは、$e$ を零元とする位数 $2$ の群 $\{e,g\}$ に、新しい零元 $0$ を付け加えたものである。群 $\{e,g\}$ の演算は結合的かつ可換なので、$0$ を含む三つ組の結合律と合わせて $M$ は可換モノイドである。$e$ と $g$ に何を足しても $0$ にならないので、単元は $0$ だけである。一方 $e+g=g$ から $e\preceq g$、$g+g=e$ から $g\preceq e$ であり、$e\neq g$ だから $\preceq$ は反対称でない。$e+e=e=e+0$ だが $e\neq0$ なので、$M$ は消去的でない。
すべての元が冪等($a+a=a$)な可換モノイドを冪等可換モノイドという。合併を演算とする冪集合(ex-power-set-cmon)がその例である。冪等な場合には、代数的前順序は次の形の半順序になる。
$M$ を冪等可換モノイドとする。$a\le b$ を $a+b=b$ で定めると、次が成り立つ。
冪等性は外せない。$\mathbb N$ の加法では $a\le b$($a+b=b$)が成り立つのは $a=0$ のときだけで、$1+1=2\neq1$ だから $1\le1$ すら成り立たず、$\le$ は反射律を満たさない。
有限であることは、無限の可換モノイドには起こらない制約を課す。
有限な可換モノイド $M$ が消去的ならば、$M$ はアーベル群である。
$a\in M$ を固定し、写像 $t_a\colon M\to M$、$t_a(x):=a+x$ を考える。$a+x=a+y$ なら可換律と消去律から $x=y$ なので、$t_a$ は単射である。$M$ は有限なので $t_a$ は全射でもあり、$a+y=0$ となる $y$ がある。すなわち $a$ は単元である。$a$ は任意なので $M^\times=M$ であり、prop-units-form-group により $M$ はアーベル群である。$\square$
有限性は外せない。$\mathbb N$ は消去的だが群でない。
$M$ を有限な可換モノイドとする。各 $a\in M$ に対し、ある $k\ge1$ で $ka$ が冪等元になる。とくに $M$ が $0$ 以外の冪等元をもたなければ、各 $a$ についてある $k\ge1$ で $ka=0$ となり、$M$ はアーベル群である。
$a,2a,3a,\ldots$ は有限集合 $M$ の元なので、ある $1\le i< j$ で $ia=ja$ となる。$p:=j-i\ge1$ とおくと、prop-natural-multiple-laws により $n\ge i$ ならば $na+pa=(n-i)a+ja=(n-i)a+ia=na$ であり、繰り返して任意の $m\ge0$ で $na+mpa=na$ である。$k$ を $k\ge i$ を満たす $p$ の倍数、たとえば $k:=ip$ とすると、$2k\ge k\ge i$ かつ $k$ は $p$ の倍数なので
$$
2k\,a=ka+ka=ka+\tfrac{k}{p}\,(pa)=ka
$$
となり、$ka$ は冪等元である。後半の主張では $ka=0$ となるので、$a+(k-1)a=0$ から $a$ は単元であり、$M$ はアーベル群である。$\square$
有限性は外せない。$\mathbb N$ の $1$ の倍元 $k\cdot1=k$($k\ge1$)はどれも冪等でない。
加法に関して $\mathbb N$ は可換モノイドであり、$1$ が生成する自由可換モノイドである。$\mathbb Z$ も可換モノイドだが、すべての元が単元なのでアーベル群でもある。
集合 $S$ の冪集合 $\mathcal P(S)$ は、合併を加法、空集合を零元とすると可換モノイドになる。すべての元が $A\cup A=A$ を満たすため冪等である。$S\ne\emptyset$ なら消去的ではない。
可換モノイド $M,N$ の直積 $M\times N$ は
$$
(m,n)+(m',n')=(m+m',n+n'),
\qquad
0=(0_M,0_N)
$$
により可換モノイドになる。
$\mathbb N$ の部分集合 $\{1,2,3,\ldots\}$ は加法について閉じているが、零元 $0$ を含まないため部分モノイドではない。演算について閉じていることだけでは部分モノイドにならない反例である。
$\mathbb N$ に、$1$ の「写し」となる新しい元 $1'$ を付け加えた $M:=\mathbb N\cup\{1'\}$ を考える。写像 $\varphi\colon M\to\mathbb N$ を $\varphi(1'):=1$、$\mathbb N$ の上では恒等写像と定め、
$$
x+y:=\begin{cases}x&(y=0)\\ y&(x=0)\\ \varphi(x)+\varphi(y)&(x\neq0,\ y\neq0)\end{cases}
$$
とおく(第 3 の場合の右辺は $\mathbb N$ の和で、値は $2$ 以上)。可換律は定義から明らかである。結合律は、$x,y,z$ のどれかが $0$ なら両辺ともその $0$ を除いた和になり、三つとも $0$ でなければ、$2$ 以上の自然数の上で $\varphi$ は恒等写像だから両辺とも $\varphi(x)+\varphi(y)+\varphi(z)$ になることから従う。よって $M$ は可換モノイドである。
$1+1=2=1'+1$ だが $1\neq1'$ なので、$M$ は消去的でない。一方、$x\neq0$ が冪等なら $x+x=2\varphi(x)\ge2$ が $x$ に等しいので $x\in\mathbb N$、$2x=x$ となり $x=0$ に反する。よって冪等元は $0$ だけである。すなわち「冪等元が $0$ だけなら消去的」という含意は成り立たない。
主な例の性質をまとめる。
| 可換モノイド | 消去的 | 単元 | 冪等元 | 代数的前順序は半順序 |
|---|---|---|---|---|
| $\langle\mathbb N,+\rangle$ | はい | $0$ だけ | $0$ だけ | はい(ふつうの大小) |
| $\langle\mathbb Z,+\rangle$ | はい | すべて | $0$ だけ | いいえ |
| $\langle\mathcal P(S),\cup\rangle$($S\neq\emptyset$) | いいえ | $\emptyset$ だけ | すべて | はい(包含) |
| $\langle\mathbb Z,\times\rangle$(単位元は $1$) | いいえ | $\pm1$ | $0,1$ | いいえ($-1$ と $1$) |
| $\{0,e,g\}$(ex-commutative-monoid-not-antisymmetric) | いいえ | $0$ だけ | $0,e$ | いいえ |
| $\mathbb N\cup\{1'\}$(ex-commutative-monoid-doubled-one) | いいえ | $0$ だけ | $0$ だけ | はい |
最後の列の「はい」はそれぞれ、prop-commutative-monoid-preorder の 3、prop-commutative-monoid-semilattice、および直接の確認($\mathbb N\cup\{1'\}$ では $0$ でない和が $2$ 以上になるので、$x\preceq y\preceq x$ から $x=y$ が出る)による。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 単元が $0$ だけ | $\langle\mathbb Z,+\rangle$ | 代数的前順序は半順序(prop-commutative-monoid-preorder の 3) |
| 消去律 | $\{0,e,g\}$(ex-commutative-monoid-not-antisymmetric) | 同上 |
| 冪等性 | $\langle\mathbb N,+\rangle$ | $a+b=b$ で定めた $\le$ は半順序(prop-commutative-monoid-semilattice) |
| 有限性 | $\langle\mathbb N,+\rangle$ | 消去的なら群(prop-commutative-monoid-finite-cancellative)、ある倍元が冪等(prop-commutative-monoid-finite-idempotent) |
| 消去律(「冪等元が $0$ だけ」に弱める) | $\mathbb N\cup\{1'\}$(ex-commutative-monoid-doubled-one) | 冪等元が $0$ だけなら消去的 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する