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

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

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

参照用 記事

順序集合や距離空間も実はモノイドだった

モノイド圏のなかでは、モノイド対象というものを考えることができます。外側のモノイド圏を取り替えてモノイド対象を作ると、色々な構造が現れます。モノイド圏の作り方を工夫すると、意外なものがモノイド対象になったりします。順序集合と距離空間は、モノイド圏のモノイド対象になります。

この事実の背後には大きなストーリーがありそうですが、個別事例としても面白いと思います。

内容:

普通のモノイドといろいろなモノイド

普通のモノイドは、集合Mと、写像 m:M×M→M および u:1→M の組 (M, m, u) として定義されます。ここで1は単元集合(シングルトンセット)で、mは掛け算(乗法)を与える写像、uは単位元を特定する写像です。

モノイドの結合律、左単位律、右単位律は、可換図式で書けます。

[結合律]
  M×M×M - m×id → M×M
    |                |
  id×m               m
    ↓                ↓
   M×M  ----- m --→ M

[左単位律]
  1×M - u×id →M×M
   |             |
   |             m
   ↓             ↓
   M ============ M

[右単位律]
  M×1 - id×u →M×M
   |             |
   |             m
   ↓             ↓
   M ============ M

普通のモノイドは集合圏Setのなかで定義されますが、Setをモノイド圏 C = (C, \otimes, I) へと一般化して、「C内のモノイド」を定義できます。一般化の方法は:

普通のモノイド C内のモノイド
Setの対象(集合)M C対象A
集合の直積× Cのモノイド積\otimes
単元集合1 Cの単位対象I
乗法を与える写像 M×M→M Cの射 A\otimesA→A
単位元を特定する写像 1→M Cの射 I→A

モノイドの法則である「結合律/左単位律/右単位律」は、C内でも同様な3つの可換図式で定義できます。

この方法で作った「C内のモノイド」をCモノイド対象(monoid object)と呼ぶことがあります。単に、Cのモノイドでもいいと思います。次は、いろいろなモノイドの実例です。

