対称モノイド多圏（簡約版） - 檜山正幸のキマイラ飼育記 (はてなBlog)

単なる圏ではなくて多圏〈polycategory〉という概念が必要になることがけっこうあります。例えば、シーケント計算、テンソル計算、データベース理論などの圏論的定式化には多圏が欲しいところです。しかし、多圏をちゃんと定義するのはなかなかに難しい。そのことは次の記事に書きました。

多圏の必要性、煩雑さ、そして単純化 // 多圏はメンドクセー

上記の過去記事で次にように書いています。

最近、対称性がある場合の構成法を眺めていたら、同様な方法が非対称のケースにも適用可能なことに気が付きました。先入観があったんですね。対称性を仮定した議論が非対称の場合に通用できるはずがない、って。
というわけで、特定目的のための特定状況下においては、多圏の構成はそれほど難しくないことが分かりました。とはいえ、ブログ記事一回分で述べられるほどのショートカットではないです。多圏の話を少しずつでも書き進めることが出来たらいいな、とゆるく思っています。

ウーン、引用した過去記事を書いてから4年以上経過してるのね。“少しずつでも書き進め”てないなー。

ともかくも「特定目的のための特定状況下においては、多圏の構成はそれほど難しくない」のは事実です。「ブログ記事一回分で述べられるほどのショートカットではない」と書いてますが、ある程度の予備知識を仮定して、ザックリと述べるならばブログ記事一回でもなんとかなりそうです。この記事がそれです。記事タイトルの「簡約版」は、“簡約化した多圏”について簡約に〈手短に〉説明するという二重の意味です。

ところで、たまたま僕のこの記事を読んだ方は「多圏？そんなもの何の役に立つんだ？サッパリわからん」となるでしょう。しかし、多圏の概念を必要としている人が読めば、極めて具体的で有用な概念であると即座に気が付くはずです。アブストラクトナンセンスの抽象性・有用性とはそういうものです。

内容：

簡約多圏
圏のリストの圏
簡約多圏の射とシーケント
モノイド圏の標準簡約多圏
標準簡約多圏の事例
埋め込み関手と連言関手
置換の圏
置換の圏をリストの圏へ挿入する
対称性を持つモノイド簡約多圏
おわりに

簡約多圏

ちゃんとした多圏は、それを定義することさえ至難の業です。それは、「多圏の必要性、煩雑さ、そして単純化 // 多圏はメンドクセー」で引用したコスロウスキやガーナーの論文を眺めれば分かる通りです。そこで、ここでは単純化したバージョンの多圏を導入します。

Xを集合（大きい集合でもよい*1）として、Xの要素を（今の文脈では）~~アトム~~分子〈~~atom~~ molecule〉と呼ぶことにします*2。Xの要素〈分子〉のリストの全体を List(X) とします。List(X) は、リストの連接〈concatenation〉により（大きいかも知れない）モノイドになります。モノイド単位は空リストです。連接演算の中置演算子記号を'#'とします。空リストはεと書きましょう。

List(X) の要素を、A, B のように下線を引いた文字で表します。Aの（リストとしての）長さをm、Bの長さをnとすると、次のように書けます。

A = (A₁, ..., A_m)
B = (B₁, ..., B_n)
A#B = (A₁, ..., A_m)#(B₁, ..., B_n) = (A₁, ..., A_m, B₁, ..., B_n)
ε = ()

厳密モノイド圏 D = (D, $\otimes$ , I) （記号の乱用）が、次の性質を持つとき、分子集合X上の簡約多圏〈reduced polycategory〉と呼ぶことにします。

|D| = List(X)
Dの厳密モノイド構造を対象に制限したものは、List(X) の連接演算によるモノイド構造に一致する。

|D| = List(X) なので、Dの対象は A, B などと書きましょう。二番目の条件から、A $\otimes$ B = A#B, I = ε が成立します。

簡約多圏の定義には特に難しいことは使ってません。厳密モノイド圏の特殊なものに過ぎません。簡約多圏の対象は分子のリストですが、多対象〈polyobject | ポリオブジェクト〉と呼ぶことがあります。

圏のリストの圏

