モノイド

数学、とくに抽象代数学における単系︵たんけい、英: monoid; モノイド︶はひとつの二項演算と単位元をもつ代数的構造である。モノイドは単位元をもつ半群︵単位的半群︶であるので、半群論の研究対象の範疇に属する。

モノイドの概念は数学のさまざまな分野に現れる。たとえば、モノイドはそれ自身が﹁ただひとつの対象をもつ圏﹂と見ることができ、したがって﹁集合上の写像とその合成﹂といった概念を捉えたものと考えることもできる。モノイドの概念は計算機科学の分野でも、その基礎付けや実用プログラミングの両面で広く用いられる。

モノイドの歴史や、モノイドに一般的な性質を付加した議論などは半群の項に譲る。

定義

集合 Sとその上の二項演算 •: S× S→ Sが与えられ、以下の条件

結合律

S の任意の元 a, b, c に対して、(a • b) • c= a• (b • c).

単位元の存在

S の元 eが存在して、S の任意の元 aに対して e• a= a• e= a.

を満たすならば、組 (S, •, e) をモノイドという。まぎれの虞のない場合、対 (S, •) あるいは単に Sのみでも表す。 二項演算の結果 a• bを aと bの積と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、群が得られる。逆に任意の群はモノイドである。

二項演算の記号は省略されることが多く、たとえば先ほどの公理に現れる等式は (ab)c = a(bc), ea= ae= aと書かれる。本項でも明示する理由がない限り二項演算の記号を省略する。

モノイドの構造

部分モノイド

モノイド Mの部分集合 Nが Mの部分モノイド (submonoid) とは、M の単位元を含み、閉性質: x, y∈ Nならば xy∈ Nとなるようなものをいう。これは Mのモノイド演算の制限 •|_N: N× N→ Mの像が im(•|_N) ⊂ Nを満たすということであり、従って •|_N は N上の二項演算を定め、部分モノイド Nは明らかにそれ自身が一つのモノイドとなる。

モノイドの生成

部分集合 Sがモノイド Mの生成系 (generator) であるとは Mの任意の元が Sの元だけから二項演算を繰り返して得られることをいう︵生成系に属する元を生成元という︶。モノイド Mがその部分集合 Sで生成されるとき M= ⟨S⟩ などと書く。

$\langle S\rangle =\{s_{k_{1}}^{e_{k_{1}}}s_{k_{2}}^{e_{k_{2}}}\cdots s_{k_{m}}^{e_{k_{m}}}\mid \exists m\in \mathbb {N} ,(k_{1},\ldots ,k_{m})\in \mathbb {N} ^{m},e_{k_{j}}\in \mathbb {N} ,s_{k_{j}}\in S\}.$$\langle S\rangle =\{s_{k_{1}}^{e_{k_{1}}}s_{k_{2}}^{e_{k_{2}}}\cdots s_{k_{m}}^{e_{k_{m}}}\mid \exists m\in \mathbb {N} ,(k_{1},\ldots ,k_{m})\in \mathbb {N} ^{m},e_{k_{j}}\in \mathbb {N} ,s_{k_{j}}\in S\}.$
M の各元 xに対し x⁰ = 1_M を Mの単位元とする規約を設けるならば、⟨S⟩ における Sの元の冪が零となることも許し、⟨S⟩ は Sを含む最小の部分モノイドを表す。

M が有限個の元からなる生成系をもつとき、有限生成 (finitely generated) あるいは有限型 (finite type) であるという。特に、M のただ一つの元 fで生成されるモノイド ⟨f⟩ は単項生成モノイドあるいは巡回モノイド (cyclic monoid) と呼び、集合としては fの冪全体の成す集合 {f⁰, f¹, …} に一致する。

可換モノイド

演算が可換であるようなモノイドは、可換モノイド (commutative monoid) という︵稀にアーベルモノイド (abelian monoid) ともいう︶。可換モノイドはしばしば二項演算の記号を "+" として加法的に書かれる。任意の可換モノイド Mは

$x\leq y\iff x+z=y\quad \exists z\in M$$x\leq y\iff x+z=y\quad \exists z\in M$
として定まる代数的前順序 "≤" を持つ。可換モノイド Mの順序単位 (order-unit) u∈ Mとは、M の各元 xに対して適当な正の整数 nをとれば x≤ nu(右辺は n個の uの和を表す)とできるようなものをいう。これは Mが半順序可換群 Gの正錐である場合にもよく用いられ、この場合には uを Gの順序単位と呼ぶ。

部分可換モノイド

