今年（2024年）最後の投稿。内容はいつもと変わらんけど。
一般化ハイパーグラフについては、「一般化ハイパーグラフ」で述べました。一般化ハイパーグラフは、スケマティック集合のなかでも特に扱いやすいモノです。最近、その重要性を再認識しています。この記事では、一般化ハイパーグラフを活用するための補足事項を幾つか追加します。$`
\newcommand{\cat}[1]{ \mathcal{#1} }
\newcommand{\mbf}[1]{ \mathbf{#1} }
\newcommand{\mrm}[1]{ \mathrm{#1} }
\newcommand{\o}[1]{ \overline{#1} }
\newcommand{\u}[1]{ \underline{#1} }
\newcommand{\id}{ \mathrm{id} }
\newcommand{\In}{ \text{ in }}
%\newcommand{\On}{ \text{ on }}
\newcommand{\Iff}{ \Leftrightarrow }
\newcommand{\op}{ \mathrm{op}}
\newcommand{\hyp}{\text{－} }
\newcommand{\twoto}{\Rightarrow }
`$
内容：
一般化ハイパーグラフの圏
「一般化ハイパーグラフ // 一般化ハイパーグラフ」で述べたように、一般化ハイパーグラフは次の構成素を持ちます。ただし、過去記事では単なる写像だった $`P`$ を、ここでは関手だとします。そうする理由は後述します。
- プロファイル・コンストラクタ： $`P: \mbf{Set} \to \mbf{Set} \In \mbf{CAT}`$
- 頂点の集合： $`V \in |\mbf{Set}|`$
- 辺の集合： $`E \in |\mbf{Set}|`$
- 境界写像： $`\mrm{bdry}: E \to P(V) \In \mbf{Set}`$
プロファイル・コンストラクタが $`P`$ である一般化ハイパーグラフの圏を $`\mbf{HyGraph}^P`$ と書きます。$`H\in |\mbf{HyGraph}^P|`$ であるとき、プロファイル・コンストラクタ $`P`$ は周知なので省略して、次のように書きます。
$`\quad H = (V, E, \mrm{bdry}) \;\in |\mbf{HyGraph}^P|`$
圏 $`\mbf{HyGraph}^P`$ の対象である一般化ハイパーグラフを$`P`$-ハイパーグラフ〈$`P`$-hypergraph〉と呼びます。プロファイル・コンストラクタ $`P`$ が文脈から明らかなら、$`P`$-ハイパーグラフを単にハイパーグラフ〈hypergraph〉と略称してかまいません。
話が前後しますが、圏 $`\mbf{HyGraph}^P`$ の射は、$`P`$-ハイパーグラフのあいだの準同型射です。$`H, K\in |\mbf{HyGraph}^P|`$ のあいだの準同型射〈homomorphism〉 $`f`$ は、次の構成素を持ちます。
- 頂点パート〈vertex part〉： $`f_{\mrm{vert}} : \mrm{Vert}(H) \to \mrm{Vert}(K) \In \mbf{Set}`$
- 辺パート〈edge part〉： $`f_{\mrm{edge}} : \mrm{Edge}(H) \to \mrm{Edge}(K) \In \mbf{Set}`$
次の図式の可換性を課します。
$`\quad \xymatrix{
\mrm{Edge}(H) \ar[r]^{\mrm{bdry}_H} \ar[d]_{f_\mrm{edge} }
& {P(\mrm{Vert}(H))} \ar[d]^{P( f_\mrm{vert} )}
\\
\mrm{Edge}(K) \ar[r]^{\mrm{bdry}_K}
& {P(\mrm{Vert}(K))}
}\\
\quad \text{commutative}\In \mbf{Set}
`$
上記の図式が意味を持つには、プロファイル・コンストラクタ $`P`$ は単なる写像ではなくて、関手である必要があったのです。
通常のグラフ（有向グラフ）と複グラフ〈multigraph〉と多グラフ〈polygraph〉を定義するには、次のプロファイル・コンストラクタを使います。
- $`\mrm{Sq}(X) := X\times X,\; \mrm{Sq}(f) := f\times f`$ （'Sq' は square から）
- $`\mrm{Multi}(X) := \mrm{List}(X)\times X,\; \mrm{Multi}(f) := \mrm{List}(f)\times f`$
- $`\mrm{Poly}(X) := \mrm{List}(X)\times \mrm{List}(X),\; \mrm{Poly}(f) := \mrm{List}(f)\times\mrm{List}(f)`$
これらの関手をプロファイル・コンストラクタとする一般化ハイパーグラフの圏はそれぞれ、グラフの圏、複グラフの圏、多グラフの圏です。
- $`\mbf{Graph} := \mbf{HyGraph}^\mrm{Sq}`$
- $`\mbf{Multigraph} := \mbf{HyGraph}^\mrm{Multi}`$
- $`\mbf{Polygraph} := \mbf{HyGraph}^\mrm{Poly}`$
ここまでの話では、頂点の集合も辺の集合も小さい集合だったので、一般化ハイパーグラフは小さい一般化ハイパーグラフ〈small generalized hypergraph〉です。大きな集合（小さいとは限らない集合）をベースとすると、大きい一般化ハイパーグラフ〈large generalized hypergraph〉が定義できます。同様な定義ですが構成素を繰り返すと：
- プロファイル・コンストラクタ： $`P: \mbf{SET} \to \mbf{SET} \In \mathbb{CAT}`$
- 頂点の集合： $`V \in |\mbf{SET}|`$
- 辺の集合： $`E \in |\mbf{SET}|`$
- 境界写像： $`\mrm{bdry}: E \to P(V) \In \mbf{SET}`$
大きな$`P`$-ハイパーグラフのあいだの準同型射も小さい場合と同様です。大きな$`P`$-ハイパーグラフとそのあいだの準同型射からなる圏は $`\mbf{HyGRAPH}^P`$ と書きます。
用語法
通常のグラフは圏の台〈underlying thing | carrier〉となっています。複グラフはオペラッド〈複圏〉の台です。一般化ハイパーグラフに関して語る場合でも、圏の用語法やオペラッドの用語法が混じってしまいます。異なる典型事例や異なるメンタルモデルに由来する用語・記号がゴチャ混ぜになるので注意が必要です。
| 一般化ハイパーグラフ | 圏 | オペラッド〈複圏〉 |
|---|---|---|
| 頂点 | 対象 | 色 |
| 頂点の集合 | 対象の集合 | 色の集合 |
| プロファイル・コンストラクタ（一般論） | 集合の平方（具体例） | リスト構成と直積構成（具体例） |
| 辺〈ハイパー辺〉 | 射 | オペレーション〈オペレーター〉 |
| 辺の集合 | 射の集合 | オペレーション〈オペレーター〉の集合 |
一般論では、辺をセル〈cell〉と呼ぶかも知れません。頂点を0-セル〈0-cell〉、辺を1-セル〈1-cell〉と呼ぶこともあります。ここでの 0, 1 は次元ですが、「辺の次元は 1」とは言いにくい状況もあります。例えば、多グラフの辺〈多辺〉は2次元図形で描画されることが多いので「辺の次元は 2」と言いたくなります。
ある特定の典型事例やメンタルモデルに起因する用語・記号は、別な状況ではひどくトンチンカンでミスリーディングになり得ます。用語・記号から、根拠のない連想をしないようにしましょう。
構成素の略記法
$`H \in |\mbf{HyGraph}^P|`$ のとき、$`H`$ の構成素を次のように書きます。
- 頂点の集合： $`\mrm{Vert}(H)`$
- 辺の集合： $`\mrm{Edge}(H)`$
- 境界写像： $`\mrm{bdry}_H`$
$`f:H \to K \In \mbf{HyGraph}^P`$ のとき、$`f`$ の構成素を次のように書きます。
- 頂点パート： $`f_\mrm{vert}: \mrm{Vert}(H) \to \mrm{Vert}(K) \In \mbf{Set}`$
- 辺パート： $`f_\mrm{edge}: \mrm{Edge}(H) \to \mrm{Edge}(K) \In \mbf{Set}`$
頂点パートと辺パートをオーバーロードして、どちらも $`f`$ と書くこともあります。
さらに、ハイパーグラフの頂点の集合と辺の集合を次のように略記していいとします。
- 頂点の集合： $`|H| := \mrm{Vert}(H)`$
- 辺の集合： $`\o{H} := \mrm{Edge}(H)`$
絶対値記号は圏の場合と同じです。オーバーライン記法は他の用途でも使うのでコンフリクトのリスクがありますが、短く書けて便利です。
この略記法と、準同型射の頂点パートと辺パートのオーバーロードを使うと、準同型射の条件である可換図式は次のように書けます。
$`\quad \xymatrix{
\o{H} \ar[r]^{\mrm{bdry}_H} \ar[d]_{f }
& {P( |H| )} \ar[d]^{P( f )}
\\
\o{K} \ar[r]^{\mrm{bdry}_K}
& {P( |K| )}
}\\
\quad \text{commutative}\In \mbf{Set}
`$
自己関手とモナドの略記法
$`P`$-ハイパーグラフの圏 $`\mbf{HyGraph}^P`$ （または $`\mbf{HyGRAPH}^P`$）の上のモナドは、スケマティック代数系（スケマティック集合を台とする代数系）の定義の道具として重要です。
モナドは自己関手 $`E: \mbf{HyGraph}^P \to \mbf{HyGraph}^P`$ を台とします。自己関手 $`E`$ の適用をダイアクリティカルマークで表すことにします。アキュート〈アクサンテギュ〉やチルダはダイアクリティカルマークですが、言語学的なダイアクリティカルマークではなくても、右肩のアスタリスクやダッシュ〈プライム〉も利用します。
例えば、ダッシュ $`(\hyp)'`$ を自己関手 $`E`$ の略記に使うとするなら：
$`\text{For }H \in |\mbf{HyGraph}^P|\\
\quad H' := E(H)\\
\text{For }f:H\to K \In \mbf{HyGraph}^P\\
\quad f' := E(f)
`$
しばしば、共変関手なら $`f_* :=E(f)`$ 、反変関手なら $`f^* := E(f)`$ という略記が使われますが、ここではダッシュだけで済ませることにします。「上にマークが付くなら反変」というルールは使えなくなります。
「モナドの乗法自然変換は $`\mu`$ 、単位自然変換は $`\eta`$」という習慣は使うことにします。モナドの台関手をダッシュで略記する記法で自然変換の成分を書けば：
$`\text{For }H \in |\mbf{HyGraph}^P|\\
\quad \mu_H : {H'}' \to H' \In \mbf{HyGraph}^P\\
\quad \eta_H : H \to H' \In \mbf{HyGraph}^P
`$
$`\mu, \eta`$ の自然性〈naturality〉は次のように書けます。
$`\text{For }f:H \to K \In \mbf{HyGraph}^P\\
\quad \xymatrix{
{{H'}'} \ar[r]^{\mu_H} \ar[d]_{{f'}'}
& {H'} \ar[d]^{f'}
\\
{{K'}'} \ar[r]^{\mu_K}
& {K'}
}\\
\text{commutative}\In \mbf{HyGraph}^P
`$
$`\text{For }f:H \to K \In \mbf{HyGraph}^P\\
\quad \xymatrix{
H \ar[r]^{\eta_H} \ar[d]_{f}
& {H'} \ar[d]^{f'}
\\
K \ar[r]^{\eta_K}
& {K'}
}\\
\text{commutative}\In \mbf{HyGraph}^P
`$
モナド乗法の結合法則〈結合律 | associative law〉は次のようです。
$`\text{For }H \in |\mbf{HyGraph}^P|\\
\quad \xymatrix{
{{{{H}'}'}'} \ar[r]^{(\mu_{H})'} \ar[d]_{\mu_{{H}'}}
& {{\cat{H}'}'} \ar[d]^{\mu_{{H}}}
\\
{{{H}'}'} \ar[r]_{\mu_{{H}}}
& {{H}'}
}\\
\quad \text{commutative}\In \mbf{HyGraph}^P
`$
モナド単位の単位法則〈単位律 | unit law〉は次のようです*1。
$`\text{For }H \in |\mbf{HyGraph}^P|\\
\quad \xymatrix{
{H'} \ar[r]^{(\eta_H)'} \ar@{=}[dr]
& {{{H}'}'} \ar[d]^{\mu_{H}}
\\
{}
& {H'}
}\\
\quad \text{commutative}\In \mbf{HyGraph}^P\\
\quad \xymatrix{
{H'} \ar[r]^{ \eta_{H'}} \ar@{=}[dr]
& {{{H}'}'} \ar[d]^{\mu_{H}}
\\
{}
& {H'}
}\\
\quad \text{commutative}\In \mbf{HyGraph}^P
`$
法則が簡潔な図式で表現できます。
アイレンベルク／ムーア代数
$`E = (E, \mu, \eta)`$ （記号の乱用）を圏 $`\mbf{HyGraph}^P`$ 上のモナドとします*2。モナド $`E`$ のアイレンベルク／ムーア代数〈Eilenberg-Moore algebra〉 $`A`$ を次のように書きます。
$`\quad A = (U(A), m_A)\\
\text{Where}\\
\quad U(A) \in |\mbf{HyGraph}^P|\\
\quad m_A : E(U(A)) \to U(A) \In \mbf{HyGraph}^P
`$
アイレンベルク／ムーア代数の構成素は次のように呼びます。
- $`U(A)`$ ： アイレンベルク／ムーア代数の台対象〈underlying object〉
- $`m_A: E(U(A))\to U(A)`$ ： アイレンベルク／ムーア代数の演算〈operation〉
アイレンベルク／ムーア代数に関しては、記号の乱用はしないほうがいいでしょう。台対象 $`U(A)`$ を $`\u{A}`$ という略記は使います。
アイレンベルク／ムーア代数に対しても結合法則〈結合律 | associative law〉と単位法則〈単位律 | unit law〉を要請します。モナドの台関手をダッシュで略記する記法で書くと以下のようです。
$`\quad \xymatrix{
{{\u{A}'}'} \ar[r]^{(m_A)'} \ar[d]_{\mu_{\u{A}} }
& {\u{A}'} \ar[d]^{m_A}
\\
{\u{A}'} \ar[r]_{m_A}
& \u{A}
}\\
\quad \text{commutative}\In \mbf{HyGraph}^P
`$
$`\quad \xymatrix{
\u{A} \ar[r]^{\eta_{\u{A}}} \ar@{=}[dr]
& {\u{A}'} \ar[d]^{m_A}
\\
{}
& \u{A}
}\\
\quad \text{commutative}\In \mbf{HyGraph}^P
`$
$`A = (\u{A}, m_a), B = (\u{B}, m_B)`$ を2つのアイレンベルク／ムーア代数だとして、$`f:\u{A} \to \u{B}`$ がアイレンベルク／ムーア代数の準同型射〈homomorphism〉である条件は次の可換図式になります。
$`\quad \xymatrix{
{\u{A}'} \ar[r]^{f'} \ar[d]_{m_A}
&{\u{B}'} \ar[d]^{m_B}
\\
\u{A} \ar[r]^{f}
& \u{B}
}\\
\quad \text{commutative}\In \mbf{HyGraph}^P
`$
モナド $`E`$ のアイレンベルク／ムーア代数とそのあいだの準同型射の圏を $`\mrm{EM}(E)`$ と書きます。忘却関手〈forgetful functor〉 $`U`$ は、アイレンベルク／ムーア代数にその台対象を対応させます。
$`\quad U: \mrm{EM}(E) \to \mbf{HyGraph}^P \In \mbf{CAT}\\
\text{For }A = (\u{A}, m_A) \in |\mrm{EM}(E)|\\
\quad U(A) := \u{A}\\
\text{For }f: A\to B \In \mrm{EM}(E)\\
\quad U(f) := (f: \u{A} \to \u{B})
`$
自由生成関手〈free generating functor〉 $`F`$ は、対象（今は$`P`$-ハイパーグラフ）にその自由アイレンベルク／ムーア代数を対応させます。
$`\quad F: \mbf{HyGraph}^P \to \mrm{EM}(E) \In \mbf{CAT}\\
\text{For }H \in | \mbf{HyGraph}^P|\\
\quad F(H) := (H', \mu_H)\\
\text{For }f: H\to K \In \mbf{HyGraph}^P\\
\quad F(f) := (f': H' \to K')
`$
$`F, U`$ は自由忘却随伴系〈free-forgetful adjunction〉を形成します。
$`\quad \xymatrix@R+1.5pc{
\mbf{HyGraph}^P \ar@/^1.5pc/[r]_{F}
\ar@{}[r]|\top
& \mrm{EM}(E) \ar@/^1.5pc/[l]_{U}
}`$