外側のモノイド圏 モノイド積 モノイド単位 モノイド対象
ベクトル空間の圏 テンソル スカラー 代数(多元環
頂点集合がXである反射的グラフの圏 ファイバー積 離散グラフ Xを対象集合とする圏
Cの自己関手と自然変換の圏 関手の結合 Cの恒等関手 C上のモナド
(小さい)圏の圏 圏の直積 単一対象とidだけの圏 (小さい)厳密モノイド圏

プレ順序集合と一般化距離空間

前節の最後の表を見ると、モノイド概念が多様なのが分かります。しかし、掛け算と単位元を持つ代数構造という共通点は残しています。この共通な雰囲気から外れた例もあります。順序集合と距離空間もモノイドとして定義できます。

正確には、順序集合の条件をゆるめたプレ順序集合、距離空間の条件をゆるめた一般化距離空間(generalized metric space)がモノイドの形に書けます。

集合XとX上の関係≦がプレ順序集合だとは、次が成立することです。

  1. x∈X に対して、x≦x (反射律)
  2. x, y, z∈X に対して、x≦y かつ y≦z ならば x≦z (推移律)

集合Xと関数 d:A×A→[0, ∞] が一般化距離空間だとは、次が成立することです。[0, ∞]は、無限大を含めた非負実数全体です。(詳しくは、「移動のコストとしての距離」)

  1. x∈X に対して、d(x, x) = 0
  2. x, y, z∈X に対して、d(x, y) + d(y, z) ≧ d(x, z) (三角不等式)

定義を並べてみると、プレ順序集合と一般化距離空間が似ているのは分かると思います。実際、この2つを特殊事例として含む、より一般的な記述が可能です。

その一般的な記述には、順序半環係数の正方行列を使います。Kを順序半環として、MatK(X, X) を、添字集合がXでK係数の正方行列の全体とします。MatK(X, X) をモノイド圏とみなして、そのなかでモノイド対象を作ることができます。

  • 順序半環Kがブール半環のとき、MatK(X, X) のモノイド対象は、Xを台集合とするプレ順序集合となる。
  • 順序半環Kがmin-plus半環のとき、MatK(X, X) のモノイド対象は、Xを台集合とする一般化距離空間となる。

順序半環係数の正方行列

Kを集合として、(K, +, 0, ・, 1) が半環だとは:

  1. (K, +, 0) は可換モノイドである。
  2. (K, ・, 1) はモノイドである。
  3. 左右の分配法則が成立する。

半環の例をいくつか挙げます。

K + 0 1
自然数全体 足し算 0 掛け算 1
非負実数全体 足し算 0 掛け算 1
特定集合のベキ集合 合併 空集合 共通部分 全体集合
区間 [0, 1] max 0 掛け算 1
{true, false} false true
非負実数全体と∞ min 足し算 0

最後の例はmin-plus半環(min-plus代数)と呼ばれるものです。minをmaxに変えるとmax-plus半環です。「掛け算が足し算」となっているので分かりにくいかも知れません。次の記事に説明があります。

半環Kに順序があって、その順序が半環の構造と協調していれば、K = (K, +, 0, ・, 1, ≦) を順序半環と呼びます。詳しく言えば:

  1. Kは半環である。
  2. K上に順序≦が定義されている。
  3. x≦y かつ x'≦y' ならば、x + x' ≦ y + y'
  4. x≦y かつ x'≦y' ならば、x・x' ≦ y・y'
  5. 0≦x

先に挙げた半環の例は、すべて順序半環になります。min-plus半環は注意が必要で、通常の順序の逆を順序として採用します。∞がmin-plus半環のゼロなので、普通の順序ではゼロ=∞が最小になりません。逆向き順序を入れたmin-plus半環のなかでは、∞≦ x ≦0 です。

Kを半環(順序はなくてもよい)として、Sを集合とします。写像 a:S×S→K は正方行列とみなせます。Sの要素を添字と思い、a(t, s) を at,s と下付きで書けば、縦横のサイズが同じで、成分(係数)がKに入る行列です。下付きの at,s は面倒なので、a[t, s] と書くことにします。

Kには足し算・掛け算があるので、行列の乗法は普通どおりに定義できます。a, b:S×S→K に対して、c = ba は、次のように定義します。

  • c[u, s] = Σ(t∈S | b[u, t]a[t, s])

ここで、右辺は、t∈S を動かしての総和です。総和が定義できるためには、KやSに条件が必要ですが、今は気にしないことにします。総和が定義できるようなSだけを考える、と思ってください。気になる人は:

正方行列のモノイド圏

ここからは、Kを順序半環とします。単なる半環ではダメで、順序が必要です。Sを集合として、MatK(S, S) を正方行列全体からなる集合とします。

これから、MatK(S, S) をベースに厳密モノイド圏M(イタリックであることに注意)を構成します。圏MはKとSに依存するので、MK,S のように書くべきかも知れませんが、KとSは固定して考えます。

a, b∈MatK(S, S) に対して、a≦b とはすべての成分において不等号が成立することです。

  • a≦b ⇔ (s, t∈S に対して、a[t, s]≦b[t, s])

Mの対象の集合は、|M| = MatK(S, S) として、a≦b である (a, b) ごとに射 a→b が一本あるとします。もう少しハッキリと書くと:

  1. Obj(M) = |M| = MatK(S, S)
  2. Mor(M) = {(a, b)∈|M|×|M| | a≦b }
  3. dom:Mor(M)→|M| は、dom((a, b)) = a
  4. cod:Mor(M)→|M| は、cod((a, b)) = b
  5. ida = (a, a)
  6. (a, b);(b, c) = (a, c)

要するに、MatK(S, S)の順序に基いて作ったやせた圏です。

次に、圏Mにモノイド構造を与えます。|M| には行列の積によりモノイド構造が既にあります。単位対象は単位行列です。射にもモノイド積を入れるのですが、これはほとんど自明です。自明なんですが、当たり前すぎると難しい、ということがままあるので、少し説明します。「ステファネスク師匠の厳密モノイド圏の扱い方」が参考になるかも知れません。

a, bなどは圏Mの対象として、f, gなどは射とします。f:a→b, g:c→d が在ることは、a≦b and c≦d という順序関係の成立と同値です。Mがやせていることから、f\otimesg が存在すれば一意的に決まってしまうので、f\otimesg:a\otimesc→b\otimesd の存在だけを示せば十分です。\otimesは行列の積だったので、ac≦bd が示せればいいのですが、これは行列の積と≦の定義からすぐに出ます。

厳密モノイド圏としての次の法則達も、順序関係に言い換えれば自明なのがわかるでしょう。iは単位行列とします。

  • (f\otimesg)\otimesh = f\otimes(g\otimesh)
  • idi\otimesf = f\otimesidi = f
  • (f\otimesf');(g\otimesg') = (f;g)\otimes(f';g')
  • ida\otimesb = ida\otimesidb

モノイド対象

前節で定義したモノイド圏M内のモノイドを考えます。aをMの対象、つまりK係数のS×S正方行列とします。m:a\otimesa→a と u:i→a をモノイドの乗法と単位を表す射とします。

\otimesは行列の積で、mとuは順序関係なので、aa≦a と i≦a がモノイドを構成する要素です。結合律、左単位律、右単位律は、すべて自動的に成立してしまうので、追加の法則は不要です。結局、圏Mにおけるモノイドとは:

  • aa≦a と i≦a を満たす行列aがMのモノイドである。

Kがブール半環のとき

Kがブール半環({true, false}, ∨, false, ∧, true, ≦)だとします。モノイドaは、ブール値のS×S正方行列になります。モノイドである条件 aa≦a と i≦a を書き下してみます。

行列の積の公式から (aa)[u, s] = Σ(t∈S | a[u, t]a[t, s]) なので、aa≦a は、

  • Σ(t∈S | a[u, t]a[t, s]) ≦ a[u, s]

Kがブール半環なので、論理の書き方で書きなおしてみましょう。

  • ∃(t∈S | a[u, t]∧a[t, s]) ⇒ a[u, s]

今使っている≦と混同しないように、\sqsubsetという記号を使って、

  • u\sqsubsett ⇔ a[u, t]

のように約束すると、先の論理式は次のように言い換えられます。

  • u\sqsubsett かつ t\sqsubsets であるtが在るならば、u\sqsubsets

若干持ってまわった言い方ですが、関係\sqsubsetに関する推移律です。

同様にして、i≦a (iは単位行列)の表現を変えていけば:

  1. i≦a
  2. i[t, s]≦a[t, s]
  3. t≠s ならば 0≦a[t, s]、t = s ならば、1≦a[t, s]
  4. 0≦a[t, s] は常に成立、1≦a[s, s] だけが問題
  5. true≦a[s, s] は、true=a[s, s] と同じなので、a[s, s] が真
  6. s\sqsubsets が成立

i≦a は、行列aが定義する関係\sqsubsetに関する反射律でした。

まとめると; Kがブール半環のとき、圏Mのモノイド対象は、集合S上の反射的・推移的関係です。つまり、Sを台集合とするプレ順序です。

Kがmin-plus半環のとき

Kがmin-plus半環 (非負実数と∞, min, ∞, +, 0, ≦) だとします。再度注意しますが、実数の普通の足し算はmin-plus半環の掛け算です。順序は普通の順序を逆転させています。モノイドaは、非負実数(∞も含む)値のS×S正方行列になります。モノイドである条件 aa≦a と i≦a を書き下してみます。ブール半環のときと同様に進みます。

  • Σ(t∈S | a[u, t]a[t, s]) ≦ a[s, t]

Kがmin-plus半環なので、普通の書き方で書きなおしてみましょう。次の行の≧は普通の大小関係に直しました。

  • Min(t∈S | a[u, t] + a[t, s]) ≧ a[u, s]

aをdという文字に置き換えて、表現を少し修正すると:

  • tをどう動かしても、d(u, t) + d(t, s) ≧ d(u, s)

これは三角不等式です。

i≦a (iは単位行列)の表現を変えていけば:

  1. i≦a
  2. i[t, s]≦a[t, s]
  3. t≠s ならば 0≦a[t, s]、t = s ならば、1≦a[t, s]

ここで、min-plus半環から通常の実数と通常の順序に変更すると:

  • t≠s ならば ∞≧a[t, s]、t = s ならば、0≧a[t, s]

0≧a[s, s] だけが問題ですが、aをdという文字に置き換えてみれば:

  • d(s, s) = 0

まとめると; Kがmin-plus半環のとき、圏Mのモノイド対象は、集合S上の一般化距離です。

大きなストーリー?

冒頭で、「この事実の背後には大きなストーリーがありそう」と言いました。とはいえ、大きなストーリーはよく分かってません。

プレ順序や一般化距離空間は、豊饒圏として解釈できます(「モノイド圏、豊饒圏、閉圏と内部ホム」参照)。ということは、順序半環と正方行列を使った構成は、豊饒圏と同じことなのでしょう。

形式言語理論のための代数」においてオートマトン(ラベル付き遷移系)を作ったときも、順序半環係数の正方行列を使いました。あれは今回の構成とまったく同じです。関係ないはずはありません。

オートマトンの文脈でグロタンディーク平坦化したらシミュレーション(模倣)が出てきたのですが、他の状況でシミュレーションに対応するものは何なんでしょうか。それに意味があるのでしょうか。

今回は正方行列に注目してますが、必ずしも正方でない行列 MatK(S, T) の役割はなんでしょう。添字集合を固定しないで、すべての行列からなる圏 MatK を考えるとどうなるのでしょうか。

どの問いかけもデジャブな感じがするのですが、クリアに答えられたことがないし、今も答えられません。でも、面白い。