Cを通常の圏とします。Cにモノイド構造は要求しません（モノイド構造があってもいいけど）。Cから簡約多圏を作りましょう。それは、Cの対象と射をリストにした圏です。D = List(C) と置いて、新しい圏Dを定義します。

|D| = Obj(D) := List(Obj(C))
Mor(D) := List(Mor(C))

f, g∈Mor(D), f = (f₁, ..., f_m), g = (g₁, ..., g_m), A = (A₁, ..., A_m) として、

dom(f) := (dom(f₁), ..., dom(f_m))
cod(f) := (cod(f₁), ..., cod(f_m))
dom(ε) := I = ε （左辺のεは射としての空リスト、右辺のεは対象としての空リスト）
cod(ε) := I = ε （左辺のεは射としての空リスト、右辺のεは対象としての空リスト）
id_A = (id_A₁, ..., id_{A_m})
id_ε := ε （左辺のεは対象としての空リスト、右辺のεは射としての空リスト）
f;g = (f₁, ..., f_m);(g₁, ..., g_m) := (f₁;g₁, ..., f_m;g_m)

以上にように定義すると、D = List(C) は圏になります。対象（リスト）のモノイド積も、射（これもリスト）のモノイド積もリストの連接で定義すると、D = List(C) は厳密モノイド圏になります。今定義された厳密モノイド圏を、圏Cのリストの圏〈category of lists〉と呼びます。

A, B∈|D|, A = (A₁, ..., A_m), B = (B₁, ..., B_n)で、n ≠ m とします。このとき、D(A, B) = ∅ となることに注意。多くのホムセットが空です。

モノイド構造まで考えた D = List(C) が、簡約多圏になることはすぐに確認できるでしょう。これで我々は、簡約多圏の例を作れるようになりました。既に知っている圏に対して、そのリストの圏を作れば、それは簡約多圏です。

[補足]
圏C $\mapsto$ List(C) という対応は、CAT→CAT という自己関手になります。集合圏Set上でリストモナドが構成できるのと同様に、CAT上でもリストモナドが構成できます。CAT上のリストモナドの作り方は、Set上のそれと同じです。記号の乱用で、List = (List, μ, η) をCAT上のリストモナドとします。

CAT上のListモナドのアイレンベルク／ムーア圏 EM(CAT, List) を考えることができます。次の圏同値があります。

EM(CAT, List) $\cong$ StrMonCAT

右辺のStrMonCATは、厳密モノイド圏の圏です。以上の概念・構成は、2次元の圏論のなかで定式化できそうですが、僕はよく分かってないです。
[/補足]

簡約多圏の射とシーケント

Dを、分子集合X上の簡約多圏だとします。簡約多圏の定義から、|D| = List(X) で、モノイド構造 $\otimes$ , I を持ちます。Dの対象〈多対象〉の上では、モノイド積 $\otimes$ はリストの連接 # と一致します。

簡約多圏の対象を多対象と呼んだので、簡約多圏の射は多射と呼ぶのが順当でしょう。実際そう呼ぶことにします。が、英語で言うときは注意が必要です。polymorphism は別な意味（日本語だと多相、多態）で使われることが多いので polymap, polyarrow とすることがあります。

一般に、射fの域と余域を矢印で区切って並べた形 A→B を、ｆのプロファイルと呼びます。簡約多圏の射fのプロファイルは、f:A→B のようになります。ここで、A, B は分子のリストです。リストの成分〈項目〉まで書けば、f:(A₁, ..., A_m)→(B₁, ..., B_n) となります。多射（簡約多圏の射）のプロファイルをシーケント〈sequent〉とも呼びます。

[補足]
論理で出てくる古典論理のシーケントでは、矢印の左側のカンマと右側のカンマの解釈が違います。簡約多圏のシーケントでは、左右のカンマの扱いに違いはありません。

簡約多圏のシーケントはより単純なシーケントなので、コンパクトシーケント〈compact sequent〉と呼ぶのが正確です。が、コンパクトシーケントしか出てこないので、単にシーケントで済ませます。
[/補足]

