「木と林(有向グラフ)」で、有向グラフの特別なものである木〈ツリー〉と林について述べました。(主に“ファイバーの計算”への)応用のためには、まだ必要なことが残っているので、そのまま続きと補足を書きます。$`\newcommand{\mrm}[1]{ \mathrm{#1} }
\newcommand{\hyp}{\text{-} }
\newcommand{\In}{\text{ in }}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\F}[1]{ {{#1}^{-1}} } % fiber
\newcommand{\obj}[1]{ {{#1}\!\downarrow} }
\newcommand{\dimU}[2]{ {{#1}\!\updownarrow^{#2}} }
`$
内容:
林の辺の向き
「木と林(有向グラフ) // 特殊なグラフ」で、林の辺の向きについて次のように書きました。
ここでは、辺の向きはルートに向かう方向ですが、逆向きで定義することもできます。どちらの向きを採用するかは目的によりますが、単なる気まぐれで決めるときもあります。
パス〈有向パス〉がルートに向かうような向き付けをleaf-to-rootな向き〈leaf-to-root direction〉とかボトムアップな向き〈bottom-up direction〉と言います。逆な向き付けはroot-to-leafな向き〈root-to-leaf direction〉、トップダウンな向き〈top-down direction〉です。
向き付けはどっちでもいいのですが、「どっちでもいい」ということを記述するのが意外と面倒です。まず、一般的グラフ〈有向グラフ〉に対して、始端頂点〈initial vertex〉の集合と終端頂点〈terminal vertex〉の集合を定義します。
$`\quad \mrm{Init}(G) := \{ v\in \mrm{Vert}(G) \mid \mrm{In}(G, v) = \emptyset\}\\
\quad \mrm{Term}(G) := \{ v\in \mrm{Vert}(G) \mid \mrm{Out}(G, v) = \emptyset\}
`$
比喩的に言えば、始端頂点に他の頂点から行くことは出来ません。終端頂点から他の頂点へ行くことは出来ません。反対グラフ〈opposite graph〉では、始端頂点と終端頂点が入れ替わります。
$`\quad \mrm{Init}(G^\mrm{op}) = \mrm{Term}(G)\\
\quad \mrm{Term}(G^\mrm{op}) = \mrm{Init}(G)
`$
林の定義をボトムアップな向きで定義したときの $`\mrm{Root}(\hyp)`$ を $`\mrm{Root}_\mrm{bottomup}(\hyp)`$ とします。$`\mrm{Leaf}_\mrm{bottomup}(\hyp)`$ も同じです。一方、林の定義をトップダウンな向きで定義したときは $`\mrm{Root}_\mrm{topdown}(\hyp), \mrm{Leaf}_\mrm{topdown}(\hyp)`$ とします。
以上の約束のもとで、ボトムアップな向きで定義した林 $`F`$ に対して次の等式が成立します。
$`\quad \mrm{Root}_\mrm{bottomup}(F) = \mrm{Term}(F)\\
\quad \mrm{Leaf}_\mrm{bottomup}(F) = \mrm{Init}(F)\\
\quad \mrm{Root}_\mrm{topdown}(F^\mrm{op}) = \mrm{Init}(F)\\
\quad \mrm{Leaf}_\mrm{topdown}(F^\mrm{op}) = \mrm{Term}(F)
`$
ボトムアップな向きが便利なときもあれば、トップダウンな向きが便利なときもあるので、どちらの定義も使います。ここでのデフォルトはボトムアップな向きとします。
高さ関数と高さ関手
林はグラフ〈有向グラフ〉に条件を付けたものです。したがって、すべての林の集合を対象とする $`{\bf Graph}`$ の充満部分圏が存在します。その充満部分圏を $`{\bf Forest} \subseteq {\bf Graph}`$ とします。すべての林の集合は $`|{\bf Forest}|`$ と書けます。$`F`$ が林であることは $`F \in |{\bf Forest}|`$ と書けます。
「木と林(有向グラフ) // 高さ」より:
頂点〈ノード〉の高さと林/ツリーの高さは、関連してますが別な概念なので混同しないようにしましょう。
混乱が起きないように、頂点〈ノード〉の高さを返す関数は小文字で $`\mrm{height}`$ として、林の高さを返す関数は大文字始まりの $`\mrm{Height}`$ とします。
高さ関数は、林 $`F \in |{\bf Forest}|`$ ごとに決まるので:
$`\quad \mrm{height}_F : \mrm{Vert}(F) \to {\bf N} \In {\bf Set}`$
これは $`F`$ をパラメータとする多相関数なので、パイ型を使って次のように書けます(「多相関数の書き方」参照)。
$`\quad \mrm{height} \in \prod_{F\in |{\bf Forest}|}\mrm{Map}(\mrm{Vert}(F), {\bf N})`$
関数空間〈写像集合〉をブラケットで書くなら:
$`\quad \mrm{height} \in \prod_{F\in |{\bf Forest}|} [\mrm{Vert}(F), {\bf N}]`$
林 $`F`$ の高さは $`\mrm{Height}(F)`$ と書きますが、「木と林(有向グラフ) // グラフの例」の $`\mrm{Bamboo}_\infty`$ のように高さ無限の例もあります。したがって、関数 $`\mrm{Height}`$ の余域には $`\infty`$ を付け足す必要があります。また、「木と林(有向グラフ) // 高さ」では「空な林の高さは未定義です。」と書きましたが、例外があると面倒なので、空なグラフの高さは $`-\infty`$ にしておきましょう。
そうすると、$`\mrm{Height}`$ は次のような関数です。
$`\quad \mrm{Height} : |{\bf Forest}| \to {\bf N}_{\infty, -\infty} \In {\bf SET}`$
ここで、$`{\bf N}_{\infty, -\infty} := {\bf N}\cup \{\infty, -\infty\}`$ です。
上記の $`\mrm{Height}`$ は関数〈写像〉ですが、$`\mrm{Height}`$ を関手に拡張しておきます。高さ関手 $`\mrm{Height}`$ の余域〈ターゲット圏〉は、$`\mrm{COS}({\bf N}_{\infty, -\infty})`$ です。"COS" の三文字は Category from Ordered Set からです。集合 $`{\bf N}_{\infty, -\infty}`$ は大小の順序(常識的に考える)を持つので、その順序から作ったやせた圏が $`\mrm{COS}({\bf N}_{\infty, -\infty})`$ です。
$`\mrm{Height}`$ が関手となるためには、次のことが必要です。
- 林のあいだのグラフ準同型射 $`f: F \to G`$ が存在するなら、
$`\mrm{Height}(F) \le \mrm{Height}(G)`$ 。
グラフ準同型射 $`f`$ で、$`F`$ のパスは $`G`$ のパスに移されます。このときパスの長さは保存されます。このことから、上記の命題が言えます。
高さ関手にも同じ名前 $`\mrm{Height}`$ を使います。
$`\quad \mrm{Height} : {\bf Forest} \to \mrm{COS}({\bf N}_{\infty, -\infty}) \In {\bf CAT}`$
高さ保存準同型射
$`F`$ を林とすると、$`F`$ の頂点〈ノード〉 $`v`$ にはその高さ $`\mrm{height}_F(v) \in {\bf N}`$ が決まります。頂点の高さは、ルートからの“距離”と言えます。頂点がルートなら高さは 0 です。林のあいだの準同型射で高さが保存されるとは限りません。
例えば、$`F`$ を頂点集合 $`\{0\}`$ で辺を持たない林(ルートでありリーフでもある頂点だけの林)、$`G`$ を頂点集合 $`\{0, 1\}`$ で $`1`$ から $`0`$ への辺だけを持つ林とします。準同型射 $`0 \mapsto 1`$ は高さを保存しません。
林のあいだの準同型射 $`f`$ が、高さを保存する〈height preserving〉とは、次の図式が可換になることです。
$`\require{AMScd}
\quad \begin{CD}
\mrm{Vert}(F) @>{f_{\mrm{vert}} }>> \mrm{Vert}(G)\\
@V{\mrm{height}_F}VV @VV{\mrm{height}_G}V\\
{\bf N} @= {\bf N}
\end{CD}\\
\quad \text{commutative }\In {\bf Set}
`$
圏 $`{\bf Forest}`$ の射を、高さ保存準同型射〈height preserving homomorphism〉だけに制限すると、部分圏を形成します。その部分圏を $`{\bf Forest}^\mrm{hp}`$ とします。"hp" は height preserving から。
高さ保存準同型射により、林のルート集合はルート集合に移ります。このことから、$`\mrm{Root}(\hyp)`$ を関手に拡張できます。関手としてのルート集合にも同じ名前 $`\mrm{Root}`$ を使います(オーバーロード)。
$`\quad \mrm{Root} : {\bf Forest}^\mrm{hp} \to {\bf Set} \In {\bf CAT}`$
林のリーフ集合がリーフ集合に移ることは保証できないので、何の細工もなしに $`\mrm{Leaf}`$ を関手にすることはできません。
ルートをルートに移す(root preserving)準同型射は、高さも保存することが言えるので、高さ保存準同型射は、ルート保存準同型射〈root preserving homomorphism〉と呼んでもいいかも知れません。
頂点の高さ/林の高さ
$`F`$ が林のとき、頂点集合 $`\mrm{Vert}(F)`$ を高さごとの部分集合に分けます。
$`\quad \mrm{Vert}(F) = \bigcup_{n\in {\bf N}} \mrm{Vert}_n(F)\\
\text{Where}\\
\quad \mrm{Vert}_n(F) := \{v\in \mrm{Vert}(F) \mid \mrm{height}_F(v) = n \}
`$
$`\mrm{Vert}_0(F)`$ は $`\mrm{Root}(F)`$ と同じです。$`F`$ の高さ(頂点の高さではない) $`\mrm{Height}(F)`$ が有限なら、大きな $`n`$ に対する $`\mrm{Vert}_n(F)`$ は空集合になります。
場合により、$`\mrm{Bamboo}_\infty`$ のような高さ無限な林は除外して、高さを有限な $`n`$ 以下に抑えたいときもあります。$`\mrm{Height}(F) \le n`$ である林だけを対象とした $`{\bf Forest}`$ の部分圏を次のように書きます。
$`\quad {\bf Forest}_{\le n}`$
高さ有限な林を対象とする圏は、次のように書きます。
$`\quad {\bf Forest}_{\lt \infty}`$
記法を揃えるために、次のように約束します。
$`\quad {\bf Forest}_{\le \infty} := {\bf Forest}`$
射を高さ保存準同型射〈ルート保存準同型射〉に制限した場合は、次のようです。
$`\quad {\bf Forest}_{\le n}^\mrm{hp}\\
\quad {\bf Forest}_{\lt \infty}^\mrm{hp}\\
\quad {\bf Forest}_{\le \infty}^\mrm{hp}
`$
$`n, m\in {\bf N},\; n \le m`$ のとき、次のような射影関手〈projection functor〉が存在します。
$`\quad \pi^m_n : {\bf Forest}_{\le m}^\mrm{hp} \to {\bf Forest}_{\le n}^\mrm{hp} \In {\bf CAT}`$
この関手は、$`{\bf Forest}_{\le m}^\mrm{hp}`$ に属する林に対して、高さ $`n`$ を超える頂点とそれに伴う辺を(あれば)捨ててしまう操作です。次の形の射影関手も存在します。
$`\quad \pi^\infty_n : {\bf Forest}_{\le \infty}^\mrm{hp} \to {\bf Forest}_{\le n}^\mrm{hp} \In {\bf CAT}`$
圏 $`{\bf Forest}_{\le 0} = {\bf Forest}_{\le 0}^\mrm{hp}`$ は集合圏と同一視可能です。$`{\bf Forest}_{\le 1}^\mrm{hp}`$ は、(ベースを固定しない)バンドルの圏と同一視可能です。
林-ファミリー対応
関手 $`\mrm{Root}`$ を、$`{\bf Forest}^\mrm{hp}_{\le \infty}`$ の部分圏に制限した関手も同じ名前で表します。
$`\quad \mrm{Root} : {\bf Forest}^\mrm{hp}_{\le n} \to {\bf Set} \In {\bf CAT}\\
\quad \mrm{Root} : {\bf Forest}^\mrm{hp}_{\lt \infty} \to {\bf Set} \In {\bf CAT}
`$
$`X\in |{\bf Set}|`$ に対して、$`\mrm{Root}(F) = X`$ であるような林を対象として、$`\mrm{Root}(f) = \mrm{id}_X`$ である射を射とする $`{\bf Forest}^\mrm{hp}`$ の部分圏(と変種達)を次のように書きます。
$`\quad {\bf Forest}^\mrm{hp}_{\le n}\!\downarrow_X \\
\quad {\bf Forest}^\mrm{hp}_{\lt \infty}\!\downarrow_X \\
\quad {\bf Forest}^\mrm{hp}_{\le \infty}\!\downarrow_X
`$
バンドル-ファミリー対応の一般化として、次の林-ファミリー対応〈forest-family correspondence〉があります。
$`\quad {\bf Forest}^\mrm{hp}_{\le n}\!\downarrow_X \;\cong
({\bf Forest}^\mrm{hp}_{\le n - 1})^X\\
\quad {\bf Forest}^\mrm{hp}_{\lt \infty }\!\downarrow_X \;\cong
({\bf Forest}^\mrm{hp}_{\lt \infty })^X \\
\quad {\bf Forest}^\mrm{hp}_{\le \infty}\!\downarrow_X \;\cong
({\bf Forest}^\mrm{hp}_{\le \infty})^X
`$
特に $`n = 1`$ と置くと:
$`\quad {\bf Forest}^\mrm{hp}_{\le 1}\!\downarrow_X \;\cong
({\bf Forest}^\mrm{hp}_{\le 0})^X
`$
これは、集合圏におけるバンドル-ファミリー対応(下)と同じことです。
$`\quad {\bf Set}/X \cong {\bf Set}^X
`$
林-ファミリー対応は、林の絵を描いてみれば直感的に明らかだと思いますが、いずれまた、集合圏の部分圏に相対化した形(次節参照)で扱いたいと思います。
林の抽象化(少し)
前節の $`{\bf Forest}^\mrm{hp}_{\le n}, {\bf Forest}^\mrm{hp}_{\lt \infty}, {\bf Forest}^\mrm{hp}_{\le \infty}`$ などを少しだけ抽象化します。集合圏 $`{\bf Set}`$ の代わりに、集合圏の部分圏 $`\cat{S}`$ を考えます。$`\cat{S}`$ はファイバーに関して閉じてる圏だとします。
自然数を頂点とする次の形のグラフを考えます。
$`\quad n \to n - 1 \to \cdots \to 0`$
これは、「木と林(有向グラフ) // グラフの例」で述べた $`\mrm{bamboo}(n)`$ です。すべての自然数を頂点とする次の形の無限グラフは $`\mrm{bamboo}(\infty)`$ とします(林 $`\mrm{Bamboo}_\infty`$ とは別物)。
$`\quad \cdots \to n \to n - 1 \to \cdots \to 0`$
$`\mrm{bamboo}(n)`$ (あるいはそれから生成した自由圏)から $`\cat{S}`$ への共変関手の全体と自然変換の圏を次のように書きます。
$`\quad \mrm{Path}_n(\cat{S}) := [\mrm{bamboo}(n), \cat{S}]_1 \; \in |{\bf CAT}|`$
$`[\hyp,\hyp]_1`$ は関手圏を意味しますが、「変換手n-圏のブラケット記法」で導入したブラケット記法です。$`\mrm{Path}_\infty(\cat{S})`$ も同様に関手圏として定義します。
$`\quad \mrm{Path}_\infty(\cat{S}) := [\mrm{bamboo}(\infty), \cat{S}]_1 \; \in |{\bf CAT}|`$
次が成立します。
$`\quad \mrm{Path}_0(\cat{S}) \cong \cat{S} \In {\bf CAT}\\
\quad \mrm{Path}_1(\cat{S}) \cong \mrm{Arr}(\cat{S}) \In {\bf CAT}
`$
ここでの $`\cong`$ は圏同値を意味します。$`\mrm{Arr}(\hyp)`$ はアロー圏構成です(「自然変換は関手」参照)。
有限個、あるいは可算無限個の圏の直和は作れるので、次のように定義します。
$`\quad \mrm{Path}_{\le n}(\cat{S}) := \sum_{k = 0}^n \mrm{Path}_k (\cat{S}) \;\in |{\bf CAT}|\\
\quad \mrm{Path}_{\lt \infty}(\cat{S}) := \sum_{k \in {\bf N}} \mrm{Path}_k (\cat{S}) \;\in |{\bf CAT}|\\
\quad \mrm{Path}_{\le \infty}(\cat{S}) := \mrm{Path}_{\lt \infty}(\cat{S}) + \mrm{Path}_{\infty}(\cat{S}) \;\in |{\bf CAT}|
`$
以上に定義した $`\mrm{Path}_* (\cat{S})`$ の形(アスタリスクはワイルドカード)をした圏を、圏 $`\cat{S}`$ のパスの圏〈category of paths〉と呼びます。「パスの圏」は、グラフから自由生成された圏の意味もあるので、用語のコンフリクト〈衝突〉ですが、他の呼び名が思いつきません。
パスの圏の対象はパス(竹 $`\mrm{bamboo}(*)`$ からの関手)ですが、$`0`$ の値であるパス終端の対象が $`X`$ であるパスと、$`0`$-成分が $`\mrm{id}_X`$ であるパス射(自然変換)からなる圏を次のように書きます(アスタリスクはワイルドカード)。
$`\quad \mrm{Path}_* (\cat{S})\!\downarrow_{X}`$
この圏が、$`{\bf Forest}^\mrm{hp}_{*}\!\downarrow_X`$ の抽象化になります。抽象化とは言っても、$`\cat{S}`$ は集合圏の部分圏なので、対象・射は集合・写像なので、十分に具象的です。写像のパスは、グラフとしての林の言い換えに過ぎません。
そしてそれから
林と写像のパスを同一視することにより、林の議論と“ファイバーの計算”(「ファイバーの計算 基本概念」参照)の連絡がスムーズになります。林は、“ファイバーの計算”の事例と視覚化の道具を提供します。
林=写像のパスは、それ自体でも興味の対象になります。林に対して色々な演算が定義できます。
- 関数による林の引き戻しと前送り
- 高さによる部分林の抜き出し
- 林の切断と接ぎ木
- 林の一部に林を挿入
- 辺の短絡による林の縮約
これら豊富な演算の計算法則や利用法を探るのは面白そうです。