代数学の初心者に向けた半群論の理解の助け
For the understanding of semigroup theory for novices of algebra

20th Apr. 2018 (Update)
11th May 2017 (First)
半群論へ
圏論を勉強しようへ
トップページへ

趣旨(このドキュメントの目的と使用上の注意)

十分に数学の訓練を受けている大学の数学科3年生,4年生,大学院生にとっては, こちらでご紹介した A.J.Cainの本は,丁寧に書いてありますので,簡単に読めると思います.

しかし,例えば,計算機科学専攻で, 集合論などの基礎的な数学的知識はあっても,数学について十分な訓練を 受けていない場合は,ここで 出てくる諸概念を理解するのは難しいかもしれません.実は,私自身もそうです. 集合論の初歩や簡単な群論の知識はあっても,次々に出てくる 代数学の抽象概念に翻弄されてしまいます.

ここではいくつかの基本的な概念を 私なりに解説して,この本や,あるいは,他の半群に関する本を読むための一助と していただけたらと思います.

したがって,数学科の3年生以上まで苦痛に耐えた人たちや,痛みに麻痺している 人たちは,このドキュメントは 読む必要はありません.ここの説明は,かなり私の感覚に寄って説明していますし, また,(私の)既存知識の体系の中で定着するように計算機科学など他の概念との 関連も書いています.これと合わないと,もしかしたら かえって混乱するかもしれません.その場合も読むのをやめて,難しくても 教科書の内容を一つずつ理解していってください.また,申し訳ありませんが, 集合論の初歩とできれば群論の初歩もどこかほかで勉強しておいてください.

以上を要約すると,半群の概念で冗談を書きますので,付き合える人だけ読んで いってくださいということです.

