このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

畳み込み半環の前送り準同型 -- パリクの定理に向けて

雑記／備忘

このブログで何度か名前を出している（例えばコレ）M.W.ホプキンス（Mark William Hopkins）は、パリクの定理（Parikh's theorem ）に興味を持っていたようです。

「Mark W. Hopkinsは今どこに？」で紹介した"Parikh's Theorem in Commutative Kleene Algebra"という、マークとデクスター・コォゼンの論文は、パリクの定理が主題です。この論文は、今でもコォゼンのサイトに掲載されています。

僕も影響を受けて、パリクの定理について考えたことがあります。ホプキンス／コォゼンが扱っている場合より簡単な命題で、正規言語の可換化イメージの形状に関するものです（今、詳細は述べませんが） -- このタイプのパリクの定理は、うまいこと枠組みを準備すると自明になります。

このうまい枠組みの中核は、モノイドの準同型写像に畳み込み半環の準同型写像を対応させる関手です。この関手が共変であることがポイントです。一般的には共変関手の構成は出来ないのですが、スカラー半環の総和可能性を仮定するとうまくいきます。

以上に述べたような背景があるのですが、今回は、「モノイドの準同型写像が、畳み込み半環の前送り準同型写像を誘導する」という事実だけを手短に説明します。

内容：

  1. 関数半加群
  2. 総和の記法
  3. 関数半加群の前送り準同型
  4. モノイドの畳み込み半環
  5. 畳み込み半環の前送り準同型
  6. 無限分配法則と入れ子の総和公式
  7. 計算の実行
  8. まとめ

関数半加群

Hは可換で総和可能な半環だとします。可換モノイド／半環の総和可能性は何度か説明しています。

「形式言語理論のための代数」の「基数条件と総和可能性」において、基数条件χに対するχ-総和可能という概念を出しました。ここでは、話を簡単にするために、Hはany-総和可能だとします。つまり、任意の基数を持つ添字集合（index set）に対する族が総和可能だとします。ブール半環Bや、無限大付きの自然数 N∪{∞} は可換でany-総和可能です。選んで固定した可換総和可能半環Hをスカラー半環とも呼びます。

Xを集合として、Xからスカラー半環Hへの関数の全体を Fun(X, H) と書きます。f, g∈Fun(X, H) と a∈H に対して、足し算とスカラー乗法は次のように定義できます。

  • (f + g)(x) := f(x) + g(x)
  • (a・f)(x) := a・f(x)

この足し算とスカラー乗法は、当たり前の計算法則を満たし、Fun(X, H) は半環H上の半加群と呼ばれる構造を持ちます。「半環上の半加群」は、「環上の加群」から引き算の要求を除いただけのものです。Hが総和可能であることから、点ごとの総和で Fun(X, H) も総和可能になります。この半加群を、X上の関数半加群（function semimodule）と呼びます。

(f・g)(x) := f(x)・g(x) として掛け算も入れられますが、今は考えません。この掛け算は、後で述べる前送り準同型写像とうまく協調しません。相性の悪いものを一緒に考えてもメリットがありません。

なお、関数半加群の要素を関数と呼び、それ以外では写像という言葉を使うことにします。

総和の記法

先に進む前に、総和を表す記法を準備しておきましょう。f∈Fun(X, H) に対して、関数fをXの部分集合A上で総和することが多いので、その状況を想定します。

普通は総和を Σx∈Af(x) のように書きますが、下付きだと書くのも読むのも負担なので、Σ(x∈A | f(x)) と書きます。

集合Aが、A = {t∈X | P(t)} と内包的に与えられているとき、Σ(x∈{t∈X | P(t)} | f(x)) は煩雑なので、Σ(x: P(x) | f(x)) とコロンを使って書きます。Σ((x, y): R(x, y) | h(x, y)) は丸括弧が重なって鬱陶しいので、Σ(x, y: R(x, y) | h(x, y)) とします。

このような略記により、記述や計算がだいぶスッキリします。かえって意味がわかりにくくなったら、もとの定義に戻って考えて下さい。

関数半加群の前送り準同型

