モノイド

同義語:monoid

概要

モノイド(monoid)とは、結合律を満たす二項演算と両側単位元 $1_M$ を備えた集合であり、群と違って逆元は要求せず、自然数の加法、写像全体 $\operatorname{End}(X)$ の合成、語の連接などを統一する。モノイド準同型は積と単位元の両方を保つ写像で、語のモノイド $\Sigma^*$ は任意の写像 $\Sigma\to M$ を一意に準同型へ延ばす自由モノイドであり、モノイドとその準同型は単一対象の小圏と関手に一対一に対応する。単元全体 $M^\times$ は群になるが、片側逆元だけでは単元とは限らず、有限モノイドでは左消去律だけで群になる。左乗法 $a\mapsto L_a$ はモノイドを $\operatorname{End}(M)$ に単射準同型で埋め込む。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 集合, 二項演算, 写像

モノイドとは、集合に結合的な二項演算と単位元を与えたものである。群と違って各元の逆元は要求せず、積の順序を入れ替えてよいとも限らない。たとえば自然数の加法 $(\mathbb{N},+,0)$ や、有限長の語の連接(空語が単位元)がモノイドの例になる。

定義

単位元をもつ結合的演算

集合 $M$ と二項演算
$$ \cdot\colon M\times M\longrightarrow M, \qquad (a,b)\longmapsto a\cdot b $$
の組 $(M,\cdot)$ がモノイド(monoid)であるとは、次の二つの条件を満たすことをいう。

  1. 結合律:任意の $a,b,c\in M$ に対して $(a\cdot b)\cdot c=a\cdot(b\cdot c)$。
  2. 単位元の存在:ある $1_M\in M$ が存在し、任意の $a\in M$ に対して $1_M\cdot a=a=a\cdot1_M$。
    演算を積のように書くときはしばしば $a\cdot b$ を $ab$ と略記する。加法記法を用いる場合は演算を $+$、単位元を $0$ と書く。モノイドの定義は Mac98 Introduction, pp. 3–4 にもまとめられている。
演算と単位元を保つ写像

モノイド $M,N$ の間のモノイド準同型(monoid homomorphism)とは、写像 $f\colon M\to N$ であって
$$ f(ab)=f(a)f(b),\qquad f(1_M)=1_N $$
を満たすものをいう。積だけでなく単位元も保つことを定義に含める。

演算で閉じた部分集合

モノイド $M$ の部分集合 $S\subset M$ が部分モノイド(submonoid)であるとは、$1_M\in S$ であり、任意の $a,b\in S$ に対して $ab\in S$ となることをいう。このとき $S$ は $M$ の演算と単位元をそのまま制限することでモノイドになる。

直感

モノイドは、「二つの操作を順番に合成でき、何もしない操作がある」という状況の最小の代数的な器である。結合律があるため、$a_1a_2\cdots a_n$ の括弧の付け方を指定する必要がない。一方、群 と違って各元の逆元は要求しない。また、積の順序を入れ替えてよいとは限らない。入れ替えが常に可能な場合が 可換モノイド である。

例と反例

加法モノイド

$(\mathbb{N},+,0)$ はモノイドである。加法は結合的であり、0 が単位元である。この例は可換モノイドであるが、$1$ の加法に関する逆元は $\mathbb{N}$ にないので群ではない。

写像の合成

集合 $X$ から自身への写像全体 $\operatorname{End}(X)$ は、合成を演算、恒等写像 $\operatorname{id}_X$ を単位元とするモノイドである。
$X=\{0,1\}$ とし、$f$ を $0$ への定数写像、$g$ を $0$ と $1$ を入れ替える写像とする。このとき $f\circ g$ は $0$ への定数写像だが、$g\circ f$ は $1$ への定数写像である。したがって $\operatorname{End}(X)$ は一般に非可換である。

語の連接

アルファベット $\Sigma$ の文字からなる有限長の語の集合を $\Sigma^*$ と書く。語の連接は結合的であり、空語 $\varepsilon$ が単位元であるから、$(\Sigma^*,\text{連接},\varepsilon)$ はモノイドである。$\Sigma$ が異なる文字 $x,y$ を含めば、語 $xy$ と $yx$ は異なるので、このモノイドは非可換である。

反例:結合律だけでは足りない

正の整数全体 $\mathbb{Z}_{>0}$ は加法について閉じており、加法は結合律を満たす。しかし加法の単位元 $0$ は $\mathbb{Z}_{>0}$ に属さない。よって $(\mathbb{Z}_{>0},+)$ は 半群 ではあるがモノイドではない。この反例は、「結合的な二項演算をもつならモノイドである」という含意を破る。

