モノイド

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数学、とくに抽象代数学における単系(たんけい、: monoid; モノイド)はひとつの二項演算単位元をもつ代数的構造である。モノイドは単位元をもつ半群単位的半群)であるので、半群論の研究対象の範疇に属する。

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

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

定義[編集]

モノイド集合 S とその上の二項演算 “•” の組 (S, •) で、この二項演算が以下の二条件

結合律
S の任意の元 a, b, c に対して、(ab) • c = a • (bc)
単位元の存在
S の元 e が存在して、S の任意の元 a に対して ea = ae = a

を満たすものである。二項演算の結果 abab[* 1]と呼ぶ。手短に述べれば、モノイドとは単位元を持つ半群のことである。モノイドに各元の可逆性を課せば、が得られる。逆に任意の群はモノイドである。

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

モノイドの構造[編集]

生成系と部分モノイド[編集]

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

逆に、ある固定された文字集合 Σ 上の有限文字列全体(空文字列を含む)は、文字列の連接を二項演算とし単位元を空文字列としてモノイドとなる。このモノイドを Σ で表す[* 2]と、これは Σ を生成系としてもち、公理の等式以外に元の間の関係式をもたないので Σ 上の自由モノイドと呼ぶ。自由モノイド英語版モノイドの圏における自由対象である。

可換モノイド[編集]

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

x\le y \iff x+z = y\quad \exist z\in M

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

半可換モノイド[編集]

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

[編集]

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

性質[編集]

モノイドにおいて、元 x の自然数冪を

  • x1 := x,
  • xn := x • … • xn 個の x の積、n > 1)

と定義することができる。このとき、指数法則 xn+p = xnxp の成立は明らかである。定義から直接従うこととして、単位元 e が一意に存在するので、任意の x に対して x0 := e と定義すると、指数法則は任意の非負整数冪に対してなお有効である。

モノイドにおいては、可逆元(あるいは単元)の概念を定義することができる。モノイドの元 x が可逆であるとは xy = e かつ yx = e を満たす元 y が存在するときにいう。yx逆元と呼ばれる。y および zx の逆元ならば、結合律により y = (zx)y = z(xy) = z となるから、逆元は存在すればただひとつである[3]

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

しかしながら、任意のモノイドが必ず何らかの群に含まれるとは限らない。例えば、b が単位元ではない場合にも ab = a を満たすような二つの元 a, b をとることができるモノイドというものを矛盾なく考えることができるが、このようなモノイドを群に埋め込むことはできない。なぜなら、埋め込んだ群において必ず存在する a の逆元を両辺に掛けることにより b = e が導かれ、b が単位元でないことに矛盾するからである。モノイド (M, •) が消約律 (cancellation property) を満たす、あるいは消約的 (cancellative) であるとは

M の任意の元 a, b, c に対し、ab = ac が成り立つならば、常に b = c を帰結することができる

という条件を満たすときにいう。消約的可換モノイドは常にグロタンディーク構成によって群に埋め込むことができる。これは、整数全体の成す加法群(加法演算 "+" に関する群)を自然数全体の成す加法モノイド(加法演算 "+" に関する消約的可換モノイド)から構成する方法の一般化である。しかし、非可換消約的モノイドは必ずしも群に埋め込み可能でない。

消約的モノイドが有限ならば、実は群になる。実際、モノイドの元 x を一つ選べば、有限性より適当な m > n > 0 をとって xn = xm とすることができるが、これは消約律により xmn = ee はモノイドの単位元)となり、xmn−1x の逆元となる。

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

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

a = aa−1a かつ a−1 = a−1aa−1

となる M の元 a−1 をただひとつ持つとき、M逆モノイド (inverse monoid) あるいは山田モノイドという[* 4]。逆モノイドが消約的ならばそれは群を成す。

モノイド作用と作用素モノイド[編集]

