s-完備可換半環上の非可換半代数上の加群の圏に関する随伴性とその応用

「の」が幾つも続いた長たらしいタイトルですが、実際にそういう話なんです。

表題の件、技術的に難しいことは無いですが、特別な動機がないとちょっと気付かない事実だと思います。僕の動機はオートマトン理論を圏論的に理解したい、というものです。聞き慣れない言葉が出てくるので、言葉の定義を淡々と書き連ねます。最後にオートマトンの話に触れます。

内容：

概略
可換半環
s-完備性
非可換半代数
非可換半代数上の半加群
モノイド作用を持つ集合
自由生成関手
忘却関手
K-テンソル積
随伴性
随伴性、もっとカッコよく(?)
決定性オートマトンと非決定性オートマトン

概略

ModAlg_K という圏と、SetMon という圏を定義します。ModAlg_K は可換半環K上の線形代数により作る圏で、SetMon は集合へのモノイド作用を全部集めた圏です。自由生成関手 F:SetMon→ModAlg_K と、忘却関手 U:ModAlg_K→SetMon を定義してやると、この2つの関手は随伴ペアになります。

つまり、次のようなホムセットの同型が系統的に存在します。

ModAlg_K(F(S_M), Y_B) $\stackrel{\sim}{=}$ SetMon(S_M, U(Y_B))

オートマトンから始状態と終状態を取り除いた（アルファベットと状態遷移だけの）構造をプレオートマトンと呼ぶことにすると、上記の随伴関手ペア F -| U は、非決定性プレオートマトンの圏（ModAlg_Kの部分圏）と決定性プレオートマトンの圏（SetMonの部分圏）との随伴関係を与えます。

可換半環

可換半環は、可換環から引き算を抜いたものです。足し算と掛け算は自由にできます。

自然数の全体（0も入れる）Nに普通の足し算・掛け算を考えると可換半環です。集合Sのベキ集合Pow(S)に、部分集合の合併（足し算）と共通部分（掛け算）を考えても可換半環ですね。

少し変わった例としては、0以上の実数に無限大を追加した P_∞ = {x∈R | x ≧ 0}∪{∞} に「足し算を掛け算」として、「大きい方を取る演算を足し算」とする半環があります。これについては、「零の概念とmax-plus半環の紹介」の「max-plus半環」の節を見て下さい。「なぜ、どのように足し算が消失したのか：プランク定数の大惨事と生存者達」とか「インド、ロシアだけじゃないぞ、ブラジル発の熱帯式算数もあるんだぜ」にも関連する話題があります。

s-完備性

可換モノイドや半環には、無限個の要素の総和可能性という概念があります。総和可能性に関しては「いろいろな総和可能性」に書いてあります。

Kが半環で、任意の集合Iに関して、添字族 ψ:I→K が総和可能で無限分配法則を満たすとき、半環Kは完備だと言います。僕の他の記事では、完備性を“any総和可能性”と呼んでいる場合もあります。完備性は、どんな基数のIに対しても合理的に総和 Σ(i∈I | ψ_i) を求めることが出来ることです。ただし、「完備」というと距離空間の完備性を思い出す人が多いでしょう。そこで、summation（総和）のsを付けてs-完備と呼ぶことにします。

半環Kの足し算がベキ等なら、添字族 ψ:I→K の総和は、Kの部分集合 {ψ(i)∈K | i∈I} の総和で置き換えても同じです。先に例に出したベキ集合の可換半環はベキ等でs-完備です。max-plus半環もベキ等でs-完備です。自然数の半環Nはベキ等でなくs-完備でもありません。

以下では、s-完備可換半環Kを固定して、これをスカラー半環（基礎半環）とみなし、K上の（半）線形代数の議論をします。

非可換半代数

通常の線形代数（体上の線形代数）と同様に、可換モノイドVにスカラー半環Kによるスカラー乗法があるとき、（スカラー乗法を込めた）Vを、K上の半ベクトル空間と呼びます。形容詞「半」は引き算がないことを示唆しますが、面倒なので「半」を付けないこともあります。

