順序集合や距離空間も実はモノイドだった - 檜山正幸のキマイラ飼育記 (はてなBlog)

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

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

内容：

普通のモノイドといろいろなモノイド
プレ順序集合と一般化距離空間
順序半環係数の正方行列
正方行列のモノイド圏
モノイド対象
- Kがmin-plus半環のとき
大きなストーリー？

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

普通のモノイドは、集合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 $\otimes$ A→A
単位元を特定する写像 1→M	Cの射 I→A

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

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

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

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

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

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

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

x∈X に対して、x≦x （反射律）
x, y, z∈X に対して、x≦y かつ y≦z ならば x≦z （推移律）

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

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

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

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

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

順序半環係数の正方行列

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

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

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

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, ≦) を順序半環と呼びます。詳しく言えば：

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

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

Kを半環（順序はなくてもよい）として、Sを集合とします。写像 a:S×S→K は正方行列とみなせます。Sの要素を添字と思い、a(t, s) を a_t,s と下付きで書けば、縦横のサイズが同じで、成分（係数）がKに入る行列です。下付きの a_t,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を集合として、Mat_K(S, S) を正方行列全体からなる集合とします。

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

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

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

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

Obj(M) = |M| = Mat_K(S, S)
Mor(M) = {(a, b)∈|M|×|M| | a≦b }
dom:Mor(M)→|M| は、dom((a, b)) = a
cod:Mor(M)→|M| は、cod((a, b)) = b
id_a = (a, a)
(a, b);(b, c) = (a, c)

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

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

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

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

(f $\otimes$ g) $\otimes$ h = f $\otimes$ (g $\otimes$ h)
id_i $\otimes$ f = f $\otimes$ id_i = f
(f $\otimes$ f');(g $\otimes$ g') = (f;g) $\otimes$ (f';g')
id_ab = id_a $\otimes$ id_b

モノイド対象

前節で定義したモノイド圏M内のモノイドを考えます。aをMの対象、つまりK係数のS×S正方行列とします。m:a $\otimes$ a→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 $\sqsubset$ t ⇔ a[u, t]

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

u $\sqsubset$ t かつ t $\sqsubset$ s であるtが在るならば、u $\sqsubset$ s

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

同様にして、i≦a （iは単位行列）の表現を変えていけば：

i≦a
i[t, s]≦a[t, s]
t≠s ならば 0≦a[t, s]、t = s ならば、1≦a[t, s]
0≦a[t, s] は常に成立、1≦a[s, s] だけが問題
true≦a[s, s] は、true=a[s, s] と同じなので、a[s, s] が真
s $\sqsubset$ s が成立

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は単位行列）の表現を変えていけば：

i≦a
i[t, s]≦a[t, s]
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上の一般化距離です。

大きなストーリー？

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

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

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

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

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

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