半群論の諸概念(important concepts in semigroup theory

  1. Idempotent and E(S)
    半群 S の要素 e で,
    e2 = e*e = e
    を満たす要素を idempotent と言います.半群 S の中の idempotents をすべて集めたものを E(S) と書きます.典型的にはモノイド(単位元を持つ半群)の中の単位元 1 は 1*1 = 1 ですから idempotent です.idempotents は単位元に準ずる性質を持っていて,とても重要な要素です.

    例えば,e を 半群 S のidempotent とすると,S1 = eSe はモノイドで単位元は e になります.つまり,

    1. S1 = eSe は半群

      S1*S1 = eSe * eSe = e(SeS)e ⊆ eSe

      => S1 = eSe は演算で閉じているので半群

    2. e は eSe の単位元

      S1=eSe の元はみな e*x*eの形をしている.

      1. e * (e*x*e) = (e*e) * (x*e) = (e*x*e)

      2. (e*x*e) * e = (e*x) * (e*e) = (e*x*e)

      つまり e は S1 = eSe の要素のどちらから掛けても元のままであり,S1 の単位元になる.

    ということで eSe は e を単位元とするモノイドになります. ちなみに,idempotent でなくとも,∀y∈S に対して,ySy は半群ですね. これがモノイドになるかどうかが,y が idempotent かどうかに係わっているだけです.

    idempotents は,具体的にはどんな要素かと言いますと 変換モノイド Tn (つまり, {1, 2, ..., n} を自分に写すすべての写像の集合を写像の合成でモノイドと 見たもの)での

    (1 2 3 4 5)
    (1 2 3 3 2)
    などです(上の数を下の対応する場所の数に写す変換と思ってください). これは {1, 2, 3} については恒等写像で,4 と 5 は {1, 2, 3} の中に 写しています.このように領域を限った中では恒等写像でそれ以外の値はその中に 写される変換が idempotent になります.

    これは半群が適当な集合 X を取って, X → X の関数の集合に埋め込めるという Cayley の定理の半群版を考えれば,一般的に成立するということが分かります.つまり, その埋め込みで idempotent e が f : X → X に 写されるとすると,f(f(x)) = f(x) ですから,領域 f(X) ⊆ X に限って言えば,f は恒等写像になるわけです.

    idempotent は半群論の中で,これでもかというくらいよく働きますので いつも頭の片隅に置いておいてください.特に,regular 半群,inverse 半群など では,こんなに重要な概念だったのかと思います(私は思いました).ちなみに x ∈ S が regular とは x*y*x = x となる y∈Sが存在することで,このとき,x*y は

    (x*y)*(x*y) = (x*y*x)*y = (x*y)
    となり,idempotent になります.このときの idempotent が単位元に準ずる要素で, y は逆元に準ずる元なんですね.

    idempotent は,日本語では,冪等元(べきとうげん)とか巾等元(べきとうげん)と 言うようです.難しい日本語です.でも,もともと,idempotent も ラテン語系の単語なので 難しい単語(しかも後世の造語)なのかもしれません.ちなみに wikipedia を見ると C言語のヘッダファイルを idempotent に作るとは,複数回 include されても,1回だけ include されたのと同じ効果を持つように作ることだそうです.

    2017.8.31

  2. 右ゼロと右ゼロ半群(Right zeros and Right zero semigroups)
    これも重要です.計算機屋さんには特に重要な半群です.右ゼロ半群は,要は最後に適用した要素を覚えておく性質を持つわけで,これは言ってみれば計算機のメモリーですね.まず御託ですが,
    半群論の後ろの方で,Krohn-Rhodes の定理という,
    すべての有限半群は,この右ゼロ半群に単位元を加えたモノイドいくつかと群との Wreath Product(直積より少し一般的な積) に分解できる
    という定理がでてきます.つまり, 有限半群の部品となる重要な半群です.この定理はハードウェア屋さんには,
    すべての計算回路は組み合わせ回路とフリップフロップ(メモリー)回路を 組み合わせることによって実現できる
    という形でかなり常識的に身についていると思いますが,ソフトウェア屋さんには忘れ去られているような気がします.Krohn-Rhodes の定理の発表は 1963 年で,当時から,今まで,その 数学的な表現はとっつきにくいですから(Wreath Product が分かりにくいのです).

    ごたくはこれくらいにして,どんなものか書きます.

    まったく面白くない半群だと思うでしょう.ところがどっこい,これが結構役にたつのです.最初に言ったように,右ゼロ半群は計算機の分野ではメモリーとして働くのです.つまり,最後に入れた要素が結果として残っているので,これはつまり,最後に入れた値を覚えておくのと同じなわけです. さらに,これを複数個,Wreath Product で組み合わせて使うことにより,最後に掛けた要素だけでなく,最後のいくつかの演算の列,つまり,演算の履歴を表現することができます.この能力が,右ゼロ半群いくつかと群を Wreath Product で組み合わせることで, 任意の半群を埋め込むことができる理由です.

    変換半群(適当な集合 X から自分自身への写像のなすモノイドの部分半群)で右ゼロ半群を作るのは 簡単です.例えば,上の半群 {a, b} は,これらを {1, 2} → {1, 2} の関数

    a = λx.1
    b = λx.2

    λx.f(x) は,x を受け取って,f(x) を返す関数を表す.
    したがって,λx.1 は何を受け取っても 1 を返す定数関数
    とすればできます.ただし,二つの関数 f と g の積 f・g = λx.g(f(x)) とします.

  3. 左ゼロと左ゼロ半群(Left zero and Left zero semigroup)
    左ゼロおよび左ゼロ半群は右ゼロおよび右ゼロ半群の左右と逆にしたものです. したがって,2元の左ゼロ半群 {a, b} の x・y の乗法表は次のようになります.
        y
    x
    ab
    aaa
    bbb
    皆さんは,これを上に書いた右ゼロ半群のように変換半群で表現できるでしょうか? ここで変換半群で表現するとは,適当に集合 X を決めて, X → X の関数の集合として半群を表すことです.ただし,関数の積は f・g = λx.g(f(x)) とします.したがって, 具体的には次の式を満たすような集合 X と関数 fa : X → X, fb : X → X の 例を作れという問題です.

    下にある Cayley's Theorem for semigroups を知っていれば簡単なのですが,ちょっと工夫が必要です.

    解答例をここに書いておきます.

    関数はその入力と出力を逆にすると,関数にはならず「関係 (Relation) 」になるのです. これは普段あまり意識しないのですが,関数は矢を逆にしたときのいわゆる 双対が関数にならないので,双対概念が結構もとの概念と違うように見えるのです. 例えば圏論で集合の圏の initial object が空集合唯一なのに対して terminal object は 要素一個の集合すべてです.これが関係の圏ならどちらも空集合になります. この非対称性が関数の面白さでもありますね.

  4. Cayley's Theorem for semigroups
    群論では,任意の群 G は,適当な集合の置換の集合がなす群に埋め込めるという Cayley の定理がありますが,半群でも同様のものがあります.任意の半群は, 適当な変換半群に埋め込めるという定理です.もっと具体的に書けば次のようになります.
    ケイリー(Cayley)の定理の半群版
    S を半群とすると,S は関数のなす半群(実はモノイド)S1 → S1 に埋め込める.ここで,S1 は半群 S に(今無ければ)単位元 1 を追加したものである.この時の対応は s ∈ S に fs = λx.x・s を対応させるものである.
    集合として S でなく S1 を使うところがミソです.動かされるものに 1 を入れることによって,異なる s, t に対して fs(1) = s ≠t = ft と なること,つまり,Sの元を忠実に変換することを保証しているのです. この定理を使うことによって,上で書いた左ゼロ半群を作ることができると思います.

    (to fill the rest)

  5. M-Automaton
    普通の有限オートマトンに,モノイドの値ををとることができるレジスタを追加し,状態遷移が 起こるたびに,そのレジスタに,前もって遷移ごとに決めたモノイドの要素を 掛け込むことを許したオートマトンです.遷移はレジスタの値に寄ってはいけません. レジスタの値は,最後に受理するかどうかだけの判断に使います.レジスタの値を 参照して遷移することを許してしまえば,あっという間に強力すぎる能力を持った 機械になってしまいます.

    レジスタの値として採用した モノイドが有限モノイドでしたら,結局は有限オートマトンと同じ表現力しか ありませんが,無限モノイドを許すと,そのモノイドによって再帰的列挙可能 な言語の族まで受理する言語の族が広がります. M-Automaton の解説

    に, M-Automaton を簡単に説明したものがあります.当面,そちらをご参照ください.

  6. S1
    半群 S に,単位元を加えて,モノイドにしたものです.もし,すでに単位元があれば 何も加えず,そのままです.

    ということで,半群にはいつでも形式的に単位元を加えることができるので, モノイドと半群は実用上それほど区別しなくてよいと思います.

    (to fill the rest)

  7. S0
    (to fill)

  8. C(S) : Center of S
    (to fill)

  9. 可換性(Commutatibity)
    (to fill)

  10. V(x) : Inverse of x

    (to fill)

  11. イデアル(Ideal)
    環論でもイデアルはでてきますが,半群のイデアルは0の逆像と考えてよいと思います. つまり何らかの準同型で0に移る要素の集合がイデアルです.言い換えれば,0という1つの要素に つぶすことができる要素の集合であるということです.

    実際,半群Sから0のある半群Tに準同型 h : S -> T があるとすれば, I = h-1(0)は

    h(x*u*y) = h(x)*h(u)*h(y) = h(x)*0*h(y) = 0 for x, y∈S, u∈I
    ですから,x*u*y∈I ,つまり,SIS⊆Iとなり,Iはイデアルになります.

    逆に I がイデアルなら,半群SのIを0につぶした半群(Rees の商半群(factor semigroup) S/I)があり,SからS/Iへの準同型 h でI= h-1(0)のものがあります.

    ということで,イデアルは0につぶすことができる要素の集合ですね.

    ちなみに束論(lattice theory)でもイデアルは0の逆像です.また,1 の 逆像はフィルター(filter)と言います.超準解析(nonstandard analysis)などで 使うのはこのフィルターのうち,極大なものですね(超準フィルター).

    最後に,環論のイデアルは乗法に関しては半群と同じようにゼロ元(zero element)ですが, 加法に関しては単位元(unit)です.加法の単位元というと,あれ? 0ですから やっぱり,0の逆像なんですかね.

  12. イデアルとリー商半群(Ideals and Rees Factor Semigroups ) writing ...
    イデアルを0につぶした半群です.
    A Rees factor semigroup is the factor semigroup given by putting its certain ideal to single element 0.

    イデアルを取り去って,代わりに0を入れます.
    Remove the ideal and put the element 0.

  13. Ideal Extension of S by T
    リー商半群の逆です(Reverse of Rees factor semigroup).

    画像が小さくてごめんなさい.リー商半群の方をご覧ください(Sorry for the small picture. Please see the picutures for Rees factor semigroups.)

    Ideal Extension of S by T again

  14. Greenの関係(Green's relation)
    半群の右イデアル,左イデアル,両側イデアルを使って,半群の中に順序構造や同値類を導入するものです.グリーンの関係には, L, R, H, D, J の5種類があり,S を半群として,定義は次のようになります(⇔は左辺を右辺で定義していると読んでください).
    x L y ⇔ S1・x = S1・y

    x R y ⇔ x・S1 = y・S1

    x H y ⇔ x L y and x R y

    x D y ⇔ ∃z ∈ S x L z R y ⇔ ∃z' ∈ S x R z' L y
    (関係 L と R は可換です)

    x J y ⇔ S1・x・S1 = S1・y・S1

    これだけの定義だとなかなかイメージし辛いし,また,何の役に立つか分かりにくいと思います. 何の役に立つかは,例えば,itempotent(e・e = e)のHクラスを取ると群になるなど,群との 繋がりをつける役割を果たしたりします.また,計算機科学との関係で言えば,Hクラスが すべて唯一の要素からなる半群と対応するオートマトンは star-free 言語を受理するといった 定理があります.

    イメージしにくさを克服する一つの方法としては,いくつかの半群に対して,実際に それぞれの関係のクラスを計算してみて絵を描いてみるという方法があります.手始めに 変換半群の T3 ({1, 2, 3} からそれ自身への写像すべての集合)に対してやってみるのは 良い方法です.これは wikipedia にも例が載っていますし, こちらにはさらに推し進めて

    のようなペーパークラフトを作ってみるという企画をやってみました.

    上の資料の中でも参照していますが,Green の関係の例をさらに2つ載せておきます.

    1. 2進化4進数を受理するオートマトンの半群
      (Semigroup of the Automaton that accepts Binary-coded Quaternary)
    2. D-class が沢山あるもの
      (Sample with many D-classes)

    例えば, A.J. Cain の教科書などで,対応する勉強しながらこれらの例を参照してみてください.

    (fill the rest)

  15. TX : Monoid of full transformations
    集合 X から X へのすべての写像が作るモノイドです.X = {1, ..., n} のとき Tn と書くこともあります.例えば,T3 は X = {1, 2, 3} から X へのすべての写像なので33=27 個の写像からなるモノイドです. 上に書いた Cayley の定理の半群版から,任意の半群は変換モノイドに埋め込めますから, このモノイドに慣れておくことは有益です.

    (to fill the rest)

  16. Free semigroup, free monoid
    (to fill)

  17. 直積(direct product)
    直積は皆さんご存知だと思いますが,これから後,半群の色々な積を書きますので, 直積も書いておきます.

    直積は,複数の半群からそれらを部品として大きな半群を合成した半群です. S と T を半群とします.このとき直積 S × T は,集合としての 直積 S × T に次の演算を入れたものです.

    (s1, t1)・(s2, t2) := (s1・s2, t1・t2)
    for (s1, t1), (s2, t2) ∈ S × T
    つまり,S 成分と T 成分で独立に演算を行う演算が定義された半群です. 以下では,S と T が独立ではない演算が入る半群の合成方法が紹介されます.

  18. 輪積(Wreath product) ... 13th May 2017, 20th April 2018 加筆
    Wreath product は,二つの半群を合成して新しい半群を作る操作の一つです. 日本語ではと言います. 関連した操作として,半直積(semidirect product),直積(direct product)が あります.直積は皆さんよくご存じだと思います.

    Wreath product と semidirect product は初心者には分かりにくいと思います. でも,直積では合成できない半群がたくさんありますから,やっぱり理解しないと いけません.

    ここでは直積も含めて,少し掘り下げて理解しておこうと思います.

    まずは考え方を説明します.正確な定義はその後で行います.

    いま,集合 X があり,変換の集合 P ⊆ (X -> X) の性質を調べたいと します(例えば,X の要素 x1 から x2 へ P の変換の組み合わせで到達できるかなどの性質です). X が 巨大で複雑な集合の ときは大変な仕事です.近代科学の方法論としては,今のところ, 分割統治(divide & conquer)は有効な方法ですから, X⊆A×Bのように集合 X を直積に分解できると,問題を簡単にできるかも しれません(X⊆A×Bは同型で考えます.つまり X~X'⊆A×BとなるX'が あればということです).

    A×Bがうまい分解で,Pの中の変換がAとB独立に変換するときは,問題は非常に 簡単になります.つまり,A, B それぞれの要素に対して目的の変換を施して 繋げばよいのです.これは,A×Bの分解で,変換の集合も運よく2つの直積に 分かれる場合です.

    でも,一般にはこのような分解が可能とは限りません.可能性としては,次の 図のように3つの可能性があります.

    があります. この,片方の変換が1つの集合にだけ依存するときの変換の合成が Wreath Product です.

    wreath product, direct product, general product

    少し正確に記述しましょう.上の図の中の真ん中のもので, (f, g) の組

    (f, g) ∈ (A × B → A) × (B → B)
    に対して,それが表すものを次のように (A × B) → (A × B) の変換として意味づけをします.つまり, (f, g) は (a, b) ∈ (A × B) に対して,(f(a, b), g(b)) を対応させる関数を表すことに するわけです.

    このような意味付けをして,(f1, g1), (f2, g2) に対して,次の図のように,これらを関数として合成した結果の (A × B) → (A × B) の関数で演算を定義すれば,関数の合成は 結合法則が成立しますから,半群になります.

    このときの (f1, g1) と (f2, g2) の演算の式は次の図のようになります.ここで, λb.g(b) は,b を入力として受け取って,g(b) を返す関数という意味です.

    同様に λ(a, b).f(a, b) は (a, b) という値の組を受け取って,f(a, b) という値を返す関数と いう意味です.これらはラムダ記法と呼ばれ,計算機科学でよく使われる記法で,関数を表すのによく使われます. 通常の数学の本では,f(a, b) は,f(a, b) という値を表すのか,(a, b) を受け取って,f(a, b) を 返す関数を表すのか曖昧で,説明文の中でそれらが指示されます.ラムダ記法はそれを明示的に 表す記号です.意外と便利です.

    以上をまとめると,(f1, g1), (f2, g2) ∈ (A × B → A) × (B → B) に 対して,
    (f1, g1)*(f2, g2) := (λ(a, b).f2(f1(a, b), g1(b)), λb.g2(g1(b)))
    と定義すると,(A × B → A) × (B → B) を半群にすることができます. この半群を(A → A) と (B → B) の Wreath product と言います.

    ここでは,A と B の上の monoids of full transformations に対して Wreath product を 定義しましたが,Wreath product は,任意の二つの半群に対して定義することができます. その前に,上の例を少し整理しましょう.そのためには2つの定義が必要になります.

    一つ目は,A × B → A を半群にする演算の定義です.A × B → A は 次の演算で半群になります.

    f1, f2 ∈ A × B → A に対して, f1・f2 := λ(a, b).f1(f2(a, b), b)

    二つ目は,g ∈ B → B による f ∈ A × B → A への作用の定義です.

    gf := λ(a, b).f(a, g(b))

    これら2つを使うと,上の (f1, g1)*(f2, g2) の定義式は

    (f1, g1)*(f2,g2) := (f1・g1f2, g1・g2)
    のように書き表すことができます.つまり,直積のように要素ごとに演算を行うのではなく, 第2要素は単に演算を行うが,第1要素は,f2 に g1 を作用させてから f1 と演算を 行うという非対称的な定義になります.

    これらの動機付けと準備が終わりましたので,Wreath product の一般的な定義を行います. この定義は,前の定義では必要だった変換される集合は抽象化され合成される半群だけの 言葉で記述されています.

    定義 (Wreath product)
    S, T を半群とします.このとき,S と T の Wreath product S Wr T は,
    (T → S) × S に次の演算を入れたものである.
    (f1, t1)*(f2, t2) := (f1・t1f2, t1・f2)
    ここで t1f1 := λt.f1(t1・t) とする.また・は,それぞれの半群の演算である.

    S Wr T は,要素の集合としては T → S と S の直積ですから,要素数は |S||T|・|S| になります.

    ちなみに Wreath product は演算を繰り返すと,式がどんどん複雑になっていきます.次に多段の骨格を強調した図を挙げておきます.
    (figure emphasize the skeleton of the cascades)
    wreath product

    
    
    参考文献
    Wreath product は,結構,ややこしいので,色々な本で定義を確認するのも良い方法だと 思います.いくつか参考文献を挙げておきます.PDF が公開されていますので,ぐぐってみて 下さい.
    1. A. J. Cain's "Nine Chapters on the Semigroup Art"
      第7章 Finite semigroups に Wreath product や semidirect product の定義が あります.この章では Krohn-Rhodes の定理,つまり,有限半群は有限群といくつかの 右ゼロ半群の Wreath product で表現できることを証明します.

    2. Mathematical Foundations of Automata Theory by JE Pin
      chapter XV Wreath product そのものの章があります.

  19. Semidirect product
    (to fill)

  20. Subdirect product
    (to fill)

ホームページトップ(Top of My Homepage)