树 (范畴论) [树]

观念

树是表达 “多个对象到一个对象的态射” 所需的基本结构. 因此, 可被树探测的对象 (即树形对象) 给出算畴 (多重范畴) 的一种定义.

这里所说的树特指有限, 有根 (rooted), 对称 (即一个节点上的边不计顺序) 的树.

定义

通过结点和边

树由结点 (vertex), 内边 (internal edge) 和外边 (external edge) 构成, 内边是两个结点之间的边, 外边是仅联系到一个结点的边; 每个结点有若干个 (可能是零个) 入边和一个出边. 整个树有一个唯一的根 (root), 即唯一指向外部的出边. 外部的入边称为叶 (leaf).

树

上图是一棵树的例子, 其中

  • $g$ 是根,
  • $e$ 是一个叶, 是外边, 是结点 $w$ 的入边,
  • $f$ 是内边, 是结点 $v$ 的出边, 也是结点 $w$ 的入边.

注意, 我们不要求树可以画在平面上. 同一结点的所有入边之间没有顺序.

作为偏序集

树的所有边的上下关系构成一个偏序. 具体地, 树可定义为满足如下条件的 (有限) 偏序集 $(P,\leq)$:

  • $P$ 有最小元 $\bot$ (即树的根);
  • 对任意 $x\in P$, 不超过 $x$ 的元素的子集构成一个全序.

此时 $P$ 的极大元 (可能不唯一) 即是树的叶.

作为递归嵌套结构

树有一种递归定义:

  • 平凡树 $\{\}$ 是树;
  • 若 $x_1,\cdots,x_n$ 是树, 那么 $\{x_1,\cdots,x_n\}$ 也是树.

作为多项式

树还可以简洁地定义为 “多项式” (这个名词的直观参见多项式函子): $$ E\overset{s}{\leftarrow} M \overset{p}{\rightarrow} N \overset{t}{\to} E, $$ 其中

  • $E$ 是边的集合;
  • $N$ 是顶点的集合, $t\colon N\to E$ 给出顶点的唯一出边, 要求 $t$ 为单射;
  • $M$ 是边与顶点之间的 “入边” 关系, 分别带有到 $E$ 和 $N$ 的投影, 满足 $s\colon M\to E$ 为单射, 且 $E\setminus M$ 只有一个元素, 即树的根.

注意即使在生象语境中, 我们也要求树的定义中 $E,M,N$ 是集合 ($0$-截断生象). 因为上述定义中涉及的差集只对集合有意义.

但对于任意多项式函子 $P$ (其分量未必为集合) 我们可以定义 $P$-树, 即树 (作为多项式函子) 到 $P$ 的态射. 这里, 多项式 $X\overset{s}{\leftarrow} E \overset{p}{\rightarrow} B \overset{t}{\to} Y$ 中, $p\colon E\to B$ 的纤维要求为集合.

树的态射

树 $S$ 到 $T$ 的映射是如下资料:

  • 将 $S$ 的每个结点 $n$ 对应到 $T$ 的一个子树 (例如下图中蓝色结点对应到右边蓝圈中的子树), 满足结点 $n$ 的入边数等于该子树的叶数;
  • 将 $S$ 的每个边对应到 $T$ 的一个边, 且与结点的对应相容.
tree morphism

树的态射由如下几种基本态射生成:

  • 树的同构;
  • 退化 (degeneracy) $S \twoheadrightarrow T$, 其中 $S$ 是由 $T$ 在一条边中间插入一个新结点所得 ($S$ 的这个新结点对应到无结点的子树);
  • 内部面映射 (inner face map) $S \hookrightarrow T$, 其中 $S$ 是由 $T$ 缩合一条内边所得;
  • 外部面映射 (outer face map) $S \to T$, 其中 $S$ 是由 $T$ 剪除一个外顶点 (仅关联一条内边的顶点) 所得;

另一种概念性的理解是将树理解为特殊的多项式, 考虑多项式函子之间的态射 $$ \begin{CD} E @<{s}<< M @>{p}>> N @>{t}>> E \\ @VVV @VVV \square @VVV @VVV \\ E' @<<{s'}< M' @>>{p'}> N' @>>{t'}> E', \end{CD} $$ 其中标记 $\square$ 的方块为拉回. 换言之, 树的这种态射要保持 $p\colon M\to N$ 的纤维, 也即每个结点的入边的数量. 但这样定义的只是树的态射中的一部分, 即树的含入映射 (Kock 的 $\mathsf{TEmb}$), 又称惰性 (inert) 映射 (GHK 中的 $\Omega_{\mathrm{int}}$, 也即算畴的代数模式中的惰性映射).

例. 树的每个边给出一个含入 $$ \begin{array}{ccccccc} 1 & \leftarrow & 0 & \rightarrow & 0 & \rightarrow & 1 \\ \downarrow & & \downarrow & & \downarrow & & \downarrow \\ E & \leftarrow & M & \rightarrow & N & \rightarrow & E, \end{array} $$ 每个结点给出一个含入 $$ \begin{array}{ccccccc} K+1 & \leftarrow & K & \rightarrow & 1 & \rightarrow & K+1 \\ \downarrow & & \downarrow & & \downarrow & & \downarrow \\ E & \leftarrow & M & \rightarrow & N & \rightarrow & E, \end{array} $$ 其中 $K$ 是 $p\colon M\to N$ 在 $1\to N$ 处的纤维, 即该结点的入边的全体.

要得到树的全部态射需要考虑多项式函子生成的自由单子.

命题. 树 $T$ 的自由单子是多项式 $$ E\leftarrow\operatorname{Sub}(T)'\to\operatorname{Sub}(T)\to E $$ 给出的函子. 其中 $E$ 是 $T$ 的边集, $\operatorname{Sub}(T)$ 是 $T$ 的子树的集合, $\operatorname{Sub}'(T)$ 是带一个特殊标记的子树的集合, 到 $E$ 的映射给出子树的根.

因此, 树 $S$ 到 $T$ 的映射恰好等同于 $S$ 对应的多项式函子到 $T$ 的自由单子的态射.

例

线性树

线性树是形如 $$ \begin{array} {c} \downarrow\\ \bullet\\ \downarrow\\ \bullet\\ \vdots\\ \bullet\\ \downarrow \end{array} $$ 的树. 这给出单纯形范畴到树的范畴的嵌入 $$ \Delta \hookrightarrow \Omega. $$