樹状集合

前提知識: 前層, 単体的集合, オペラッド, 脈体

定義

単体的集合では、順序付きの頂点列を添字にして、合成可能な射の列を記述する。複数の入力から一つの出力を作る演算を同じ方法で扱うには、列だけでは足りない。二つの入力を受け取る演算の出力を別の演算へ代入すれば、合成の形は枝分かれした木になる。樹状集合は、このような木を添字にする集合の族である。
以下では一つの集合の宇宙を固定し、集合値の対称有色オペラッドと小さい木の圏を考える。木は有限で空でない根付き非平面木とする。ここで木は、頂点と辺からなる連結で閉路のない図形であり、外辺は一端だけが頂点につながる。例外として頂点のない一本の辺も許す。「空でない」とは少なくとも一本の辺を持つという意味である。出力側の外辺を根として一つ指定すると、各頂点から根へ向かう向きが決まり、各頂点には出力辺が一本ある。入力辺の本数は零でもよい。木の入力の左右の並び順は構造に含めない。

従って各木に集合 $X_T=X(T)$ があり、木の射 $\alpha\colon S\to T$ に対して制限写像 $\alpha^*\colon X_T\to X_S$ がある。条件は $\operatorname{id}^*=\operatorname{id}$ と、$\alpha\colon S\to T$、$\beta\colon R\to S$ に対する $(\alpha\beta)^*=\beta^*\alpha^*$ である。$X_T$ の元は形 $T$ の樹状単体、または dendrix と呼ばれる。定義の中心は、この反変性とすべての木の射に対する整合性にある。単に木ごとに独立な集合を並べるだけでは樹状集合にはならない。定義と基本構成は MW07 §3–4 による。

色付き演算と木の読み方

有色オペラッドに必要なデータ

ここで使う有色オペラッド $P$ は、色の集合 $C$ と、各 $r\ge0$ および各色の列 $c_1,\ldots,c_r,c$ に対する演算の集合
$$ P(c_1,\ldots,c_r;c) $$
を持つ。セミコロンの左が入力、右が出力である。各色には単位演算 $1_c\in P(c;c)$ があり、入力の並べ替えは対称群の作用で表す。また $p\in P(c_1,\ldots,c_r;c)$ と $p_i\in P(d_{i1},\ldots,d_{ik_i};c_i)$ から、各入力へ代入した演算
$$ p(p_1,\ldots,p_r) \in P(d_{11},\ldots,d_{1k_1},\ldots,d_{r1},\ldots,d_{rk_r};c) $$
ができる。代入の順序に依存しない結合律、単位を代入しても変わらない単位律、入力の並べ替えと代入の整合性を要求する。零項演算は $P(;c)$ の元である。これは入力を必要としない定数型の演算であり、単位演算とは異なる。単位は一つの入力をそのまま出力へ通す単項演算である。
オペラッドの射は色の写像と、対応するすべての演算集合の写像で、単位・代入・対称群作用を保つものとする。色の写像は単射でなくてよい。異なる辺に同じ色を割り当てることも、この定義では許される。一色の場合の基本的な代入構造や代数の概念は オペラッド で扱う。ここでは、一本一本の辺に異なる色を用意するため、有色版が必要になる。

辺、頂点、零項演算

木を描くときは根を下に置き、各辺を根へ向かって読む。頂点から根へ出る辺が出力辺で、その頂点へ上から入る辺が入力辺である。根辺は最下部の外辺であり、葉辺は上端で頂点に接続されていない入力の外辺である。内辺は二つの頂点の間を結ぶ。零項頂点は入力辺を持たない頂点であり、その場所は葉辺ではない。「木の上端はすべて葉辺」と考えると、零項演算を見落とす。
頂点を持たず一本の辺だけからなる木を $\eta$ と書く。その同じ辺が入力側と出力側の両方を担う。これに対して、入力のない頂点一つとその出力辺を持つ木を $C_0$ と書く。$\eta$ には生成演算がなく、$C_0$ には零項生成演算が一つある。この二つの木は違う。一般に $C_r$ は、頂点一つ、入力辺 $r$ 本、出力辺一本を持つ木で、$r$ 項の corolla と呼ぶ。$C_1$ は単項頂点を持つ。