いくつかの元については可換だが、必ずしもすべての元が可換でないようなモノイドはトレースモノイドという。トレースモノイドは並列計算の理論によく現れる。

例

●任意の一元集合 {x} は x• x= xと置くことによりモノイドとなる。これを自明なモノイドという。

●任意の単位的環の元の全体は、加法あるいは乗法に関してそれぞれモノイドを成す。
●整数全体、有理数全体、実数全体、複素数全体は加法あるいは乗法に関してそれぞれモノイドを成す。

●与えられた環に係数を持つ n-次正方行列の全体は行列の加法または行列の乗法に関してモノイドを成す。

●任意の有界半束は冪等可換モノイドである。
●特に、任意の有界束は交わりについても結びについてもモノイドとなる︵モノイドの単位元はそれぞれ束の最大元および最小元で与えられる︶。したがって、束であるハイティンク代数やブール代数はそのようなモノイド構造を持つ。

●︵0 を含む︶自然数の全体 N₀ は加法に関して 0 を単位元とするモノイドを成し、また乗法に関して 1を単位元とするモノイドを成す。N₀ の加法に関する部分モノイドは自然数モノイド (numerical monoid) と呼ばれる。N₀ の 0 以外の元︵正の整数︶からなる部分集合 Nは乗法に関して 1を単位元とする部分モノイドを成す。

●閉曲面の同相類の全体は連結和 "#" に関して可換モノイドを成す。単位元は通常の球面︵2-球面︶の属する同相類である。さらにいえば、トーラスの属する同相類 aと射影平面の属する同相類 bに対して、このモノイドの任意の元 cは c= na# mbの形に一意的に表される。ここで nは非負の整数で、m は 0, 1, 2 の何れか︵実は3b = a# bが成り立つ︶である。

●集合 S上の自己写像︵変換︶S → S全体の成す集合は、恒等写像を単位元とし写像の合成をモノイド演算としてモノイドになる。これを S上の全変換モノイド (full transformation monoid) と呼ぶ。S が有限であることと S上の全変換モノイドが有限であることは同値である。

モノイドの構成法

与えられた代数系をモノイドにする操作や、既知のモノイドから新たなモノイドを作り出す操作がいくつか存在する。

自由モノイド

固定された字母集合 Σ 上の有限文字列全体(空文字列を含む)は、連接を二項演算とし単位元を空文字列としてモノイドとなる。このモノイドを Σ* で表すと、これは Σ を生成系としてもち、公理の等式以外に元の間の関係式をもたないので Σ 上の自由モノイドと呼ぶ。自由モノイドはモノイドの圏 Mon における自由対象であり、その普遍性はモノイドの表示として理解することができる︵後述︶。

1-添加

任意の半群 Sは、S に属さない新たな元 eを︵新たな︶単位元として添加してモノイドにすることができる。すなわち、S^e ≔ S∪ {e} とし、S の任意の元 sに対して e• s= s= s• eと定めるとき S^eはモノイドである。

S 上の左零半群に単位元 eを添加したものは︵find-first としても知られる︶冪等モノイドであり、S 上の右零半群に単位元 eを添加したものは︵find-last とも呼ばれる︶反モノイドとなる。 二つの元 {<, >} を持つ左零半群に単位元 "=" を添加して得られる冪等モノイド {<, =, >} は順序の与えられた集合の元の列に対する辞書式順序のモデルを与える。

逆転モノイド

任意のモノイド (M, •) に対し、その反モノイド (opposite monoid) (M^op, •^op) とは、台集合と単位元は Mと同じものとし、その演算を

$x{\stackrel {\text{op}}{{}\bullet {}}}y:=y\bullet x$$x{\stackrel {\text{op}}{{}\bullet {}}}y:=y\bullet x$
と定めて得られるモノイドである︵逆モノイド、逆転モノイド、反対モノイドなどともいう︶。任意の可換モノイドは自分自身を反モノイドとして持つ。

直積モノイド

二つのモノイド M, N に対して︵より一般に、有限個のモノイド M₁, …, M_kに対して、あるいは無限族 {M_i}_i∈I に対して︶、それらの直積集合 M× N︵あるいは M₁× ⋯ × M_k, ∏_i∈I M_i︶もまたモノイドとなる。モノイド演算および単位元は、成分ごとの積および成分ごとの単位元の組として与えられる。

与えられたモノイド Mに対し、与えられた集合 Sから Mへの写像の全体 Map(S, M) は再びモノイドとなる。単位元は任意の元を Mの単位元へ写す定値写像で、演算は Mの積から導かれる点ごとの積で、それぞれ与えられる。これは Sで添字付けられたモノイドの族 {M}_i∈S の直積モノイドと本質的に同じものである。

