始代数 (自函子) [始代数]

观念

始代数可理解为某些归纳类型的范畴语义.

定义

对于范畴 $\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$ 上的自由幺半群.

上述三个例子都是多项式函子, 这种函子总是保持滤余极限.