木 $T$ の自由オペラッドの意味を明確にしよう。辺集合を $E(T)$ とする。各頂点 $v$ の入力辺を一時的に $e_1,\ldots,e_r$ と並べ、出力を $e$ とすると、生成演算 $v\in\Omega(T)(e_1,\ldots,e_r;e)$ を置く。これらから単位・代入・入力の並べ替えによって演算を作り、オペラッドの公理による関係を課す。入力順を取り替えれば対称群作用で同じ構造を表すので、平面上の左右の配置を追加データにしない。
自由性は次の普遍性で使う。射 $\Omega(T)\to P$ を与えることは、各辺に $P$ の色を付け、各頂点に、その入力辺と出力辺の色に合う $P$ の演算を付けることと同じである。辺の色と頂点の演算が決まれば、すべての合成演算の像は一意に決まる。この自由対称有色オペラッドの構成を木の圏の基礎として用いる。

木の射は、頂点を頂点に送るグラフ写像に限らない。直前の例のように、一つの頂点を合成演算へ送ることができる。また単項頂点を単位演算へ送ることもできる。従って、木の形だけから通常のグラフ準同型を採用すると、必要な射を失う。圏 $\Omega$ の射をオペラッドの射として定めた理由はここにある。

線形木と単体圏

圏を単項演算だけのオペラッドにする

小圏 $\mathcal C$ に対して $j_!\mathcal C$ を次で定める。色は $\mathcal C$ の対象、単項演算は
$$ (j_!\mathcal C)(c;d)=\operatorname{Hom}_{\mathcal C}(c,d) $$
であり、$r\ne1$ の演算集合はすべて空とする。特に零項演算も空である。単位と代入は圏の恒等射と合成を使う。非自明な代入が可能なのはすべての演算が単項の場合だけなので、オペラッドの公理は圏の公理から従う。
逆に $P$ の色を対象、$P(c;d)$ を射とし、代入を合成とすると小圏 $j^*P$ ができる。多項演算や零項演算はこの圏では忘れる。オペラッドの単位律と結合律がそのまま圏の恒等射の条件と結合律になる。

線形木の埋め込みと sieve

単項頂点が $n$ 個連なった木を $L_n$ と書く。辺は $n+1$ 本あり、葉から根に向かって $0,1,\ldots,n$ と番号を付ける。$L_0=\eta$ である。各頂点は隣り合う辺 $k-1$ から $k$ への生成射を表す。その合成は $a\le b$ のときの一意な射 $a\to b$ であり、逆向きの射はない。従って
$$ \Omega(L_n)\cong j_![n] $$
である。ここで $[n]$ は全順序 $0< \cdots< n$ を圏とみなしたものを表す。

sieve という語は、部分圏の対象へ入る射の始域も部分圏に属することを意味する。ここでは「非線形木から線形木への射がない」であって、その逆ではない。例えば $\eta\to C_2$ は $C_2$ の三本の辺のいずれかを選ぶ射である。これに対して $C_2\to\eta$ は二項生成演算の行き先がないので存在しない。この向きが、次の空延長で決定的になる。
単体圏の単射は線形木の辺を選び、弱増加な全射は隣り合う辺の番号を同じにする。後者は対応する単項生成演算を単位へ送る。特に $L_1\to L_0=\eta$ は存在する。頂点が一つから零個に減るこの射は、頂点を頂点へ送るというグラフ写像の規則だけでは表せない。

空集合による単体的集合の延長

