モノイド

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
マグマグループの間の代数的構造たとえば、モノイドは同一性を持つ半群です。

数学の一分野である抽象代数ではモノイドは結合二項演算単位元を備えた集合です。

モノイドはアイデンティティを持つ半群です。このような代数的構造は、数学のいくつかの分野で発生します。

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

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

理論計算機科学では、モノイドの研究はオートマトン理論クローン・ロードス理論)と形式言語理論(クリーネ閉包の問題)の基本です。

主題の歴史、およびモノイドの他のいくつかの一般的な特性については、 半群を参照してください。

定義

二項演算S × SSを備え集合 Sは、次の2つの公理を満たす場合 モノイドです。

連想性
Sのすべてのab、およびcについて、式ab)• c = a •(bcが成り立ちます。
単位元
Sには要素eが存在し、Sすべての要素aについて、方程式ea = aおよびae = aが成り立ちます。

言い換えれば、モノイドは単位元を持つ半群です。それはまた、結合性とアイデンティティを備えたマグマと考えることもできます。モノイドの単位元は一意です。[1] このため、IDは定数、つまり0-ary(またはnullary)演算と見なされます。したがって、モノイドはトリプルS、•、e)の指定によって特徴付けられます。

コンテキストによっては、二項演算の記号が省略される場合があるため、演算は並置で示されます。たとえば、モノイド公理はabc = abcおよびea = ae = aと書くことができます。この表記は、数値が乗算されていることを意味するものではありません。

各要素が逆を持つモノイドはグループです

モノイド構造

サブモノイド

モノイドサブモノイドM、•)、モノイド演算の下で閉じられ、Mの単位元e含むMのサブセット Nです[2] [3]象徴的にx 、 y∈Nおよびe∈Nの場合は常にN⊆Mxy∈N場合NMサブモノイドですこの場合、NMから継承された二項演算のモノイドです。

一方、Nがモノイド操作で閉じられるモノイドのサブセットであり、この継承された操作のモノイドである場合、単位元が異なる可能性があるため、 Nは必ずしもサブモノイドであるとは限りません。たとえば、単集合 {0}は乗算で閉じられ、非負の整数の(乗法)モノイドのサブモノイドではありません

ジェネレーター

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

可換モノイド

動作が可換であるモノイドは、可換モノイド(または、あまり一般的ではありませんが、アーベルモノイド)と呼ばれます。可換モノイドはしばしば相加的に書かれます。可換モノイドにはx + z = yなるzが存在する場合、 x≤yで定義される代数的 前順序 が与えられます。[4]可換モノイドM次数単位は、 Mの要素uであり、Mの任意の要素xに対してx≤vなるようにuによって生成されたセットにvが存在します。これは、Mが半順序アーベル群Gの正円錐である場合によく使用されます。この場合、 uGの順序単位であると言います。

部分可換モノイド