(M, •) をモノイドとする。集合 X への(左)M-作用 (M-act) あるいは M による左作用とは、集合 X と外部演算 .: M × XX の組で、外部演算 "." が

  • X の任意の元 x に対して、 e.x = x が成り立つ。
  • M の任意の元 a, bX の任意の元 x に対して、a.(b.x) = (ab).x が成り立つ。

という二つの条件を満たす(ただし eM の単位元)という意味でモノイド構造と両立することをいう。これは群作用のモノイド論における類似物である。右 M-作用も同様に定義される。ある作用に関するモノイドは作用素モノイドとも呼ばれる。重要な例として、オートマトンに現れる状態遷移系が挙げられる。ある集合上の自分自身への写像から成る半群(変換半群)は、恒等変換を付け加えることで作用素モノイドにすることができる。

モノイド準同型[編集]

ふたつのモノイド (M, •), (M′, •′) の間のモノイド準同型 (monoid homomorphism) とは、写像 f: MM′ であって、

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

を満たすものをいう。ここで、e および e′ はそれぞれ M および M′ の単位元である。モノイド準同型は簡単にモノイド射 (monoid morphisms) と呼ばれることもある。

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

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

生成元と基本関係[編集]

モノイドは、群が生成系と基本関係による表示によって特定できるというのと同じ意味で、表示 (presentation) を持つ。すなわち、モノイドは生成系 Σ と Σ が生成する自由モノイド Σ 上の基本関係の集合を特定することによって決まる。任意のモノイドは、自由モノイド Σ 上の(有限個の)二項関係を積と両立するように拡張して得られる同値関係(モノイド合同)で Σ を割って得られる商モノイドである。

実際、二項関係 R ⊂ Σ × Σ が与えられたとき、R の対称閉包 RR−1

(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}

で定義される対称的関係 E ⊂ Σ × Σ に拡張できる。この E

(x, y) ∈ E かつ (x′, y′) ∈ E ならば (xx′, yy′) ∈ E

をみたし、さらに反射閉包および推移閉包をとることにより、モノイド合同が得られる。

典型的な状況では、関係 R は単に関係式の集合 R = {u1 = v1, ..., un = vn} として与えられ、例えば

\langle p,q \mid pq=1\rangle

双巡回モノイド英語版の生成元と基本関係式による表示であり、また

\langle a,b \mid aba=baa, bba=bab\rangle

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

圏論との関係[編集]

集合 S に対して、 S から S への写像全体 Map(S, S) は写像の合成を二項演算、恒等写像を単位元としてモノイドになる。

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

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

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

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

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

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

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

計算機科学におけるモノイド[編集]

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

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

\mathrm{fold}\colon M^{*} \to M
\mathrm{fold}\, l = \begin{cases}
  \varepsilon & \text{if } l = \mathrm{nil} \\
  m \bullet \mathrm{fold}\, l' & \mbox{if } l = \mathrm{cons}\, m \, l' 
\end{cases}

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

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

関連項目[編集]

[編集]

  1. ^ 用語を流用しているだけでの項で扱われている意味での「積」とは無関係であることに注意。特にここでいう「積」は和を繰り返したもの(反復和)の意味ではないので、和が定義されている必要も無い。
  2. ^ 与えられたモノイドの元からなる文字集合 N から有限文字列全体を取り出す操作(ただし連接をモノイドの積で置き換える)を、その文字集合 N の生成するクリーネ閉包 Nと呼び、"∗" で表すためクリーネスターとも呼ばれる 。ただし、クリーネ閉包構成は一般には(もともと)形式言語の範疇で考えられるもっと広い概念である。
  3. ^ この名称は、逆半群 (inverse semi-group) であるようなモノイドとややこしい
  4. ^ 半群として、逆半群となるようなモノイドということ。逆半群は山田半群とも言われる(田村 1972)。

参考文献[編集]

  1. ^ Jacobson (2009), p. 29, examples 1, 2, 4 & 5.
  2. ^ Jacobson (2009), p. 35.
  3. ^ Jacobson, I.5. p. 22

外部リンク[編集]