商モノイド

モノイド (M, •, 1_M) 上の合同関係︵モノイド合同︶∼ とは、モノイド構造と両立する︵すなわち、a ∼ bかつ c∼ dならば ac∼ bdを満たす︶同値関係を言う。モノイド Mのモノイド合同 ∼ による剰余モノイドあるいは商モノイドは、各元 x∈ Mの属する同値類を [x] と書くとき、商集合 M/∼ に

${\displaystyle [$x]\circ [y]:=[xy]} $[x]\circ [y]:=[xy]$
で定まるモノイド演算を入れて得られるモノイド (M/∼, ∘, [1_M]) を言う。

冪集合モノイド

モノイド (M, •) を固定して、M の冪集合 P(M) を考える。P(M) の 部分集合 $S,T$$S,T$の間の二項演算 "∗" を

$S*T:=\{s\bullet t\mid s\in S,t\in T\}$$S*T:=\{s\bullet t\mid s\in S,t\in T\}$
で定めれば、P(M) は自明モノイド {e} を単位元とするモノイドとなる。同じ方法で、群 Gの冪集合は群の部分集合の積に関するモノイドとなる。

性質

モノイドにおいて、元 xの自然数冪を

●x¹ := x,

●xⁿ := x• … • x︵n 個の xの積、n >1︶

と定義することができる。このとき、指数法則 x^n+p = xⁿ• x^pの成立は明らかである。定義から直接従うこととして、単位元 eが一意に存在するので、任意の xに対して x⁰ := eと定義すると、指数法則は任意の非負整数冪に対してなお有効である。

モノイドにおいては、可逆元︵あるいは単元︶の概念を定義することができる。モノイドの元 xが可逆であるとは xy= eかつ yx= eを満たす元 yが存在するときにいう。y は xの逆元と呼ばれる。y および zが xの逆元ならば、結合律により y= (zx)y = z(xy) = zとなるから、逆元は存在すればただひとつである。

元 xが逆元 yを持つ場合には、x の負の整数冪を x⁻¹ := yおよび x⁻ⁿ := y• … • y︵n 個の yの積、n >1︶と定義することができて、先ほどの指数法則が n, pを任意の整数として成立する。このことが xの逆元がふつう x⁻¹ と書かれることの理由である。モノイド Mの単元の全体は Mの演算 • に関して単元群と呼ばれる群を成す。この意味で任意のモノイドは必ず少なくとも一つの群を含む︵ただし、それが単位元のみからなる自明な群である場合もある︶。

しかしながら、任意のモノイドが必ず何らかの群に含まれるとは限らない。例えば、b が単位元ではない場合にも a• b= aを満たすような二つの元 a, bをとることができるモノイドというものを矛盾なく考えることができるが、このようなモノイドを群に埋め込むことはできない。なぜなら、埋め込んだ群において必ず存在する aの逆元を両辺に掛けることにより b= eが導かれ、b が単位元でないことに矛盾するからである。モノイド (M, •) が消約律 (cancellation property) を満たす、あるいは消約的 (cancellative) であるとは

M の任意の元 a, b, cに対し、a • b= a• cが成り立つならば、常に b= cを帰結することができる

という条件を満たすときにいう。消約的可換モノイドは常にグロタンディーク構成によって群に埋め込むことができる。これは、整数全体の成す加法群︵加法演算 "+" に関する群︶を自然数全体の成す加法モノイド︵加法演算 "+" に関する消約的可換モノイド︶から構成する方法の一般化である。しかし、非可換消約的モノイドは必ずしも群に埋め込み可能でない。

消約的モノイドが有限ならば、実は群になる。実際、モノイドの元 xを一つ選べば、有限性より適当な m> n> 0 をとって xⁿ= x^mとすることができるが、これは消約律により x^m−n = e︵e はモノイドの単位元︶となり、x^m−n−1 が xの逆元となる。

巡回モノイドの位数が有限な nであるとき、0 ≤ k≤ n− 1 をみたす適当な kに対して fⁿ= f^kが成り立つ。実は、そのような kを定めるごとに位数 nの相異なるモノイドが得られ、逆に任意の巡回モノイドはそれらのモノイドのうちの何れか一つに同型となる。特に k= 0 の場合は、全ての fⁱが逆元を持ち、︵ただひとつの位数 nの︶巡回群を定める。このとき fは巡回置換として