Aが可換半環K上の半ベクトル空間で、掛け算 A×A→A を持っているとき、AをK上の半代数（半多元環）と呼びます。「半」を付けないで単に代数または多元環と呼んでしまうこともあります。Aの掛け算に可換性は要求しません。「可換とは限らない」の意味で非可換半代数とも言います。

スカラー半環Kはs-完備という仮定を置いているので、半ベクトル空間／半代数もs-完備なものを考えることにします。

非可換半代数上の半加群

Aが可換半環K上の非可換（可換とは限らない）半代数とします。K上の半ベクトル空間Xがあり、Aによる作用（半代数によるスカラー乗法） α:X×A→X があるとき、(X, A, α)をA-半加群と呼びます。作用は右作用の形に書きます（どっちでもいいけど）。(X, A, α) を、X_AあるいはXだけで表すことがあります。以下では常に、AもXもs-完備性を仮定します。そして、K-半ベクトル空間のK-スカラー乗法、K-半代数の掛け算、A-加群への半代数Aの右作用は無限分配法則を満たすと仮定します。

スカラー半環Kは固定してますが、半加群の半代数は固定しません。(X, A, α)と(Y, B, β)が半加群のとき、準同型写像は、K-半ベクトル空間としての準同型（半線形写像） f_vect:X→Y と、K-半代数の準同型 f_alg:A→B の組 (f_vect, f_alg) で、半代数による右作用を保つものです。「右作用を保つ」とは次のことです。

f_vect(α(m, a)) = β(f_vect(m), f_alg(a))

さらに、半ベクトル空間／半代数はs-完備と仮定しているので、f_vectもf_algも総和を保つとします。総和を保つ写像を「連続」と形容することがあります。位相や距離による連続性とは違うのでその点は注意してください。紛れがないようにs-連続と言うことにすれば：

f_vect:X→Y はs-連続なK-半線形写像
f_alg:A→B はs-連続なK-半代数準同型写像

K-半代数上の半加群の圏 ModAlg_K を次のように定義します。

対象は、K-半代数上の半加群 (X, A, α)
射 f:(X, A, α)→(Y, B, β) は、K-半代数上の半加群のあいだの準同型 f = (f_vect, f_alg)
恒等射は自明な準同型写像
射の結合は、準同型写像の結合（合成）

s-完備性とs-連続性が、すべての所で仮定されていることに注意して下さい。この仮定がないと後の議論がうまくいきません。

なお、ModAlg_Kは module over K-algebra の略で、semi（半）は付けてません。SemiModSemiAlg_Kはちょっとうざいからね。

モノイド作用を持つ集合

Sは集合、M = (M, ・, e) はモノイドとします。右作用 μ:S×M→S を考えます。ここで右作用とは、次が成立することです。

μ(μ(s, m), n) = μ(s, m・n) （s∈S、m, n∈M、・はMの乗法）
μ(s, e) = s （s∈S、eはMの単位元）

SとM、それと右作用μの組 (S, M, μ) をM-作用を持つ集合（set with M-action）と呼びます。(S, M, μ) を、S_MあるいはSだけで表すことがあります。

(S, M, μ)と(T, N, ν)が、モノイド作用を持つ集合のとき、準同型写像は、単なる写像 f_set:S→T と、モノイドの準同型 f_mon:M→N の組 (f_set, f_mon) で、モノイドによる右作用を保つものです。

f_set(μ(s, m)) = ν(f_set(s), f_mon(m))

モノイド作用を持つ集合の圏 SetMon を次のように定義します。

対象は、モノイド作用を持つ集合 (S, M, μ)
射 f:(S, M, μ)→(T, N, ν) は、モノイド作用を持つ集合のあいだの準同型 f = (f_set, f_mon)
恒等射は自明な準同型写像
射の結合は、準同型写像の結合（合成）

自由生成関手

モノイド作用を持つ集合 (S, M, μ) をS_Mのように略記してもいいとします。同様に、K-半代数上の半加群 (X, A, α) をX_Aと略記します。モノイドによる右作用と半代数による右作用をいずれも中置演算子記号「・」で示し、モノイドの乗法と半代数の乗法は併置で記します。例えば次のように書きます。

(s・m)・n = s・(mn) （s∈S、m, n∈M）
(x・a)・b = x・(ab) （x∈X、a, b∈A）

