モノイド

数学、とくに抽象代数学における単系（たんけい、テンプレート:Lang-en-short; モノイド）はひとつの二項演算と単位元をもつ代数的構造である。モノイドは単位元をもつ半群（単位的半群）であるので、半群論の研究対象の範疇に属する。

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

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

定義

集合 S とその上の二項演算 • : S × S → S が与えられたとき、組 (S, • ) が以下の条件を満たすならば、これを モノイド という。

結合律

S の任意の元 a, b, c に対して、(a • b) • c = a • (b • c)

単位元の存在

S の元 e が存在して、S の任意の元 a に対して e • a = a • e = a

二項演算の結果 a • b を a と b の積と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、群が得られる。逆に任意の群はモノイドである。

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

モノイドの構造

生成系と部分モノイド

モノイド M の部分モノイド (submonoid) とは、M の部分集合 N であって、M の単位元を含み、x, y ∈ N ならば必ず xy ∈ N となるようなものをいう。従って部分モノイド N をなす集合は明らかに M の演算から誘導される演算に関してそれ自身モノイドとなる。部分集合 N がモノイド M の生成系 (generator) であるとは M の任意の元が N の元だけの二項演算を繰り返して得られることをいう（生成系に属する元を生成元という）。M が有限個の元からなる生成系をもつとき、M は有限生成 (finitely generated) あるいは有限型 (finite type) であるという。

逆に、ある固定された文字集合 Σ 上の有限文字列全体(空文字列を含む)は、文字列の連接を二項演算とし単位元を空文字列としてモノイドとなる。このモノイドを Σ^∗ で表すと、これは Σ を生成系としてもち、公理の等式以外に元の間の関係式をもたないので Σ 上の自由モノイドと呼ぶ。テンプレート:仮リンクはモノイドの圏における自由対象である。

可換モノイド

演算が可換であるようなモノイドは、可換モノイド (commutative monoid) という（稀にアーベルモノイド (abelian monoid) ともいう）。可換モノイドはしばしば二項演算の記号を "+" として加法的に書かれる。任意の可換モノイド M は

<math>x\le y \iff x+z = y\quad \exist z\in M</math>

として定まる代数的前順序 "≤" を持つ。可換モノイド M の順序単位 (order-unit) とは、M の元 u であって、M の任意の元 x に対して適当な正の整数 n をとれば x ≤ nu (右辺は n 個の u の和を表す)とできるようなものをいう。これは M が半順序可換群 G の正錐である場合にもよく用いられ、この場合には u を G の順序単位と呼ぶ。

半可換モノイド

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

例

• 任意の一元集合 {x} は x • x = x と置くことによりモノイドとなる。これを自明なモノイドという。
• 任意の単位的環の元の全体は、加法あるいは乗法に関してそれぞれモノイドを成す。
  • 整数全体、有理数全体、実数全体、複素数全体は加法あるいは乗法に関してそれぞれモノイドを成す。
  • 与えられた環に係数を持つ n-次正方行列の全体は行列の加法または行列の乗法に関してモノイドを成す。
• 任意の有界半束は冪等可換モノイドである。
  • 特に、任意の有界束は交わりについても結びについてもモノイドとなる（モノイドの単位元はそれぞれ束の最大元および最小元で与えられる）。したがって、束であるハイティング代数やブール代数はそのようなモノイド構造を持つ。
• 任意の半群 S は、 S に属さない元 e を添加してモノイドにすることができる。すなわち、S^e := S ∪ {e} とし、S の任意の元 s に対して e • s = s = s • e と定めるとき S^e はモノイドである。
  • S 上の左零半群に単位元 e を添加したものは（find-first としても知られる）冪等モノイドであり、S 上の右零半群に単位元 e を添加したものは（find-last とも呼ばれる）反モノイドとなる。
    • 二つの元 {<, >} を持つ左零半群に単位元 "=" を添加して得られる冪等モノイド {<, =, >} は順序の与えられた集合の元の列に対する辞書式順序のモデルを与える。
• （0 を含む）自然数の全体 N₀ は加法に関して 0 を単位元とするモノイドを成し、また乗法に関して 1 を単位元とするモノイドを成す。N₀ の加法に関する部分モノイドは自然数モノイド (numerical monoid) と呼ばれる。N₀ の 0 以外の元（正の整数）からなる部分集合 N は乗法に関して 1 を単位元とする部分モノイドを成す。
• 任意のモノイド (M, •) に対し、その反モノイド (opposite monoid) (M^op, •^op) とは、台集合と単位元は M と同じものとし、その演算を
  <math>x \stackrel{\text{op}}{{}\bullet{}} y := y \bullet x</math>
  と定めて得られるモノイドである（逆モノイド、逆転モノイド、反対モノイドなどともいう）。任意の可換モノイドは自分自身を反モノイドとして持つ。
• 二つのモノイド M, N に対して（あるいは一般に、有限個のモノイド M₁, ..., M_k に対して）、それらの直積集合 M × N（あるいは M₁ × ... × M_k）もまたモノイドとなる。モノイド演算および単位元は、成分ごとの積および成分ごとの単位元の組として与えられる。
• 与えられたモノイド M に対し、与えられた集合 S から M への写像の全体 Map(S, M) は再びモノイドとなる。単位元は、任意の元を M の単位元へ写す定値写像であり、演算は M の積から導かれる点ごとの積である。
• モノイド (M, •) を固定して、M の部分集合の全体の成す冪集合 P(M) を考える。部分集合の間の二項演算 "∗" を
  <math>S * T := \{s\bullet t \mid s \in S, t \in T\}</math>
  で定めれば、P(M) は単位元を {e} とするモノイドである。同じ方法で、群 G の冪集合は群の部分集合の積に関するモノイドとなる。
• 閉曲面の同相類の全体は連結和 "#" に関して可換モノイドを成す。単位元は通常の球面（2-球面）の属する同相類である。さらにいえば、トーラスの属する同相類 a と射影平面の属する同相類 b に対して、このモノイドの任意の元 c は c = na # mb の形に一意的に表される。ここで n は非負の整数で、m は 0, 1, 2 の何れか（実は 3b = a # b が成り立つ）である。
• 台集合がある元 f の冪から成る、つまり {f⁰, f¹, ..., fⁿ} であるモノイドを 〈f〉 と書いて単項生成モノイドあるいは巡回モノイド (cyclic monoid) と呼ぶ。巡回モノイドの位数が有限な n であるとき、0 ≤ k ≤ n − 1 をみたす適当な k に対して fⁿ = f^k が成り立つ。実は、そのような k を定めるごとに位数 n の相異なるモノイドが得られ、逆に任意の巡回モノイドはそれらのモノイドのうちの何れか一つに同型となる。特に k = 0 の場合は、全ての f ⁱ が逆元を持ち、（ただひとつの位数 n の）巡回群を定める。このとき f は巡回置換として
  <math>

\begin{pmatrix}

0 & 1 & 2 & ... & n-2 & n-1 \\
1 & 2 & 3 & ... & n-1 & k

\end{pmatrix}

</math>