观念
始代数可理解为某些归纳类型的范畴语义.
定义
对于范畴 $\mathcal C$ 的自函子 $F\colon \mathcal C \to \mathcal C$, 称一个对象 $X$ 配备一个态射 $F(X)\to X$ 的结构为 $F$-代数 (又称 Lambek 代数). 定义 $F$ 的始代数为 $F$-代数范畴 $\mathsf{alg}_F(\mathcal C)$ 的始对象.
值得注意的是始代数还有个相对版本. 对于任意对象 $c\in\mathcal C$, 自函子 $F$ 给出切片的自函子 $c+F\colon \mathcal C_{c/} \to\mathcal C_{c/}$, $(c\to d)\mapsto (c\to c+F(d))$; 那么
$$
\begin{aligned}
\mathsf{alg}_{c+F}(\mathcal C_{c/})&=\Big\{
\begin{array}{ccc}
c & & \\
\downarrow & \searrow & \\
c+F(d) & \rightarrow & d
\end{array}
\Big\}\\
&=\mathsf{alg}_F(\mathcal C)_{c/}.
\end{aligned}
$$
因此 $c+F$ 的始代数等同于 $\mathsf{alg}_F(\mathcal C)_{c/}$ 的始对象, 即 “$c$ 生成的最小 $F$-代数”.
性质
Lambek 定理
定理 (Lambek). 若 $F$ 有始代数 $\alpha\colon F(X) \to X$, 则 $\alpha$ 为同构.
因此始代数又称最小不动点.
命题. 假设范畴 $\mathcal C$ 有滤余极限及始对象 $0$, 且 $F$ 保持滤余极限. 那么 $F$ 有始代数
$$
\operatorname{colim}_n F^n0.
$$
例
自然数
自然数集 $\mathbb{N}$ 是 $\mathsf{Set}$ 上的函子 $X\mapsto 1+X$ 的始代数:
$$
\mathbb{N} = \operatorname{colim}_n \underbrace{1+1+\cdots+1}_{n}.
$$
二叉树
二叉树的集合 $B$ 是 $\mathsf{Set}$ 上的自函子 $X\mapsto 1 + X^2$ 的始代数.
注意, 由于一棵二叉树要么为空要么由两棵更小的二叉树构成, 故有
$$
B \simeq 1 + B^2.
$$
更有趣的是, 由上式可得
$$
B\simeq B^7,
$$
并且这个同构由 Andreas Blass 的著名文章 “七树合一” 显式构造.
列表
对于集合 $A$, 函子 $X \mapsto 1 + A\times X$ 的始代数是 $A$ 的列表集合
$$
\operatorname{List}(A) = \bigsqcup_n A^n,
$$
也即 $A$ 上的自由幺半群.
上述三个例子都是多项式函子, 这种函子总是保持滤余极限.