さて、モノイド作用を持つ集合S_Mが与えられたとき、S_Mから自由生成された半加群X_A（AはK-半代数）を構成しましょう。

まず、K-半ベクトル空間Xを X = Fun(S, K) として定義します。Sはモノイド作用を持つ集合（の台集合）でKは基礎スカラー半環、Funは関数の全体を表します。通常の線形代数の自由生成では、有限線形結合だけを考えますが、s-完備性があるので、すべての関数をまるごと使います。なお、有限線形結合だけを使う方法は、「ベクトルと行列の圏論的な解釈」の「ベクトル構成」の節に書いてあります（Fun^fin(S, K)を使った構成）。

X = Fun(S, K) のs-完備性も含めた半ベクトル空間構造に関しては、「畳み込み半環の前送り準同型 -- パリクの定理に向けて」の「関数半加群」の節を参照してください。

次に、A = Fun(M, K) と置いて、Aにもs-完備なK-半ベクトル空間の構造を入れます。さらにAには、モノイドMの乗法を利用して畳み込み積（convolution product）も入れます。a, b∈Fun(M, K) に対して、それらの掛け算＝畳み込み積の定義は次のとおりです。

k∈M に対して、(ab)(k) = (a*b)(k) := Σ(m, n∈M, mn = k | a(m)b(n))

この掛け算により、A = Fun(M, K) はs-完備なK-半代数となります。この半代数の作り方も「畳み込み半環の前送り準同型 -- パリクの定理に向けて」にあります。

集合Sから生成されたs-完備自由半ベクトル空間Xの要素をx、モノイドM上から生成されたs-完備自由K-半代数Aの要素をaとします。半代数Aによる半ベクトル空間Xへの右作用αを次のように定義します。

t∈S に対して、(α(x, a))(t) = (x・a)(t) := Σ(s・m = t| x(s)a(m))

この右作用もやはり畳み込み積で、Mの乗法の代わりにMの右作用を使ったものです。

以上の手順により、モノイド作用を持つ集合S_Mが与えられたとき、集合SからK-半ベクトル空間Xが構成でき、モノイドMからはK-半代数Aが構成できて、さらに右作用 α:X×A→X も作れました。これらをまとめると、K-半代数A上の半加群 X_A = (X, A, α) が完成します。半ベクトル空間の公理や半代数の公理が成立していることを確認する必要がありますが、それは難しくありません。

モノイド作用を持つ集合S_Mから作られたX_Aを、X_A = F(S_M) とも書きます。自由生成する操作をFで表します。Fは、圏SetMonの対象を、圏ModAlg_Kの対象に対応させます。さらに射のあいだの対応に拡張できて、Fは関手になります。

関手としてのFを完成させるには、射から射への対応を作ります。f = (f_set, f_mon):S_M→T_N を圏SetMonの射、つまりモノイド作用を持つ集合のあいだの準同型写像だとします。射fに対するF(f)は、fの成分（f_setとf_mon）ごとに前送りにより定義します。

F(f) = F((f_set, f_mon)) := ((f_set)_*, (f_mon)_*)

(f_set)_*と(f_mon)_*の下付きアスタリスクは前送りを意味しますが、前送りについては「畳み込み半環の前送り準同型 -- パリクの定理に向けて」に書いてあります。前送りが作れるのは、基礎スカラー半環Kがs-完備でありs-連続写像を考えているからです。s-完備性／s-連続性がない純代数的なセッティングでは前送りを作れません。s-完備性／s-連続性が大事だよ、ってことです。

細かい点をチェックすれば、自由生成の関手 F:SetMon→ModAlg_K の定義が完了します。手間さえかければいい話なので、細かい点のチェックは割愛します。

集合Sから作ったs-完備自由K-半ベクトル空間をKS、モノイドMから作ったs-完備自由K-半代数を同じくKMと略記することがあります。この記法はかなり横着で誤解や意味不明の恐れもありますが、便利なので後で使います。この横着記法を使うと次のように書けます。

F(S_M) = (KS, KM, α) = KS_KM

忘却関手

忘却関手 U:ModAlg_K→SetMon を作りましょう。これは簡単です。

