十数年前に書いた次の記事があります。
- 圏、関手、モナドはどうしたら分かるの？ （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]) `$ と書きましょう。
前節では、$`\mathrm{Mon}({\bf Graph}[X]) `$ の対象を $`C`$ と書きましたが、文字や記号の書き換えをします。もちろん、書き換えても意味は何も変わりません。気分が変わるだけです。
- $`C \longrightarrow \cat{C}`$ （フォントを変えています）
- $`m \longrightarrow (-;-)`$
- $`e \longrightarrow \id_{-}`$
- $`\src_{\u{C}} \longrightarrow \dom`$
- $`\trg_{\u{C}} \longrightarrow \cod`$
すると、$`\mathrm{Mon}({\bf Graph}[X]) `$ の対象は次のように書けます。
$`\quad \cat{C} = (\u{\cat{C}}, (-;-), \id_{-})\\
\quad \u{\cat{C}} = (\u{\u{\cat{C}}}, \dom, \cod)
`$
モノイドとグラフの記法を、圏論の標準的な記法に置き換えました。外の圏である $`\mathrm{Mon}({\bf Graph}[X])`$ や $`{\bf Graph}[X]`$ と同じ記法になるので混乱しないように注意してください。
定義を再確認してみると、$`\mathrm{Mon}({\bf Graph}[X])`$ の対象は、対象集合が $`X`$ である小さい圏になります。射は、対象集合上では恒等である関手になります。次のように書いてもいいでしょう*3。
$`\quad {\bf Cat}[X] := \mathrm{Mon}({\bf Graph}[X]) `$
以上で、以下の表の一行の意味が説明できました。
| 環境となる圏 | その圏の積 | その圏の単位 | モノイド概念 |
|---|---|---|---|
| 頂点集合がXであるグラフの圏 | バンドル積（ファイバー積） | 反射的離散グラフ | Xを対象集合とする圏 |