${\begin{pmatrix}0&1&2&...&n-2&n-1\\1&2&3&...&n-1&k\end{pmatrix}}$${\begin{pmatrix}0&1&2&...&n-2&n-1\\1&2&3&...&n-1&k\end{pmatrix}}$
と表すことができ、モノイドの積と置換の積が対応する。

モノイドの右消約元の全体あるいは左消約元の全体は部分モノイドを成す︵単位元を含むのは明らかだが、演算が閉じていることはそれほど明らかではない︶。これは、任意の可換モノイドの消約元の全体はかならず群に延長することができるということを意味している。

モノイド Mは、M の各元 aがそれぞれ

a = a• a⁻¹ • aかつ a⁻¹ = a⁻¹ • a• a⁻¹

となる Mの元 a⁻¹ をただひとつ持つとき、M を逆モノイド (inverse monoid) あるいは山田モノイドという。逆モノイドが消約的ならばそれは群を成す。

モノイド作用と作用素モノイド

(M, •) をモノイドとする。集合 Xへの︵左︶M-作用 (M-act) あるいは Mによる左作用とは、集合 Xと外部演算 .: M× X→ Xの組で、外部演算 "." が

●X の任意の元 xに対して、 e.x = xが成り立つ。

●M の任意の元 a, bと Xの任意の元 xに対して、a.(b.x) = (a • b).x が成り立つ。

という二つの条件を満たす︵ただし eは Mの単位元︶という意味でモノイド構造と両立することをいう。これは群作用のモノイド論における類似物である。右 M-作用も同様に定義される。ある作用に関するモノイドは作用素モノイドとも呼ばれる。重要な例として、オートマトンに現れる状態遷移系が挙げられる。ある集合上の自分自身への写像から成る半群(変換半群)は、恒等変換を付け加えることで作用素モノイドにすることができる。

モノイド準同型

ふたつのモノイド (M, •), (M′, •′) の間のモノイド準同型 (monoid homomorphism) とは、写像 f: M→ M′ であって、

●M の任意の元 x, yに対して f(x • y) = f(x) •′ f(y),

●f(e) = e′

を満たすものをいう。ここで、e および e′ はそれぞれ Mおよび M′ の単位元である。モノイド準同型は簡単にモノイド射 (monoid morphisms) と呼ばれることもある。

半群準同型は単位元を保つことを要しないため、必ずしもモノイド準同型とはならない。これは群準同型の場合とは対照的な事実で、群の間の半群準同型はかならず単位元を保ち、したがって群準同型となることを、群の公理から示すことができる。モノイドではそのようなことは一般には望めないので、モノイド準同型の定義では﹁単位元を保つ﹂ことを改めて別に要請する必要がある。

全単射なモノイド準同型はモノイド同型と呼ばれる。ふたつのモノイドが同型であるとは、それらの間にモノイド同型が存在するときにいう。

生成元と基本関係

モノイドは、群が生成系と基本関係による表示によって特定できるというのと同じ意味で、表示 (presentation) を持つ。すなわち、モノイドは生成系 Σ と Σ が生成する自由モノイド Σ^∗ 上の基本関係の集合を特定することによって決まる。任意のモノイドは、適当な自由モノイド Σ^∗ をその上のモノイド合同で割って得られる商モノイドになっていると言っても同じである。

実際、二項関係 R⊂ Σ^∗ × Σ^∗ が与えられたとき、R の対称閉包 R∪ R⁻¹ を

$(x,y)\in E\iff \exists u,\exists v,\exists s,\exists t\in \Sigma ^{*}{\text{ s.t. }}x=sut\land y=svt\land (u,v)\in R\cup R^{-1}$$(x,y)\in E\iff \exists u,\exists v,\exists s,\exists t\in \Sigma ^{*}{\text{ s.t. }}x=sut\land y=svt\land (u,v)\in R\cup R^{-1}$
で定義される対称的関係 E⊂ Σ^∗ × Σ^∗ に拡張できる。この Eは

(x, y) ∈ Eかつ (x′, y′) ∈ Eならば (xx′, yy′) ∈ E

をみたし、さらに反射閉包および推移閉包をとることにより、モノイド合同が得られる。

典型的な状況では、関係 Rは単に関係式の集合 R= {u₁ = v₁, ..., u_n= v_n} として与えられ、例えば

$\langle p,q\mid pq=1\rangle$$\langle p,q\mid pq=1\rangle$
は双巡回モノイドの生成元と基本関係式による表示であり、また