性質

単位元の一意性

モノイドの単位元は一意的である。

単位元の一意性の所在

これは 単位元 の系「単位元の一意性」をモノイドに適用したものである。

直積と成分ごとの演算

モノイド $M,N$ に対し、直積集合 $M\times N$ 上に
$$ (a,b)(a',b'):=(aa',bb') $$
と定めると、$M\times N$ は単位元 $(1_M,1_N)$ をもつモノイドになる。

$(a,b),(a',b'),(a'',b'')\in M\times N$ に対し、$M,N$ の結合律から
$$ \bigl((a,b)(a',b')\bigr)(a'',b'')=((aa')a'',(bb')b'')=(a(a'a''),b(b'b''))=(a,b)\bigl((a',b')(a'',b'')\bigr) $$
である。また
$$ (1_M,1_N)(a,b)=(a,b)=(a,b)(1_M,1_N) $$
であるから、$(1_M,1_N)$ は単位元である。$\square$

部分モノイドの共通部分

モノイド $M$ の部分モノイドからなる族 $(S_i)_{i\in I}$ に対し、$\bigcap_{i\in I}S_i$ も $M$ の部分モノイドである。ただし $I=\emptyset$ のときは共通部分を $M$ と定める。

各 $S_i$ は $1_M$ を含むので、$1_M\in\bigcap_{i\in I}S_i$ である。$a,b\in\bigcap_{i\in I}S_i$ ならば、すべての $i\in I$ に対して $a,b\in S_i$ である。各 $S_i$ は積について閉じているから $ab\in S_i$ であり、$ab\in\bigcap_{i\in I}S_i$ となる。$I=\emptyset$ の場合は $M$ 自身が部分モノイドである。$\square$

自由モノイド

語がもつ普遍性

集合 $\Sigma$ とモノイド $M$ をとり、$\iota\colon\Sigma\to\Sigma^*$ を各文字を長さ $1$ の語とみなす写像とする。任意の写像 $u\colon\Sigma\to M$ に対し、
$$ \overline{u}\circ\iota=u $$
を満たすモノイド準同型 $\overline{u}\colon\Sigma^*\to M$ がただ一つ存在する。この性質により $\Sigma^*$ を $\Sigma$ 上の自由モノイド(free monoid)という。
$$ \xymatrix{ \Sigma \ar[r]^\iota \ar[dr]_u & \Sigma^* \ar@{.>}[d]^{\overline u} \\ & M } $$
図式が可換とは $\overline u\circ\iota=u$ ということである。

語 $w=a_1a_2\cdots a_n$ に対し
$$ \overline{u}(w):=u(a_1)u(a_2)\cdots u(a_n), \qquad \overline{u}(\varepsilon):=1_M $$
と定める。$\Sigma^*$ の各語は文字の有限列として一意的に書けるので、これは写像を定める。語 $w=a_1\cdots a_m$ と $v=b_1\cdots b_n$ の連接に対して
$$ \overline{u}(wv)=u(a_1)\cdots u(a_m)u(b_1)\cdots u(b_n)=\overline{u}(w)\overline{u}(v) $$
であり、$\overline{u}(\varepsilon)=1_M$ だから $\overline{u}$ はモノイド準同型である。また長さ $1$ の語について $\overline{u}(a)=u(a)$ であるから $\overline{u}\circ\iota=u$ である。
一意性を示す。$v\colon\Sigma^*\to M$ を $v\circ\iota=u$ を満たすモノイド準同型とする。準同型は単位元を保つから $v(\varepsilon)=1_M=\overline{u}(\varepsilon)$ である。任意の非空語 $w=a_1\cdots a_n$ に対し、
$$ v(w)=v(a_1)\cdots v(a_n)=u(a_1)\cdots u(a_n)=\overline{u}(w) $$
である。よって $v=\overline{u}$ である。$\square$

単一対象小圏との対応

モノイドと単一対象小圏

モノイドのデータと、対象を一つだけもつ 小圏(局所小圏) のデータは互いに移し合える。さらに、モノイド準同型は対応する単一対象小圏の間の 関手 と一対一に対応する。ここで小圏とは対象と射が集合をなす 圏 をいう。

