一般化反射的グラフ

圏の下部構造は有向グラフです。圏には恒等射がありますが、恒等射に相当する特別な辺を備えた有向グラフは反射的有向グラフと呼びます。よって、圏の下部構造は反射的有向グラフだと言ってもいいでしょう。

圏を一般化した構造である一般化圏〈generalized category〉（あるいは圏類似代数構造〈category-like algebraic structure〉）を考える場合に、下部構造である反射的有向グラフを一般化してみるアプローチがあります。この記事では、そのアプローチに従い、一般化反射的グラフ／一般化反射的有向グラフを定義します。$`
\newcommand{\cat}[1]{ \mathcal{#1} }
\newcommand{\mbf}[1]{ \mathbf{#1} }
\newcommand{\mrm}[1]{ \mathrm{#1} }
\newcommand{\o}[1]{ \overline{#1} }
\newcommand{\id}{ \mathrm{id} }
\newcommand{\In}{ \text{ in }}
\newcommand{\op}{ \mathrm{op}}
`$

一般化反射的グラフを調べたい動機は、「オプティックの圏とコエンドと米田テンソル計算」に書いた次の問題を考えるためです。

それと、コエンドによりホムセットを定義する際のストリング図と、ホムセットの要素（つまり射）のストリング図は無関係ではないのですが、どういう関係があるかハッキリしない。これがハッキリしたら楽しい気がします。

内容：

反射的無向グラフ
一般化反射的グラフ
プロファイルごとの辺集合＝ホムセット
一般化グラフの有向性
一般化圏へ

反射的無向グラフ

無向グラフの定義の仕方は色々ありますが、ここでは「頂点の順序無しペアを境界とする辺の集まり」として定義しましょう。

$`A`$ を集合として、写像 $`\mrm{swap}_A`$ を次のように定義します。

$`\quad \mrm{swap}_A : A\times A \to A\times A\\
\text{For }(a, b)\in A\times A\\
\quad \mrm{swap}_A( (a, b) ) := (b, a)
`$

$`\mrm{swap}_A`$ と $`\id_{A\times A}`$ からなる二元集合は、写像の結合〈合成〉で群になります。この二元群を $`\mrm{Swap}_A`$ とします。群 $`\mrm{Swap}_A`$ は集合 $`A\times A`$ に自然に作用します。群作用による商集合〈軌道空間〉を $`(A\times A)/\mrm{Swap}_A`$ と書きます。

商集合 $`(A\times A)/\mrm{Swap}_A`$ の要素は、$`A`$ の部分集合のなかで、基数が 1 （単元集合）または基数が 2 （二元集合）である部分集合に対応します。つまり、次の同型が成立します（$`\mrm{card}`$ は集合の基数）。

$`\quad (A\times A)/\mrm{Swap}_A \cong \{x\in \mrm{Pow}(A) \mid \mrm{card}(x) = 1 \lor \mrm{card}(x) = 2\}`$

$`(A\times A)/\mrm{Swap}_A`$ の要素を、単元集合／二元集合と同一視して、$`\{a\}`$ または $`\{a, b\}`$ のように書きます。

以上の準備のもとで、無向グラフと反射的無向グラフを定義します。

無向グラフ〈undirected graph〉 $`G`$ の構成素は：

頂点の集合： $`V`$
辺の集合： $`E`$
境界写像： $`\mrm{bdry} : E\to (V\times V)/\mrm{Swap}_V`$

辺 $`e\in E`$ に対して、$`\mrm{bdry}(e) = \{a\}`$ のときは $`e`$ は自己ループ無向辺で、$`\mrm{bdry}(e) = \{a, b\}`$ （$`a\ne b`$ ）のときは異なる二頂点を結ぶ無向辺です。

反射的無向グラフ〈reflexive undirected graph〉では、構成素に次の写像が追加されます。

