モノイド
計算機科学において、多くの抽象データ型はモノイド構造を持つ。よくあるパターンとして、モノイド構造を持つデータ型の元の列を考えよう。この列に対して 「重畳」(fold) あるいは「堆積」(accumulate) の操作を施すことで、列が含む元の総和のような値が取り出される。例えば、多くの反復アルゴリズムは各反復段階である種の「累計」を更新していく必要があるが、モノイド演算の重畳を使うとこの累計をすっきりと表記できる。別の例として、モノイド演算の結合性は、多コアや多CPUを効果的に利用するために、prefix sumあるいは同様のアルゴリズムによって、計算を並列化できることを保証する。
単位元 ε と演算 • を持つモノイド M に対して、その列の型 M から M への重畳関数 fold は次のように定義される。
fold : M ∗ → M {\displaystyle \operatorname {fold} \colon M^{*}\to M}
モノイド (M, •, 1M) 上の合同関係(モノイド合同)∼ とは、モノイド構造と両立する(すなわち、a ∼ b かつ c ∼ d ならば ac ∼ bd を満たす)同値関係を言う。モノイド M のモノイド合同 ∼ による剰余モノイドあるいは商モノイドは、各元 x ∈ M の属する同値類を [x] と書くとき、商集合 M/∼ に
[ x ] ∘ [ y ] := [ x y ] {\displaystyle [x]\circ [y]:=[xy]}
で定まるモノイド演算を入れて得られるモノイド (M/∼, ∘, [1M]) を言う。
(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-作用も同様に定義される。ある作用に関するモノイドは作用素モノイドとも呼ばれる。重要な例として、オートマトンに現れる状態遷移系が挙げられる。ある集合上の自分自身への写像から成る半群(変換半群)は、恒等変換を付け加えることで作用素モノイドにすることができる。
しかしながら、任意のモノイドが必ず何らかの群に含まれるとは限らない。例えば、b が単位元ではない場合にも a • b = a を満たすような二つの元 a, b をとることができるモノイドというものを矛盾なく考えることができるが、このようなモノイドを群に埋め込むことはできない。なぜなら、埋め込んだ群において必ず存在する a の逆元を両辺に掛けることにより b = e が導かれ、b が単位元でないことに矛盾するからである。モノイド (M, •) が消約律 (cancellation property) を満たす、あるいは消約的 (cancellative) であるとは
M の任意の元 a, b, c に対し、a • b = a • c が成り立つならば、常に b = c を帰結することができる
という条件を満たすときにいう。消約的可換モノイドは常にグロタンディーク構成によって群に埋め込むことができる。これは、整数全体の成す加法群(加法演算 "+" に関する群)を自然数全体の成す加法モノイド(加法演算 "+" に関する消約的可換モノイド)から構成する方法の一般化である。しかし、非可換消約的モノイドは必ずしも群に埋め込み可能でない。
消約的モノイドが有限ならば、実は群になる。
この E は
(x, y) ∈ E かつ (x′, y′) ∈ E ならば (xx′, yy′) ∈ E
をみたし、さらに反射閉包および推移閉包をとることにより、モノイド合同が得られる。
典型的な状況では、関係 R は単に関係式の集合 R = {u1 = v1, ..., un = vn} として与えられ、例えば
⟨ p , q ∣ p q = 1 ⟩ {\displaystyle \langle p,q\mid pq=1\rangle }
は双巡回モノイド(英語版)の生成元と基本関係式による表示であり、また
⟨ a , b ∣ a b a = b a a , b b a = b a b ⟩ {\displaystyle \langle a,b\mid aba=baa,bba=bab\rangle }
は次数 2 のプラクティックモノイド(英語版)となる(位数は無限大である)。基本関係式は ba が a および b とそれぞれ可換になることを示すものとみることができるので、このプラクティックモノイドの任意の元は適当な整数 i, j, k を用いて ab(ba) の形に表される。