セミグループアクション

代数学および理論計算機科学において、半群の集合に対する作用または動作とは、半群の各要素に集合の変換を関連付ける規則であり、半群の 2 つの要素の積 (半群演算を使用)が、対応する 2 つの変換の合成に関連付けられます。この用語は、半群の要素が集合の変換として動作しているという考えを伝えます。代数の観点から見ると、半群作用は群論における群作用の概念を一般化したものです。計算機科学の観点から見ると、半群作用はオートマトンと密接に関連しています。集合はオートマトンの状態をモデル化し、動作は入力に応答したその状態の変換をモデル化します。

重要な特殊なケースはモノイド作用または行為であり、半群はモノイドであり、モノイドの単位元は集合の単位変換として機能します。カテゴリ理論の観点からは、モノイドは1つのオブジェクトを持つカテゴリであり、行為はそのカテゴリから集合のカテゴリへの関数です。これにより、集合のカテゴリ以外のカテゴリのオブジェクトに対するモノイド作用への一般化が直ちに提供されます。

もう一つの重要な特殊なケースは、変換半群です。これは集合の変換の半群であり、したがってその集合に対してトートロジー作用を持ちます。この概念は、ケーリーの定理の類似物によって、より一般的な半群の概念に結び付けられています。

(用語に関する注意: この分野で使用される用語は、著者によって大きく異なる場合があります。詳細については記事を参照してください。)

S を半群とする。このとき、 Sの (左)半群作用(または行為) は、集合Xと、半群作用∗ と互換性のある作用• : S × X → Xを組み合わせたものである。

• すべてのs、Sに含まれるt、Xに含まれるxについて、s • ( t • x ) = ( s ∗ t ) • xです。

これは半群論における（左）群作用の類似物であり、X上の関数の集合への半群準同型と同等です。右半群作用は、同様の方法で、( x • a ) • b = x • ( a ∗ b )を満たす演算• : X × S → Xを使用して定義されます。

Mがモノイドである場合、 Mの（左）モノイド作用（または作用）は、 Mの（左）半群作用であり、さらに次の性質を持つ。

• X内の任意のxについて: e • x = x

ここで、e はMの単位元です。これにより、モノイド準同型が得られます。右モノイドの作用も同様の方法で定義されます。集合に対する作用を持つモノイドM は、演算子モノイドとも呼ばれます。

SのXへの半群作用は、半群に恒等変換を付加し、それがX上の恒等変換として作用することを要求することによって、モノイド作用にすることができます。

Sが半群またはモノイドである場合、 Sが上（たとえば左側）に作用する集合X は、（左） S作用、S集合、S作用、S被演算子、またはS上の左作用とも呼ばれます。著者の中には、恒等元が存在しない場合に恒等公理（e • x = x ）を空と見なしたり、恒等元を持つS作用にユニタリS作用という用語を使用したりして、半群作用とモノイド作用を区別しない人もいます。^[1]

行為の定義特性は、半群演算の結合性に類似しており、すべての括弧を省略できることを意味します。特にコンピュータ サイエンスでは、半群演算と行為の両方が並置によって示されるように、演算も省略するのが一般的です。このようにして、 Sの文字列はXに作用します。たとえば、 stx for s、t in S and x in Xという式があります。

左作用よりも右作用を扱うことも非常に一般的です。^[2]しかし、すべての右S作用は、 Sと同じ要素を持つ反対の半群上の左作用として解釈できますが、乗算は因数を逆にすることによって定義され、s • t = t • sであるため、2つの概念は本質的に同等です。ここでは、主に左作用の観点を採用します。

機能を表すために、 などの文字を使用すると便利な場合が多い（例えば、検討対象の行為が複数ある場合）。${\displaystyle T}$

${\displaystyle T\colon S\times X\to X}$

作用を定義し、の代わりに と書きます。すると内の任意の に対して、 と書きます。 ${\displaystyle S}$${\displaystyle T(s,x)}$${\displaystyle s\cdot x}$${\displaystyle s}$${\displaystyle S}$

${\displaystyle T_{s}\colon X\to X}$

定義 による変換${\displaystyle X}$

${\displaystyle T_{s}(x)=T(s,x).}$

- 行為の定義特性により、${\displaystyle S}$${\displaystyle T}$

${\displaystyle T_{s*t}=T_{s}\circ T_{t}.}$

さらに、関数 を考えてみましょう。これは と同じです（カリー化 を参照）。は一対一なので、半群作用は、 ${\displaystyle s\mapsto T_{s}}$${\displaystyle \operatorname {curry} (T):S\to (X\to X)}$${\displaystyle \operatorname {curry} }$${\displaystyle S\to (X\to X)}$

${\displaystyle \operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).}$

つまり、 がのへの半群作用である場合、かつ がから の完全変換モノイドへの半群準同型である場合に限ります。 ${\displaystyle T}$${\displaystyle S}$${\displaystyle X}$${\displaystyle \operatorname {curry} (T)}$${\displaystyle S}$${\displaystyle X}$

XとX ′をS-作用とする。すると、XからX ′へのS-準同型写像は