まずモノイド $M$ から小圏 $\mathcal{B}M$ を作る。対象は一つ $*$ だけとし、
$$ \operatorname{Hom}_{\mathcal{B}M}(*,*)=M $$
とおく。$f,g\in M$ に対して射の合成を
$$ g\circ f:=gf $$
と定め、恒等射を $1_M$ と定める。$M$ の結合律が射の合成の結合律を与え、単位元の等式 $1_Mf=f=f1_M$ が恒等射の法則を与える。よって $\mathcal{B}M$ は小圏である。
逆に、対象が $*$ 一つだけの小圏 $\mathcal{C}$ からモノイドを作る。底集合を
$$ M_{\mathcal{C}}:=\operatorname{Hom}_{\mathcal{C}}(*,*) $$
とし、$f,g\in M_{\mathcal{C}}$ に対して $gf:=g\circ f$ と定める。圏における合成の結合律によりこの積は結合的であり、$\operatorname{id}_*$ が単位元になる。したがって $M_{\mathcal{C}}$ はモノイドである。
第一の構成の後に第二の構成を施すと、底集合、積、単位元はそれぞれ $M$、もとの積、$1_M$ に戻る。逆順では、唯一の対象、射集合、合成、恒等射がすべてもとのものに戻る。よって二つの構成は互いに逆である。
最後に射の対応を確かめる。モノイド準同型 $h\colon M\to N$ は唯一の対象を唯一の対象へ送り、各射 $f\in M$ を $h(f)\in N$ へ送る。等式
$$ h(g\circ f)=h(gf)=h(g)h(f)=h(g)\circ h(f), \qquad h(1_M)=1_N $$
により、これは関手 $\mathcal{B}M\to\mathcal{B}N$ である。逆にそのような関手は射の合成と恒等射を保つから、射集合上でモノイド準同型を定める。これらの対応も互いに逆である。$\square$

モノイドを単一対象の圏とみなす標準的な観点は Mac98 Chapter I §1 にも記載されている。この対応は、モノイドが単に「圏に似たもの」だという類比ではなく、合成と単位元を同じデータとして見直す精密な対応である。

有限個の積と冪

二項演算の公理は三つの元について書かれているが、実際には任意の有限個の積を扱いたい。積の順序と括弧を分けて考えることが大切である。結合律が保証するのは括弧の変更であり、順序の変更ではない。空の列の積を $1_M$ と定めると、空語、空の合成、指数 $0$ の冪を同じ規約で扱える。

有限列の積の分割

列 $a_1,\ldots,a_n$ の積を左から順に計算して定める。$0\le k\le n$ なら
$$ a_1\cdots a_n=(a_1\cdots a_k)(a_{k+1}\cdots a_n) $$
である。両側で空の積は $1_M$ とする。

積の分割の証明の所在

$0< k< n$ の場合は 代数構造 の補題「左積と右側の積の連結」を $p=k$、$q=n-k$ に適用する。$k=0$ の場合は左単位元の法則、$k=n$ の場合は右単位元の法則による。$n=0$ の場合も $1_M=1_M1_M$ である。

任意の括弧付きの積は、一番外の演算で列を二つの連続する部分列に分けている。それぞれの部分列の括弧を帰納的に外し、prop-monoid-list-product を適用すれば、左から順に計算した積と等しいことが分かる。ここでは文字の並び順は一度も変えていない。この区別は写像の合成で特に重要である。
元 $a\in M$ について $a^0=1_M$、$a^{n+1}=a^na$ と定めると、有限列の分割から $a^{m+n}=a^ma^n$ が従う。また $(a^m)^n=a^{mn}$ も $n$ に関する帰納法で従う。したがって一つの元の冪だけからなる部分モノイドは、もとのモノイドが非可換でも可換である。しかし異なる元 $a,b$ について $(ab)^n=a^nb^n$ とは限らない。

冪の公式に可換性が必要な例

集合 $\{0,1\}$ 上で $f$ を $0$ への定数写像、$g$ を交換写像とする。積を合成とすると $fg=f$、したがって $(fg)^2=f$ である。一方 $f^2=f$、$g^2=\operatorname{id}$ だから、この組では偶然 $f^2g^2=f$ も成り立つ。より区別のはっきりした例として、実数の写像 $a(x)=x+1$、$b(x)=2x$ を使うと、$(ab)^2(x)=4x+3$、$a^2b^2(x)=4x+2$ となる。結合律だけでは異なる元の冪をまとめられない。

単位元の保存と可逆な元

準同型の条件で単位元の保存を別に要求するのには理由がある。演算の保存から分かるのは $f(1_M)^2=f(1_M)$ という冪等性にすぎない。行き先の全体に対する単位元だとは限らない。

反例:積を保っても単位元を保たない

