モノイド

数学の一分野である抽象代数学において、モノイドは結合二項演算と単位元を備えた集合である。例えば、加算された非負整数はモノイドを形成し、単位元は0である。

モノイドは単位元を持つ半群です。このような代数構造は数学のいくつかの分野で発生します。

集合からそれ自身への関数は、関数合成に関してモノイドを形成します。より一般的には、圏論では、オブジェクトからそれ自身への射がモノイドを形成し、逆にモノイドは単一のオブジェクトを持つ圏として見ることができます。

コンピュータサイエンスとコンピュータプログラミングでは、与えられた文字セットから構築された文字列のセットは自由モノイドと呼ばれます。遷移モノイドと構文モノイドは有限状態マシンの記述に使用されます。トレースモノイドと履歴モノイドはプロセス計算と並行コンピューティングの基礎を提供します。

理論計算機科学において、モノイドの研究はオートマトン理論（クローン・ローズ理論）や形式言語理論（スターハイト問題）の基礎となります。

このテーマの歴史とモノイドのその他の一般的な性質については、 semigroup を参照してください。

二項演算S × S → S （以下、 •と表記）を備えた集合S がモノイド と呼ばれるのは、次の2つの公理を満たす場合 です。

結合性

S内のすべてのa、b、cについて、式( a • b ) • c = a • ( b • c )が成立します。

アイデンティティ要素

Sには要素e が存在し、 Sのすべての要素aに対して、等式e • a = aおよびa • e = aが成り立ちます。

言い換えれば、モノイドは単位元を持つ半群です。また、結合性と単位元を持つマグマと考えることもできます。モノイドの単位元は一意です。 ^[a] このため、単位元は定数、つまり0項（またはゼロ項）演算と見なされます。したがって、モノイドは3つの（S、•、e）の指定によって特徴付けられます。

文脈によっては、二項演算の記号が省略され、演算が並置で表記されることがあります。たとえば、モノイド公理は( ab ) c = a ( bc )やea = ae = aと表記されることがあります。この表記は、数値の乗算を意味するものではありません。

各要素に逆元が存在するモノイドは群です。

モノイド( M , •)のサブモノイドは、モノイド演算に関して閉じており、Mの単位元e を含むMの部分集合Nです。^{[1] [b]}記号的に、N がMのサブモノイドである場合は、 e ∈ N ⊆ Mであり、x、y ∈ Nのときはいつでもx • y ∈ Nです。この場合、N はMから継承された二項演算に関してモノイドです。

一方、N がモノイド演算に関して閉じているモノイドのサブセットであり、この継承された演算に関してモノイドである場合、単位元が異なる可能性があるため、 N は常にサブモノイドであるとは限りません。たとえば、シングルトン セット {0}は乗算に関して閉じており、非負整数の (乗法) モノイドのサブモノイドではありません。

MのサブセットS は、 Sを含むMの最小のサブモノイドがMである場合に、 M を生成すると言われます。 M を生成する有限集合がある場合、M は有限生成モノイドであると言われています。

演算が可換なモノイドは可換モノイド（または、あまり一般的ではないが、アーベルモノイド）と呼ばれる。可換モノイドはしばしば加法的に記述される。任意の可換モノイドには、代数的 順序付け ≤が備わっており、 x + z = yとなるz が存在する場合、x ≤ yによって定義される。^[2]可換モノイドMの順序単位は、 Mの任意の要素xに対して、 uによって生成される集合に、 x ≤ vとなるv が存在するようなMの要素uである。これは、 M が半順序アーベル群Gの正の錐である場合によく使用され、その場合、 u はGの順序単位であると言われる。

一部の要素に対しては演算が可換だが、すべての要素に対しては可換ではないモノイドをトレースモノイドといいます。トレースモノイドは並行計算の理論でよく登場します。

• 16 個の可能な二項ブール演算子のうち、4 つは両側の恒等式を持ち、これは可換かつ結合的です。これら 4 つはそれぞれ、集合{False, True}を可換モノイドにします。標準の定義では、ANDとXNOR は恒等式Trueを持ち、XORとOR は恒等式Falseを持ちます。 AND と OR のモノイドも冪等ですが、 XOR と XNOR のモノイドは冪等ではありません。
• 自然数 の集合N = {0, 1, 2, ...} は、加法（単位元0）または乗法（単位元1 ）に関して可換モノイドです。加法に関してNのサブモノイドは数値モノイドと呼ばれます。
• 正の整数 の集合N ∖ {0}は乗法に関して可換モノイドである（単位元は1）。
• 集合Aが与えられたとき、 Aの部分集合の集合は交差に関して可換モノイドである（単位元はA自身である）。
• 集合Aが与えられたとき、 Aの部分集合の集合は和集合に関して可換モノイドである（単位元は空集合である）。
• 前の例を一般化すると、すべての有界半格子は冪等可換モノイドになります。
  • 特に、任意の有界格子には、 meetモノイド構造とjoinモノイド構造の両方を持たせることができます。単位元は、それぞれ格子の上部と下部です。格子であるHeyting 代数とブール代数には、これらのモノイド構造が備わっています。