s-完備なK-半代数Bと、B上の半加群 (Y, B, β) = Y_B を取ります。U(Y_B) はモノイド作用を持つ集合 (T, N, ν) = T_N で、次のように定義されます。

Tは、K-ベクトル空間としてのYから、（半）線形構造を忘れ去って単なる集合とみなしたもの。
Nは、K-半代数Aから、足し算を忘れ去って掛け算によるモノイドとみなしたもの。
νは、βと同じだが、集合TへのNの右作用とみなしたもの。

ModAlg_Kの射、つまりK-半代数上の半加群の準同型写像に対しても、同じように構造に関する条件を忘れ去って、単なる写像とモノイド準同型写像とみなせば、SetMonの射となります。

ここでも細かい点のチェックはありますが、忘却関手 U:ModAlg_K→SetMon が定義可能です。

K-テンソル積

集合圏SetとK-半ベクトル空間の圏Vect_Kは並行的に議論できて、次の対応があります。

集合圏	K-半ベクトル空間の圏
集合	K-半ベクトル空間
写像	K-線形写像
直和	直和（双積）

集合圏における直積に対応するモノイド積はなんでしょうか？常識的に言ってテンソル積ですよね。体上の線形代数では、代数的なテンソル積はよく知られています。ヒルベルト空間では、距離完備化も併用してテンソル積を作るようです。

可換半環K上の半ベクトル空間に関してテンソル積は作れるでしょうか。代数的テンソル積にはいくつかの定義があるようです。Kがs-完備のとき、s-完備半ベクトル空間のK-テンソル積は、代数的には構成できそうにありません。s-完備性／s-連続性を反映させるには、代数的有限和では済まないからです。

可換半環上の半ベクトル空間のテンソル積に関しては、マーコス・バンナーグ（Markus Banagl）の次の論文があります。

Title: THE TENSOR PRODUCT OF FUNCTION SEMIMODULES
Author: Markus Banagl
URL: https://www.mathi.uni-heidelberg.de/~banagl/pdfdocs/TensorSemimod.pdf

タイトルのとおり、一般的なs-完備半ベクトル空間の話ではなくて、K値関数の空間として実現される関数半加群（ここでの加群は、K上の加群＝K-半ベクトル空間のこと）のテンソル積を扱っています。

K-半ベクトル空間のK-テンソル積が使えると話が劇的に簡単になるケースがあります。オートマトンの話のときに少しだけK-テンソル積を使います。そこで使われる公式は、s-完備可換半環Kに対して K(S×T) = (KS) $\otimes$ (KT) です。ここで、KSはSから自由生成されたs-完備K-半ベクトル空間です。

随伴性

自由生成関手Fと忘却関手Uの随伴性（随伴関手ペアを成すこと）を示すには、冒頭に挙げた同型を構成する必要があります。

SetMon(S_M, U(Y_B)) $\stackrel{\sim}{=}$ ModAlg_K(F(S_M), Y_B)

モノイド作用を持つ集合S_Mと、K-半代数B上の半加群Y_Bが具体的に与えられた状況を想定すると、f = (f_set, f_mon):S_M→U(Y_B) から、F(S_M)→Y_B を作る手順は、形式的K-線形結合に対してfを拡張するだけのことです。ただし、K-線形結合が有限和だけではなくて、無限和もある点が注意が必要です。

形式的K-線形結合（無限和あり）の計算では、（半）線形構造を忘却した集合U(Y_B)上の形式的K-線形結合を（線形構造を思い出して）実際に計算する操作が入ります。これは、FU(Y_B)→Y_B という線形写像で、随伴関手ペアの余単位自然変換（の成分）です。

逆方向の対応は、g = (g_vect, g_alg):F(S_M)→Y_B から S_M→U(Y_B) を作るものです。集合Sは、線形構造を忘却した集合UYに自然に埋め込めます。この埋込みとg_vecを繋いで S→UY が作れます。同様に M→FM→B と連なる、埋め込みとg_mon を繋いで M→UB が作れます。これらを組み合わせれば、目的の S_M→U(Y_B) が得られます。今使った埋め込みは、随伴関手ペアの単位自然変換（の成分）です。

