このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

グラフ達のモノイド圏内のモノイド対象は圏

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

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

環境となる圏 その圏の積 その圏の単位 モノイド概念
集合圏 直積 単元集合 普通のモノイド
ベクトル空間の圏 テンソル スカラー 代数(多元環
頂点集合が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] と書いたら次の意味になります。

  1. f:\u{A} \to \u{B} \In {\bf Set} である*2
  2. \forall a\in \u{A}.\, \src_B(f(a)) = \src_A(a) を満たす。
  3. \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つ定義しましょう。

  1. {\bf 0}_X \in |{\bf Graph}[X]|
  2. {\bf 1}_X \in |{\bf Graph}[X]|
  3. \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) と書きます。それぞれの構成素は:

  1. 台集合: \u{M} \in |{\bf Set}|
  2. 二項演算:  m: \u{M}\times \u{M} \to \u{M} \In {\bf Set}
  3. 単位元 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を対象集合とする圏

*1:十数年前と比べると、数式や可換図式がブログ記事内に書けるようになり、格段に説明がしやすくなりました。感慨深いですね。

*2:準同型写像とその台写像をキチンと区別するなら \u{f}: \u{A} \to \u{B} と書くべきです。

*3:自然変換については考えてないので、2-射はありません。