モノイドのソースを表示

{{about||一般の圏におけるモノイド|モノイド対象}}
[[数学]]、とくに[[抽象代数学]]における'''単系'''（たんけい、{{lang-en-short|''monoid''}}; '''モノイド'''）はひとつの[[二項演算]]と[[単位元]]をもつ[[代数的構造]]である。モノイドは単位元をもつ[[半群]]（'''単位的半群'''）であるので、半群論の研究対象の範疇に属する。

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

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

== 定義 ==
[[集合]] {{mvar|S}} とその上の[[二項演算]] {{math|&bull;: ''S'' × ''S'' → ''S''}} が与えられ、以下の条件
; [[結合法則|結合律]]: {{mvar|S}} の任意の元 {{mvar|a, b, c}} に対して、{{math|1=(''a'' &bull; ''b'') &bull; ''c'' = ''a'' &bull; (''b'' &bull; ''c'').}}
; [[単位元]]の存在: {{mvar|S}} の元 {{mvar|e}} が存在して、{{mvar|S}} の任意の元 {{mvar|a}} に対して {{math|1=''e'' &bull; ''a'' = ''a'' &bull; ''e'' = ''a''.}} 
を満たすならば、組 {{math|(''S'', &bull;, ''e'')}} を'''モノイド'''という。まぎれの虞のない場合、対 {{math|(''S'', &bull;)}} あるいは単に {{mvar|S}} のみでも表す。
二項演算の結果 {{mvar|''a'' &bull; ''b''}} を {{mvar|a}} と {{mvar|b}} の'''積'''{{efn|用語を流用しているだけで[[積]]の項で扱われている意味での「積」とは無関係であることに注意。特にここでいう「積」は和を繰り返したもの（反復和）の意味ではないので、和が定義されている必要も無い。}}と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の[[逆元|可逆性]]を課せば、[[群 (数学)|群]]が得られる。逆に任意の群はモノイドである。

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

== モノイドの構造 ==
=== 部分モノイド ===
モノイド {{mvar|M}} の部分集合 {{mvar|N}} が {{mvar|M}} の'''部分モノイド''' {{lang|en|(''submonoid'')}} とは、{{mvar|M}} の単位元を含み、[[閉性|閉性質]]: {{math|''x'', ''y'' &isin; ''N''}} ならば {{math|''xy'' &isin; ''N''}} となるようなものをいう。これは {{mvar|M}} のモノイド演算の制限 {{math|&bull;{{!}}{{sub|''N''}}: ''N'' × ''N'' → ''M''}} の像が {{math|im(&bull;{{!}}{{sub|''N''}}) &sub; ''N''}} を満たすということであり、従って {{math|&bull;{{!}}{{sub|''N''}}}} は {{mvar|N}} 上の二項演算を定め、部分モノイド {{mvar|N}} は明らかにそれ自身が一つのモノイドとなる。

=== モノイドの生成 ===
部分集合 {{mvar|S}} がモノイド {{mvar|M}} の'''生成系''' {{lang|en|(''generator'')}} であるとは {{mvar|M}} の任意の元が {{mvar|S}} の元だけから二項演算を繰り返して得られることをいう（生成系に属する元を生成元という）。モノイド {{mvar|M}} がその部分集合 {{mvar|S}} で生成されるとき {{math|1=''M'' = {{angbr|''S''}}}} などと書く。
: <math>\lang S\rang = \{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\}.</math>
{{mvar|M}} の各元 {{mvar|x}} に対し {{math|1=''x''{{sup|0}} = 1{{sub|M}}}} を {{mvar|M}} の単位元とする規約を設けるならば、{{math|{{angbr|''S''}}}} における {{mvar|S}} の元の冪が零となることも許し、{{math|{{angbr|''S''}}}} は {{mvar|S}} を含む最小の部分モノイドを表す{{efn|そのような規約を入れない場合は、{{math|{{angbr|''S''}}}} が単位元を含むとは限らず、一般には部分モノイドとならないから、文脈には注意すべきである。}}。

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