ψ:X→Y を集合のあいだの写像とします。f∈Fun(X, H) に対して、f'∈Fun(Y, H) を次のように決めます。

  • y∈Y に対して、f'(y) := Σ(x: ψ(x) = y | f(x))

固定されたyに対して、yの逆像 ψ-1(y) = {x∈X | ψ(x) = y} の上で総和を取ります。yの逆像（ファイバー）がどんな集合であっても、Hの総和可能性からf'(y)は確定します。したがって、y｜→f'(y) はwell-definedです。

f'はfとψから決まるので、ψ→(f) と書きます。つまり、

  • (ψ→(f))(y) := Σ(x: ψ(x) = y | f(x))

関数引数が入る括弧をブラケットにして、(ψ→(f))(y) を ψ→[f](y) と書くと多少読みやすくなるので、ブラケットも使うことにします。

f｜→ψ→[f] は関数を関数に対応させるので、ψ→:Fun(X, H)→Fun(Y, H) という写像です。ψ→ は、ψ:X→Y と同じ方向であることに注意して下さい。ψと逆方向の ψ←[g] := ψ;g はいつでも定義できますが、ψ→はHの総和可能性に依拠しています。

ψ→:Fun(X, H)→Fun(Y, H) は、半加群の準同型になっています。総和記法の練習に計算をやってみましょう。

ψ→[f + g] = ψ→[f] + ψ→[g] を示します。総和の加法性を使います。



  ψ→[f + g](y)

= Σ(x: ψ(x) = y | (f + g)(x))

= Σ(x: ψ(x) = y | f(x) + g(x))

= Σ(x: ψ(x) = y | f(x)) + Σ(x: ψ(x) = y | g(x))

= ψ→[f] + ψ→[g]

ψ→[a・f] = a・ψ→[f] も、総和の分配法則から出ます。

ここまでのことを圏論の言葉を使って言えば、Fun(-, H) と (-)→ の組み合わせが、集合の圏からH-半加群の圏への共変関手となるのです。興味がある方は細部まで確認してみてください。

モノイドの畳み込み半環

今までは、集合X上の関数半加群 Fun(X, H) を考えてきました。ここからは、単なる集合ではなくてモノイドMに対する Fun(M, H) を考えます。Mにはモノイド演算（「・」とします）があるので、それを使って Fun(M, H) に掛け算を導入できます。この掛け算は畳み込み積（convolution product）と呼ばれるものです。

畳み込み積に関しては「半群の上の畳み込み積」にかなり詳しく書きました。念のため、定義を書いておくと：

  • (f*g)(x) := Σ(s, t: s・t = x | f(s)g(t))

「*」は畳み込み積の記号、「・」はモノイド乗法、スカラー半環Hの掛け算は単なる並置で書いています。畳み込み積が定義可能なのも、Hの総和可能性のおかげです。

モノイドMに対する関数半加群 Fun(M, H) は、畳み込み積を掛け算として半環となります。こうして作られた半環を、Mの畳み込み半環と呼ぶことにします。Hが可換でも、Fun(M, H) が可換とは限りません。むしろ、多くの場合で畳み込み半環は非可換です。そのことは、「半群の上の畳み込み積」の例で確認できます。

畳み込み半環の前送り準同型

MとNをモノイドとします。ψ:M→N はモノイドの準同型とします。ψは単なる写像ではなくて、次を満たします。

  1. ψ(x・y) = ψ(x)・ψ(y)
  2. ψ(1) = 1

先に述べた前送りψ→は、H-半加群の準同型となることは確認済みです。では、半環の準同型となるでしょうか？

ψ→が半環の準同型となるには、掛け算（畳み込み積）を保存する必要があるので、次が要求されます。

  • ψ→[f*g] = ψ→[f]*ψ→[g]
  • ψ→[e] = e

ここで、関数eは畳み込み積の単位元で、「e(1) = 1、その他では e(x) = 0」と定義される関数です。

今書いた準同型の等式は実際に成立します。それは、総和の計算により確認できますが、次節で総和の計算法をハッキリとさせておきましょう。

無限分配法則と入れ子の総和公式

