Terminal Coalgebras in Countably Many Steps

技术摘要：在可数步内完成的终极余代数

问题陈述
本文探讨了在各种范畴上构造端函子（endofunctors）的终极余代数（terminal coalgebras）的问题。构造终极余代数 $\nu F$ 的标准方法是通过在唯一态 $F1 \to 1$ 上迭代函子 $F$，从而形成一个超限链（transfinite chain，即终极余代数链）。虽然当函子保持相关的极限时，该链会收敛到 $\nu F$，但所需的迭代次数可能任意大，或者该链可能根本不收敛（例如对于幂集函子）。

Worrell [49] 的一项开创性结果表明，对于集合范畴（$\mathbf{Set}$）上的有限型端函子，终极余代数在恰好 $\omega + \omega$ 步内获得（即 $\nu F = V_{\omega+\omega}$）。本文的核心问题是将 Worrell 的结果推广到其他基范畴，并确定特定类函子（如拓扑空间和度量空间上的多项式函子）的收敛界限。

方法论
作者结合了范畴论技术与特定的有限性论证：

1. 下降链条件 (DCC)： 本文引入了 DCC-范畴 的概念，即局部有限呈现的范畴，其中有限呈现对象在子对象和强商（strong quotients）上满足下降链条件。这一条件确保了这些范畴中的 $\omega^{op}$-极限是“有限型”的（命题 3.16）。
2. 保持性质： 作者分离出了实现收敛所需的特定保持性质：
   • 保持非空二元交集（非严格初始域的拉回）。
   • 保持等距嵌入（在度量空间的语境下）。
3. 两阶段迭代： 该方法依赖于 Worrell 的“第二次无限迭代”技术。如果第一个 $\omega$-极限 $V_\omega$ 未被保持，作者会对连接态 $m: FV_\omega \to V_\omega$ 再次迭代 $F$ 以形成链 $V_\omega \leftarrow V_{\omega+1} \leftarrow \dots$，其极限为 $V_{\omega+\omega}$。
4. 树表示： 对于特定函子（有限幂集、Vietoris、Hausdorff），作者使用树（强外延的、紧分支的以及边标签的树）来刻画极限 $V_\omega$ 和终极余代数。

主要贡献与结果

1. 向 DCC-范畴的推广 (第 4 节)
本文证明，对于任何 DCC-范畴 $\mathcal{A}$ 以及任何保持 非空二元交集 的 有限型端函子 $F$，终极余代数链在 $\omega + \omega$ 步内收敛（即 $\nu F = V_{\omega+\omega}$）。

• 范围： 这适用于包括 $\mathbf{Set}$（集合）、$\mathbf{Pos}$（偏序集）、$\mathbf{Gra}$（图）、$\mathbf{K\text{-}Vec}$（向量空间）、$\mathbf{Nom}$（名义集）和有限集上的预层范畴。
• 度量空间： 由于 $\mathbf{Met}$（度量空间）不是局部有限呈现的，作者提供了一个单独的充分条件（定理 4.10）：在 $\mathbf{Met}$ 上保持非空二元交集且保持 等距嵌入 的有限型端函子也以 $\omega + \omega$ 步收敛。

2. 拓扑空间上的多项式函子 (第 7 节)
作者研究了拓扑空间范畴（$\mathbf{Top}$）上的 Vietoris 多项式函子，这些函子由 Vietoris 函子 $V$（分配带有 Vietoris 拓扑的紧子集）、常数和恒等映射构成。

• 结果： 如果函子中的常数是 Hausdorff 空间，则终极余代数在 $\omega$ 步 内获得（即 $\nu F = V_\omega$）。
• 子范畴： 该结果适用于 $\mathbf{Haus}$（Hausdorff 空间）、$\mathbf{KHaus}$（紧 Hausdorff 空间）和 Stone 空间。证明依赖于展示 Vietoris 函子在这些范畴中保持 $\omega^{op}$-链的极限。
• 意义： 这通过提供一个直接的 $\omega$ 步收敛证明，改进了 Hofmann 等人 [29] 和 Abramsky [1] 的结果，且该证明不依赖于 Zenor [50] 不完整的证明。

3. 度量空间上的多项式函子 (第 8 节)
作者在 $\mathbf{Met}$ 上定义了 Hausdorff 多项式函子，使用 Hausdorff 函子 $H$（分配带有 Hausdorff 度量的紧子集）。

• 结果： 与 Vietoris 情况不同，Hausdorff 多项式函子的终极余代数需要 $\omega + \omega$ 步（即 $\nu F = V_{\omega+\omega}$）。
• 原因： Hausdorff 函子并不保持 $\mathbf{Met}$ 中 $\omega^{op}$-链的极限（这与 $\mathbf{Haus}$ 中的 Vietoris 函子不同）。
• 具体表示： 本文将度量标签转移系统函子 $FX = H(\Sigma \times X)$ 的终极余代数具体表示为 强外延的、有限分支的边标签树，并配备了由标签导出的特定度量。

4. 详细证明与反例

• Worrell 的描述： 本文对 Worrell 关于有限幂集函子 $P_f$ 在树层面的描述提供了详细证明，此前该描述仅有陈述而无证明。
• 闭子集： 作者证明了 $\mathbf{Met}$ 上的函子 $P_{cl}$（分配所有闭子集）没有终极余代数（没有不动点），且子函子 $P'_{cl}$（非空闭子集）除了空集和单元素集外没有其他不动点（定理 8.19）。

意义与主张
本文声称通过识别保证 $\omega + \omega$ 步收敛的结构性质（DCC 和交集保持性），将 Worrell 定理推广到了 $\mathbf{Set}$ 之外。它根据基范畴区分了不同的多项式函子：

• $\mathbf{Haus}$ 上的 Vietoris 多项式 在 $\omega$ 步内收敛。
• $\mathbf{Met}$ 上的 Hausdorff 多项式 和 $\mathbf{Set}$ 上的 Kripke 多项式 在 $\omega + \omega$ 步内收敛。

作者明确指出，其工作改进了 Abramsky [1] 和 Hofmann 等人 [29] 关于 Vietoris 函子的结果。他们还指出，虽然 Makkai 和 Paré 的极限定理 [34] 保证了局部呈现范畴上可达函子（accessible functors）的终极余代数存在性，但它并未提供 $\omega + \omega$ 步的具体收敛界限，而这正是本研究的主要贡献。

开放问题
论文留下了两个问题：

1. 是否每一个全范畴 $\mathbf{Top}$ 上的 Vietoris 多项式函子（允许非 Hausdorff 常数）都具有终极余代数？
2. 是否每一个 $\mathbf{KHaus}$ 上的 Vietoris 多项式函子（具有紧 Hausdorff 常数和有限余积）都具有初始代数（initial algebra）？（作者指出，由于单态射在 $\mathbf{KHaus}$ 中不是光滑的，标准的初始代数论证在此失效）。