多射fのシーケント〈プロファイル〉 (A₁, ..., A_m)→(B₁, ..., B_n) は、混乱の恐れがなければ括弧を省略して、A₁, ..., A_m → B₁, ..., B_n と書いてもかまいません。空リストがあるときは、 → B₁, ..., B_n、A₁, ..., A_m → 、→ （矢印だけ）のようになります。括弧の省略で混乱してしまうことがあるので、最初はちゃんと括弧で囲むことをおすすめします。

モノイド圏の標準簡約多圏

与えられた任意の圏からリストの圏を作れば簡約多圏になることは既に見ました。今度は与えられた圏Cがモノイド圏だとして、それから簡約多圏を作ってみます。Cから作られる簡約多圏をDと置きます。

Dの分子集合Xは、X := |C| とします。したがって、|D| = List(|C|) です。Dの2つの対象〈多対象〉A = (A₁, ..., A_m), B = (B₁, ..., B_n) に対して、ホムセット D(A, B) を定義しましょう。

D(A, B) = D((A₁, ..., A_m), (B₁, ..., B_n))
:= C(A₁ $\otimes$ ... $\otimes$ A_m, B₁ $\otimes$ ... $\otimes$ B_n)

ホムセット D(A, B) の要素は、Cの射であることに注意してください。よって、Dの多射の結合と恒等多射は、Cの射の結合と恒等射により定義できます。

今の説明で、A₁ $\otimes$ ... $\otimes$ A_m という書き方をしました。こういう「...」を使った書き方には注意が必要です。m ≧ 2 ならいいのですが、m = 1, m = 0 のケースが曖昧になりがちです。A₁ $\otimes$ ... $\otimes$ A_m = $\bigotimes$ [A] という書き方を使うとして：

m = 2 のとき： $\bigotimes$ [A] = $\bigotimes$ [(A₁, A₂)] = A₁ $\otimes$ A₂
m = 1 のとき： $\bigotimes$ [A] = $\bigotimes$ [(A₁)] = A₁
m = 0 のとき： $\bigotimes$ [A] = $\bigotimes$ [()] = I

ここで、Iはモノイド圏Cの単位対象です。

上記の手順でモノイド圏Cから作られた簡約多圏Dを、Cの標準簡約多圏〈standard reduced polycategory〉と呼び、StdPoly(C) と書くことにします。既に知られたモノイド圏Cがあれば、それから標準簡約多圏を作り出すことができます。

標準簡約多圏の事例

実際に、よく知られたモノイド圏からその簡約多圏を作ってみましょう。まず、Set = (Set, ×, 1) を、集合圏に直積でモノイド構造を入れたモノイド圏とします。StdPoly(Set) の対象〈多対象〉と射〈多射〉は：

対象は、集合達 A₁, ..., A_m のリスト A = (A₁, ..., A_m)。m = 1 のときは A = (A₁)、m = 0 のときは A = ()。
射は、f:A₁×...×A_m→B₁×...×B_n という形の写像。
- n = 1 のときは、f:A₁×...×A_m→B （B = B₁）という形の“多変数関数”。
- m = 1 のときは、f:A→B₁×...×B_n （A = A₁）という形の“多値関数”。
- m = n = 1 のときは、f:A→B という通常の写像。
- m = 0 のときは、f:A₁×...×A_m→1 という“多変数Void値関数”。
- n = 0 のときは、f:1→B₁×...×B_n という（事実上の）“タプル定数”。

通常、タプル一変数関数と多変数関数は区別しませんが、タプル一変数関数ではない多変数関数、タプル値関数ではない多値関数を定義したいなら、簡約多圏の枠組みが必要です。ここでの多値関数は、非決定性関数ではなくて、複数の値を一度に返す関数です -- プログラミング言語Common LispやSchemeでは多値関数が使えます。

StdPoly(Set) のなかでは、「タプル一変数関数と多変数関数」「タプル単値関数と多値関数」を明確に区別できます。これだけでも、気持ちいいと思いませんか？

次に、モノイド圏として FdVect = (FdVect, $\otimes$ , R) を取りましょう。有限次元ベクトル空間と線形写像に、テンソル積でモノイド構造を入れたモノイド圏です。ベクトル空間の係数体〈スカラー体 | 基礎体〉は実数体に固定します。