反射写像： $`\mrm{refl} : V\to (V\times V)/\mrm{Swap}_V`$
恒等辺写像： $`\mrm{id} : V\to E`$

さらに、次の可換図式を要求します。

$`\quad
\xymatrix{
{}
& E \ar[d]^{\mrm{bdry}}
\\
V \ar[ur]^{\mrm{id}} \ar[r]_-{\mrm{refl}}
& (V\times V)/\mrm{Swap}_A
}\\
\quad \text{commutative }\In \mbf{Set}
`$

前節の反射的無向グラフの例を少し抽象化して一般化反射的グラフを定義します。一般化反射的グラフ〈generalized reflexive graph〉 $`G`$ の構成素は：

頂点の集合： $`V`$
プロファイルの集合： $`P`$
辺の集合： $`E`$
境界写像： $`\mrm{bdry} : E\to P`$
反射写像： $`\mrm{refl} : V\to P`$ 単射であることを要求する。
恒等辺写像： $`\mrm{id} : V\to E`$ 単射であることを要求する。

次の可換図式を要求します。

$`\quad
\xymatrix{
{}
& E \ar[d]^{\mrm{bdry}}
\\
V \ar[ur]^{\mrm{id}} \ar[r]_-{\mrm{refl}}
& P
}\\
\quad \text{commutative }\In \mbf{Set}
`$

頂点の集合からプロファイルをどう作るかにより、様々な一般化反射的グラフが現れます。以下に幾つかの例を列挙します。

反射的無向グラフ

前節の反射的無向グラフは一般化反射的グラフの例です。

頂点の集合： $`V`$
プロファイルの集合： $`P := (V\times V)/\mrm{Swap}_V`$
辺の集合： $`E`$
境界写像： $`\mrm{bdry} : E\to P`$
反射写像： $`\mrm{refl} : V\to P`$
$`\mrm{refl}(A) := \{A, A\} = \{A\}`$
恒等辺写像： $`\mrm{id} : V\to E`$

反射的有向グラフ

反射的有向グラフ〈reflexive directed graph〉は一般化反射的グラフの例です。

頂点の集合： $`V`$
プロファイルの集合： $`P := V\times V`$
辺の集合： $`E`$
境界写像： $`\mrm{bdry} : E\to P`$
反射写像： $`\mrm{refl} : V\to P`$
$`\mrm{refl}(A) := (A, A)`$
恒等辺写像： $`\mrm{id} : V\to E`$

反射的複グラフ

反射的複グラフ〈reflexive multigraph〉は一般化反射的グラフの例です。

頂点の集合： $`V`$
プロファイルの集合： $`P := \mrm{List}(V) \times V`$
辺の集合： $`E`$
境界写像： $`\mrm{bdry} : E\to P`$
反射写像： $`\mrm{refl} : V\to P`$
$`\mrm{refl}(A) := ( (A), A)`$
恒等辺写像： $`\mrm{id} : V\to E`$

反射的多グラフ

反射的多グラフ〈reflexive polygraph〉は一般化反射的グラフの例です。

頂点の集合： $`V`$
プロファイルの集合： $`P := \mrm{List}(V) \times \mrm{List}(V)`$
辺の集合： $`E`$
境界写像： $`\mrm{bdry} : E\to P`$
反射写像： $`\mrm{refl} : V\to P`$
$`\mrm{refl}(A) := ( (A), (A) )`$
恒等辺写像： $`\mrm{id} : V\to E`$

プロファイルごとの辺集合＝ホムセット

$`G = (V, P, E, \mrm{bdry}, \mrm{refl}, \mrm{id})`$ を一般化反射的グラフとします。次の記法の約束をします。

$`\text{For }\alpha \in P\\
\quad G(\alpha) := \mrm{bdry}^{-1}(\alpha)
`$

$`\mrm{bdry}^{-1}`$ は、写像 $`\mrm{bdry}`$ の各点ごとの逆像集合を対応させる関数です。

