余代数

代数结构由"生成元 + 运算"决定；反过来，"观察/展开"驱动的结构（状态机、无限流、自动机）由余代数描述。它把函子的"构造"翻转为"析构"（$X\to T(X)$），其终余代数给出"最大的对象"（如无限列表），是共归纳（coinduction）的范畴论基础。

需先掌握函子（自函子）、始对象与终对象（终对象的泛性质）与单子（对偶的代数侧）。

定义

设 $T:\mathcal{C}\to\mathcal{C}$ 为自函子。$T$-余代数是对象 $X$ 连同态射 $\alpha:X\to T(X)$（称为结构映射/析构器）。余代数态射 $f:(X,\alpha)\to(Y,\beta)$ 是满足 $\beta\circ f=T(f)\circ\alpha$ 的态射，构成范畴 $\mathbf{CoAlg}(T)$。

性质

• 终余代数（若存在）$(Z,\zeta)$ 满足：对每个余代数 $X$ 有唯一余代数态射 $X\to Z$；且 $\zeta:Z\to T(Z)$ 是同构（Lambek 定理）——$Z$ 是 $T$ 的最大不动点
• 共归纳：终余代数的元素由"观察行为"区分，两个元素相等 $\iff$ 逐次析构后总是相等（bisimulation）
• 与单子的关系：余代数处理"展开"（$X\to T(X)$），代数处理"折叠"（$T(X)\to X$）；自动机、流、非良基集合都是余代数

例子

• 流（streams）：$T(X)=\mathbb{N}\times X$ 的终余代数 $\cong \mathbb{N}^{\mathbb{N}}$（所有自然数列），由"首项+后继"唯一确定
• 确定性自动机：状态集 $Q$、字母表 $A$、转移 $\delta:Q\times A\to Q$ 与输出，可编码为余代数 $Q\to Q^A\times B$
• 无限二叉树：$T(X)=\{1\}\times X\times X$ 的终余代数给出所有无限二叉树（惰性数据结构）

应用

余代数是程序语义（共归纳定义、bisimulation）、自动机理论（Hasse 图、行为等价）与函数式编程（惰性求值、无限数据结构）的数学框架；它与单子共同构成"代数-余代数"的对偶语言。