• 二項演算の下で閉じているすべての単集合 { x }は、自明な（1要素の）モノイドを形成します。これは自明な群でもあります。
• すべての群はモノイドであり、すべてのアーベル群は可換モノイドです。
• 任意の半群 S は、 Sに含まれない元eを付加し、すべてのs ∈ Sに対してe • s = s = s • eと定義するだけでモノイドに変換できます。この任意の半群のモノイドへの変換は、半群のカテゴリとモノイドのカテゴリ間の自由関手によって行われます。 ^[3]
  • したがって、冪等モノイド（find-firstと呼ばれることもある）は、単位元e を集合S上の左ゼロ半群に付加することによって形成されます。反対のモノイド（find-lastと呼ばれることもある）は、 S上の右ゼロ半群から形成されます。
    • 2 つの要素{lt, gt}を持つ左ゼロ半群に恒等基e を付加します。その結果得られる冪等モノイド{lt, e , gt}は、要素の順序が与えられたシーケンスの辞書式順序をモデル化します。ここで、 e は等式を表します。
• 任意の環の基礎となる集合。演算は加算または乗算です。(定義により、環は乗法単位元1を持ちます。)
  • 加算または乗算を演算とする整数、有理数、実数、複素数。^[4 ]
  • 行列の加算または乗算を演算として行う、指定されたリング上のすべてのn行n 列の行列の集合。
• ある固定されたアルファベットΣ上のすべての有限文字列の集合は、文字列の連結を演算とするモノイドを形成します。空の文字列は単位元として機能します。このモノイドはΣ ^∗で表され、 Σ上の自由モノイドと呼ばれます。 Σ に少なくとも 2 つの要素がある場合、それは可換ではありません。
• 任意のモノイドMに対して、その反対のモノイド M ^{op は}Mと同じキャリア集合と単位元を持ち、その演算はx • ^op y = y • xで定義されます。任意の可換モノイドは、それ自身の反対のモノイドです。
• モノイド構造を持つ2つの集合MとN（または、一般には任意の有限個のモノイド、M ₁、...、M _k）が与えられた場合、それらの直積 M × N（対応する座標で定義された二項演算と単位元を持つ直積）もモノイドである（それぞれ、M ₁ × ⋅⋅⋅ × M _k）。^[5]
• モノイドM を固定します。与えられた集合からMへのすべての関数の集合もモノイドです。単位元は、任意の値をMの単位元にマッピングする定数関数です。結合演算は点ごとに定義されます。
• 演算•と単位元eを持つモノイドM を固定し、Mのすべての部分集合からなるその冪集合P ( M )を考えます。このような部分集合の二項演算は、 S • T = { s • t  : s ∈ S、t ∈ T }で定義できます。これにより、P ( M ) は単位元{ e }を持つモノイドになります。同様に、群Gの冪集合は、群の部分集合の積によるモノイドです。
• S を集合とする。すべての関数S → Sの集合は、関数合成の下でモノイドを形成する。恒等関数は、恒等関数そのものである。これはSの完全変換モノイドとも呼ばれる。Sがn個の要素を持つ有限である場合、 S上の関数のモノイドはn個^の要素を持つ有限である。
• 前の例を一般化して、C をカテゴリ、XをCのオブジェクトとします。 Xのすべての自己準同型の集合はEnd _C ( X )と表記され、射の合成によってモノイドを形成します。カテゴリ理論とモノイドの関係の詳細については、以下を参照してください。
• 連結和を持つコンパクト曲面の同相 類の集合。その単位元は通常の 2 次元球面の類である。さらに、a がトーラスの類、b が射影平面の類を表す場合、モノイドのすべての元cはc = na + mbの形式で一意の表現を持ちます。ここでnは正の整数、m = 0、1、または2です。3 b = a + bです。
• ⟨ f ⟩ をn次巡回モノイド、すなわち⟨ f ⟩ = { f ⁰ , f ¹ , ..., f ^{n −1} }とする。すると、0 ≤ k < nに対してf ⁿ = f ^kとなる。このようなk はそれぞれn次モノイドを 1 つ与え、巡回モノイドはすべてこれらのうちの 1 つと同型である。さらに、f は点{0, 1, 2, ..., n −1}上の関数として考えることができ、次のように表される。
  