集合 $`G(\alpha)`$ は、境界プロファイルが $`\alpha`$ である辺の集合です。圏論の言葉ならホムセット〈homset〉です。前節の事例ごとにホムセットを見ていきます。略記とは、括弧の一部を省略して書くことです。

反射的無向グラフ

プロファイル： $`\alpha = \{A, B\}, \alpha' = \{A\}`$
ホムセット： $`G(\alpha) = G(\{A, B\}), G(\alpha') = G(\{A\})`$
略記： $`G(\alpha) = G\{A, B\}, G(\alpha') = G\{A\} = G\{A, A\}`$

反射的有向グラフ

プロファイル： $`\alpha = (A, B)`$
ホムセット： $`G(\alpha) = G( (A, B) )`$
略記： $`G(\alpha) = G( A, B )`$

反射的複グラフ

プロファイル： $`\alpha = ( (A_1, \cdots, A_n) , B)`$
ホムセット： $`G(\alpha) = G( ( (A_1, \cdots, A_n) , B) )`$
略記： $`G(\alpha) = G( (A_1, \cdots, A_n), B )`$

反射的多グラフ

プロファイル： $`\alpha = ( (A_1, \cdots, A_n) , (B_1, \cdots, B_m))`$
ホムセット： $`G(\alpha) = G( ( (A_1, \cdots, A_n) , (B_1, \cdots, B_m)) )`$
略記： $`G(\alpha) = G( (A_1, \cdots, A_n), (B_1, \cdots, B_m) )`$

一般化グラフの有向性

一般化反射的グラフは次のように書けます。

$`\quad G = (V, P, E, \mrm{bdry}, \mrm{refl}, \mrm{id})`$

反射性の記述を取り除いてしまえば、単なる一般化グラフになります。

$`\quad G = (P, E, \mrm{bdry})`$

一般化グラフが有向〈directed〉であるとは、プロファイルの集合 $`P`$ が2つの集合の直積で書けていることです。

$`\quad P = S\times T`$

集合 $`S`$ をソースプロファイル〈source profile〉の集合、集合 $`T`$ をターゲットプロファイル〈target profile〉の集合と呼びます。

有向な一般化グラフにおいて、写像 $`\mrm{src}, \mrm{trg}`$ を次の図式が可換になるように決めます。$`\pi_1, \pi_2`$ は直積の射影です。

$`\quad
\xymatrix@C+1pc{
{}
& S
\\
E \ar[r]^{\mrm{bdry}} \ar[ur]^{\mrm{src}} \ar[dr]_{\mrm{trg}}
& S\times T \ar[u]_{\pi_1} \ar[d]^{\pi_2}
\\
{}
& T
}\\
\quad \text{commutative }\In \mbf{Set}
`$

$`G`$ が一般化有向グラフのとき、以上の構造を反映させて、次のように書きます。

$`\quad G = (S, T, E, \mrm{src}, \mrm{trg})`$

また、$`G`$ が一般化反射的有向グラフのとき、$`\mrm{refl}`$ を分解して次のように書きます。

$`\quad G = (V, S, T, E, \mrm{src}, \mrm{trg}, \mrm{srcRefl}, \mrm{trgRefl}, \mrm{id})\\
\text{Where}\\
\quad \mrm{srcRefl} : V \to S\\
\quad \mrm{trgRefl} : V \to T
`$

$`\mrm{srcRefl} = \mrm{id}; \mrm{src}`$ 、$`\mrm{trgRefl} = \mrm{id}; \mrm{trg}`$ という等式があるので、次のように短く書いてもかまいません。

$`\quad G = (V, S, T, E, \mrm{src}, \mrm{trg}, \mrm{id})`$

$`V = S = T`$ の場合が単なる（プレーンな）有向グラフです。

$`\quad G = (V, E, \mrm{src}, \mrm{trg}, \mrm{id})`$