すべての要素ではなく一部の要素で操作が可換であるモノイドは、半アーベルモノイドです。トレースモノイドは、一般的に並行計算の理論で発生します。

  • 16の可能なバイナリブール演算子のうち、両面単位元を持つ4つの演算子のそれぞれも可換で結合的であるため、集合{False、True}は可換モノイドになります。標準の定義では、ANDXNORのIDはTrueであり、XORORのIDはFalseです。ANDとORのモノイドもべき等ですが、XORとXNORのモノイドはそうではありません。
  • 自然数のセット は、加算(単位元0)または乗算(単位元1 )中の可換モノイドです。加算中のNのサブモノイドは数値モノイドと呼ばれます。
  • 正の整数のセット 乗算中の可換モノイド(単位元1)です。
  • セットAが与えられると、Aのサブセットのセットは、共通部分の下の可換モノイドです(単位元はA自体です)。
  • 集合Aが与えられると、 Aのサブセットの集合は、和集合の下で可換モノイドになります(単位元は空集合です)。
  • 前の例を一般化すると、すべての有界半束はべき可換モノイドです。
  • 二項演算で閉じられたすべての単集合 { x }は、•自明群でもある自明(1要素)モノイドを形成します
  • すべてのグループはモノイドであり、すべてのアーベル群は可換モノイドです。
  • 任意の半群 Sは、 Sにない要素eを隣接させ、すべてs∈Sに対してes = s = seを定義するだけでモノイドに変えることができます。半群からモノイドへのこの変換は、半群のカテゴリーとモノイドのカテゴリーの間のフリーファンクターによって行われます。[5]
    • したがって、べき等モノイド(find-firstとしても知られる)は、集合S上の左ゼロ半群に単位元eを隣接させることによって形成される場合があります反対のモノイド( find-lastと呼ばれることもあります)は、 S上の右零半群から形成されます。
      • 2つの要素{lt、gt}を使用して、単位元eを左ゼロ半群に隣接させます。次に、結果として得られるべき等モノイド{lt、e、gt}は、要素の順序が与えられたシーケンスの辞書式順序をモデル化します。eは等式を表します。
  • 演算として加算または乗算を使用した、任意のリングの基になるセット。(定義上、リングには乗法的なアイデンティティがあります1。)
  • いくつかの固定アルファベットΣ上のすべての有限文字列のセットは、操作として文字列連結を持つモノイドを形成します。の文字列はID要素として機能します。このモノイドはΣ で表され、 Σ上自由モノイドと呼ばれます。可換ではありません。
  • 任意のモノイドMが与えられると、反対のモノイド M opはMと同じキャリアセットと単位元を持ち、その操作はxop y = yxによって定義されます。可換モノイドは、それ自体の反対のモノイドです。
  • モノイド構造(または、一般に、任意の有限数のモノイド、M 1、…、M kを備えた2つのセットMおよびNが与えられると、それらのデカルト積M × Nもモノイドです(それぞれ、M 1 ×⋯× M k)。連想演算と単位元はペアで定義されます。[7]
  • モノイドMを修正します。与えられたセットからMまでのすべての関数のセットもモノイドです。単位元は、任意の値をMの単位元にマッピングする定数関数です。結合演算は点ごとに定義されます
  • 演算と単位元eを使用してモノイドMを修正し、 Mのすべてのサブセットで構成されるべき集合PMを検討します。このようなサブセットの二項演算は、ST = { st  :s∈St∈T }定義できますこれにより、PM)が単位元{ e }を持つモノイドに変わります。 同様に、群Gのべき集合は、群の部分集合の積の下にあるモノイドです。
  • Sを集合とします。すべての関数のセットSSは、関数合成の下でモノイドを形成しますアイデンティティは単なるアイデンティティ関数です。Sの完全変換モノイドも呼ばれます。Sn個の要素で有限である場合、 S上の関数のモノイドはnnの要素で有限です。
  • 前の例を一般化して、CカテゴリXをCのオブジェクトとしますエンドCXで表されるXのすべての自己準同型の集合は、の合成の下でモノイドを形成します。圏論とモノイドの関係の詳細については、以下を参照してください。
  • 連結和を持つコンパクトな表面の同相写像 クラスセットその単位要素は通常の2球のクラスです。さらに、aがトーラスのクラスを示しbが射影平面のクラスを示す場合、モノイドのすべての要素cは、 c = na + mbという形式の一意の式を持ちます。ここで、nは正の整数、m = 0です。 1、または23 b = a + bがあります。
  • させて次数nの環状モノイド、つまりそれでいくつかのための実際、そのような各kは、次数nの別個のモノイドを与え、すべての巡回モノイドはこれらの1つと同型です。
    さらに、fは点の関数と見なすことができますによって与えられた
または、同等に
の要素の乗算次に、関数の合成によって与えられます。
いつその場合、関数fは次の順列です。そして位数nの一意の巡回群を与えます。

