半群

数学における半群（はんぐん、英: semigroup）は、集合 S とその上の結合的二項演算とをあわせて考えた代数的構造である。言い換えれば、半群とは演算が結合的なマグマである。「半群」という名は群に由来する。群と異なり半群では、単位元が存在するとは限らず、また各元は必ずしも逆元を持たない。 半群の演算は多くの場合乗法的に書く（順序対 (x, y) に演算を施した結果を x • y あるいは単に xy と表す）。 半群について本格的な研究が行われるようになるのは20世紀に入ってからである。半群は、「無記憶」系 ("memoryless" system) すなわち各反復時点でゼロから開始される時間依存系 (time-dependent system) の抽象代数的な定式化の基盤であり、数学の様々な分野において重要な概念となっている。応用数学においては、半群は線型時間不変系（英語版）の基本モデルである。また偏微分方程式論では、半群は空間発展的かつ時間非依存な任意の方程式に対応している。有限半群論は1950年代以降、有限半群と有限オートマトンとの間の自然な関連性から、理論計算機科学の分野で特に重要となっている。確率論では半群はマルコフ過程に関連付けられる (Feller 1971)。 集合 S とその上の二項演算 • : S × S → S の対 (S, • ) が以下の条件を満たすとき、これを半群という。 結合律 S の各元 a, b, c に対して、等式 (a • b) • c = a • (b • c) が成り立つ。 S を半群 (S, •) の台集合とよぶ。また誤解のおそれがなければ「半群 S」のように台集合と同じ記号で半群を表す。 台集合が有限集合である半群を有限半群 (finite semigroup) または有限位数を持つ半群 (semigroup with finite order)、台集合が無限集合である半群を無限半群 (infinite semigroup) または無限位数を持つ半群 (semigroup with infinite order)という。 空半群: 空集合は空写像を演算として半群を成す。半群の定義に台集合が空でないことを課して、空半群を除外することもある。 一元半群: 一元集合 {a} に aa = a で演算を定めたものは、ただひとつの元からなる半群となる。これは（同型の違いを除けば）本質的に一つしか存在しない。しばしばこれを自明半群 (trivial semigroup) と呼ぶ。 二元半群: 台集合が2元からなる半群は同型を除いて5種類の異なったものが存在する。 正の整数全体の成す集合 N は加法に関して半群を成す。 非負正方行列（すべての成分が非負であるような正方行列）の全体に行列の積を与えたものは半群を成す。 第一列が全て0であるような2次正方行列全体に行列の積を与えたものは半群を成す。 任意の環のイデアルは環の乗法に関する半群である。 文字集合 Σ を固定して、その上の有限文字列全体を考えると、文字列の連接を演算とする半群が得られる。これを Σ 上の自由半群という。空文字列をも含めて考えるとこの半群は Σ 上の自由モノイドとなる。 確率分布 F に対して、F の畳み込み冪全体の成す集合に畳み込みを演算として考えたものは半群を成す。これは畳み込み半群 (convolution semigroup) と呼ばれる。 任意のモノイドは単位元を持つ半群である。 任意の群は各元が逆元を持つモノイドである。 繰り込み群は、繰り込み変換からなる半群である（群ではないが慣用的にこのように呼ばれる）。 任意の半群が持つことのできる単位元は高々ひとつである（これは任意のマグマについても成り立つ）。単位元を持つ半群は、単位的半群あるいはモノイドと呼ばれる。半群 S にS のどの元とも異なる元 e を添加して S ∪ {e} の各元 s に対して es = se = s と定めることによって、半群をモノイドに埋め込むことができる。S に単位元を添加して得られるモノイドを S1 で表し、S の単位元添加あるいは 1-添加と呼ぶ（誤解のおそれがなければ、S の 1-添加も同じ記号 S で表すこともある）。したがって、任意の可換半群をグロタンディーク構成を通じて群に埋め込むことができる。 任意のマグマが持ちうる吸収元は高々一つであり、半群ではそれを零元と呼ぶ。零元を持たない半群 S に S に属さない元 0 を添加して、零元付き半群 S0 に S を埋め込むことができる。S0 を S の零元添加あるいは 0-添加と呼ぶ。 半群 (S, ∗) の部分集合 A, B が与えられたとき、A ∗ B （あるいは単に AB） で表される S の部分集合を A B := { a b ∣ a ∈ A , b ∈ B } {\displaystyle AB:=\{ab\mid a\in A,\,b\in B\}} と定める。この記法を用いれば、半群 S の部分集合 A について A が S の部分半群 (subsemigroup) であるとは、AA ⊂ A であることを言う。 A が S の右イデアル (right ideal) であるとは、AS ⊂ A であることを言う。 A が S の左イデアル (left ideal) であるとは、SA ⊂ A であることを言う。 A が左イデアルかつ右イデアルであるとき、A を両側イデアル (two-sided ideal) あるいは単にイデアル (ideal) と言う。 半群 S の部分半群からなる族の交わりは再び S の部分半群となる。すなわち、S の部分半群の全体は完備束を成す。 極小イデアル（包含関係に関して極小なイデアル）を持たない半群の例は、正の整数全体が加法に関して成す半群 N である。可換半群の極小イデアルは（存在するならば）群を成す。 元をそれが生成する主イデアルの言葉で特徴付ける、五つの同値関係からなるグリーンの関係式（英語版）は半群のイデアルや関連する構造概念を調べる重要な道具である。 半群の準同型 (semigroup homomorphism) とは半群構造を保つ写像のことである。2つの半群 S, T の間の写像　f: S → T が準同型であるとは、等式 f(ab) = f(a)f(b) が S の各元 a, b に対して成立することを言う。つまり（S の中で）積をとってから f で写しても、f で写してから（T のなかで）積をとっても同一の結果が得られると言うことである。半群が単位元を持つ場合でも、半群準同型は必ずしも単位元を単位元に移すとは限らない。 ふたつの半群 S, T が同型であるとは、全単射の半群準同型（すなわち半群同型写像）f: S ↔ T が存在することを言う。同型な半群は、半群として同一の構造を持つ。 半群合同 (semigroup congruence) ∼ は、半群演算と両立する同値関係である。つまり、半群合同 ∼ (⊂ S × S) は S 上の同値関係であって、かつ [x ∼ y かつ u ∼ v] ならば xu ∼ yv が S の任意の元 x, y, u, v に対して成立するものを言う。任意の同値関係と同じく半群合同 ∼ は合同類 [ a ] = { x ∈ S ∣ x ∼ a } {\displaystyle [a]=\{x\in S\mid x\sim a\}} を定めるが、さらに合同類の間の二項演算 ∘ を [ u ] ∘ [ v ] = [ u v ] {\displaystyle [u]\circ [v]=[uv]} で定めるとこれは矛盾無く定義できて半群演算となる。これにより、半群合同 ∼ による合同類の全体 S/∼ は ∘ を演算として半群を成す。この半群を剰余半群 (residue class semigroup)、商半群 (quotient semigroup, factor semigroup) などと呼ぶ。自然な写像 S → S / ∼ ; x ↦ [ x ] {\displaystyle S\to S/{\sim }\,;\;x\mapsto [x]} は全射半群準同型であり、商写像などと呼ばれる。S がモノイドならばその剰余半群は S の単位元の属する合同類を単位元とするモノイドを成す。逆に、任意の半群準同型の核は半群合同を与える。これらの結果は、普遍代数学における第一同型定理の特別な場合にほかならない。 半群の任意のイデアル I は、 x ρ y ⟺ x = y  or  x , y ∈ I {\displaystyle x\,\rho \,y\iff x=y{\text{ or }}x,y\in I} で定まる半群合同 ρ に関するリース剰余半群（英語版）として部分半群を誘導する。 S の任意の部分集合 A に対し、A を含むような S の最小の部分半群 T が存在する。この T を A が生成する (generate) 部分半群という。S の一つの元 x が（つまり単元集合 {x} が）生成する部分半群（の台集合） { xn | n は正の整数} が有限集合であるとき、x は有限な位数を持つ、あるいは位数有限 (finite order) であるといい、そうでないとき無限位数を持つあるいは位数無限 (infinite order) であるという。 半群が周期的 (periodic) あるいはねじれ半群 (torsion semigroup) であるとは、その任意の元が位数有限であるときに言う。また、ただ一つの元から生成される半群は単項生成または巡回半群であるという。巡回半群が位数無限ならばそれは正の整数全体が加法に関して成す半群に同型であり、位数有限かつ空でないならば少なくとも一つは冪等元を含まねばならない。したがって、任意の空でない周期的半群は少なくともひとつの冪等元を含む。 半群の部分半群は、それ自身が群を成すならば部分群と呼ばれる。半群の部分群と半群の冪等元の間には近しい関係が存在する。半群の各部分群はちょうど一つの冪等元を含み、それはつまり部分群の単位元である。逆に、半群の各冪等元 e に対し、e を含む極大部分群が唯一つ存在する。半群の各極大部分群は必ずこのやり方で得ることができ、したがって半群の極大部分群と冪等元との間に一対一対応がとれる。ここでの、極大部分群は群論における標準的な語法とは異なる。 位数有限の場合にはさらにいろいろなことが言える。例えば、任意の空でない有限半群は、周期的で、極小イデアルを持ち、少なくとも一つの冪等元を持つ。さらなる有限半群の構造についての議論はKrohn-Rhodes理論（英語版）の項を参照せよ。 モノイドは単位的半群である。 部分半群は半群の部分集合であって、もとの半群の演算について閉じているようなものである。部分半群が群を成すならば、それをもとの半群の部分群と呼ぶ。 帯はその演算が冪等であるような半群である。 消約半群は左消約律「ab = ac ならば b = c」かつ右消約律「ba = ca ならば b = c」を満たす半群である。 半束はその演算が冪等かつ可換な半群である。 0-単純半群 変換半群は何らかの集合上の変換からなる、写像の合成を積とする半群である。任意の有限半群 S は高々 |S| + 1 個の状態をもつ（状態）集合 Q 上の変換半群として表現することができる。S の各元 x は Q をそれ自身に写す写像 x: Q → Q であり、列 xy は Q の各元 q に対して q(xy) = (qx)y と定義される。変換の列を作る操作は明らかに結合的演算で、ここでは写像の合成と等価である。この表現は任意のオートマトンあるいは有限状態機械 (FSM) に対する基本である。 双巡回半群（英語版）（実はモノイド）は、二つの生成元 p, q が生成する自由半群を基本関係式 pq = 1 で割ったものとして得られる。 C0-半群は発展方程式の解の時間発展を表す半群である。これは解析学における半群の代表例である。 正則半群は各元 x が少なくとも一つの一般化逆元 y（xyx=x かつ yxy=y を満たす元）を持つ半群である。このとき元 x および y は「互いに逆である」("mutually inverse") ということもある。 逆半群は任意の原がちょうど一つの一般化逆元をもつような正則半群である。あるいは、正則半群が逆半群となるために必要十分な条件として、任意の二つの冪等元が互いに可換となることが挙げられる。 アフィン半群は Zd の有限生成部分半群に同型な半群である。アフィン半群は可換環論に応用を持つ。 半群 S の分数群あるいは商の群 (group of fractions) G = G(S) とは、S の元全体で生成され、S において成立する xy = z の形の等式すべてを基本関係とするような群である。商の群は S から群への射に対する普遍性を示す。 明らかに S の各元を G(S) の中の対応する生成元に写す写像が存在する。重要な問題として、この写像が埋め込みとなるような半群の特徴づけの問題がある。必ずしも埋め込みとならないことの例として、S をある集合 X の部分集合が交わりを演算として成す半群がある（実は半束を成す）。これは、S の任意の元が AA = A を満たすから G(S) の生成元もすべてそうでなければならず、したがって G(S) は自明群となっている。問題の写像 S → G(S) が埋め込みとなるためには S が消約律を満たすことが必要となるのは明らかである。S が可換ならばそれは十分条件にもなり、かつ半群のグロタンディーク群が分数群の構成を与える。非可換半群に対するこの問題は半群について本格的にあつかった最初の論文 (Suschkewitsch 1928) で追求されている。アナトリー・マルチェフ（英語版）は1937年に埋め込み可能性についての必要条件を与えている。 半群論は、偏微分方程式論においてもある種の問題の研究のために用いられる。大雑把にいえば、半群を使った手法というのは偏微分方程式をある種の函数空間上の常微分方程式とみなすことである。例えば、次のような空間的な区間 (0, 1) ⊂ R と時間 t ≥ 0 上の熱方程式の初期値/境界値問題 { ∂ t u ( t , x ) = ∂ x 2 u ( t , x ) , ( x ∈ ( 0 , 1 ) , t > 0 ) ; u ( t , x ) = 0 , ( x ∈ { 0 , 1 } , t > 0 ) ; u ( t , x ) = u 0 ( x ) , ( x ∈ ( 0 , 1 ) , t = 0 ) {\displaystyle {\begin{cases}\partial _{t}u(t,x)=\partial _{x}^{2}u(t,x),&(x\in (0,1),t>0);\\u(t,x)=0,&(x\in \{0,1\},t>0);\\u(t,x)=u_{0}(x),&(x\in (0,1),t=0)\end{cases}}} を考える。X をL2((0, 1); R) とし、A を D ( A ) = { u ∈ H 2 ( ( 0 , 1 ) ; R ) ∣ u ( 0 ) = u ( 1 ) = 0 } {\displaystyle D(A)=\{u\in H^{2}((0,1);\mathbf {R} )\mid u(0)=u(1)=0\}} を定義域とする二階微分作用素とすれば、先ほどの初期値/境界値問題は空間 X 上の常微分方程式の初期値問題 { u ˙ ( t ) = A u ( t ) ; u ( 0 ) = u 0 {\displaystyle {\begin{cases}{\dot {u}}(t)=Au(t);\\u(0)=u_{0}\end{cases}}} として解釈することができる。発見的方法のレベルでいえば、この問題の解は u(t) = exp(tA)u0 という形をしている「はず」である。しかし厳密に言えば tA の冪とは何であるかということに意味を与えなければならない。t の函数としては、exp(tA) は X から X への作用素からなる半群であり、時刻 t = t0 において初期状態 u0 をとり、任意の時刻 t において状態 u(t) = exp(tA)u0 をとるものである。このとき、作用素 A はこの半群の無限小生成作用素と呼ばれる。 半群の研究は、群や環といったより複雑な公理から決まるほかの代数的構造からすると、随分と若い。いくつかの文献 によれば、半群に対応する用語が用いられた最初はフランス語で、1904年に J.-A. de Séguier の著した Élements de la Théorie des Groupes Abstraits（『抽象群原論』）においてである。 Anton Suschkewitschは半群についてのそれなりに意味のある結果を得た最初の人で、1928年の論文 Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit（『一意可逆性の条件を外した有限群について』）で有限単純半群の構造を決定し、有限半群の極小イデアル（あるいはグリーンの関係式の J-系列）が単純であることを示した。そういったことからすれば、有限群論の基礎付けが行われるのは随分と後になってからのことで、デヴィット・リース、ジェイムス・アレクサンダー・グリーン、Evgenii Sergeevich Lyapin、アルフレッド・クリフォードおよびゴードン・プレストンらによる。最後の二者は半群論に関する二巻のモノグラフを1961年と1967年にそれぞれ出版している。1970年には『半群フォーラム』という定期刊行雑誌（現在はシュプリンガー・フェアラークが編集）が発行され、半群論全般を扱う数少ない数学雑誌の一つとなっている。 近年の在野の研究ではより分化が進んでおり、（逆半群のような）半群の重要なクラスに焦点を当てたモノグラフや、代数的オートマトン理論（特に有限オートマトン）や函数解析学における応用などに焦点を当てたものなども現れている。 半群から演算の結合性の公理を落とせば、マグマが得られる。これは 二項演算 M × M → M を備えた集合 M という意味以上のものではない。 別な方向での一般化として、n-項半群 (n-ary semigroup) あるいはn-半群 (n-semigroup)、多重項半群 (polyadic semigroup) とか多項半群 (multiary semigroup) などと呼ばれるタイプの一般化がある。これは演算のアリティを変更し、二項演算の替わりに多項演算を備えた「半群」G を考えるものである。結合律の一般化は、たとえば三項版の結合律が (abc)de = a(bcd)e = ab(cde) つまり文字列のどの隣り合う三つを括弧で括ったものも相等しい、というふうに与えられる。一般の n-項版は n + (n − 1) の長さの文字列のどの隣り合う n-項を括っても相等しいとなる。2-半群が通常の半群である。詳細は多項群（英語版） を参照