整数の乗法モノイド $M=(\mathbb Z,\cdot,1)$ から自身への定数写像 $f(n)=0$ は $f(mn)=0=f(m)f(n)$ を満たす。しかし $f(1)=0\ne1$ なのでモノイド準同型ではない。結合的演算の準同型と、単位元も備えた構造の準同型の差がこの例に現れる。

元 $u$ が両側の逆元をもつとき、$u$ を単元という。つまり、ある $v$ について $uv=vu=1_M$ となることである。この条件はモノイドの中で可逆な操作を選び出す。すべての元が単元であるモノイドが群である。

単元の集合は群になる

モノイド $M$ の単元全体を $M^\times$ とする。$M^\times$ は $M$ の部分モノイドであり、もとの積について群になる。モノイド準同型 $f\colon M\to N$ は単元を単元へ送る。

単元群と準同型

群構造は 逆元 の命題「可逆元全体は群をなす」による。$1_M$ を含み積で閉じるので部分モノイドでもある。準同型については $f(u)f(u^{-1})=f(1_M)=1_N$ と逆順の等式により、$f(u)$ は単元である。

両側の逆元は一意である。$v,w$ が $u$ の逆元なら $v=v(uw)=(vu)w=w$ となる。ただし一方だけの逆元では、無限のモノイドにおいて他方の等式を保証しない。

反例:片側逆元だけでは可逆でない

$\mathbb N$ 上で $s(n)=n+1$ とし、$r(0)=0$、$r(n+1)=n$ と定める。このとき $r\circ s=\operatorname{id}$ だが、$(s\circ r)(0)=1\ne0$ である。$s$ は全射でないので、写像としての両側逆元をもたない。したがって「左逆元をもつなら単元である」という含意は一般のモノイドでは偽である。

消去律と有限性

左消去律とは $ab=ac$ なら $b=c$ となる性質であり、右消去律とは $ba=ca$ なら $b=c$ となる性質である。群なら逆元をかけることで両方が成り立つ。しかし自然数の加法モノイドも両方の消去律を満たすので、消去できることと逆元の存在は同じではない。

有限モノイドにおける消去律

有限モノイド $M$ が左消去律を満たせば $M$ は群である。右消去律だけを仮定しても同じ結論になる。

左消去律を仮定する。$a\in M$ に対し左乗法 $L_a(x)=ax$ は単射である。有限集合上の単射は全射だから、ある $b\in M$ が $ab=1_M$ を満たす。このとき $a(ba)=(ab)a=a=a1_M$ なので、左消去律より $ba=1_M$ である。よって $a$ は単元であり、すべての元について同じ議論ができる。右消去律の場合は左右を交換して証明すればよい。$\square$

この証明で有限性を使うのは単射から全射へ移る箇所だけである。無限集合の自己写像は単射でも全射とは限らず、$\mathbb N$ の平行移動 $n\mapsto n+1$ がまさにそうなっている。有限性を外したときに、消去律から逆元が生じなくなる理由をこの写像で見ることができる。

外す条件反例成り立たなくなること
単位元の存在正の整数の加法結合的演算がモノイドになる
準同型による単位元の保存整数の乗法上の零定数写像単元が単元へ写る
逆元の両側性自然数上の後者写像片側逆元から単元になる
消去的モノイドの有限性自然数の加法モノイドが群になる

正則作用による具体化

抽象的な元の積を、集合上の操作の合成として表せる。各 $a\in M$ に左乗法 $L_a\colon M\to M$ を対応させると、結合律は $L_{ab}=L_a\circ L_b$ という等式になる。単位元は恒等写像に対応するので、この対応はモノイド準同型である。

自分自身への作用は忠実である

写像 $\lambda\colon M\to\operatorname{End}(M)$、$a\mapsto L_a$ は単射モノイド準同型である。

任意の $x$ に対して $L_{ab}(x)=(ab)x=a(bx)=(L_a\circ L_b)(x)$ であり、$L_{1_M}(x)=x$ だから準同型である。$L_a=L_b$ なら、$1_M$ における値を比較して $a=L_a(1_M)=L_b(1_M)=b$ となるので単射である。$\square$

ここでの写像 $L_a$ 自身が単射である必要はない。対応 $a\mapsto L_a$ の単射性と、各 $L_a$ の単射性は異なる主張である。前者はどんなモノイドでも成り立ち、後者は左消去律と同値である。例えば零を含む乗法モノイドでは $L_0$ は定数写像だが、$L_0$ と他の $L_a$ は単位元での値により区別できる。この観点から、消去律は作用の中の個々の操作が情報を失わないこととして理解できる。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する