プロパティ

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

製品とパワー

非負の整数nごとに、積を定義できます。任意のシーケンスのモノイドn個要素を再帰的に:p 0 = eとし、p m = p m −1am1≤m≤nます。

特別な場合として、モノイドの要素xの非負の整数乗を定義できます。x0 = 1およびxn = x n −1 x n≥1場合次にすべてmn≥0に対してx m + n = xmxn

可逆要素

xy = eおよびyx = eのような要素yが存在する場合、要素xは可逆と呼ばれます要素yxの逆数と呼ばれます。逆元が存在する場合、それは一意です。yzxの逆元である場合、結合法則によりy = ey =(zxy = zxy)= ze = z[8]

xが可逆である場合、たとえば逆y場合、各n≥1に対してx n = y nを設定することにより、 xの負の累乗を定義できますこれにより、方程式x m + n = xm xnがすべてmn∈Zに対して成り立ちます

モノイド内のすべての可逆要素のセットは、操作•とともに、グループを形成します。

グロタンディーク群

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

モノイドM、•)は、Mのすべてのab、およびcについて、等式ab = acがb = cを意味し、等式ba = c •である場合、キャンセル特性を持ちます(またはキャンセル可能です) 。 aはb = cを意味します

キャンセルプロパティを持つ可換モノイドは、グロタンディーク群の構築を介して常にグループに埋め込むことができます。このようにして、整数の加法群(演算+を持つ群)は、自然数の加法モノイド(演算+と簡約律を持つ可換モノイド)から構築されます。ただし、非可換のキャンセル可能なモノイドは、グループに埋め込むことができる必要はありません。

モノイドがキャンセル特性を持ち、有限である場合、それは実際にはグループです。[9]

モノイドの右と左のキャンセル要素は、それぞれサブモノイドを形成します(つまり、操作の下で閉じられ、明らかに単位元が含まれます)。これは、可換モノイドのキャンセル要素をグループに拡張できることを意味します。

グロタンディーク群の構築を実行するために、モノイドのキャンセル特性は必要ありません。可換性は十分です。ただし、可換モノイドにキャンセル特性がない場合、グロタンディーク群へのモノイドの準同型は単射ではありません。より正確には、ab = acの場合、 bcであっても、 bcはグロタンディーク群で同じイメージを持ちます特に、モノイドが吸収元を持っている場合、そのグロタンディーク群は自明群です。

モノイドの種類

逆モノイドは、Mのすべてaに対して、a = aa -1aおよびa -1 = a -1aa -1のような一意のa -1Mに存在するモノイドです。逆モノイドがキャンセル可能である場合、それはグループです。

反対の方向では、ゼロサムフリーモノイドは加法的に書かれたモノイドであり、a + b = 0はa = 0およびb = 0[10]を意味し、ゼロ以外の要素には反数がありません。

行為と演算子のモノイド

Mをモノイドとします。二項演算は•で示され、単位元はeで示されます。次に、(左)M -act(またはM上の左act は、次のようにモノイド構造と互換性 のある操作⋅:M × XXを伴う集合Xです。

  • Xすべてxに対してe⋅x = x ;
  • すべてのabMxX場合:a⋅(b⋅x =(ab ⋅x

これは、(左)群作用のモノイド理論の類似物です。右のM -actsも同様の方法で定義されます。行為を伴うモノイドは、演算子モノイドとしても知られています。重要な例には、半自動の遷移システムが含まれます変換半群は、恒等変換に隣接することにより、演算子モノイドにすることができます

モノイド準同型

N、+、0)からN、×、1)までモノイド準同型x↦2xの例。それは単射ですが、全射ではありません。

2つのモノイドM、∗)N、•)の間の準同型は、次のような関数f  :MNです 。

  • fxy)= fx)• fy for all x y in M
  • fe M)= e N

ここで、 eMeNは、それぞれMNのIDですモノイド準同型は、単にモノイド射と呼ばれることもあります。

