观念
树是表达 “多个对象到一个对象的态射” 所需的基本结构. 因此, 可被树探测的对象 (即树形对象) 给出算畴 (多重范畴) 的一种定义.
这里所说的树特指有限, 有根 (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$ 的纤维要求为集合.
树的态射
树的态射是个比较复杂的概念.
一种方便的定义是, 树的态射由如下几种基本态射生成:
- 树的同构;
- 退化 (degeneracy) $S \twoheadrightarrow T$, 其中 $S$ 是由 $T$ 在一条边中间插入一个新结点所得;
- 内部面映射 (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$ 处的纤维, 即该结点的入边的全体.
要得到树的全部态射需要考虑多项式函子生成的自由单子.
例
线性树
线性树是形如
$$
\begin{array}
{c}
\downarrow\\
\bullet\\
\downarrow\\
\bullet\\
\vdots\\
\bullet\\
\downarrow
\end{array}
$$
的树. 这给出单纯形范畴到树的范畴的嵌入
$$
\Delta \hookrightarrow \Omega.
$$