$${\displaystyle {\begin{bmatrix}0&1&2&\cdots &n-2&n-1\\1&2&3&\cdots &n-1&k\end{bmatrix}}}$$または、同等に$${\displaystyle f(i):={\begin{cases}i+1,&{\text{if }}0\leq i<n-1\\k,&{\text{if }}i=n-1.\end{cases}}}$$

⟨ f ⟩ の要素の乗算は関数合成によって与えられます。

k = 0のとき、関数f は{0, 1, 2, ..., n −1}の順列となり、n次数の唯一の巡回群を与えます。

モノイド公理は、単位元eが一意であることを意味します。つまり、 eとf がモノイドの単位元である場合、e = ef = fです。

それぞれの非負整数nに対して、モノイドのn要素の任意のシーケンス( a ₁、...、a _n )の積を再帰的に定義できます。つまり、 1 ≤ m ≤ nに対して、 p ₀ = eおよびp _m = p _{m −1} • a _mとします。 ${\displaystyle p_{n}=\textstyle \prod _{i=1}^{n}a_{i}}$

特別な場合として、モノイドの要素xの非負整数乗を定義できます。 x ⁰ = 1かつx ⁿ = x ^{n −1} • x ( n ≥ 1 )。 このとき、すべてのm、n ≥ 0についてx ^{m + n} = x ^m • x ⁿが成立します。

元xが可逆であるとは、元yが存在してx • y = eかつy • x = e が成り立つことをいう。元y はxの逆元と呼ばれる。逆元は、存在する場合、一意である。つまり、yとz がxの逆元であれば、結合法則によりy = ey = ( zx ) y = z ( xy ) = ze = z となる。^[6]

xが逆数、つまりy の逆数を持つ場合、各n ≥ 1に対してx ^{− n} = y ⁿと設定することでxの負の累乗を定義できます。これにより、すべてのm、n ∈ Zに対して方程式x ^{m + n} = x ^m • x ⁿが成立します。

モノイド内のすべての可逆な要素の集合は、演算 • とともに群を形成します。

すべてのモノイドがグループ内に存在するわけではありません。たとえば、2 つの要素aとbが存在し、bが単位元でなくてもa • b = aが成り立つようなモノイドを持つことは完全に可能です。このようなモノイドはグループに埋め込むことはできません。なぜなら、グループ内で両辺にaの逆数を掛けるとb = eとなり、これは正しくないからです。

モノイド( M , •)が相殺特性を持つ(または相殺可能である) とは、M内のすべてのa、b、cについて、等式a • b = a • c がb = cを意味し、等式b • a = c • a がb = c を意味する場合です。

相殺特性を持つ可換モノイドは、グロタンディーク群の構成を介して常に群に埋め込むことができます。これは、整数の加法群 (演算+を持つ群) が自然数の加法モノイド (演算+と相殺特性を持つ可換モノイド) から構築される方法です。ただし、非可換な相殺モノイドは、群に埋め込むことができる必要はありません。

モノイドが相殺特性を持ち有限である場合、それは実際には群である。^[c]

モノイドの右および左の相殺要素はそれぞれサブモノイドを形成します (つまり、演算に関して閉じており、明らかに単位元を含みます)。これは、任意の可換モノイドの相殺要素をグループに拡張できることを意味します。

モノイドの相殺性は、グロタンディーク構成を実行するために必要ではなく、可換性があれば十分です。しかし、可換モノイドが相殺性を持たない場合、モノイドのグロタンディーク群への準同型性は単射ではありません。より正確には、a • b = a • cの場合、b ≠ cであっても、 bとc はグロタンディーク群で同じ像を持ちます。特に、モノイドが吸収元を持つ場合、そのグロタンディーク群は自明群です。

逆モノイドとは、 Mの任意のaに対して、 Mに一意のa ⁻¹が存在し、 a = a • a ⁻¹ • aかつa ⁻¹ = a ⁻¹ • a • a ⁻¹となるモノイドです。逆モノイドが相殺可能であれば、それは群です。

逆に、ゼロサムフリーモノイドは、 a + b = 0であればa = 0かつb = 0となるような加法的に記述されたモノイドである。^[7]つまり、ゼロ以外の要素には加法的逆元がないということである。

M をモノイドとし、二項演算を• 、単位元をeで表すとします。このとき、 (左) M作用(またはM上の左作用) は、集合Xと、次のモノイド構造と互換性のある演算⋅ : M × X → Xを組み合わせたものになります。