モノイド間のすべての半群準同型が準同型であるとは限りません。これは、アイデンティティが準同型のイメージのアイデンティティであっても、ターゲットのモノイドのアイデンティティにアイデンティティをマッピングできない場合があるためです。[11]たとえば、、モジュロ剰余クラスのセット掛け算を装備。特に、のクラスアイデンティティです。関数によって与えられたは半群準同型であるしかし、したがって、モノイド準同型は、最初のモノイドのアイデンティティを2番目のモノイドのアイデンティティにマッピングするモノイド間の半群準同型であり、後者の条件は省略できません。

対照的に、グループ間の半群準同型は、必然的に同一性を保持するため、常に群準同型です(グループ内では、同一性はxx = xとなる唯一の要素であるため)。

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

等式プレゼンテーション

モノイドは、グループプレゼンテーションによってグループを指定できるのとほぼ同じ方法で、プレゼンテーションを行うことができます。これを行うには、生成元Σのセットと、自由モノイドΣ の関係のセットを指定します。これを行うには、Σ の(有限の)二元関係をモノイド合同に拡張し、上記のように商モノイドを構築します。

バイナリ関係R⊂Σ ×Σ が与えられると、その対称閉包をR∪R−1と定義ますこれいくつ文字uvst∈Σ with uv _ _ _ _ _ _ _ _ _ _ _ _ _ ∈R∪R 1最後に、Eの反射的で推移的な閉包を取ります。これは、モノイドの合同です。

典型的な状況では、関係Rは単純に方程式のセットとして与えられるため、次のようになります。したがって、たとえば、

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

次数2プラクティックモノイドです(無限の位数を持ちます)。このプラクティックモノイドの要素は次のように書くことができます整数ijkの場合、関係はbaがabの両方で通勤することを示しています。

圏論との関係

グループのような構造
全体α 連想性 身元 可逆性 可換性
セミグループイド 不要 必須 不要 不要 不要
小カテゴリ 不要 必須 必須 不要 不要
亜群 不要 必須 必須 必須 不要
マグマ 必須 不要 不要 不要 不要
準群 必須 不要 不要 必須 不要
単位的多元環 必須 不要 必須 不要 不要
セミグループ 必須 必須 不要 不要 不要
ループ 必須 不要 必須 必須 不要
逆半群 必須 必須 不要 必須 不要
モノイド 必須 必須 必須 不要 不要
可換モノイド 必須 必須 必須 不要 必須
グループ 必須 必須 必須 必須 不要
アーベル群 必須 必須 必須 必須 必須
多くの閉包公理は同等です。

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

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

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

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

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

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

カテゴリ内のモノイドとは何かの抽象的な定義であるモノイドオブジェクトの概念もあります。Set内のモノイドオブジェクトは単なるモノイドです。

コンピュータサイエンスのモノイド

コンピュータサイエンスでは、多くの抽象データ型にモノイド構造を与えることができます。一般的なパターンでは、モノイドの一連の要素が「折りたたまれ」または「蓄積」されて、最終的な値が生成されます。たとえば、多くの反復アルゴリズムでは、反復ごとにある種の「現在の合計」を更新する必要があります。このパターンは、モノイド操作によってエレガントに表現できます。あるいは、モノイド操作の結合性により、複数のコアまたはプロセッサーを効率的に利用するために、 プレフィックス合計または同様のアルゴリズムを使用して操作を並列化できることが保証されます。

単位元を持つタイプMの値のシーケンスが与えられますおよび連想演算折り畳み操作は次のように定義されます。

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

MapReduce

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

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

完全なモノイド

完全モノイドは、無限和演算を備えた可換モノイドです[13] [14] [15] [16]のようなインデックスセット Iの場合

順序付けられた可換モノイドは、すべてa∈Mに対してa≥0となるような半順序を持つ可換モノイドMでありa≤bすべてのabc∈Mに対してa + c≤b + c意味ます