StdPoly(FdVect) の対象〈多対象〉と射〈多射〉は：

対象は、ベクトル空間達 V₁, ..., V_m のリスト V = (V₁, ..., V_m)。m = 1 のときは V = (V₁)、m = 0 のときは V = ()。
射は、f:V₁...V_m→W₁...W_n という形の線形写像。
- n = 1 のときは、f:V₁ $\otimes$ ... $\otimes$ V_m→W （W = W₁）という形の（事実上の）“複線形写像”。
- m = 1 のときは、f:V→W₁ $\otimes$ ... $\otimes$ W_n という形の“テンソル値線形写像”。
- m = n = 1 のときは、f:V→W （V = V₁）という通常の線形写像。
- m = 0 のときは、f:V₁ $\otimes$ ... $\otimes$ V_m→R という（事実上の）“複線形形式”。
- n = 0 のときは、f:R→W₁ $\otimes$ ... $\otimes$ W_n という（事実上の）“テンソル定数”。

テンソル計算の定式化には、FdVect より StdPoly(FdVect) のほうがずっと便利です。例えば、ベクトル空間のペア (V₁, V₂) とそのテンソル積である単一のベクトル空間 V₁ $\otimes$ V₂ が区別できずに混乱することがありますが、StdPoly(FdVect) を使えばそのへんはクリアになります。

StdPoly(Set) と StdPoly(FdVect) を使うだけでも、従来、曖昧さや気持ち悪さがつきまとった概念の明確化に役立ちます。おすすめです。

埋め込み関手と連言関手

任意の圏Cに対して、そのリストの圏 List(C) は簡約多圏になりました。そのとき、A $\mapsto$ (A), f $\mapsto$ (f) という対応をJとすると、J:C→List(C) は関手になります。Jは、忠実関手で、対象の上では単射になるので埋め込み関手です。Jによって埋め込まれた対象／射は、List(C) 内では長さ1のリストになります。

Cが単なる圏のときは、List(C)→C という方向の関手を規準的に〈canonically〉作る方法はありません。が、Cがモノイド圏のときは、StdPoly(C)→C を規準的に作ることができます。

規準的な StdPoly(C)→C は、次のように定義します。

対象に対して： |StdPoly(C)|∋ A = (A₁, ..., A_m) $\mapsto$ A₁ $\otimes$ ... $\otimes$ A_m ∈|C|
射に対しては何もしない。

この対応は関手になるので、Conj:StdPoly(C)→C と書き、連言関手〈conjunction functor〉と呼びます。「連言」は論理の言葉を拝借しています。連言関手の対象部分〈object part〉は、先に出した $\bigotimes$ です。

StdPoly(C) は、List(C) とは違いますが、同様にして埋め込み関手 J:C→StdPoly(C) は定義できます。埋め込み関手Jと連言関手Conjは、モノイド圏のあいだのモノイド圏同値を定義します。つまり、モノイド圏Cとモノイド圏StdPoly(C)は、モノイド圏として事実上同じとみなしてかまわないのです。

もとの圏Cが厳密モノイド圏でなくても、それと同値な圏 StdPoly(C) は厳密モノイド圏になります。これは、任意のモノイド圏を厳密モノイド圏にする方法を与えています。言い換えると、厳密化定理〈strictification theorem〉が得られたことになります。厳密化定理に関しては：

置換の圏

予備知識として、置換の圏〈category of permutations〉の説明をします。

自然数nに対して、集合{1, 2, ..., n}上の全単射写像の集合を Perm(n) または Sym(n) と書き、n次の置換群または対称群と呼びます。最初から群構造を考えます。Perm(0) は、空集合の恒等写像だけからなる単元群です。

置換の圏Permは次のように定義します。

|Perm| := N
m, n∈|Perm| に対して、ホムセット Perm(m, n) は：
- m = n のとき、Perm(m, n) = Perm(n)
- m ≠ n のとき、Perm(m, n) = ∅
id_n は恒等写像
射の結合は写像の結合〈合成〉

