グラフ達のモノイド圏内のモノイド対象は圏 (オリジナル版)

十数年前に書いた次の記事があります。

圏、関手、モナドはどうしたら分かるの？（2007年3月）

上記過去記事のなかに「いろいろな圏におけるモノイド概念」の表があります。

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

上から3番めの「環境となる圏」に「頂点集合がXである反射的グラフの圏」とありますが、反射的の条件は無くてもかまなない、いやむしろ、無いほうが面白いことに気付きました。つまり、次のようなモノイド概念〈モノイド対象〉があるわけです。

環境となる圏	その圏の積	その圏の単位	モノイド概念
頂点集合がXであるグラフの圏	バンドル積（ファイバー積）	反射的離散グラフ	Xを対象集合とする圏

頂点集合がXであるグラフの圏にモノイド構造を入れて、そのモノイド圏内のモノイドが“Xを対象集合とする圏”になるのです。このことをこの記事で説明します。だいぶ時を隔てた敷衍です*1。
$\newcommand{\u}[1]{\underline{#1}} \newcommand{\hyp}{\text{-}} \newcommand{\id}{\mathrm{id} } \newcommand{\cat}[1]{\mathcal{#1} } \newcommand{\In}{\text{ in } } \newcommand{\src}{\mathrm{src} } \newcommand{\trg}{\mathrm{trg} } \newcommand{\dom}{\mathrm{dom} } \newcommand{\cod}{\mathrm{cod} } \newcommand{\K}{\mathrm{K} } \require{color} \newcommand{\Keyword}[1]{ \textcolor{green}{\text{#1}} }% \newcommand{\For}{\Keyword{For } }% \newcommand{\Let}{\Keyword{Let } }% \newcommand{\Define}{\Keyword{Define } }% \newcommand{\Where}{\Keyword{Where } }% \newcommand{\Declare}{\Keyword{Declare } }% \newcommand{\Holds}{\Keyword{Holds } }% \newcommand{\Justification}{\Keyword{Justification } }%$

内容：

頂点集合を固定したグラフの圏
グラフの圏のなかの特別な対象
セクションと反射的グラフ
グラフの圏のモノイド構造
モノイドの定義
グラフのモノイド圏内のモノイド
それって圏でしょ

頂点集合を固定したグラフの圏

集合 $X$ を選んで固定します。 $X$ を頂点集合とするグラフ（ここでのグラフは有向グラフ）の圏 ${\bf Graph}[X]$ を定義しましょう。グラフを $A = (\u{A}, \src_A, \trg_A)$ とします。頂点集合 $X$ もグラフの構成素なのですが、固定しているのでイチイチ書くのはやめます。

辺の集合： $\u{A} \in |{\bf Set}|$
辺の始点： $\src_A:\u{A} \to X \In {\bf Set}$ （src = source）
辺の終点： $\trg_A:\u{A} \to X \In {\bf Set}$ （trg = target）

$A, B$ が、 $X$ を頂点集合とする2つのグラフのとき、そのあいだの準同型写像〈homomorphism〉は次の図式を可換にする写像 $f:\u{A} \to \u{B}$ です。

$\require{AMScd} \begin{CD} \u{A} @>{f}>> \u{B}\\ @V{\src_A}VV @VV{\src_B}V\\ X @= X \end{CD}\\ \:\\ \begin{CD} \u{A} @>{f}>> \u{B}\\ @V{\trg_A}VV @VV{\trg_B}V\\ X @= X \end{CD}\\ \text{commutative in }{\bf Set}$

等式で書けば：

$\forall a\in \u{A}.\, \src_B(f(a)) = \src_A(a)$
$\forall a\in \u{A}.\, \trg_B(f(a)) = \trg_A(a)$

$f: A \to B \In {\bf Graph}[X$ ] と書いたら次の意味になります。

$f:\u{A} \to \u{B} \In {\bf Set}$ である*2。
$\forall a\in \u{A}.\, \src_B(f(a)) = \src_A(a)$ を満たす。
$\forall a\in \u{A}.\, \trg_B(f(a)) = \trg_A(a)$ を満たす。

$X$ を頂点集合とするグラフを対象として、そのあいだの準同型写像を射とする圏を定義するのは容易です（やってみてください）。その圏を ${\bf Graph}[X$ ] とします。

両端を固定した辺の集合と、準同型写像の制限を（圏と同じ記法で）定義しておくと便利です（この記事内で使う機会がなかったのですが）。

$\For A \in |{\bf Graph}[X]| \\ \For x, y\in X\\ \Define A(x, y) := \{ a\in \u{A} \mid \src_A(a) = x \land \trg_A(a) = y\}$

$\For f:A \to B \In {\bf Graph}[X] \\ \For x, y\in X\\ \Define f_{x, y} := f|_{A(x, y)}^{B(x, y)} : A(x, y) \to B(x, y) \In {\bf Set}$

$f|_{A(x, y)}^{B(x, y)}$ は、域と余域を部分集合に制限した写像です。

グラフの圏のなかの特別な対象

圏 ${\bf Graph}[X$ ] のなかの特別な対象を3つ定義しましょう。

${\bf 0}_X \in |{\bf Graph}[X]|$
${\bf 1}_X \in |{\bf Graph}[X]|$
$\K_X \in |{\bf Graph}[X]|$

最初は辺をまったく持たないグラフです。

$\Define \u{{\bf 0}_X } := {\bf 0} = \emptyset\\ \Define \src_{{\bf 0}_X } := \theta_X\\ \Define \trg_{{\bf 0}_X } := \theta_X$

ここで、 $\theta_X$ は空集合から集合 $X$ への唯一の写像です。

次は、頂点ごとの自己ループ辺だけを持つグラフ。

$\Define \u{{\bf 1}_X } := X\\ \Define \src_{{\bf 1}_X } := \id_X\\ \Define \trg_{{\bf 1}_X } := \id_X$

三番目は、任意の2頂点を結ぶ辺が必ず一本だけある完全有向グラフです。

$\Define \u{\K_X } := X\times X\\ \Define \src_{\K_X } := \pi^1_{X, X}\\ \Define \trg_{\K_X } := \pi^2_{X, X}$

ここで、 $\pi^1, \pi^2$ は直積の第一射影、第二射影です。

さらに、任意の集合 $S$ に対してグラフ $S_{/X}$ を定義しましょう。

$\Define \u{S_{/X} } := X\times S\\ \Define \src_{S_{/X} } := \pi^1_{X, S}\\ \Define \trg_{S_{/X} } := \pi^1_{X, S}$

この定義を使うと、先に定義した ${\bf 0}_X, {\bf 1}_X$ は次のように書けます。先の定義と同じ、または同型なグラフが得られます。

$\quad {\bf 0}_X := {\bf 0}_{/X}\\ \quad {\bf 1}_X := {\bf 1}_{/X}$

グラフ ${\bf 0}_X$ は圏 ${\bf Graph}[X]$ の始対象になります。しかし、 ${\bf 1}_X$ は終対象ではありません。 $\K_X$ が終対象になります。この事実の確認も容易ですからやってみてください。

セクションと反射的グラフ

$A = (\u{A}, \src_A, \trg_A)$ が ${\bf Graph}[X]$ の対象として、次の性質を持つ写像 $s:X \to \u{A}$ を $A$ のセクション〈section〉と呼びます。

$\quad s;\src_A = \id_X\\ \quad s;\trg_A = \id_X$

$s$ は、 $\src_A$ のセクションでもあり $\trg_A$ のセクションでもあるので、「双セクション」とでも呼んだほうがいいでしょうが、単に「セクション」で済ませます。

セクションは、頂点に自己ループ辺を対応させる写像になっています。セクションを持たないグラフもあります。例えば、 ${\bf 0}_X$ は（ $X$ が空でないなら）セクションを持ちません。 ${\bf 1}_X, \K_X$ は唯一つのセクションを持ちます。 $\{1, 2\}_{/X}$ は（ $X$ が空でないなら）たくさんのセクションを持ちます。

グラフにセクションを添えた構造 $(\u{A}, \src_A, \trg_A, \mathrm{sec}_A)$ を反射的グラフといいます。各頂点ごとに特定された自己ループ辺がくっついているグラフですね。「反射的」の語源は、グラフの辺を頂点のあいだの“関係”とみたときに反射的関係になるからですが、語源に拘ると誤解の原因になります。

$X = {\bf 1}$ のケースを考えると、 ${\bf Graph}[{\bf 1}]$ の対象（グラフ）は単なる集合と同一視可能で、反射的グラフは付点集合〈pointed set〉に相当します。

圏から結合〈合成〉だけを忘れても、恒等射は残ります。恒等射 $x \mapsto \id_x$ はグラフのセクションなので、忘却後の構造は反射的グラフとみなせます。したがって、圏の下部構造は反射的グラフと考えることもできますが、今は、さらに恒等射のセクションも忘れてグラフを議論しています。

辺をまったく持たないグラフ、つまり ${\bf 0}_X$ を離散グラフと呼びます。この用法をそのまま踏襲すると、反射的離散グラフは（ $X$ が空でないなら）存在しません。次のように語義を再解釈します。

反射的であり、辺が最小であるグラフを反射的離散グラフ〈reflexive discrete graph〉と呼ぶ。

結局、反射的離散グラフは ${\bf 1}_X$ のことになります。

次の事実はしばしば使われます。意識しておいてください。

グラフ $A$ のセクションと、 ${\bf 1}_X \to A$ というグラフ準同型写像は、1：1に対応する。

グラフの圏のモノイド構造

圏 ${\bf Graph}[X]$ にモノイド構造を定義しましょう。以下、演算 $\boxtimes_X$ について記述します。

まずは、2つの対象〈グラフ〉に対する $\boxtimes_X$ の定義です。

$\For A, B \in |{\bf Graph}[X]|\\ \Define A \boxtimes_X B := (\u{C}, \src_C, \trg_C)\\ \Where\\ \quad \u{C} := \{(a, b)\in \u{A}\times \u{B}\mid \trg_A(a) = \src_B(b) \}\\ \quad \src_C := \lambda\, (a, b)\in \u{C}. \src_A(a)\\ \quad \trg_C := \lambda\, (a, b)\in \u{C}. \trg_B(b)$

辺のペア $(a, b)$ で“繋げる”ペアを新たに辺だと思ったグラフが $C = A\boxtimes_X B$ です。

次に、2つの射に対する $\boxtimes_X$ の定義です。以下で、 $\Keyword{Declare}$ は定義すべき射のプロファイル（域と余域）の宣言です。 $\Keyword{Justification}$ は定義の正当性条件で、well-defined になるために必要な命題達です。

$\For f:A \to B, g:C \to D \In {\bf Graph}[X]\\ \Declare f\boxtimes_X g : A\boxtimes_X C \to B\boxtimes_X D \In {\bf Graph}[X]\\ \Define f\boxtimes_X g := \lambda\, (a, c) \in \u{A \boxtimes_X C}.\, (f(a), g(c))\\ \Justification\\ \quad \Let S := A\boxtimes_X C\\ \quad \Let T := B\boxtimes_X D\\ \quad \forall\, (a, c)\in \u{S}. \, (f(a), g(c)) \in \u{T}\\ \quad \forall\, (a, c)\in \u{S}. \, \src_T( (f\boxtimes_X g)(a, c) ) = \src_S( (a, c) )\\ \quad \forall\, (a, c)\in \u{S}. \, \trg_T( (f\boxtimes_X g)(a, c) ) = \trg_S( (a, c) )$

正当性条件は容易に示せるので、写像 $\boxtimes_X$ は well-defined です。

これで、同じ記号で表される2つの写像が定義できました。

$\quad \boxtimes_X : |{\bf Graph}[X]| \times |{\bf Graph}[X]| \to |{\bf Graph}[X]| \\ \quad \boxtimes_X : \mathrm{Mor}({\bf Graph}[X]) \times \mathrm{Mor}({\bf Graph}[X]) \to \mathrm{Mor}({\bf Graph}[X])$

これらが双関手〈二項関手〉となるためにはさらに次の条件を満たす必要があります。以下に出てくる $\dom, \cod$ は、グラフの準同型写像の域／余域のことです。

$\For f: A \to B, h:C \to D \In {\bf Graph}[X]\\ \Holds \dom(f \boxtimes_X h) = \dom(f) \boxtimes_X \dom(h)\\ \Holds \cod(f \boxtimes_X h) = \cod(f) \boxtimes_X \cod(h)\\ \:\\ \For A, B \in |{\bf Graph}[X]|\\ \Holds \id_{A \boxtimes_X B} = \id_A \boxtimes_X \id_B\\ \:\\ \For f: A \to B, g:B \to C, f':A'\to B', g':B' \to C' \In {\bf Graph}[X]\\ \Holds (f \boxtimes_X f');(g \boxtimes_X g') = (f;g)\boxtimes_X(f';g')$

これらも、定義に基づいた具体的な表示で確認すれば容易に示せます。例えば、最後の等式（交替律）の両辺を $(a, a') \in \u{A}\times \u{A'}$ に対して計算すると $(g(f(a)), g'(f'(a') )$ になります。

モノイド圏の定義には、以下のような構造同型射の族とそれに関するマックレーンの五角形／三角形法則も必要です。

$\For A, B, C \in |{\bf Graph}[X]|\\ \quad \alpha_{A, B, C} : (A\boxtimes_X B) \boxtimes_X C \to A\boxtimes_X (B \boxtimes_X C) \In {\bf Graph}[X]\\ \For A \in |{\bf Graph}[X]|\\ \quad \lambda_{A} : {\bf 1}_X \boxtimes_X A \to A\In {\bf Graph}[X]\\ \quad \rho_{A} : A \boxtimes_X {\bf 1}_X \to A\In {\bf Graph}[X]$

$\u{A\boxtimes_X B} \subseteq \u{A}\times \u{B}$ が成立するので、集合圏の直積に関する $\alpha, \lambda, \rho$ をそのまま流用して圏 ${\bf Graph}[X]$ の構造同型射の族を定義できます。マックレーンの五角形／三角形法則も、集合圏のそれから導くことができます。

以上から、 $({\bf Graph}[X], \boxtimes_X, {\bf 1}_X, \alpha, \lambda, \rho)$ がモノイド圏になることが分かりました。

モノイドの定義

通常のモノイド、つまり集合圏内のモノイド対象について復習しましょう。モノイド $M$ を、 $M = (\u{M}, m, e)$ と書きます。それぞれの構成素は：

台集合： $\u{M} \in |{\bf Set}|$
二項演算： $m: \u{M}\times \u{M} \to \u{M} \In {\bf Set}$
単位元： $e: {\bf 1} \to \u{M} \In {\bf Set}$

モノイドの（二項演算と単位元に関する）結合律、左単位律、右単位律を可換図式で記述しましょう。以下、 $\alpha, \lambda,\rho$ は“モノイド圏としての集合圏”の構造同型射です。

$\begin{CD} (\u{M}\times \u{M})\times \u{M} @>{\alpha_{\u{M},\u{M},\u{M}}}>> \u{M}\times (\u{M} \times \u{M})\\ @V{m\times \id_\u{M}}VV @VV{\id_\u{M} \times m}V \\ \u{M}\times \u{M} @. \u{M}\times \u{M}\\ @V{m}VV @VV{m}V\\ \u{M} @= \u{M} \end{CD}\\ \text{commutative in }{\bf Set}$

$\begin{CD} \u{M} @>{\lambda_{\u{M}}^{-1}}>> {\bf 1}\times \u{M}\\ @| @VV{e \times \id_\u{M}}V\\ \u{M} @<{m}<< \u{M}\times \u{M} \end{CD}\\ \text{commutative in }{\bf Set}$

$\begin{CD} \u{M} @>{\rho_{\u{M}}^{-1}}>> \u{M} \times {\bf 1}\\ @| @VV{\id_\u{M} \times e}V\\ \u{M} @<{m}<< \u{M}\times \u{M} \end{CD}\\ \text{commutative in }{\bf Set}$

以上の可換図式は、すべて集合圏のなかで考えましたが、集合圏以外のモノイド圏でも同じ図式を考えることができます。つまり、任意のモノイド圏のなかでモノイド対象を定義可能なわけです。「モノイド対象を定義する環境となるモノイド圏を変えれば、色々なモノイド概念が得られるよ」ということが冒頭で引用した「いろいろな圏におけるモノイド概念」の表の内容です。

グラフのモノイド圏内のモノイド

モノイド圏としての ${\bf Graph}[X]$ 内のモノイドを考えましょう。モノイド $C$ を、 $C = (\u{C}, m, e)$ と書きます。集合圏の場合と同じです。

ここで注意すべきは、 $C$ が ${\bf Graph}[X]$ 内のモノイドなので、 $\u{C}$ はモノイドの台、つまり ${\bf Graph}[X]$ の対象であるグラフであることです。 $\u{C}$ をさらに構成素に分解すると次のように書けます。

$\quad \u{C} = (\u{\u{C}}, \src_{\u{C}}, \trg_{\u{C}})\\ \Where\\ \quad \u{\u{C}} \in |{\bf Set}|\\ \quad \src_{\u{C}} : \u{\u{C}} \to X \In {\bf Set}\\ \quad \trg_{\u{C}} : \u{\u{C}} \to X \In {\bf Set}$

次のような二段階の忘却関手があります。（より詳しいことは「構造付き圏の定義と記述 // 忘却関手と忘却階層グラフ」参照）。以下で、 $\mathrm{Mon}({\bf Graph}[X] )$ は ${\bf Graph}[X]$ 内のモノイドの圏です。

$\xymatrix@1{ {\mathrm{Mon}({\bf Graph}[X] )} \ar[r]^-{\mathrm{U}} &{ {\bf Graph}[X] } \ar[r]^-{\mathrm{U}} &{ {\bf Set} }\\ }$

モノイドの法則〈公理〉となる可換図式は以下のとおり。前節の可換図式の文字と記号を置換しただけですけどね。

$\begin{CD} (\u{C}\boxtimes_X \u{C})\boxtimes_X \u{C} @>{\alpha_{\u{C},\u{C},\u{C}}}>> \u{C}\boxtimes_X (\u{C} \boxtimes_X \u{C})\\ @V{m\boxtimes_X \id_\u{C}}VV @VV{\id_\u{C} \boxtimes_X m}V \\ \u{C}\boxtimes_X \u{C} @. \u{C}\boxtimes_X \u{C}\\ @V{m}VV @VV{m}V\\ \u{C} @= \u{C} \end{CD}\\ \text{commutative in }{\bf Graph}[X]$

$\begin{CD} \u{C} @>{\lambda_{\u{C}}^{-1}}>> {\bf 1}_X \boxtimes_X \u{C}\\ @| @VV{e \boxtimes_X \id_\u{C}}V\\ \u{C} @<{m}<< \u{C}\boxtimes_X \u{C} \end{CD}\\ \text{commutative in }{\bf Graph}[X]$

$\begin{CD} \u{C} @>{\rho_{\u{C}}^{-1}}>> \u{C} \boxtimes_X {\bf 1}_X\\ @| @VV{\id_\u{C} \boxtimes_X e}V\\ \u{C} @<{m}<< \u{C}\boxtimes_X \u{C} \end{CD}\\ \text{commutative in }{\bf Graph}[X]$

それって圏でしょ

集合圏 ${\bf Set}$ 内のモノイドとモノイド準同型写像の全体は圏をなしますが、それを $\mathrm{Mon}({\bf Set}) = {\bf Mon}$ と書くわけです。グラフの圏 ${\bf Graph}[X]$ 内のモノイドとモノイド準同型写像の全体も同様に圏をなし、それを $\mathrm{Mon}({\bf Graph}[X])$ と書きましょう。