連続モノイドは、すべての有向サブセット最小の上限を持ち、これらの最小の上限がモノイド操作と互換性が ある、順序付けられた可換モノイドM、≤)です。

すべてa∈MおよびMの有向サブセットSに対して

M、≤)が連続モノイドである場合、任意のインデックスセットIおよび要素のコレクションa ii∈Iに対して、のように定義できます。

Mは、この無限和演算とともに完全なモノイドです。[16]

も参照してください

メモ

  1. ^ e1e2の両方が上記の満たす場合e 1 = e1 e2 = e2
  2. ^ ジェイコブソン2009
  3. ^ 一部の作成者は、サブモノイドがその定義から単位元を含まなければならないという要件を省略し、 Mの単位元とは異なる単位元を持っていることだけを要求しています。
  4. ^ ゴンドラン、ミシェル; Minoux、Michel(2008)。グラフ、ダイオイド、セミリング:新しいモデルとアルゴリズムオペレーションズリサーチ/コンピュータサイエンスインターフェイスシリーズ。41.ドルドレヒト:Springer-Verlagp。13. ISBN 978-0-387-75450-5Zbl1201.16038 _
  5. ^ ロードス、ジョン; スタインバーグ、ベンジャミン(2009)、有限セミグループのq理論:新しいアプローチ、数学におけるスプリンガーモノグラフ、vol。71、Springer、p。22、ISBN 9780387097817
  6. ^ Jacobson 2009、p。29、例1、2、4、5。
  7. ^ Jacobson 2009、p。35。
  8. ^ ジェイコブソン、I.5。p。22
  9. ^ 証明:モノイドの要素xを修正します。モノイドは有限でため、いくつかのm > n > 0に対してxn = xmです。しかし、キャンセルすると、 x mn = eとなります。ここで、 eはアイデンティティです。したがって、 xx mn − 1 = eであるため、 xは逆になります。
  10. ^ Wehrung、Friedrich(1996)。「補間を伴う構造のテンソル積」パシフィックジャーナルオブ数学176(1):267–285。土井10.2140 /pjm.1996.176.267Zbl0865.06010_ 
  11. ^ fx)* fe M)= fx * e M)= fxMの各xについて、f半群準同型であり、eMその定義域モノイドMの単位元である場合
  12. ^ a b c Awodey、Steve(2006)。圏論オックスフォードロジックガイド。49.オックスフォード大学出版局p。10. ISBN 0-19-856861-4Zbl1100.18001 _
  13. ^ Droste、M。、およびKuich、W。(2009)。セミリングと形式的べき級数。加重オートマトンのハンドブック、3–28。土井 10.1007 / 978-3-642-01492-5_1
  14. ^ Hebisch、Udo(1992)。「EinealgebraischeTheorie unendlicher Summen mit Anwendungen auf HalbgruppenundHalbringe」。Bayreuther Mathematische Schriften(ドイツ語)。40:21–152。Zbl0747.08005_ 
  15. ^ Kuich、Werner(1990)。「ω-連続半環、代数システム、プッシュダウンオートマトン」パターソンでは、マイケルS.(編)。Automata、Languages and Programming:17th International Colloquium、Warwick University、England、July 16-20、1990、Proceedingsコンピュータサイエンスの講義ノート。443.Springer -Verlagpp。103–110  _ ISBN 3-540-52826-1
  16. ^ a b Kuich、Werner(2011)。「代数システムとプッシュダウンオートマトン」。Kuichでは、Werner(ed。)コンピュータサイエンスにおける代数の基礎。シメオン・ボザパリディスの引退の際に捧げられたエッセイコンピュータサイエンスの講義ノート。7020.ベルリン:Springer-Verlagpp。228–256。ISBN 978-3-642-24896-2Zbl1251.68135 _

参考文献

外部リンク