${\displaystyle F\colon X\to X'}$

そのような

${\displaystyle F(sx)=sF(x)}$すべておよびについて。${\displaystyle s\in S}$${\displaystyle x\in X}$

このようなS準同型全体の集合は、一般に と表記されます。 ${\displaystyle \mathrm {Hom} _{S}(X,X')}$

Mがモノイドである場合、M行為のM準同型はまったく同じ方法で定義されます。

固定された半群Sに対して、左S -作用はS -Actと表記されるカテゴリの対象であり、その射はS -準同型である。右S -作用の対応するカテゴリはAct- Sと表記されることもある。(これは、環上の左および右加群のカテゴリR -Mod および Mod- Rに類似している。)

モノイドMの場合、カテゴリM -Act と Act- Mも同様に定義されます。

• 任意の半群は（ ）に対して作用を持ちます。 の結合法則により、作用の性質が成り立ちます。${\displaystyle (S,*)}$${\displaystyle S}$${\displaystyle \cdot =*}$${\displaystyle *}$
• より一般的には、任意の半群準同型 に対して、半群はによって与えられるへの作用を持ちます。${\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}$${\displaystyle (S,*)}$${\displaystyle T}$${\displaystyle s\cdot t=F(s)\oplus t}$
• 任意の集合 に対して、を の要素の列の集合とします。半群に対する作用はによって与えられます(ここで は繰り返し回数を表します)。${\displaystyle X}$${\displaystyle X^{*}}$${\displaystyle X}$${\displaystyle (\mathbb {N} ,\times )}$${\displaystyle X^{*}}$${\displaystyle n\cdot s=s^{n}}$${\displaystyle s^{n}}$${\displaystyle s}$${\displaystyle n}$
• 半群には、 によって与えられる右作用 があります。${\displaystyle (\mathbb {N} ,\times )}$${\displaystyle (\mathbb {N} ,\cdot )}$${\displaystyle x\cdot y=x^{y}}$

変換半群と半群作用の対応関係は以下のように記述されます。これを忠実な半群作用に限定すると、優れた特性を持ちます。

任意の変換半群は、次の構成によって半群作用に変換できます。の任意の変換半群に対して、に対するの半群作用を について定義します。この作用は忠実であり、 が単射であることと同等です。 ${\displaystyle S}$${\displaystyle X}$${\displaystyle T}$${\displaystyle S}$${\displaystyle X}$${\displaystyle T(s,x)=s(x)}$${\displaystyle s\in S,x\in X}$${\displaystyle カレー(T)}$

逆に、 の任意の半群作用に対して、変換半群を定義します。この構成では、集合 を「忘れます」。は の像に等しいです。簡潔にするためにを として表記します。 が に単射である場合、 はからへの半群同型です。言い換えると、が忠実である場合、重要なことは何も忘れていません。この主張は、次の観察によって明確になります。の半群作用に戻ると、すべての に対して となります。とは を介し​​て「同型」です。つまり、本質的に を回復しました。したがって、一部の著者^[3]は、忠実な半群作用と変換半群を区別しないと考えています。 ${\displaystyle T}$${\displaystyle S}$${\displaystyle X}$${\displaystyle S'=\{T_{s}\mid s\in S\}}$${\displaystyle S}$${\displaystyle S'}$${\displaystyle カレー(T)}$${\displaystyle カレー(T)}$${\displaystyle f}$${\displaystyle f}$${\displaystyle S}$${\displaystyle S'}$${\displaystyle T}$${\displaystyle S'}$${\displaystyle T'}$${\displaystyle S'}$${\displaystyle X}$${\displaystyle T'(f(s),x)=T(s,x)}$${\displaystyle s\in S,x\in X}$${\displaystyle T}$${\displaystyle T'}$${\displaystyle f}$${\displaystyle T}$

変換半群は、オートマトン理論における有限状態機械の構造理論にとって極めて重要である。特に、半オートマトンとは三つ組（Σ、X、T ）であり、Σは入力アルファベットと呼ばれる空でない集合、Xは状態集合と呼ばれる空でない集合、Tは関数である。

${\displaystyle T\colon \Sigma \times X\to X}$

遷移関数と呼ばれる。半オートマトンとは、初期状態と受け入れ状態のセットを無視することで 決定論的オートマトンから生成されるものである。

セミオートマトンが与えられたとき、a ∈ Σに対してT _a : X → X を、 T _a ( x ) = T ( a , x )で定義されるXの変換を表すものとする。すると、{ T _a  : a ∈ Σ}によって生成されるXの変換の半群は、 (Σ, X , T ) の特性半群または遷移システムと呼ばれる。この半群はモノイドであるため、このモノイドは特性モノイドまたは遷移モノイドと呼ばれる。これは、 Xに対するΣ ^∗作用とみなされることもある。ここで、 Σ ^{∗ は}、アルファベット Σ によって生成される文字列の自由モノイドであり、 ^{[注 1]}文字列の作用は、次の性質を介して Σ の作用を拡張する。

${\displaystyle T_{vw}=T_{w}\circ T_{v}.}$

クローン・ローズ理論は代数オートマトン理論とも呼ばれ、より単純な要素をカスケード接続することで有限変換半群の強力な分解結果を提供します。

• AH CliffordとGB Preston (1961)、「半群の代数理論」、第 1 巻。アメリカ数学会、ISBN 978-0-8218-0272-4。 
• AH Clifford と GB Preston (1967)、「半群の代数理論」、第 2 巻。アメリカ数学会、ISBN 978-0-8218-0272-4。 
• Mati Kilp、Ulrich Knauer、Alexander V. Mikhalev (2000)、「モノイド、行為、カテゴリ：リース積とグラフへの応用」、Expositions in Mathematics 29、Walter de Gruyter、ベルリン、ISBN 978-3-11-015248-7。 
• ルドルフ・リドルとギュンター・ピルツ、応用抽象代数(1998)、シュプリンガー、ISBN 978-0-387-98290-8