モノイド

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

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

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

1. 定義
-----

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

結合律: S}} の任意の元 a, b, c}} に対して、 単位元の存在: S}} の元 e}} が存在して、S}} の任意の元 a}} に対して 1=//e// • //a// = //a// • //e// = //a//.}}を満たすならば、組 }} をモノイドという。まぎれの虞のない場合、対 }} あるいは単に S}} のみでも表す。 二項演算の結果 //a// • //b//}} を a}} と b}} の積用語を流用しているだけで積の項で扱われている意味での「積」とは無関係であることに注意。特にここでいう「積」は和を繰り返したものの意味ではないので、和が定義されている必要も無い。}}と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、群が得られる。逆に任意の群はモノイドである。

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

2. モノイドの構造
----------

2.1. 部分モノイド
-----------

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

2.2. モノイドの生成
------------

部分集合 S}} がモノイド M}} の生成系 en であるとは M}} の任意の元が S}} の元だけから二項演算を繰り返して得られることをいう。モノイド M}} がその部分集合 S}} で生成されるとき 1=//M// = angbr などと書く。

M}} の各元 x}} に対し 1=//x//sup を M}} の単位元とする規約を設けるならば、angbr における S}} の元の冪が零となることも許し、angbr は S}} を含む最小の部分モノイドを表すそのような規約を入れない場合は、math。

M}} が有限個の元からなる生成系をもつとき、有限生成 en あるいは有限型 en であるという。特に、M}} のただ一つの元 f}} で生成されるモノイド angbr は単項生成モノイドあるいは巡回モノイド en と呼び、集合としては f}} の冪全体の成す集合 mset に一致する。

2.3. 可換モノイド
-----------

演算が可換であるようなモノイドは、可換モノイド }} という。可換モノイドはしばしば二項演算の記号を "+" として加法的に書かれる。任意の可換モノイド M}} は

として定まる代数的前順序 "≤}}" を持つ。可換モノイド M}} の順序単位 en //u// ∈ //M//}} とは、M}} の各元 x}} に対して適当な正の整数 n}} をとれば //x// ≤ //nu//}} とできるようなものをいう。これは M}} が半順序可換群 G}} の正錐である場合にもよく用いられ、この場合には u}} を G}} の順序単位と呼ぶ。

2.4. 部分可換モノイド
-------------

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

3. 例
----

任意の一元集合 mset は 1=//x// • //x// = //x//}} と置くことによりモノイドとなる。これを自明なモノイドという。
任意の単位的環の元の全体は、加法あるいは乗法に関してそれぞれモノイドを成す。
整数全体、有理数全体、実数全体、複素数全体は加法あるいは乗法に関してそれぞれモノイドを成すJacobson。
与えられた環に係数を持つ n}}-次正方行列の全体は行列の加法または行列の乗法に関してモノイドを成す。
任意の有界半束は冪等可換モノイドである。
特に、任意の有界束は交わりについても結びについてもモノイドとなる。したがって、束であるハイティンク代数やブール代数はそのようなモノイド構造を持つ。
自然数の全体 Nsub は加法に関して 0}} を単位元とするモノイドを成し、また乗法に関して 1}} を単位元とするモノイドを成す。Nsub の加法に関する部分モノイドは自然数半群 en と呼ばれる。Nsub の 0}} 以外の元からなる部分集合 N}} は乗法に関して 1}} を単位元とする部分モノイドを成す。
閉曲面の同相類の全体は連結和 "#" に関して可換モノイドを成す。単位元は通常の球面の属する同相類である。さらにいえば、トーラスの属する同相類 //a// と射影平面の属する同相類 //b// に対して、このモノイドの任意の元 //c// は //c// = //na// # //mb// の形に一意的に表される。ここで //n// は非負の整数で、//m// は 0, 1, 2 の何れかである。
集合 S}} 上の自己写像//S// → //S//}} 全体の成す集合は、恒等写像を単位元とし写像の合成をモノイド演算としてモノイドになる。これを S}} 上の全変換モノイド  と呼ぶ。S}} が有限であることと S}} 上の全変換モノイドが有限であることは同値である。

4. モノイドの構成法
-----------

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

4.1. 自由モノイド
-----------

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

4.2. 1-添加
---------

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

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

4.3. 逆転モノイド
-----------

任意のモノイド }} に対し、その反モノイド en }} とは、台集合と単位元は M}} と同じものとし、その演算を

と定めて得られるモノイドである。任意の可換モノイドは自分自身を反モノイドとして持つ。

