Terminal Coalgebras in Countably Many Steps

技術要約：可算ステップにおける終極余代数

問題提起
本論文は、様々な圏における自己関手（endofunctor）の終極余代数の構成について扱う。終極余代数 $\nu F$ を構成する標準的な手法は、関手 $F$ を一意な射 $F1 \to 1$ に対して反復適用し、超限鎖（terminal-coalgebra chain）を形成することである。この鎖は、関手が関連する極限を保存する場合に $\nu F$ へ収束するが、反復に必要な回数は任意に大きくなる可能性があり、あるいは（べき集合関手などのように）鎖が全く収束しないこともある。

Worrell [49] による先駆的な結果は、集合の圏 ($\mathbf{Set}$) における有限生成（finitary）な自己関手に対して、終極余代数は正確に $\omega + \omega$ ステップ（すなわち $\nu F = V_{\omega+\omega}$）で得られることを確立した。本論文の中心的な問題は、Worrell の結果を他の基底圏へと一般化し、位相空間や距離空間における多項式関手のような特定のクラスの関手に対する収束境界を決定することである。

手法
著者らは、圏論的手法と特定の有限性議論の組み合わせを用いている：

1. 降下鎖条件 (DCC): 論文では DCC-圏 という概念を導入している。これは、有限生成対象が部分対象および強商（strong quotients）に関する降下鎖条件を満たす局所有限生成圏である。この条件により、これらの圏における $\omega^{op}$-極限が「有限的」であることが保証される（命題 3.16）。
2. 保存特性: 収束に必要とされる特定の保存特性を抽出している：
   • 空でない二項交わり（非厳密な始域を持つ単射のプルバック）の保存。
   • 等長埋め込み（isometric embeddings）の保存（距離空間の文脈において）。
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）を提供している。すなわち、有限生成かつ 空でない二項交わり と 等長埋め込み を保存する自己関手は、同様に $\omega + \omega$ ステップで収束する。

2. 位相空間上の多項式関手 (セクション 7)
著者らは、Vietoris 関手（コンパクト部分集合にVietoris位相を割り当てるもの）、定数、および恒等関数から構成される、位相空間の圏 ($\mathbf{Top}$) 上の Vietoris 多項式関手 を研究している。

• 結果: 関手の定数が ハウスドルフ空間 である場合、終極余代数は $\omega$ ステップ で得られる（$\nu F = V_\omega$）。
• 部分圏: この結果は、ハウスドルフ空間 ($\mathbf{Haus}$)、コンパクトハウスドルフ空間 ($\mathbf{KHaus}$)、およびStone空間の圏で成立する。証明は、Vietoris 関手がこれらの圏における $\omega^{op}$-鎖の極限を保存することを示すことに依拠している。
• 意義: これは、Zenor [50] の不完全な証明に依存しない直接的な $\omega$ ステップでの収束の証明を提供することで、Hofmann ら [29] や Abramsky [1] の結果を改善している。

3. 距離空間上の多項式関手 (セクション 8)
著者らは、Hausdorff 関手（コンパクト部分集合にHausdorff距離を割り当てるもの）を用いる $\mathbf{Met}$ 上の 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 の記述: 本論文は、以前は証明なしに述べられていた、有限べき集合関手 $P_f$ に関する木を用いた Worrell の記述について、詳細な証明を提供している。
• 閉部分集合: 著者らは、$\mathbf{Met}$ 上の関手 $P_{cl}$（すべての閉部分集合を割り当てるもの）は 終極余代数を持たない（不動点が存在しない）こと、およびその部分関手 $P'_{cl}$（空でない閉部分集合）は空集合と一点集合を除いて不動点を持たないことを証明している（定理 8.19）。

意義および主張
本論文は、構造的特性（DCCおよび交わりの保存）を特定することにより、Worrell の定理を $\mathbf{Set}$ から越えて一般化することを主張している。また、基底圏に基づいて異なる多項式関手を区別している：

• $\mathbf{Haus}$ 上の Vietoris 多項式 は $\omega$ ステップで収束する。
• $\mathbf{Met}$ 上の Hausdorff 多項式 および $\mathbf{Set}$ 上の Kripke 多項式 は $\omega + \omega$ ステップで収束する。

著者らは、Vietoris 関手に関して Abramsky [1] および Hofmann ら [29] の結果を改善したことを明示的に述べている。また、Makkai および Paré の極限定理 [34] が、局所呈示的（locally presentable）な圏における到達可能（accessible）な関手の終極余代数の 存在 を保証するものの、本研究の主要な貢献である $\omega + \omega$ ステップという具体的な収束境界は提供しないことも指摘している。

未解決問題
論文では以下の2つの問いを未解決のまま残している：

1. （非ハウスドルフな定数を許容する）完全な $\mathbf{Top}$ 圏上のすべての Vietoris 多項式関手は、終極余代数を持つか？
2. すべての Viet or 是 Vietoris 多項式関手（コンパクトハウスドルフな定数と有限余積を持つ）は、$\mathbf{KHaus}$ 上で初期代数を持つか？（著者らは、$\mathbf{KHaus}$ では単射が滑らか（smooth）ではないため、標準的な初期代数の議論がここでは失敗することを注記している）。