すべての計算は、具体的露骨に書き下せます。なぜなら、今までに出てきた定義はすべて、足し算と掛け算、K-スカラー乗法、無限和（畳み込み）しか使ってないからです。スカラー乗法も掛け算の一種、無限和も足し算の一種ですから、足し算と掛け算しか使ってないのです。ただし、足し算と掛け算をタクサン積み重ねているので、計算の作業はそれなりに大変です。

ホムセットのあいだの同型が示せても、それだけでは随伴性にはなりません。ホムセットの同型が、自然であることを示す必要があります。自然変換の条件を追い回して等式を書いて、その等式を示します。めんどくさいけど、足し算と掛け算と等式的推論の積み重ねですね。疲れるので詳細は割愛。

随伴性、もっとカッコよく(?)

圏のホムセットとして、SetMon(S_M, T_N)、ModAlg_K(X_A, Y_B) のような書き方をしてきましたが、モノイドMやK-代数Aを固定したときに次の書き方も採用しましょう。

Set[M](S_M, T_M) モノイドMを固定したとき
Mod_K[A](X_A, Y_A) K-半代数Aを固定したとき

Set[M]は、作用するモノイドをMに固定した場合の、「M-作用を持つ集合の圏」です。Mod_K[A]は、係数域のK-半代数をAに固定した場合の、「A-加群の圏」です。

Monをモノイドの圏とします。圏Set[M]のMを動かすと、Monの対象でインデックス付けられた圏の束 (Set[M] | M∈|Mon|) ができます。パランパランの束ではなくて、Monの射に沿って圏達を関手で互いに接続してあげると、ベース圏Mon上のインデックス付き圏Set[-]を作れます。

同様な方法で、K-半代数の圏Alg_Kをベース圏とするインデックス付き圏Mod_K[-]が作れます。

2つのインデックス付き圏Set[-]とMod_K[-]のあいだの準同型射を次のように定義します。

ベース圏のあいだの関手 F_base:Mon→Alg_K。これは、モノイドからK-畳み込み積を持つs-完備自由K-半代数を作る関手。F_base(M)をKMと略記することがある。
ファイバーごとの関手 F_fiber[M]:Set[M]→Mod_K[KM]。これは、S_MからKS_KMを作る関手。

「ベース圏のあいだの関手とファイバーごとの関手の束」は、インデックス付き圏一般についても適用できる準同型射の定義です。

逆方向の、Mod_K[-]からSet[-]へのインデックス付き圏の準同型射を次のように定義します。

ベース圏のあいだの関手 U_base:Alg_K→Mon。これは、K-半代数の足し算やK-線形構造を忘れて掛け算だけを残す忘却関手。
ファイバーごとの関手 U_fiber[A]:Mod_K[A]→Set[UA]。これは、加群のK-半ベクトル空間の構造を忘れ、単なる集合へのモノイド作用だとみなす忘却関手。

このように定義したとき、次のことは比較的容易に示せます。

ベース圏のあいだの関手F_baseとU_baseは随伴関手ペアとなる。
ファイバーごとの関手F_fiber[M]とU_fiber[KM]、F_fiber[UA]とU_fiber[A]は随伴関手ペアになる。

ここから先は、未確認事項ですが、たぶん、おそらく、今まで述べたような状況が成立しているなら、インデックス付き圏Set[-]のグロタンディーク平坦化とMod_K[-]のグロタンディーク平坦化のあいだにも随伴関手のペアが存在するでしょう。そのペアは、上記のように与えられたデータから本質的に一意に構成可能なはずです。

2つのインデックス付き圏の「ベース圏を繋ぐ随伴関手ペア」と「ファイバーごとの随伴関手ペアの束」、それと何らかの制約条件があれば、グロタンディーク平坦化したら、たくさんの随伴関手ペアを集約した“まるっとした随伴関手ペア”が出現するだろう、ということです。逆に、グロタンディーク平坦化のあいだの随伴関手ペアは、元のインデックス付き圏の随伴関手ペアの集まりを誘導するでしょう。たぶん、ね。

もしこれが正しいなら、2つのベース圏MonとAlg_Kを繋ぐ随伴関手ペアと、ファイバーごとの随伴関手ペア達から、MonSetとModAlg_Kを繋ぐ随伴関手ペアが得られます。