4.4. 直積モノイド
-----------

二つのモノイド M, N}} に対して、それらの直積集合 //M// × //N//}}もまたモノイドとなる。モノイド演算および単位元は、成分ごとの積および成分ごとの単位元の組として与えられるJacobson。

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

4.5. 商モノイド
----------

モノイド (//M//, •, 1sub 上の合同関係∼}} とは、モノイド構造と両立する同値関係を言う。モノイド M}} のモノイド合同 ∼}} による剰余モノイドあるいは商モノイドは、各元 //x// ∈ //M//}} の属する同値類を [//x//]}} と書くとき、商集合 //M///∼}} に

で定まるモノイド演算を入れて得られるモノイド (//M///∼, ∘, [1sub を言う。

4.6. 冪集合モノイド
------------

モノイド }} を固定して、M}} の冪集合 //P//}} を考える。//P//}} の 部分集合 の間の二項演算 "∗}}" を

で定めれば、//P//}} は自明モノイド mset を単位元とするモノイドとなる。同じ方法で、群 G}} の冪集合は群の部分集合の積に関するモノイドとなる。

5. 性質
-----

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

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

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

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

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

//M// の任意の元 //a//, //b//, //c// に対し、//a// • //b// = //a// • //c// が成り立つならば、常に //b// = //c// を帰結することができるという条件を満たすときにいう。消約的可換モノイドは常にグロタンディーク構成によって群に埋め込むことができる。これは、整数全体の成す加法群を自然数全体の成す加法モノイドから構成する方法の一般化である。しかし、非可換消約的モノイドは必ずしも群に埋め込み可能でない。

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

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

と表すことができ、モノイドの積と置換の積が対応する。モノイドの右消約元の全体あるいは左消約元の全体は部分モノイドを成す。これは、任意の可換モノイドの消約元の全体はかならず群に延長することができるということを意味している。

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

//a// = //a// • //a//−1 • //a// かつ //a//−1 = //a//−1 • //a// • //a//−1となる //M// の元 //a//−1 をただひとつ持つとき、//M// を逆モノイド en あるいは山田モノイドという半群として、逆半群となるようなモノイドということ。逆半群は山田半群とも言われるharv。逆モノイドが消約的ならばそれは群を成す。

6. モノイド作用と作用素モノイド
-----------------

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

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

7. モノイド準同型
----------

ふたつのモノイド ,  の間のモノイド準同型 en とは、写像 //f//: //M// → //M//′ であって、

//M// の任意の元 //x//, //y// に対して //f// = //f// •′ //f//,
//f// = //e//′を満たすものをいう。ここで、//e// および //e//′ はそれぞれ //M// および //M//′ の単位元である。モノイド準同型は簡単にモノイド射 en と呼ばれることもある。

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

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

8. 生成元と基本関係
-----------

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

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

で定義される対称的関係 //E// ⊂ Σ∗ × Σ∗ に拡張できる。この //E// は

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

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

は双巡回モノイドの生成元と基本関係式による表示であり、また

は次数 2 のプラクティックモノイドとなる。基本関係式は //ba// が //a// および //b// とそれぞれ可換になることを示すものとみることができるので、このプラクティックモノイドの任意の元は適当な整数 //i//, //j//, //k// を用いて //a////i////b////j////k// の形に表される。

9. 圏論との関係
---------

モノイドは圏の特別なクラスと看做すことができる。実際、モノイドにおいて二項演算に課される公理は、圏において射の合成に課される公理と同じである。すなわち、

モノイドはただひとつの対象をもつ圏と本質的に同じものである。もっとはっきり述べれば、モノイド  はただひとつの対象をもち、//M// の元を射として小さい圏を成す。

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

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

モノイドの全体は、モノイドを対象としモノイド準同型を射とする圏 Mon を成す。

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

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

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

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

更に、任意のデータ型でもその元の直列化演算が与えられれば同様に「重畳」することができる。例えば、二分木においては木の走査が直列化にあたるが、結果は走査が行きがけか帰りがけかによって異なる。

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

11. 関連項目
--------

モノイド圏
モナド 
一元体: 定式化に吸収元つきモノイドが利用される
フロベニオイド

12. 注
-----

12.1. 注釈
--------

12.2. 出典
--------

13. 参考文献
--------

John M. Howie, //Fundamentals of Semigroup Theory// , Clarendon Press, Oxford ISBN 0-19-851194-9
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.

14. 外部リンク
---------