線形木だけに制限すると、樹状集合 $Y$ から単体的集合 $i^*Y$ が得られる。具体的には $(i^*Y)_n=Y_{L_n}$ であり、$\theta\colon[m]\to[n]$ に対する作用は $Y(i\theta)\colon Y_{L_n}\to Y_{L_m}$ である。反変関手を線形木の圏へ制限しているので、ここで射の向きをさらに逆にし直す必要はない。
逆方向の構成では木の同型代表を一つずつ選び、線形木の代表を $L_n$ とする。これは添字圏をその骨格に置き換えるだけであり、木の自己同型は射としてすべて残す。単体的集合 $X$ に対して
$$ (i_!X)_T= \begin{cases} X_n&T=L_n,\\ \emptyset&T\text{ が非線形} \end{cases} $$
と置く。この添字圏の選び方の下では式は文字どおりの定義である。すべての同型な木を残して扱う場合には、選んだ同型で値と制限を運び、自然同型の意味で同じ構成になる。

これは右随伴を作ったものではない。空延長は $i^*$ の左随伴であり、多入力の木にはデータを付け加えず空集合を置く。単体的集合を樹状集合の中で扱えることと、すべての樹状集合が単体的集合から復元できることは別の主張である。後者は、以下の具体例が示すように成り立たない。

代表可能な樹状集合と樹状脈体

一つの木から作る例

任意の樹状集合 $X$ に対して、射 $\Omega[T]\to X$ は $X_T$ の一つの元を選ぶことと同じである。対応を明示すると、自然変換 $a$ から $a_T(\operatorname{id}_T)$ を取り出す。逆に $x\in X_T$ があれば、各 $f\colon S\to T$ を $f^*x$ へ送る。自然性は制限写像の合成則から従い、二つの操作が逆になることは恒等射への代入で分かる。従って $X_T$ は、抽象的な集合であるだけでなく、標準的な形 $T$ を $X$ に写したものの集合として理解できる。これは 米田の補題 のこの場合の具体形である。

オペラッドの樹状脈体

自由性により、$N_dP(T)$ の元は、$T$ の辺に色を付け、頂点に入力・出力に合う演算を付けたものである。例えば二頂点の木の内辺を縮める射に沿って制限すれば、二つの演算を代入して一つにしたラベルが現れる。単項頂点をつぶす射に沿う制限では、つぶされた場所へ単位演算を挿入する。このように、樹状脈体では木の射が合成や単位を一つの反変関手にまとめる。

一般の樹状集合についても、$X_{\eta}$ は色に相当する集合と考えられる。各辺の選択 $\eta\to T$ に沿う制限 $X_T\to X_{\eta}$ が、その辺の色を取り出す役割を果たす。ただし樹状集合の定義そのものには、頂点ごとのデータから $X_T$ の元が一意に復元されるという条件は含まれていない。従って有色オペラッドの具体的なラベル表示は樹状脈体に対する説明であり、そのまま任意の前層への追加公理にはしない。

第一の式は、オペラッドから単項演算だけを残して通常の脈体を作ることと、樹状脈体を線形木へ制限することが一致するという意味である。第二の式は、最初から単項演算しかない圏の場合には、樹状脈体に非線形部分が現れないことを述べる。二つの式は似ているが、前者は任意の $P$ に対する制限、後者は $j_!\mathcal C$ という特別なオペラッドに対する空延長である。

例と反例による使い分け

この反例は、線形木の圏が充満であることと矛盾しない。充満忠実なのは $i_!$ という埋め込みであり、$i^*$ が非線形部分の情報まで回収するという主張ではない。同じ単体的集合を線形部分に持っていても、枝分かれや零項演算に対応するデータは異なりうる。

樹状集合の定義は、木を使って多入力の構造を記述するための土台である。定義だけで高次の合成の存在や一意性を要求してはいない。高次のオペラッド的構造を表すには、別に充填条件などの追加条件を考える。∞オペラッド の作用素圏による記述と比較するときも、まず普通のオペラッドと樹状脈体、線形部分と多入力部分を区別すると、何を忘れ、何を追加する構成なのかが分かりやすい。

関連項目

• 前提: 前層, 単体的集合, オペラッド, 脈体
• 基礎: 米田の補題, 充満忠実関手, 随伴関手
• 発展: ∞オペラッド