決定性オートマトンと非決定性オートマトン

オートマトン理論では、古来より決定性オートマトンと非決定性オートマトンに分けて論じる習わしです。何故にそういうことになっているのでしょうか？ SetMonとModAlg_Kが随伴関手ペアで結ばれることは、その説明を与えます。

いま、s-完備可換半環としてブール半環Bを取ります。Bは、二値ブール代数（古典命題論理の真偽値）から否定を忘れ、論理ORを足し算、論理ANDを掛け算と思った可換半環です。Bでは足し算がベキ等でs-完備になるのは明らかです。

決定性オートマトンは、集合圏のなかでのモノイド作用であり、非決定性オートマトンは、B-半ベクトル空間の圏のなかでのモノイド作用です。決定性オートマトンは特殊な非決定性オートマトンであり、非決定性オートマトンは状態空間のベキ集合を使って決定性オートマトンに変換できます。この相互関係は、随伴関手ペアによる結び付きだったのです。

話をハッキリさせるために、プレオートマトンという概念を導入します。オートマトンでは始状態と終状態を考えますが、プレオートマトンではアルファベットと遷移しか考えません。Sを状態空間、Φをアルファベット（慣用のΣは総和記号と紛らわしいのでΦ）としたときに：

遷移写像 μ:S×Φ→S が通常の写像のとき、(S, Φ, μ)を決定性のプレオートマトンと呼ぶ。
遷移写像 μ:S×Φ→S が非決定性の写像のとき、(S, Φ, μ)を非決定性のプレオートマトンと呼ぶ。

アルファベット集合Φから生成された自由モノイドをΦ^*と記します。μ:S×Φ→S が決定性プレオートマトンのとき、写像（普通の写像）μは、S×Φ^*→S に拡張できます。拡張したμも同じ記号μで表すことにすると、μ:S×Φ^*→S は、モノイドΦ^*の右作用を持つ集合となります。よって、決定性プレオートマトンは圏SetMonの対象となり、決定性プレオートマトンの準同型写像は、圏SetMonの射と考えればよいことになります。

次に、非決定性プレオートマトン μ:S×Φ→S の場合。μが非決定性写像だということは、S×Φ→Pow(S) という普通の写像があることと同じです。Pow(S)はSのベキ集合です。ベキ集合Pow(S)は、ブール半環Bによる自由半ベクトル空間BSと同じです。

非決定性遷移写像を S×Φ→BS の形にして、決定性プレオートマトンのときと同じく S×Φ^*→BS まで拡張して、それを改めてμと置いて、μ:S×Φ^*→BS とします。

ここで、テンソル積に関する公式 B(S×T) = (BS) $\otimes$ (BT) と、モナド乗法に相当する演算 B(BS)→BS を使って次のように変形します。

 S×Φ^*→BS
  | 自由生成関手 B(-) を適用する
  v
 B(S×Φ^*)→B(BS)
  | B-テンソル積に関する公式
  v
 (BS)(BΦ^*)→B(BS)
  | 右端に、 B(BS)→BS を繋いで結合する
  v
 (BS)(BΦ^*)→BS

この手順で、B-線形写像 (BS) $\otimes$ (BΦ^*)→BS が得られます。テンソル積の性質から、これは双線形写像 (BS)×(BΦ^*)→BS と考えてよいので、自由B-半ベクトル空間BSへの自由B-半代数BΦ^*の右作用と捉えることが出来ます。

これで、圏ModAlg_Bの対象 (BS, BΦ^*, φ) が得られました。ここでφは、非決定性プレオートマトンの非決定性遷移写像μから得られた右作用です。

以上により、決定性プレオートマトンの圏はSetMonに埋め込めて、非決定性プレオートマトンの圏はModAlg_Bに埋め込めました。あとは埋め込み先のSetMonとModAlg_Bに舞台を移して、自由生成関手Fと忘却関手Uの随伴関手ペアにより、「決定性プレオートマトン ←→ 非決定性プレオートマトン」の相互関係を記述できます。これは、通常のオートマトン理論の手法を完全に再現しています。