=== 可換モノイド ===
演算が[[交換法則|可換]]であるようなモノイドは、'''可換モノイド''' {{en|(''commutative monoid'')}} という（稀に'''アーベルモノイド''' {{en|(''abelian monoid'')}} ともいう）。可換モノイドはしばしば二項演算の記号を "+" として加法的に書かれる。任意の可換モノイド {{mvar|M}} は
: <math>x\le y \iff x+z = y\quad \exist z\in M</math>
として定まる'''代数的'''[[前順序]] "{{math|&le;}}" を持つ。可換モノイド {{mvar|M}} の'''順序単位''' {{lang|en|(''order-unit'')}} {{math|''u'' ∈ ''M''}} とは、{{mvar|M}} の各元 {{mvar|x}} に対して適当な正の整数 {{mvar|n}} をとれば {{math|''x'' &le; ''nu''}} (右辺は {{mvar|n}} 個の {{mvar|u}} の和を表す)とできるようなものをいう。これは {{mvar|M}} が[[順序群|半順序可換群]] {{mvar|G}} の正錐である場合にもよく用いられ、この場合には {{mvar|u}} を {{mvar|G}} の順序単位と呼ぶ。

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

== 例 ==
* 任意の[[一元集合]] {{math|{{mset|''x''}}}} は {{math|1=''x'' &bull; ''x'' = ''x''}} と置くことによりモノイドとなる。これを'''自明なモノイド'''という。
* 任意の[[単位的環]]の元の全体は、加法あるいは乗法に関してそれぞれモノイドを成す。
** [[整数]]全体、[[有理数]]全体、[[実数]]全体、[[複素数]]全体は加法あるいは乗法に関してそれぞれモノイドを成す{{sfn|Jacobson|2009|p=29|loc=examples 1, 2, 4 & 5}}。
** 与えられた環に係数を持つ {{mvar|n}}-次[[正方行列]]の全体は行列の加法または行列の乗法に関してモノイドを成す。
* 任意の有界[[半束]]は[[冪等]]可換モノイドである。
** 特に、任意の有界[[束論|束]]は交わりについても結びについてもモノイドとなる（モノイドの単位元はそれぞれ束の最大元および最小元で与えられる）。したがって、束である[[ハイティンク代数]]や[[ブール代数]]はそのようなモノイド構造を持つ。
* （{{math|0}} を含む）[[自然数]]の全体 {{math|'''N'''{{sub|0}}}} は加法に関して {{math|[[0]]}} を単位元とするモノイドを成し、また乗法に関して {{math|[[1]]}} を単位元とするモノイドを成す。{{math|'''N'''{{sub|0}}}} の加法に関する部分モノイドは{{仮リンク|自然数半群|label=自然数モノイド|en|Numerical semigroup}} {{lang|en|(numerical monoid)}} と呼ばれる。{{math|'''N'''{{sub|0}}}} の {{math|0}} 以外の元（[[正の整数]]）からなる部分集合 {{math|'''N'''}} は乗法に関して {{math|1}} を単位元とする部分モノイドを成す。
* [[曲面|閉曲面]]の[[同相]][[同値類|類]]の全体は[[曲面#曲面の連結和|連結和]] "#" に関して可換モノイドを成す。単位元は通常の球面（2-球面）の属する同相類である。さらにいえば、トーラスの属する同相類 ''a'' と射影平面の属する同相類 ''b'' に対して、このモノイドの任意の元 ''c'' は ''c'' = ''na'' # ''mb'' の形に一意的に表される。ここで ''n'' は非負の整数で、''m'' は 0, 1, 2 の何れか（実は 3''b'' = ''a'' # ''b'' が成り立つ）である。
* 集合 {{mvar|S}} 上の自己写像（[[変換 (数学)|変換]]）{{math|''S'' → ''S''}} 全体の成す集合は、[[恒等写像]]を単位元とし[[写像の合成]]をモノイド演算としてモノイドになる。これを {{mvar|S}} 上の'''全変換モノイド''' (''full transformation monoid'') と呼ぶ。{{mvar|S}} が有限であることと {{mvar|S}} 上の全変換モノイドが有限であることは同値である。

== モノイドの構成法 ==
与えられた代数系をモノイドにする操作や、既知のモノイドから新たなモノイドを作り出す操作がいくつか存在する。
=== 自由モノイド ===
固定された字母集合 {{math|&Sigma;}} 上の有限[[文字列]]全体(空文字列を含む)は、[[文字列結合|連接]]を二項演算とし単位元を[[空文字列]]としてモノイドとなる。このモノイドを {{math|&Sigma;*}} で表す{{efn|与えられたモノイドの元からなる[[文字集合]] {{mvar|N}} から有限文字列全体を取り出す操作（ただし連接をモノイドの積で置き換える）を、その文字集合 {{mvar|N}} の生成する[[クリーネ閉包]] {{mvar|N*}} と呼び、"{{math|&lowast;}}" で表すためクリーネスターとも呼ばれる。ただし、クリーネ閉包構成は一般には（もともと）[[形式言語]]の範疇で考えられるもっと広い概念である。}}と、これは {{math|&Sigma;}} を生成系としてもち、公理の等式以外に元の間の関係式をもたないので {{math|&Sigma;}} 上の'''自由モノイド'''と呼ぶ。{{仮リンク|自由モノイド|en|Free monoid}}は[[モノイドの圏]] {{math|'''Mon'''}} における{{仮リンク|自由対象|en|free object}}であり、その普遍性は[[#表示|モノイドの表示]]として理解することができる（後述）。

=== 1-添加 ===
任意の[[半群]] {{mvar|S}} は、{{mvar|S}} に属さない新たな元 {{mvar|e}} を（新たな）単位元として添加してモノイドにすることができる。すなわち、{{math|''S{{sup|e}}'' {{coloneqq}} ''S'' &cup; {{mset|''e''}}}} とし、{{mvar|S}} の任意の元 {{mvar|s}} に対して {{math|1=''e'' &bull; ''s'' = ''s'' = ''s'' &bull; ''e''}} と定めるとき {{mvar|S{{sup|e}}}} はモノイドである。

{{mvar|S}} 上の{{仮リンク|零半群|label=左零半群|en|Null semigroup}}に単位元 {{mvar|e}} を添加したものは（''find-first'' としても知られる）冪等モノイドであり、{{mvar|S}} 上の右零半群に単位元 {{mvar|e}} を添加したものは（''find-last'' とも呼ばれる）反モノイドとなる。
二つの元 {{math|{{mset|&lt;, &gt;}}}} を持つ左零半群に単位元 "{{math|{{=}}}}" を添加して得られる冪等モノイド {{math|{{mset|&lt;, {{=}}, &gt;}}}} は[[順序集合|順序の与えられた集合]]の元の列に対する[[辞書式順序]]のモデルを与える。

=== 逆転モノイド ===
任意のモノイド {{math|(''M'', &bull;)}} に対し、その'''反モノイド''' {{lang|en|(''opposite monoid'')}} {{math|(''M''<sup>op</sup>, &bull;<sup>op</sup>)}} とは、台集合と単位元は {{mvar|M}} と同じものとし、その演算を
: <math>x \stackrel{\text{op}}{{}\bullet{}} y := y \bullet x</math>
と定めて得られるモノイドである（逆モノイド{{efn|この名称は、逆半群 (inverse semi-group) であるようなモノイドとややこしい}}、逆転モノイド、反対モノイドなどともいう）。任意の[[#可換モノイド|可換モノイド]]は自分自身を反モノイドとして持つ。

=== 直積モノイド ===
二つのモノイド {{mvar|M, N}} に対して（より一般に、有限個のモノイド {{math|''M''{{sub|1}}, …, ''M{{sub|k}}''}} に対して、あるいは無限族 {{math|{{mset|''M{{sub|i}}''}}{{sub|''i''∈''I''}}}} に対して）、それらの[[直積集合]] {{math|''M'' &times; ''N''}}（あるいは {{math|''M''{{sub|1}} &times; ⋯ &times; ''M{{sub|k}}''}}, {{math|&prod;{{sub|''i''∈''I''}} ''M{{sub|i}}''}}）もまたモノイドとなる。モノイド演算および単位元は、[[成分ごと]]の積および成分ごとの単位元の組として与えられる{{sfn|Jacobson|2009|p=35}}。

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

=== 商モノイド ===
モノイド {{math|(''M'', &bull;, 1{{sub|''M''}})}} 上の[[合同関係]]（モノイド合同）{{math|&sim;}} とは、モノイド構造と両立する（すなわち、{{math|''a'' &sim; ''b''}} かつ {{math|''c'' &sim; ''d''}} ならば {{math|''ac'' &sim; ''bd''}} を満たす）[[同値関係]]を言う。モノイド {{mvar|M}} のモノイド合同 {{math|&sim;}} による剰余モノイドあるいは商モノイドは、各元 {{math|''x'' &isin; ''M''}} の属する同値類を {{math|[''x'']}} と書くとき、商集合 {{math|''M''/&sim;}} に
: <math>[x]\circ [y] := [xy]</math>
で定まるモノイド演算を入れて得られるモノイド {{math|(''M''/&sim;, ∘, [1{{sub|''M''}}])}} を言う。

=== 冪集合モノイド ===
モノイド {{math|(''M'', &bull;)}} を固定して、{{mvar|M}} の[[冪集合]] {{math|''P''(''M'')}} を考える。{{math|''P''(''M'')}} の [[部分集合]] <math>S, T</math> の間の二項演算 "{{math|&lowast;}}" を
: <math>S * T := \{s\bullet t \mid  s \in S, t \in T\}</math>
で定めれば、{{math|''P''(''M'')}} は自明モノイド {{math|{{mset|''e''}}}} を単位元とするモノイドとなる。同じ方法で、群 {{mvar|G}} の冪集合は{{仮リンク|群の部分集合の積|en|Product of group subsets}}に関するモノイドとなる。

== 性質 ==
モノイドにおいて、元 ''x'' の自然数冪を
* ''x''<sup>1</sup> := ''x'', 
* ''x''<sup>''n''</sup> := ''x'' &bull; &hellip; &bull; ''x'' （''n'' 個の ''x'' の積、''n'' &gt; 1） 
と定義することができる。このとき、[[指数法則]] ''x''<sup>''n''+''p''</sup> = ''x''<sup>''n''</sup> &bull; ''x''<sup>''p''</sup> の成立は明らかである。定義から直接従うこととして、単位元 ''e'' が一意に存在するので、任意の ''x'' に対して ''x''<sup>0</sup> := ''e'' と定義すると、指数法則は任意の非負整数冪に対してなお有効である。

モノイドにおいては、[[可逆元]]（あるいは[[単元 (代数学)|単元]]）の概念を定義することができる。モノイドの元 ''x'' が可逆であるとは  ''xy'' = ''e'' かつ ''yx'' = ''e'' を満たす元 ''y'' が存在するときにいう。''y'' は ''x'' の[[逆元]]と呼ばれる。''y'' および ''z'' が ''x'' の逆元ならば、結合律により ''y'' = (''zx'')''y'' = ''z''(''xy'') = ''z'' となるから、逆元は存在すればただひとつである<ref>Jacobson, I.5. p. 22</ref>。

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

しかしながら、任意のモノイドが必ず何らかの群に含まれるとは限らない。例えば、''b'' が単位元ではない場合にも ''a'' &bull; ''b'' = ''a'' を満たすような二つの元 ''a'', ''b'' をとることができるモノイドというものを矛盾なく考えることができるが、このようなモノイドを群に埋め込むことはできない。なぜなら、埋め込んだ群において必ず存在する ''a'' の逆元を両辺に掛けることにより ''b'' = ''e'' が導かれ、''b'' が単位元でないことに矛盾するからである。モノイド (''M'', &bull;) が[[簡約法則|'''消約律''']] {{lang|en|(''cancellation property'')}} を満たす、あるいは'''消約的''' {{lang|en|(''cancellative'')}} であるとは
: ''M'' の任意の元 ''a'', ''b'', ''c'' に対し、''a'' &bull; ''b'' = ''a'' &bull; ''c'' が成り立つならば、常に ''b'' = ''c'' を帰結することができる
という条件を満たすときにいう。消約的可換モノイドは常に[[グロタンディーク構成]]によって群に埋め込むことができる。これは、整数全体の成す加法群（加法演算 "+" に関する群）を自然数全体の成す加法モノイド（加法演算 "+" に関する消約的可換モノイド）から構成する方法の一般化である。しかし、非可換消約的モノイドは必ずしも群に埋め込み可能でない。

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

巡回モノイドの位数が有限な ''n'' であるとき、0 &le; ''k'' &le; ''n'' &minus; 1 をみたす適当な ''k'' に対して ''f''<sup>''n''</sup> = ''f''<sup>''k''</sup> が成り立つ。実は、そのような ''k'' を定めるごとに位数 ''n'' の相異なるモノイドが得られ、逆に任意の巡回モノイドはそれらのモノイドのうちの何れか一つに同型となる。特に ''k'' = 0 の場合は、全ての ''f'' <sup>''i''</sup> が逆元を持ち、（ただひとつの位数 ''n'' の）[[巡回群]]を定める。このとき ''f'' は[[対称群#巡回置換|巡回置換]]として<div style="margin: 1ex auto 1ex 2em"><math>
\begin{pmatrix}
 0 & 1 & 2 & ... & n-2 & n-1 \\
 1 & 2 & 3 & ... & n-1 & k
\end{pmatrix}
</math></div>と表すことができ、モノイドの積と[[写像の合成|置換の積]]が対応する。

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

モノイド ''M'' は、''M'' の各元 ''a'' がそれぞれ
: ''a'' = ''a'' &bull; ''a''<sup>&minus;1</sup> &bull; ''a'' かつ ''a''<sup>&minus;1</sup> = ''a''<sup>&minus;1</sup> &bull; ''a'' &bull; ''a''<sup>&minus;1</sup>
となる ''M'' の元 ''a''<sup>&minus;1</sup> をただひとつ持つとき、''M'' を'''逆モノイド''' {{lang|en|(''inverse monoid'')}} あるいは山田モノイドという{{efn|半群として、[[逆半群]]となるようなモノイドということ。逆半群は山田半群とも言われる{{harv|田村|1972}}。}}。逆モノイドが消約的ならばそれは群を成す。

== モノイド作用と作用素モノイド ==
(''M'', &bull;) をモノイドとする。集合 ''X'' への（左）''M''-'''作用''' {{lang|en|(''M''-''act'')}} あるいは ''M'' による左作用とは、集合 ''X'' と外部演算 .: ''M'' &times; ''X'' &rarr; ''X'' の組で、外部演算 "." が
* ''X'' の任意の元 ''x'' に対して、 ''e''.''x'' = ''x'' が成り立つ。
* ''M'' の任意の元 ''a'', ''b'' と ''X'' の任意の元 ''x'' に対して、''a''.(''b''.''x'') = (''a'' &bull; ''b'').''x'' が成り立つ。
という二つの条件を満たす（ただし ''e'' は ''M'' の単位元）という意味でモノイド構造と両立することをいう。これは[[作用 (数学)|群作用]]のモノイド論における類似物である。右 ''M''-作用も同様に定義される。ある作用に関するモノイドは'''作用素モノイド'''とも呼ばれる。重要な例として、[[オートマトン]]に現れる[[状態遷移系]]が挙げられる。ある集合上の自分自身への写像から成る半群(変換半群)は、恒等変換を付け加えることで作用素モノイドにすることができる。

== モノイド準同型 ==
ふたつのモノイド (''M'', &bull;), (''M''&prime;, &bull;&prime;) の間の'''モノイド準同型''' {{lang|en|(''monoid homomorphism'')}} とは、写像 ''f'': ''M'' &rarr; ''M''&prime; であって、
* ''M'' の任意の元 ''x'', ''y'' に対して ''f''(''x'' &bull; ''y'') = ''f''(''x'') &bull;&prime; ''f''(''y''),
* ''f''(''e'') = ''e''&prime;
を満たすものをいう。ここで、''e'' および ''e''&prime; はそれぞれ ''M'' および ''M''&prime; の単位元である。モノイド準同型は簡単に'''モノイド射''' {{lang|en|(''monoid morphisms'')}} と呼ばれることもある。

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

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

== 生成元と基本関係 ==
モノイドは、群が[[群の表示|生成系と基本関係による表示]]によって特定できるというのと同じ意味で、'''{{visible anchor|表示}}''' {{lang|en|(''presentation'')}} を持つ。すなわち、モノイドは[[生成 (数学)|生成系]] &Sigma; と &Sigma; が生成する[[#自由モノイド|自由モノイド]] &Sigma;<sup>&lowast;</sup> 上の基本関係の集合を特定することによって決まる。任意のモノイドは、適当な自由モノイド &Sigma;<sup>&lowast;</sup> をその上のモノイド合同で割って得られる商モノイドになっていると言っても同じである。

実際、二項関係 ''R'' &sub; &Sigma;<sup>&lowast;</sup> &times; &Sigma;<sup>&lowast;</sup> が与えられたとき、''R'' の対称閉包 ''R'' &cup; ''R''<sup>&minus;1</sup> を
:<math>(x,y)\in E \iff \exist u,\exist v,\exist s,\exist t \in \Sigma^* \text{ s.t. } x = sut\land y = svt \land (u, v) \in R \cup R^{-1}</math>
で定義される対称的関係  ''E'' &sub; &Sigma;<sup>&lowast;</sup> &times; &Sigma;<sup>&lowast;</sup> に拡張できる。この ''E'' は
: (''x'', ''y'') &isin; ''E'' かつ (''x''&prime;, ''y''&prime;) &isin; ''E'' ならば (''xx''&prime;, ''yy''&prime;) &isin; ''E'' 
をみたし、さらに反射閉包および推移閉包をとることにより、モノイド合同が得られる。

典型的な状況では、関係 ''R'' は単に関係式の集合 ''R'' = {''u''<sub>1</sub> = ''v''<sub>1</sub>, ..., ''u''<sub>''n''</sub> = ''v''<sub>''n''</sub>} として与えられ、例えば
:<math>\langle p,q \mid pq=1\rangle</math>
は{{仮リンク|双巡回モノイド|en|bicyclic monoid}}の生成元と基本関係式による表示であり、また
:<math>\langle a,b \mid aba=baa, bba=bab\rangle</math>
は次数 2 の{{仮リンク|プラクティックモノイド|en|plactic monoid}}となる（位数は無限大である）。基本関係式は ''ba'' が ''a'' および ''b'' とそれぞれ可換になることを示すものとみることができるので、このプラクティックモノイドの任意の元は適当な整数 ''i'', ''j'', ''k'' を用いて ''a''<sup>''i''</sup>''b''<sup>''j''</sup>(''ba'')<sup>''k''</sup> の形に表される。

== 圏論との関係 ==
モノイドは[[圏 (数学)|圏]]の特別なクラスと看做すことができる。実際、モノイドにおいて二項演算に課される公理は、圏において（与えられたただ一つの対象を始域および終域とする射の集合だけで考えれば）[[射 (圏論)|射]]の合成に課される公理と同じである。すなわち、
: モノイドはただひとつの対象をもつ圏（単一対象圏）と本質的に同じものである。
もっとはっきり述べれば、モノイド (''M'', &bull;) はただひとつの対象をもち、''M'' の元を射として[[小さい圏]]を成す（射の合成はモノイド演算 &bull; で与えられる）。

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

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

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

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

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

単位元 &epsilon; と演算 &bull; を持つモノイド ''M'' に対して、その列の型 ''M<sup>*</sup>'' から ''M'' への重畳関数 ''fold'' は次のように定義される。
:<math>\operatorname{fold}\colon M^{*} \to M</math>
:<math>\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}</math>

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

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

== 関連項目 ==
* [[モノイド圏]]
* [[モナド (圏論)]]
* {{仮リンク|クリーネ閉包の高さ最小化問題|en|Star height problem}}
* {{仮リンク|クリーネ代数|en|Kleene algebra}}
* [[一元体]]: 定式化に吸収元つきモノイドが利用される
* {{仮リンク|フロベニオイド|en|Frobenioid}}

== 注 ==
=== 注釈 ===
{{reflist|group="注釈"}}
=== 出典 ===
{{reflist}}
== 参考文献 ==
* John M. Howie, ''Fundamentals of Semigroup Theory'' (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
* {{citation | last=Jacobson | first=Nathan | author-link=Nathan Jacobson | title=Lectures in Abstract Algebra | volume=I | publisher=D. Van Nostrand Company | date=1951 | isbn=0-387-90122-1}}
* {{Citation| last=Jacobson| first=Nathan| author-link=Nathan Jacobson| date=2009| title=Basic algebra| edition=2nd| volume = 1 | series= | publisher=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.
* {{cite book|和書|author=田村孝行|title=半群論|publisher=共立出版|year=2001|origyear=1972|others=（復刊）|isbn=9784320016767}}

== 外部リンク ==
* {{MathWorld | urlname=Monoid | title=Monoid}}
* {{PlanetMath| urlname=Monoid | title=Monoid | id=389}}

{{DEFAULTSORT:ものいと}}
[[Category:半群論]]
[[Category:数学的構造]]
[[Category:代数的構造]]
[[Category:圏論]]
[[Category:数学に関する記事]]