コンピュータッドとそのモデル：同義語・類義語のジャングル

$\require{color}% \newcommand{\cat}[1]{ \mathcal{#1} } \newcommand{\bbf}[1]{ \mathbb{#1} } \newcommand{\In}{ \text{ in } } \newcommand{\Keyword}[1]{ \textcolor{green}{ \bf \text{#1} } }% \newcommand{\Where}{\Keyword{Where } } \newcommand{\For}{\Keyword{For } } \newcommand{\Iff}{\Leftrightarrow } \newcommand{\Imp}{\Rightarrow } \newcommand{\str}[1]{\mathrm{s}{#1}\text{-}} \newcommand{\hyp}{\text{-}}$ 2017年12月25日の記事：

しばらくブログを更新してなくて「死んでるんじゃないか？」と思われているので、なんか書きます。

またしばらく間があきましたが、生きてます。なんか書きます。

自然数 n = 0, 1, 2, … に対して n-コンピュータッド〈n-computad〉という概念があります。1970年代にロス・ストリート〈Ross Street〉が2-コンピュータッドを定義しました。その後、一般的な n-コンピュータッドにまで一般化されました。オリジナルである2-コンピュータッドは、今でも最もよく使われる重要なコンピュータッドです。

コンピュータッドと関連する概念には、たくさんの同義語・類義語があります。逆に言えば、コンピュータッドにより、様々な名前で呼ばれるたくさんの概念を統一的に扱えることになります。

内容：

グラフと圏の自由忘却随伴
図式と関手
2-コンピュータッド
同義語・類義語

引き続く記事：

グラフと圏の自由忘却随伴

グラフには無向グラフと有向グラフがあります*1が、ここでは有向グラフしか考えないので、グラフと言えば有向グラフです。

グラフを、4つ組 $(E, V, src, trg)$ で表します。ここで：

$E$ は、辺の集合。
$V$ は、頂点の集合。
$src:E \to V$ は、辺に始点を対応させる写像。
$trg:E \to V$ は、辺に終点を対応させる写像。

グラフとグラフ準同型写像からなる圏を ${\bf Graph}$ とします。

小さい圏とそのあいだの関手からなる圏を ${\bf Cat}$ とします。“圏の圏”は、自然変換まで入れて2-圏と考えるときが多いですが、ここでは ${\bf Cat}$ を1-圏と考えます*2。

圏 $\cat{C}\in |{\bf Cat}|$ が与えられたとき、グラフ $(E, V, src, trg)$ を次のようにして作れます。

$\quad (E, V, src, trg) := (Mor(\cat{C}), |\cat{C}|, dom, cod)$

このようにして作ったグラフを $\bbf{U}_1(\cat{C})$ と書きます。関手 $F:\cat{C}\to \cat{D} \In {\bf Cat}$ にはグラフ準同型写像が対応します。

$\quad \bbf{U}_1(F): \bbf{U}_1(\cat{C}) \to \bbf{U}_1(\cat{C}) \In {\bf Graph}$

$\bbf{U}_1$ は忘却関手 $\bbf{U}_1: {\bf Cat} \to {\bf Graph} \In {\bf CAT}$ になります（ ${\bf CAT}$ は、必ずしも小さくない圏の圏）。下付きの 1 は次元で、後で自然数 n に一般化します。

グラフ $G = (E, V, src, trg) \in |{\bf Graph}|$ が与えられると、グラフから自由圏（パスの圏）を作れます。その自由圏を $\bbf{F}_1(G)$ と書きます*3。グラフ準同型写像には関手を対応付けることができて、自由生成関手 $\bbf{F}_1:{\bf Graph} \to {\bf Cat} \In {\bf CAT}$ となります。

2つの関手 $\bbf{U}_1,\, \bbf{F}_1$ は随伴関手ペアになります。

$\quad \bbf{F}_1 \dashv \bbf{U}_1\\ \Where\\ \quad \bbf{F}_1: {\bf Graph} \to {\bf Cat} \In {\bf CAT}\\ \quad \bbf{U}_1: {\bf Cat} \to {\bf Graph} \In {\bf CAT}$

随伴系〈adjunction〉に伴い、ホムセットのあいだの同型があります。

$\quad {\bf Cat}(\bbf{F}_1(G), \cat{D}) \cong {\bf Graph}(G, \bbf{U}_1(\cat{D})) \In {\bf Set}$

この同型を与える写像に明示的に名前を付けておきましょう。

$\quad \bbf{Res}_1^{G, \cat{D}}: {\bf Cat}(\bbf{F}_1(G), \cat{D}) \to {\bf Graph}(G, \bbf{U}_1(\cat{D})) \In {\bf Set}\\ \quad \bbf{Ext}_1^{G, \cat{D}}: {\bf Graph}(G, \bbf{U}_1(\cat{D})) \to {\bf Cat}(\bbf{F}_1(G), \cat{D}) \In {\bf Set}$

$\bbf{Res}$ は restriction から、 $\bbf{Ext}$ は extension からです。次元を下付きにしているので、自然変換の成分添字は上付きにしました。上付き添字はしばしば省略します。

図式と関手

この記事を書くキッカケになったことは、「『図式』という言葉がよく分からん」というハナシでした。「図式」はよく使う言葉ですが、確かによく分からんですね。

とりあえず、ホムセット ${\bf Graph}(G, \bbf{U}_1(\cat{D}))$ の要素を図式と呼ぶことにします。つまり、 $D$ が図式〈diagram〉だとは、次のことです。

$\quad D:G \to \bbf{U}_1(\cat{D}) \In {\bf Graph}$

図式 $D$ に対して、その域〈domain〉であるグラフ $G$ を何と呼ぶべきでしょう？これも「図式」なんですよね。コミュニケーションに困るので、僕は図式の形状〈shape | シェープ〉と呼んでいます。そして、圏 $\cat{D}$ が図式が描かれる場所なので、ローカル用語でキャンバス圏と呼んでいます。

	$D$	$G$	$\cat{D}$
呼び名	図式	（図式の）形状	（図式の）キャンバス圏

ところで、随伴系 $\bbf{F}_1 \dashv \bbf{U}_1$ に伴うホムセット同型から次の関手が導かれます。

$\quad \bbf{Ext}_1(D) : \bbf{F}_1(G) \to \cat{D} \In {\bf Cat}$

$D \leftrightarrow \bbf{Ext}_1(D)$ は1：1対応なので、しばしば同一視されます。そうなると、「図式」が意味するものがさらに曖昧になります。

$D :G \to \bbf{U}_1(\cat{D}) \In {\bf Graph}$
$G \in |{\bf Graph}|$
$\bbf{Ext}_1(D) : \bbf{F}_1(G) \to \cat{D} \In {\bf Cat}$
$\bbf{F}_1(G) \in |{\bf Cat}|$

これらの区別をあまり意識する必要がないときもありますが、区別しないと混乱することもあります。適切に呼び分ける方法はないので、注意深く語るか、ローカル用語を作るしかないでしょう。

2-コンピュータッド

0-コンピュータッドは集合のことです。0-コンピュータッドと0-圏（0-圏も集合）をつなぐ随伴系は次のような自明な随伴系です。

$\quad \bbf{F}_0 \dashv \bbf{U}_0\\ \Where\\ \quad \bbf{F}_0 = \mathrm{Id}_{\bf Set}: {\bf Set} \to {\bf Set} \In {\bf CAT}\\ \quad \bbf{U}_0 = \mathrm{Id}_{\bf Set}: {\bf Set} \to {\bf Set} \In {\bf CAT}$

1-コンピュータッドは有向グラフのことです。0-コンピュータッドと1-コンピュータッドは既知の概念です。新しい概念、2-コンピュータッドを定義しましょう。

1-コンピュータッド＝有向グラフを、 $\Sigma = (\Sigma_1, \Sigma_0, src, trg)$ と書きます。このような記号の選び方／書き方は、指標理論やコンピュータッド理論の習慣です。先に述べたことから、自由圏〈パスの圏〉 $\bbf{U}_1(\Sigma)$ を作れます。自由圏の射はグラフ上のパスです。2本の射〈パス〉の両端が一致するとき、その2本の射は共端〈平行 | pararell〉だといいます。

$\For p, q \in Mor(\bbf{U}_1(\Sigma))\\ \quad (p と q は共端) \Iff dom(p) = dom(q) \land cod(p) = cod(q)$

2-コンピュータッド〈2-computad〉は、1-コンピュータッドに構成素が追加されたもので、 $(\Sigma_2, src_1, trg_1, \Sigma_1, \Sigma_0, src_0, trg_0)$ と書けます。 $(\Sigma_1, \Sigma_0, src_0, trg_0)$ は1-コンピュータッドです。この1-コンピュータッドから生成された自由圏を $\cat{S} := \bbf{F}_1( (\Sigma_1, \Sigma_0, src_0, trg_0) )$ と略記します。追加された部分に関しては：

$\Sigma_2$ は、集合。
$src_1:\Sigma_2 \to Mor(\cat{S})$ は、写像。
$trg_1:\Sigma_2 \to Mor(\cat{S})$ は、写像。
$\alpha\in \Sigma_2$ に関して、 $src_1(\alpha)$ と $trg_1(\alpha)$ は共端。

以上が2-コンピュータッドの定義です。2-コンピュータッドは、圏 $\cat{S} := \bbf{F}_1( (\Sigma_1, \Sigma_0, src_0, trg_0) )$ に2-射の集合 $\Sigma_2$ がアタッチされた構造だとみなせます。

ここでは、一般的なn-コンピュータッドは定義しませんが、一般的な場合でも通用する記法だけ説明しておきます。 $\Delta(n) := \{0, 1, \cdots, n-1\}$ として、n-コンピュータッドを次のように書きます。

$\quad \Sigma = (src_k, trg_k:\Sigma_{k + 1} \to \Sigma_{k}^*)_{k \in \Delta(n)}$

n-コンピュータッド $\Sigma$ には、 $0 \le k \le n$ に対するk-コンピュータッドが含まれるので、それを $\Sigma_{\le k}$ と書くことにして、 $\Sigma_k^* := \bbf{F}_k(\Sigma_{\le k})$ という略記を使っています。 $n = 0, 1, 2$ のときは次のようになります。

$n = 0$ のとき：

$\quad \Sigma = \Sigma_0$

$n = 1$ のとき：

$\quad \Sigma = (src_k, trg_k:\Sigma_{k + 1} \to \Sigma_k^*)_{k \in \{0\} }\\ \qquad = (src_0, trg_0:\Sigma_1 \to \Sigma_0^*)$

$n = 2$ のとき：

$\quad \Sigma = (src_k, trg_k:\Sigma_{k + 1} \to \Sigma_k^*)_{k \in \{0, 1\}}\\ \qquad = ( (src_1, trg_1:\Sigma_2 \to \Sigma_1^*), (src_0, trg_0:\Sigma_1 \to \Sigma_0^*) )$

2-コンピュータッドと厳密2-圏をつなぐ随伴系は次のようになります。

$\quad \bbf{F}_2 \dashv \bbf{U}_2\\ \Where\\ \quad \bbf{F}_2: 2\hyp{\bf Compd} \to \str{2}{\bf Cat} \In {\bf CAT}\\ \quad \bbf{U}_2: \str{2}{\bf Cat} \to 2\hyp{\bf Compd} \In {\bf CAT}$

$\str{2}$ は「厳密2-」の意味です。2 を n に置き換えれば、一般的なn-コンピュータッドと厳密n-圏をつなぐ随伴系になります。今回は、この随伴系についての詳細は述べません。

同義語・類義語

「『図式』という言葉がよく分からん」となる理由のひとつは、次の関係でした。

$\quad {\bf Cat}(\bbf{F}_1(G),\cat{D}) \cong {\bf Graph}(G, \bbf{U}_1(\cat{D}))$

このホムセット同型をコンピュータッドの言葉で書けば次のようです。

$\quad \str{1}{\bf Cat}(\Sigma^*,\cat{D}) \cong 1\hyp{\bf Compd}(\Sigma, \bbf{U}_1(\cat{D}))$

次の表の上段が $\str{1}{\bf Cat}$ 側の概念、下段が $1\hyp{\bf Compd}$ 側の概念です。

関手	関手の域	関手の余域
図式	（図式の）形状	（図式の）キャンバス圏

次元が2になると、ホムセット同型は次のようです。

$\quad \str{2}{\bf Cat}(\Sigma^*,\cat{D}) \cong 2\hyp{\bf Compd}(\Sigma, \bbf{U}_2(\cat{D}))$

2次元の概念を表す言葉には「2-」を付けると：

2-関手	2-関手の域	2-関手の余域
2-図式	（2-図式の）2-形状	（2-図式の）キャンバス2-圏

使われる言葉が上の表の6個（同義語が3組）なら苦労はないのですが、実際には同義語・類義語が山のようにあります。

図式の形状であるコンピュータッドと同義・類義の言葉：

多グラフ
指標
仕様
生成系
公理系
アルファベット
文法
ドクトリン
セオリー
スキーマ
インターフェイス
型クラス

図式である関手と同義・類義の言葉：

モデル
インスタンス
代数
加群
表現
実現
実装
抽象マシン
実行エンジン

言葉が使われる分野・場面が違うので、それぞれにニュアンスはあるのですが、内容的には自由生成関手と忘却関手の随伴性の議論です。ターゲット圏（関手の域圏、図式のキャンバス圏）は多くの場合集合圏 ${\bf Set}$ ですが、ターゲット圏を変えれば色々なバリエーションが出てきます。

言葉が違えば、記法も少しずつ違ってきます。例えば、ホムセット $n\hyp{\bf Compd}(\Sigma, \bbf{U}_n(\cat{D})) \cong \str{n}{\bf Cat}(\Sigma^*, \cat{D})$ を表す記法には次のようなものがあります。

$Model(\Sigma, \cat{D}),\, Model_{\cat{D}}(\Sigma)$
$Inst(\Sigma, \cat{D}) ,\, Inst_{\cat{D}}(\Sigma)$
$Alg(\Sigma, \cat{D}) ,\, Alg_{\cat{D}}(\Sigma)$
その他色々

それぞれの分野ごとの歴史・経緯があるので、用語・記法を揃えることは出来ないでしょうが、コンピュータッドと随伴系の概念を使えば、共通性が抽出できることは留意しておいていいでしょう。

*1:無向辺と有向辺が混じったグラフもありますが、使うことは稀です。

*2:1-圏として考えることを明示するために、僕は ${}_1{\bf Cat}$ という書き方をしますが、今回はこの書き方は使わないことにします。

*3: $\bbf{F}_1$ は一元体と同じ記法になってしまいましたが、偶発的コンフリクトなので気にしないでください。