组合式计算上极限及可观测性概念

# 组合式计算上极限及可观测性概念 ## 组合式计算上极限 ### 上极限引理 有引理 colimE(colimGraph/|E|(D)) ∼= colimE(colimE · D)。证明思路是，对于任意 X ∈ E，只需证明从 colimGraph/|E|(D) 到 X 的余锥与从 colimE · D 到 X 的余锥之间存在双射。实际上，这两者都等价于一族“相容”的从 D(g)（g ∈ G）到 X 的余锥。 举个特殊例子，考虑 E 中的图的图 D = {{A} {B C}}。那么 colimE(colimGraph/|E|(D)) = colimE({A B C}) = A + B + C，而 colimE(colimE · D) = colimE({A B + C}) = A + (B + C)。该引理表明，三重和可以通过重复的双重和来形成，这也导致了和的结合律。一般形式的引理还暗示了更多的“结合律”，即任何两个产生相同图的 wscc 表达式在 cospan(E) 中都计算为相同的对象。 ### 定理示例 在 Cspn(Graph/|E|) 中，从 Ø 到 Ø 且中心为 D 的一般上推可以通过取所有箭头的不相交和，然后适当地等同顶点来构造。这给出了有限图的一般上极限的公式。设 Σdom 表示图 α∈D{dom(α)}，Σcod 表示图 α∈D{codom(α)}，Σα 表示图 α∈D{α}，Σobj 表示由 D 中所有对象组成的图。最后，设 idom 和 icod 表示与参数化 D 的图的箭头上的定义域和值域函数对应的离散上推。则上推可以写成： ```plaintext {}  η  Σdom + Σdom icod·( α)+idom Σobj + Σobj {}  ϵ  ``` 在 cospan(E) 中计算这个公式，得到用从 α∈D dom(α) 到 A∈D A（α 是 D 中的箭头，A 是 D 中的对象）的两个箭头的余等值子表示的经典上极限公式。 ### 幺半图的极限和上极限 - **幺半图的定义**：幺半图 (A, V, d0, d1) 由顶点集 V、弧集 A 以及两个函数 d0, d1 : A → V ∗（V ∗ 是 V 上的自由幺半群）组成。从 (A, V, d0, d1) 到 (B, W, d0, d1) 的幺半图态射 φ = (φ0, φ1) 由两个函数 φ1 : A → B 和 φ0 : V → W 组成，使得 φ∗0d0 = d0φ1，φ∗0d1 = d1φ1。我们将幺半图的范畴（实际上是预层范畴）记为 MonGraph。 - **幺半图上的余锥和上极限**：设 E 是具有有限上极限的范畴，将其视为以和为张量的幺半范畴。幺半图 D 到对象 X 的余锥 q 是一族箭头 (qi : Ai → X)（Ai 是图 D 的对象），使得对于图中任何箭头 f : Ai1 + Ai2 + · · · + Aim → Aj1 + Aj1 + · · · + Ajn，有 (qj1|qj2|qjn| · · · |qjn) · f = (qi1|qi2|qi3 · · · |qim)。幺半图 D 的上极限是一个对象 C 以及一个从 D 到 C 的通用余锥 q，即任何到对象 X 的余锥都能唯一地通过 q 分解。 ### Cspn(MonGraph/|E|) 设 E 是具有有限上极限的范畴，视为以和为张量的幺半范畴，|E| 表示 E 的基础幺半图。Cspn(MonGraph/|E|) 表示 cospan(MonGraph/|E|) 的全子范畴，其对象是 E 中的离散图。与 Cspn(Graph/|E|) 类似，我们可以描绘 Cspn(MonGraph/|E|) 中的箭头，唯一的区别是组件可能有多个输入和输出线。幺半上极限也可以在代数 cospan(E) 中组合式地计算，这类似于定理 1 的结果。对 E 中的图取幺半上极限诱导出一个函子 moncolim : MonGraph/|E| → E。 定理表明，函子 moncolim : MonGraph/|E| → E 可以扩展为一个函子 moncolim : Cspn(MonGraph/|E|) → cospan(E)，并且该函子保持 wscc 结