• X内のすべてのxについて: e ⋅ x = x ;
• Mに属するすべてのa、b、Xに属するすべてのxについて、a ⋅ ( b ⋅ x ) = ( a • b ) ⋅ xです。

これは、モノイド理論における（左）群作用の類似物です。右M作用も同様に定義されます。作用を持つモノイドは、演算子モノイドとも呼ばれます。重要な例としては、セミオートマトン遷移システムがあります。変換半群は、恒等変換を付加することで演算子モノイドにすることができます。

2つのモノイド( M ,∗)と( N ,•)の間の準同型とは、関数f  : M → Nであって、

• f ( x ∗ y ) = f ( x ) • f ( y ) （Mの任意のx、 yについて
• f ( e _M ) = e _N、

ここで、e _Mとe _{N は}それぞれMとN上の恒等写像です。モノイド準同型は単にモノイド射と呼ばれることもあります。

モノイド間の半群準同型は必ずしもモノイド準同型ではない。なぜなら恒等写像が準同型の像の恒等写像であっても、恒等写像を対象モノイドの恒等写像に写像しないことがあるからである。[ ^d]たとえば、乗法を備えたnを法とする剰余類の集合[ Z ] _nを考える。特に、[1] _{n は}恒等元である。[ k ] ₃ ↦ [3 k ] ₆で与えられる関数f  : [ Z ] ₃ → [ Z ] ₆は半群準同型である。なぜなら[3 k ⋅ 3 l ] ₆ = [9 kl ] ₆ = [3 kl ] ₆であるからである。しかし、f ([1] ₃ ) = [3] ₆ ≠ [1] ₆なので、モノイド準同型は、最初のモノイドの恒等式を2番目のモノイドの恒等式に写像するモノイド間の半群準同型であり、後者の条件は省略できません。

対照的に、群間の半群準同型は常に群準同型です。なぜなら、それは必然的に恒等性を保存するからです（準同型のターゲット群では、恒等元はx ⋅ x = xとなる唯一の元xであるため）。

全単射モノイド準同型はモノイド同型と呼ばれます。2 つのモノイドの間にモノイド同型がある場合、それらのモノイドは同型であると言われます。

モノイドには、グループがグループのプレゼンテーションによって指定されるのとほぼ同じように、プレゼンテーションを与えることができます。これは、生成子の集合Σと、自由モノイドΣ ^∗上の関係の集合を指定することによって行われます。これは、Σ ^∗上の(有限) 2 項関係をモノイド合同に拡張し、上記のように商モノイドを構築することによって行われます。

二項関係R ⊂ Σ ∗ ^× Σ ∗^が与えられたとき、その対称閉包をR ∪ R ⁻¹と定義する。これは、( u , v ) ^∈ R ∪ R −1であるいくつかの文字列u、v、s、t ∈ Σ ^{∗に対して}x = sutかつy = svt のときのみx ~ _E yと定義することで、対称関係 E ⊂ Σ ^∗ × Σ ∗に拡張できる。最後に、 E^の反射的かつ推移的な閉包をとり、これはモノイド合同となる 。

典型的な状況では、関係Rは単に一連の方程式として与えられ、R = { u ₁ = v ₁、...、u _n = v _n }となります。したがって、たとえば、

${\displaystyle \langle p,q\,\vert \;pq=1\rangle }$

は二環式モノイドの等式表現であり、

${\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }$

は、次数2のプラクティックモノイドです(無限の順序を持​​ちます)。このプラクティックモノイドの元は、整数i、j、kについてと表記できます。これは、ba がaおよびbと可換であることを示しているためです。 ${\displaystyle a^{i}b^{j}(ba)^{k}}$

モノイドは、カテゴリの特別なクラスとして見ることができる。実際、モノイド演算に必要な公理は、与えられたオブジェクトをソースとターゲットとするすべての射の集合に制限した場合、射合成に必要な公理とまったく同じである。^[8]つまり、

モノイドは本質的に、単一のオブジェクトを持つカテゴリと同じものです。

より正確には、モノイド( M、 • )が与えられたとき、 1 つのオブジェクトのみを持ち、その射がMの要素である小さなカテゴリを構築できます。射の合成はモノイド演算•によって与えられます 。

同様に、モノイド準同型は単一のオブジェクトカテゴリ間の単なる関数です。^[8] したがって、この構成は、（小さな）モノイドのカテゴリMonと（小さな）カテゴリのカテゴリCatの完全なサブカテゴリとの間の同値性を与えます。同様に、グループのカテゴリはCatの別の完全なサブカテゴリと同値です。