置換の圏とは、色々な次数の置換群をすべて寄せ集めたものです。

置換の圏をリストの圏へ挿入する

置換の圏Permの射、つまり置換を α, β などのギリシャ文字で表します。Cは任意の圏として、List(C) はCのリストの圏とします。

A∈|List(C)|、length(A) = m とします。ここで、length はリストの長さを計る関数です。α in Perm、dom(α) = cod(α) = m ならば、置換αはリストAに作用します。その作用を次の形で書きましょう。

A_α = (A₁, ..., A_m)_α := (A_α(1), ..., A_α(m))

置換αを、A→A_α の同型射だとみなして、List(C) に追加します。追加された同型射は $\hat{\alpha}$ とハットを被せることにします。 $\alpha \mapsto \hat{\alpha}$ という対応は埋め込みではありません。写像にさえなりません。ひとつの置換αが、色々な同型射として現れるからです。何と呼んでいいか分からないので、とりあえず、「置換を（同型射として）挿入する〈insert〉」と言うことにします。

単に $\hat{\alpha}$ と書いただけでは、置換 $\alpha$ がどこに挿入されたか分からないので、正確を期すなら

$\hat{\alpha}_{\underline{A}}:\underline{A} \to \underline{A}_\alpha$

のように書く必要があります。

すべての置換を、List(C) の挿入可能なすべての場所に挿入（追加）してできた圏を PermList(C) とします。PermList(C) の構成の細部を確認する必要がありますが、面倒なだけで難しくはありません。

もとの圏Cにモノイド構造が（ましてや対称モノイド構造が）なくても、PermList(C) は対称厳密モノイド圏になります。この事実の細部の確認も面倒だけど容易です。

対称性を持つモノイド簡約多圏

もう細かい話を端折る〈さぼる〉のですが、もとにするモノイド圏Cが対称モノイド圏であるとき、標準簡約多圏 StdPoly(C) も対称モノイド圏にすることができます。このとき、List(C) に置換の圏を挿入したのと同じような構成ができて、しかも、挿入した置換とCにもともとあった対称射を整合的に同一視することができます。置換が挿入された圏 PermStdPoly(C) がうまいこと作れるってことです。

Cの対称モノイド構造と、PermStdPoly(C)の対称モノイド構造が整合していることは、連言関手 Conj:PermStdPoly(C)→C が対称モノイド関手となり、埋め込み関手 J:C→PermStdPoly(C) と共に、対称モノイド圏としての圏同値を与えることだと言い表せます。

対称モノイド圏C、置換挿入済みの標準簡約多圏 PermStdPoly(C)、埋め込み関手 J:C→PermStdPoly(C)、連言関手（対称モノイド関手） Conj:PermStdPoly(C)→C の4つ組が、コンパクトシーケント計算の意味論の適切な舞台になります。

テンソル計算やデータベースの計算（非決定性写像の計算）も、コンパクトシーケント計算と同様で、上記の4つ組（のチューニング）で解釈できます。

おわりに

「モナドを使って多線形写像の圏を作る」では、ちょっと変わったモナドのクライスリ圏として、ある種の多圏PLを作りました。PLは、StdPoly(FdVect) と圏同型（圏同値より強い）です。PLに対称性（置換の作用）を考えてませんが、対称性を入れれば PermStdPoly(FdVect) と同じ対称モノイド簡約多圏になります。

モナドを使うか、今回の構成法を使うかで、作り方は違うのですが、得られる圏〈簡約多圏〉は同じです。通常の線形代数 → 複線形代数 → 多線形代数と系統的に展開するなら、入り口が違っても、PermStdPoly(FdVect) にたどり着きます。

PermStdPoly(FdVect) を使った計算には、とても具体的な応用がありますが、それはまたいずれ -- ではなくて、インターネット上のどこかに応用例の報告があがることを期待してます。

*1:圏論では、大きい集合（真の類）を避けようとしても避けきれないので、サイズ問題に神経質にならないほうがいいですよ。

*2:[追記]アトムなら分解不可能なのが普通です。Xの要素は、より基本的な構成素に分解される可能性があるので、アトム〈原子〉はやめて分子にします。[/追記]