$\langle a,b\mid aba=baa,bba=bab\rangle$$\langle a,b\mid aba=baa,bba=bab\rangle$
は次数2のプラクティックモノイドとなる︵位数は無限大である︶。基本関係式は baが aおよび bとそれぞれ可換になることを示すものとみることができるので、このプラクティックモノイドの任意の元は適当な整数 i, j, kを用いて aⁱb^j(ba)^k の形に表される。

圏論との関係

モノイドは圏の特別なクラスと看做すことができる。実際、モノイドにおいて二項演算に課される公理は、圏において︵与えられたただ一つの対象を始域および終域とする射の集合だけで考えれば︶射の合成に課される公理と同じである。すなわち、

モノイドはただひとつの対象をもつ圏︵単一対象圏︶と本質的に同じものである。

もっとはっきり述べれば、モノイド (M, •) はただひとつの対象をもち、M の元を射として小さい圏を成す︵射の合成はモノイド演算 • で与えられる︶。

これと平行して、モノイド準同型は単一対象圏の間の函手とみなされる。ゆえに、今考えている圏の構成は︵小さい︶モノイドの圏 Mon と︵小さい︶圏の圏 Cat のある充満部分圏との間の圏同値を与えるものになっている。同様に、︵小さい︶群の圏は、Cat の︵モノイドの圏とは別の︶ある充満部分圏に同値である。

この意味では、圏論をモノイドの概念の一般化であると考えることができ、モノイドに関する定義や定理の多くを︵ひとつまたはそれ以上の対象を持つ︶小さい圏に対して一般化することができる。例えば、単一対象圏の商圏とは、剰余モノイドのことである。

モノイドの全体は︵他の代数的構造がそうであるのと同様に︶、モノイドを対象としモノイド準同型を射とする圏 Mon を成す。

また、抽象的な定義によって、各圏における﹁モノイド﹂としてモノイド対象の概念が定まる。通常のモノイドは︵小さい︶集合の圏 Set におけるモノイド対象である。

計算機科学におけるモノイド

「高階関数」も参照

計算機科学において、多くの抽象データ型はモノイド構造を持つ。よくあるパターンとして、モノイド構造を持つデータ型の元の列を考えよう。この列に対して ﹁重畳﹂(fold) あるいは﹁堆積﹂(accumulate) の操作を施すことで、列が含む元の総和のような値が取り出される。例えば、多くの反復アルゴリズムは各反復段階である種の﹁累計﹂を更新していく必要があるが、モノイド演算の重畳を使うとこの累計をすっきりと表記できる。別の例として、モノイド演算の結合性は、多コアや多CPUを効果的に利用するために、prefix sumあるいは同様のアルゴリズムによって、計算を並列化できることを保証する。

単位元 ε と演算 • を持つモノイド Mに対して、その列の型 M^* から Mへの重畳関数 fold は次のように定義される。

$\operatorname {fold} \colon M^{*}\to M$$\operatorname {fold} \colon M^{*}\to M$
$\operatorname {fold} \,l={\begin{cases}\varepsilon &{\text{if }}l=\operatorname {nil} \\m\bullet \operatorname {fold} \,l'&{\text{if }}l=\operatorname {cons} \,m\,l'\end{cases}}$$\operatorname {fold} \,l={\begin{cases}\varepsilon &{\text{if }}l=\operatorname {nil} \\m\bullet \operatorname {fold} \,l'&{\text{if }}l=\operatorname {cons} \,m\,l'\end{cases}}$
更に、任意のデータ型でもその元の直列化演算(serialization)が与えられれば同様に﹁重畳﹂することができる。例えば、二分木においては木の走査が直列化にあたるが、結果は走査が行きがけか帰りがけかによって異なる。

単純な構造化プログラミング言語自身は文やブロックの連接を演算としてモノイドをなす。

関連項目

• モノイド圏
• モナド (圏論)
• クリーネ閉包の高さ最小化問題
• クリーネ代数
• 一元体: 定式化に吸収元つきモノイドが利用される
• フロベニオイド

参考文献

• John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
• Jacobson, Nathan (1951), Lectures in Abstract Algebra, I, D. Van Nostrand Company, ISBN 0-387-90122-1 
• Jacobson, Nathan (2009), Basic algebra, 1 (2nd ed.), Dover, ISBN 978-0-486-47189-1 
• M. Kilp, U. Knauer, A.V. Mikhalev, Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000, ISBN 3110152487.
• 田村孝行『半群論』（復刊）、共立出版、2001年（原著1972年）。ISBN 9784320016767。 

外部リンク

• Weisstein, Eric W. "Monoid". mathworld.wolfram.com (英語).
• Monoid - PlanetMath.（英語）