総和可能な半環では、分配法則の無限版が成立します（「いろいろな総和可能性」参照）。一般的な無限分配法則は次の形に書けます。

  • Σ(s∈A | f(s))・Σ(t∈B | g(t)) = Σ((s, t);∈A×B | f(s)g(t))

A = {s∈X | P(s)}、B = {t∈X | Q(t)} として、先に説明した略記法を使うと：

  • Σ(s: P(s) | f(s))・Σ(t: Q(t) | g(t)) = Σ(s, t: P(s), Q(t) | f(s)g(t))

P(s), Q(t) のカンマは論理ANDの意味で、論理記号を使って書くなら P(s)∧Q(t) です。

次に、総和が入れ子になっている場合の計算法則を述べます。A⊆X、D⊆(X×T) の状況を考えます。πを、π:X×T→X、π(x, t) = x という射影だとします。Da := {(x, t)∈X×T | (x, t)∈D かつ x = a} とします。Da := D∩π-1(a) とも書けます。

この状況で、次の公式が成立します。

  • Σ(x∈A | Σ(t∈Dx | h(x, t))) = Σ((x, t)∈(D∩π-1(A)) | h(x, t))

射影πのファイバーごとに総和して、その後でそれらの総和値をA上で総和することは、ファイバー（縦線）を寄せ集めて作った“2次元領域” D∩π-1(A) 上の総和に等しいのです。これも、分配法則の一種だと考えられます。あるいは、フビニの定理の類似物とも見られます。

入れ子の総和公式を略記法を使って書くと：

  • Σ(x: P(x) | Σ(t: R(x, t) | h(x, t))) = Σ(x, t: P(x), R(x, t) | h(x, t))

ここで、A = {x∈X | P(x)}、D = {(x, t)∈X×T | R(x, t)} です。

計算の実行

ψ→[f*g] = ψ→[f]*ψ→[g] を計算で示してみましょう。左辺と右辺を別々に計算して一致することを見ます。



  ψ→[f*g](y)

  // 前送りの定義

= Σ(x: ψ(x) = y | (f*g)(x))

  // 畳み込み積の定義

= Σ(x: ψ(x) = y | Σ(s, t: s・t = x | f(s)g(t)))

  // 入れ子の総和公式

= Σ(x, s, t: ψ(x) = y, s・t = x | f(s)g(t))

  // 条件の変形

= Σ(s, t: ψ(s・t) = y | f(s)g(t))



  (ψ→[f]*ψ→[g])(y)

  // 畳み込み積の定義

= Σ(v, w: v・w = y | (ψ→[f](v))・(ψ→[g](w)))

  // 前送りの定義

= Σ(v, w: v・w = y | Σ(s: ψ(s) = v | f(s))・Σ(t: ψ(t) = w | g(t)))

  // 分配法則

= Σ(v, w: v・w = y | Σ(s, t: ψ(s) = v, ψ(t) = w | f(s)g(t)))

  // 入れ子の総和公式

= Σ(v, w, s, t: v・w = y, ψ(s) = v, ψ(t) = w | f(s)g(t))

  // 条件の変形

= Σ(s, t: ψ(s)・ψ(t) = y | f(s)g(t))

  // 条件の変形

= Σ(s, t: ψ(s・t) = y | f(s)g(t))

一番最後の変形のところで、ψがモノイド準同型であることを使っています。

ψ→[e] = e も、前送りの定義から示せるので、ψ→:Fun(M, H)→Fun(N, H) が畳み込み半環の準同型であることが分かります。

まとめ

以上のことを圏論的にまとめると、Fun(-, H) と (-)→ の組み合わせが、モノイドの圏から半環の圏への共変関手を定義することになります。畳み込み半環は通常非可換なので、半代数（半多元環）の圏といったほうが適切かもしれません。

畳み込み積の定義でも、前送り準同型の定義でも、スカラー半環Hの総和可能性が本質的でした。位相や測度が考えられない状況でも、総和（無限和）を使うと積分に似たことができます。引き算が出来て、位相・測度があるような恵まれた環境での道具立ての一部は、引き算が出来なくて、位相・測度がない状況でも、総和により幾分かは再現できます。上記の共変関手の構成は、その一例と言えるでしょう。