モノイド

テンプレート:About テンプレート:代数的構造 抽象代数学における単系（たんけい）またはモノイド（テンプレート:Lang-en-short）とは、結合法則と単位元を有するマグマである。モノイドは単位元を有する半群（単位的半群）であるため、半群論の研究対象の範疇に属する。

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

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

定義

集合 テンプレート:Mvar とその上の二項演算 テンプレート:Math が与えられ、以下の条件

結合律

テンプレート:Mvar の任意の元 テンプレート:Mvar に対して、テンプレート:Math

単位元の存在

テンプレート:Mvar の元 テンプレート:Mvar が存在して、テンプレート:Mvar の任意の元 テンプレート:Mvar に対して テンプレート:Math

を満たすならば、組 テンプレート:Math をモノイドという。まぎれの虞のない場合、対 テンプレート:Math あるいは単に テンプレート:Mvar のみでも表す。 二項演算の結果 テンプレート:Mvar を テンプレート:Mvar と テンプレート:Mvar の積テンプレート:Efnと呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、群が得られる。逆に任意の群はモノイドである。

二項演算の記号は省略されることが多く、たとえば先ほどの公理に現れる等式は テンプレート:Math と書かれる。本項でも明示する理由がない限り二項演算の記号を省略する。

モノイドの構造

部分モノイド

モノイド テンプレート:Mvar の部分集合 テンプレート:Mvar が テンプレート:Mvar の部分モノイド テンプレート:Lang とは、テンプレート:Mvar の単位元を含み、閉性質: テンプレート:Math ならば テンプレート:Math となるようなものをいう。これは テンプレート:Mvar のモノイド演算の制限 テンプレート:Math の像が テンプレート:Math を満たすということであり、従って テンプレート:Math は テンプレート:Mvar 上の二項演算を定め、部分モノイド テンプレート:Mvar は明らかにそれ自身が一つのモノイドとなる。

モノイドの生成

部分集合 テンプレート:Mvar がモノイド テンプレート:Mvar の生成系 テンプレート:Lang であるとは テンプレート:Mvar の任意の元が テンプレート:Mvar の元だけから二項演算を繰り返して得られることをいう（生成系に属する元を生成元という）。モノイド テンプレート:Mvar がその部分集合 テンプレート:Mvar で生成されるとき テンプレート:Math などと書く。

$⟨S⟩=\{s_{k_1}^{e_{k_1}}{s}_{k_2}^{e_{k_2}}\cdots s_{k_m}^{e_{k_m}}\mid \mathrm{\exists }m\in \mathbb{N},(k_1,\dots ,k_m)\in {\mathbb{N}}^m,e_{k_j}\in \mathbb{N},s_{k_j}\in S\}.$

テンプレート:Mvar の各元 テンプレート:Mvar に対し テンプレート:Math を テンプレート:Mvar の単位元とする規約を設けるならば、テンプレート:Math における テンプレート:Mvar の元の冪が零となることも許し、テンプレート:Math は テンプレート:Mvar を含む最小の部分モノイドを表すテンプレート:Efn。

テンプレート:Mvar が有限個の元からなる生成系をもつとき、有限生成 テンプレート:Lang あるいは有限型 テンプレート:Lang であるという。特に、テンプレート:Mvar のただ一つの元 テンプレート:Mvar で生成されるモノイド テンプレート:Math は単項生成モノイドあるいは巡回モノイド テンプレート:Lang と呼び、集合としては テンプレート:Mvar の冪全体の成す集合 テンプレート:Math に一致する。

可換モノイド

演算が可換であるようなモノイドは、可換モノイド テンプレート:En という（稀にアーベルモノイド テンプレート:En ともいう）。可換モノイドはしばしば二項演算の記号を "+" として加法的に書かれる。任意の可換モノイド テンプレート:Mvar は

$x\le y⟺x+z=y\mathrm{\exists }z\in M$

として定まる代数的前順序 "テンプレート:Math" を持つ。可換モノイド テンプレート:Mvar の順序単位 テンプレート:Lang テンプレート:Math とは、テンプレート:Mvar の各元 テンプレート:Mvar に対して適当な正の整数 テンプレート:Mvar をとれば テンプレート:Math (右辺は テンプレート:Mvar 個の テンプレート:Mvar の和を表す)とできるようなものをいう。これは テンプレート:Mvar が半順序可換群 テンプレート:Mvar の正錐である場合にもよく用いられ、この場合には テンプレート:Mvar を テンプレート:Mvar の順序単位と呼ぶ。

部分可換モノイド

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

例

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

モノイドの構成法

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

自由モノイド

固定された字母集合 テンプレート:Math 上の有限文字列全体(空文字列を含む)は、連接を二項演算とし単位元を空文字列としてモノイドとなる。このモノイドを テンプレート:Math で表すテンプレート:Efnと、これは テンプレート:Math を生成系としてもち、公理の等式以外に元の間の関係式をもたないので テンプレート:Math 上の自由モノイドと呼ぶ。テンプレート:仮リンクはモノイドの圏 テンプレート:Math におけるテンプレート:仮リンクであり、その普遍性はモノイドの表示として理解することができる（後述）。

1-添加

任意の半群 テンプレート:Mvar は、テンプレート:Mvar に属さない新たな元 テンプレート:Mvar を（新たな）単位元として添加してモノイドにすることができる。すなわち、テンプレート:Math とし、テンプレート:Mvar の任意の元 テンプレート:Mvar に対して テンプレート:Math と定めるとき テンプレート:Mvar はモノイドである。