この意味で、カテゴリ理論はモノイドの概念の拡張として考えることができます。モノイドに関する多くの定義と定理は、複数のオブジェクトを持つ小さなカテゴリに一般化できます。たとえば、カテゴリと 1 つのオブジェクトの商は、商モノイドです。

モノイドは、他の代数構造と同様に、独自のカテゴリMonを形成します。Monのオブジェクトはモノイドであり、その射はモノイド準同型です。^[8]

また、モノイド オブジェクトという概念もあります。これは、カテゴリ内のモノイドが何であるかを抽象的に定義したものです。Set 内のモノイド オブジェクトは単なるモノイドです。

コンピュータ サイエンスでは、多くの抽象データ型にモノイド構造を持たせることができます。一般的なパターンでは、モノイドの要素のシーケンスが「折り畳まれ」または「累積され」、最終的な値が生成されます。たとえば、多くの反復アルゴリズムでは、反復ごとに何らかの「実行合計」を更新する必要があります。このパターンは、モノイド演算によって簡潔に表現できます。あるいは、モノイド演算の結合性により、プレフィックス合計または同様のアルゴリズムを使用して演算を並列化できるため、複数のコアまたはプロセッサを効率的に使用できます。

単位元εと結合演算 •を持つ型Mの値のシーケンスが与えられた場合、折り畳み演算は次のように定義されます。

${\displaystyle \mathrm {fold} :M^{*}\rightarrow M=\ell \mapsto {\begin{cases}\varepsilon &{\mbox{if }}\ell =\mathrm {nil} \\m\bullet \mathrm {fold} \,\ell '&{\mbox{if }}\ell =\mathrm {cons} \,m\,\ell '\end{cases}}}$

さらに、要素のシリアル化が与えられれば、任意のデータ構造を同様の方法で「折りたたむ」ことができます。たとえば、バイナリ ツリーを「折りたたむ」結果は、事前順序ツリー トラバーサルと事後順序ツリー トラバーサルによって異なる場合があります。

コンピュータ サイエンスにおけるモノイドの応用は、いわゆるMapReduceプログラミング モデルです (「Map-Reduce を左折り畳みのモノイドとしてエンコードする」を参照)。コンピューティングにおける MapReduce は、2 つまたは 3 つの操作で構成されます。データセットが与えられた場合、「Map」は任意のデータを特定のモノイドの要素にマッピングします。「Reduce」はそれらの要素を折り畳むことで、最終的に 1 つの要素だけを生成します。

たとえば、多重集合がある場合、プログラムでは、要素からその番号へのマップとして表現されます。この場合、要素はキーと呼ばれます。異なるキーの数が多すぎる場合、多重集合は分割されます。削減を適切に完了するために、「シャッフル」ステージでノード間でデータを再グループ化します。このステップが不要な場合、Map/Reduce 全体はマッピングと削減で構成されます。両方の操作は並列化可能で、前者は要素ごとの性質のため、後者はモノイドの結合性のため並列化可能です。

完全モノイドとは、任意の添字集合Iに対して無限和演算を備えた可換モノイドであり、^{[9] [10] [11] [12]}${\displaystyle \Sigma _{I}}$

${\displaystyle \sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\text{ for }}j\neq k}$

そして

${\displaystyle \sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}m_{i}\quad {\text{ if }}\bigcup _{j\in J}I_{j}=I{\text{ and }}I_{j}\cap I_{j'}=\emptyset \quad {\text{ for }}j\neq j'}$。

順序付き可換モノイドとは、可換モノイドMと半順序 ≤を組み合わせたもので、任意のa ∈ Mに対してa ≥ 0であり、すべてのa、b、c ∈ Mに対してa ≤ bであればa + c ≤ b + c が成り立つようなものです。

連続モノイドは、すべての有向部分集合に最小上限があり、これらの最小上限がモノイド演算と互換性がある 順序付き可換モノイド( M、≤)です。

${\displaystyle a+\sup S=\sup(a+S)}$

あらゆるa ∈ MとMの有向部分集合Sに対して。

( M , ≤)が連続モノイドである場合、任意の添字集合Iと要素の集合( a _i ) _{i ∈ I}に対して、定義できる。

${\displaystyle \sum _{I}a_{i}=\sup _{{\text{finite }}E\subset I}\;\sum _{E}a_{i},}$

そしてMは、この無限和演算を伴って完全なモノイドとなる。^[12]

• デカルトモノイド
• グリーンの関係
• モナド（関数型プログラミング）
• 半環とクリーネ代数
• 星の高さの問題
• ヴェーダの広場
• フロベニオイド

• 「モノイド」、数学百科事典、EMS Press、2001 [1994]
• Weisstein、Eric W.「モノイド」。MathWorld。
• PlanetMathのモノイド。