テンプレート:Mvar 上のテンプレート:仮リンクに単位元 テンプレート:Mvar を添加したものは（find-first としても知られる）冪等モノイドであり、テンプレート:Mvar 上の右零半群に単位元 テンプレート:Mvar を添加したものは（find-last とも呼ばれる）反モノイドとなる。 二つの元 テンプレート:Math を持つ左零半群に単位元 "テンプレート:Math" を添加して得られる冪等モノイド テンプレート:Math は順序の与えられた集合の元の列に対する辞書式順序のモデルを与える。

逆転モノイド

任意のモノイド テンプレート:Math に対し、その反モノイド テンプレート:Lang テンプレート:Math とは、台集合と単位元は テンプレート:Mvar と同じものとし、その演算を

$x\stackrel{\text{op}}{\bullet }y:=y\bullet x$

と定めて得られるモノイドである（逆モノイドテンプレート:Efn、逆転モノイド、反対モノイドなどともいう）。任意の可換モノイドは自分自身を反モノイドとして持つ。

直積モノイド

二つのモノイド テンプレート:Mvar に対して（より一般に、有限個のモノイド テンプレート:Math に対して、あるいは無限族 テンプレート:Math に対して）、それらの直積集合 テンプレート:Math（あるいは テンプレート:Math, テンプレート:Math）もまたモノイドとなる。モノイド演算および単位元は、成分ごとの積および成分ごとの単位元の組として与えられるテンプレート:Sfn。

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

商モノイド

モノイド テンプレート:Math 上の合同関係（モノイド合同）テンプレート:Math とは、モノイド構造と両立する（すなわち、テンプレート:Math かつ テンプレート:Math ならば テンプレート:Math を満たす）同値関係を言う。モノイド テンプレート:Mvar のモノイド合同 テンプレート:Math による剰余モノイドあるいは商モノイドは、各元 テンプレート:Math の属する同値類を テンプレート:Math と書くとき、商集合 テンプレート:Math に

$[x]\circ [y]:=[xy]$

で定まるモノイド演算を入れて得られるモノイド テンプレート:Math を言う。

冪集合モノイド

モノイド テンプレート:Math を固定して、テンプレート:Mvar の冪集合 テンプレート:Math を考える。テンプレート:Math の 部分集合 $S,T$ の間の二項演算 "テンプレート:Math" を

$S*T:=\{s\bullet t\mid s\in S,t\in T\}$

で定めれば、テンプレート:Math は自明モノイド テンプレート:Math を単位元とするモノイドとなる。同じ方法で、群 テンプレート:Mvar の冪集合はテンプレート:仮リンクに関するモノイドとなる。

性質

モノイドにおいて、元 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, •) が消約律 テンプレート:Lang を満たす、あるいは消約的 テンプレート:Lang であるとは

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 は巡回置換として

$\left(\begin{array}{cccccc}0& 1& 2& ...& n-2& n-1\\ 1& 2& 3& ...& n-1& k\end{array}\right)$

と表すことができ、モノイドの積と置換の積が対応する。

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

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

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

となる M の元 a⁻¹ をただひとつ持つとき、M を逆モノイド テンプレート:Lang あるいは山田モノイドというテンプレート:Efn。逆モノイドが消約的ならばそれは群を成す。

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

(M, •) をモノイドとする。集合 X への（左）M-作用 テンプレート:Lang あるいは 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′, •′) の間のモノイド準同型 テンプレート:Lang とは、写像 f: M → M′ であって、

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

を満たすものをいう。ここで、e および e′ はそれぞれ M および M′ の単位元である。モノイド準同型は簡単にモノイド射 テンプレート:Lang と呼ばれることもある。

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

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

生成元と基本関係

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

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

$(x,y)\in E⟺\mathrm{\exists }u,\mathrm{\exists }v,\mathrm{\exists }s,\mathrm{\exists }t\in {\mathrm{\Sigma }}^{*}\text{ s.t. }x=sut\wedge y=svt\wedge (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} として与えられ、例えば

$⟨p,q\mid pq=1⟩$

はテンプレート:仮リンクの生成元と基本関係式による表示であり、また

$⟨a,b\mid aba=baa,bba=bab⟩$

は次数 2 のテンプレート:仮リンクとなる（位数は無限大である）。基本関係式は ba が a および b とそれぞれ可換になることを示すものとみることができるので、このプラクティックモノイドの任意の元は適当な整数 i, j, k を用いて aⁱb^j(ba)^k の形に表される。

圏論との関係

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

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

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

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

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

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

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

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

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

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

$\mathrm{fold}:M^{*}\to M$

$\mathrm{fold}l=\{\begin{array}{cc}\epsilon & \text{if }l=\mathrm{nil}\\ m\bullet \mathrm{fold}{l}^{\prime }& \text{if }l=\mathrm{cons}m{l}^{\prime }\end{array}$

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

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

関連項目

• モノイド圏
• モナド (圏論)
• テンプレート:仮リンク
• テンプレート:仮リンク
• 一元体: 定式化に吸収元つきモノイドが利用される
• フロベニオイド

参考文献

• John M. Howie, Fundamentals of Semigroup Theory (1995), Clarendon Press, Oxford ISBN 0-19-851194-9
• テンプレート:Citation
• テンプレート:Citation
• 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

外部リンク

• テンプレート:MathWorld
• テンプレート:PlanetMath