超图类别 Hypergraph Categories

超图类别 Hypergraph Categories

https://arxiv.org/pdf/1806.08304

摘要：

超图范畴（hypergraph categories）至少被重新发现了五次，使用了不同的名称，包括良支撑紧致闭范畴（well-supported compact closed categories）、dgs-幺半范畴（dgs-monoidal categories）和地牢范畴（dungeon categories）。它们之所以不断被重新发明，原因可能有两方面：一方面存在许多应用——包括自动机、数据库、电路、线性关系、图重写和信念传播；另一方面，标准定义过于复杂繁琐，以至于在文献中难以找到。事实上，粗略地说，超图范畴是“一种对称幺半范畴，其中每个对象都配备了特殊交换弗罗贝尼乌斯幺半群的结构，并满足某些相干条件”。

幸运的是，这一描述可以大大简化：超图范畴 simply 是一个“余跨度代数”（cospan-algebra），粗略地说，即从余跨度到集合的一个松弛幺半函子（lax monoidal functor）。本文的目标是去掉引号，使上述陈述精确化。我们证明了两个主要定理。第一个是超图范畴的相干性定理，它表明每个超图范畴都等价于一个对象自由的超图范畴（objectwise-free hypergraph category）。第二个定理证明，对象自由超图范畴的范畴等价于余跨度代数的范畴。

关键词：超图范畴，紧致闭范畴，弗罗贝尼乌斯代数，余跨度，接线图。

1 引言 假设你希望指定下图：

这张图可能表示，例如，一个电路、一个张量网络，或逻辑公式之间共享变量的模式。

指定方程 (1) 中图片的一种方法——给定符号 f、g、h 及其元数（arities）——是定义表示合并、初始化、分裂和终止线路的原语。然后可以逐块构建该图片，

并描述为如下文本字符串：

这套符号系统提供了一种描述 f、g 和 h 之间互连模式的方法。其微妙之处——一个非平凡的微妙之处——在于理解何时由两种不同构造所定义的态射应被视为相同。事实上，我们同样可以选择将上述图片表示为

尽管如此，尽管存在这种微妙之处，我们在过去几十年中刚刚概述的方法仍被独立地重新发现了多次，每次都有不同的名称和动机。最早的是 Carboni 和 Walters，他们将这种结构称为良支撑紧致闭范畴（well-supported compact closed category），并用它来研究关系范畴、标记迁移系统以及自动机 [Car91]。Bruni 和 Gadducci 在研究 Petri 网时称其为 dgs-幺半范畴（dgs-monoidal category）[GH98]。Morton 在研究信念传播时称其为地牢范畴（dungeon category）[Mor14]。最后，Kissinger 将其统一命名为超图范畴（hypergraph category），用于研究量子系统和图重写；Fong、Baez 和 Pollard 则用它来研究电路和化学反应网络 [Kis15; Fon15; BF18; BFP16]。

与此同时，Spivak 在其关于数据库的研究中也定义了本质上相同的结构 [Spi13]，但他更倾向于一种更为统一、组合化的方法。Spivak 没有考虑如何逐块生成此类图片，而是专注于写下连接模式。例如，方程 (1) 中的图片可以描述如下：首先，我们定义三个集合，分别对应于所有内部盒子（A，白色圆圈）的端口、中间节点（N，黑色圆圈）以及外部盒子（B，灰色圆圈）的端口。

Carboni 和 Walters 早已注意到这两种方法应当是相似的，而且上述几乎所有参考文献中都出现了这种余跨度思想的某些方面。在本文中，我们将确定确切的关系。为此需要对超图范畴及其函子进行彻底的调查，包括对自对偶紧致闭结构、自由超图范畴、超图函子上的分解系统以及超图范畴的相干定理的讨论。让我们更精确一些。

复合、接线图和余跨度

关于上述图表最相关的一点是它们可以被复合：新图表可以从旧图表中构建出来。让我们探讨一下复合在超图范畴和余跨度代数中是如何运作的。

我们将表示线路合并、初始化、分裂和终止的原语称为弗罗贝尼乌斯生成元（Frobenius generators），当它们的复合物遵循反映上述关于互连直觉的定律时，我们将所得结构称为特殊交换弗罗贝尼乌斯幺半群（special commutative Frobenius monoid）。超图范畴是一种对称幺半范畴，其中每个对象都以与幺半积相容的方式配备了特殊交换弗罗贝尼乌斯幺半群的结构。

幺半结构提供了来自拼接的复合概念：我们可以通过将它们首尾相接——即范畴复合——或并排排列——即幺半积——来构建新图表。作为特殊态射的弗罗贝尼乌斯生成元负责处理网络结构。

然而还有另一个视角：即替换（substitution）的视角。下面是一个图示表示，展示了那种在范畴、半范畴、带迹幺半范畴（traced monoidal categories）和超图范畴中有意义的复合类型。

上述图片被称为接线图（wiring diagrams）。在这里，我们将外部盒子视为与内部盒子具有相同性质，这使得可以将一个接线图代入另一个接线图中。

这种复合概念——代入——在接线图范畴中得到了形式化，该范畴的态射正是此类图表。此外，还存在一个从接线图范畴到任意超图范畴的对称幺半函子，它将每个接线图解释为该超图范畴中的一个态射。

不区分输入和输出的原因是，超图范畴的结构和公理允许我们任意“弯曲箭头”，正如我们在方程 (2) 和方程 (3) 之间的差异中所见。超图范畴的公理确保这两个图表表示同一个复合态射：方向性是无关紧要的。

我们在本文中类似地使用余跨度代数来提供对超图范畴的无偏视角。然而，这样做是有代价的：虽然超图范畴及其间的函子大致上是余跨度代数，但当人们考虑 2-范畴方面时，相应的陈述并不成立。换句话说，超图函子之间的自然变换在余跨度公式中是不可见的。事实上，人们可以将余跨度代数的范畴视为超图范畴的 2-范畴

的去范畴化（decategorification）。

此外，我们将证明每一个余跨度代数的态射都以这种方式产生。

利用格罗森迪克构造（Grothendieck construction），我们可以将上述同构 (8) 封装为一个单一的同构；这是我们的第二个主要定理。

定理 1.2.存在一个 1-范畴的同构，

2 基本定义：余跨代数（cospan-algebras）与超图范畴

在本节中，我们回顾将要使用的基本概念的定义：余跨代数（§2.1）、弗罗贝尼乌斯结构（Frobenius structures，§2.2）以及超图范畴（hypergraph categories，§2.3）。随后，我们将讨论超图范畴在范畴等价方面表现不佳的一些或许不可取的方式，从而引出余跨代数视角的动机（§2.4），并简要提及算子（operads）在本文中（正在消失的）作用（§2.5）。

2.1 余跨（Cospans）与余跨代数

我们将在第4节中看到，任何超图范畴都会产生一个余跨代数。 以下观察直接由定义2.2得出。

命题2.4。我们有一个范畴同构

2.2 特殊交换弗罗贝尼乌斯幺半群

在超图范畴中，每个对象都配备了一个特殊交换弗罗贝尼乌斯幺半群（special commutative Frobenius monoid）的结构，我们称之为弗罗贝尼乌斯结构。在本节中，我们回顾其定义并给出重要示例。

2.3 超图范畴

在超图范畴中，每个对象都有一个选定的弗罗贝尼乌斯结构，且该选择与幺半结构相容。

我们用 Hyp 表示以超图范畴为对象、以超图函子为态射的范畴；用

表示 2-范畴，除了上述对象和态射外，它还以幺半自然变换作为 2-态射。

注记 2.13. 注意，超图函子之间的任何自然变换都是可逆的，即自然同构。这由命题 3.1 以及紧致闭范畴（compact closed categories）之间的任何自然变换都是可逆的这一事实得出。

2.4 作为结构化范畴的超图范畴之批判

在这个简短的小节中，我们勾勒两个例子来阐述一个观点：不应将超图范畴视为结构化范畴。首先，我们在例 2.20 中表明超图结构不能沿范畴等价进行扩展。其次，我们在例 2.21 中表明，一个本质满且完全忠实的超图函子可能不是超图等价。这些批判为接下来的余跨代数视角提供了动机。

例 2.20 和 2.21 提出的批判很重要，因为它表明在某种重要意义上，超图范畴的行为并不像结构化范畴。当我们把超图范畴视为余跨代数时，这种批判就消解了——即上述问题变得无法表述。

因此，将超图范畴视为余跨代数具有明显的优势。然而，这也伴随着一些代价。第一个代价是余跨代数不考虑 2-态射，即超图函子之间的自然变换；关于是否和/或如何修正这一点，以及确实是否需要修正的问题，仍然悬而未决。第二个代价是余跨代数对应于对象无自由（objectwise-free, OF）的超图范畴。幸运的是，这第二个问题并不是非常重要：在第 3.4 节中，我们将证明每个超图范畴都自然等价于一个 OF 的超图范畴。

2.5 关于算子（operads）的一点说明

尽管幺半风格的接线图通常比算子风格的接线图更难进行视觉解析，但幺半范畴的符号记法通常比算子的符号记法更容易解析。因此，从现在开始，算子唯一出现的地方将仅限于接线图的可视化中。

3 超图范畴的性质

3.1 超图范畴是自对偶紧致闭范畴

例 3.5 将在后面派上用场，届时我们将看到，不仅超图范畴的弗罗贝尼乌斯结构由余跨（cospans）所控制，其恒等态射和复合律也是如此！

3.2 自由超图范畴

上述论证通过一个详细的例子或许最为清晰。例 3.7. 我们现在利用引理 3.6 中的生成元来构建余跨公式 (4)——如下方左侧所示。

3.3 超图函子的分解

当然，这里有一些细节需要验证，但我们将其留给读者。

注记 3.18. 上述内容在 2-范畴

上构成了一个正交分解系统 (io, ff)。关于定义以及在迹范畴（traced categories）和紧致闭范畴情形下的类似结果，请参见 [SSR16]。然而，我们不需要使用这一事实，因此省略证明。

事实上，(ff, io) 分解的特殊之处在于它导出了一个范畴的纤维化（fibration of categories），正如我们将在命题 3.20 中展示的那样；为此，先证明一个引理会有所帮助。

3.4 超图范畴的严格化

4 余跨代数与超图范畴是等价的

4.1 从超图范畴到余跨代数

4.2 从余跨代数到超图范畴

本小节的目的是提供等价关系 (24) 的另一半，即将任意余跨代数 AA 转换为一个超图范畴

。本小节旨在详细阐述以下构造。

4.3 OF-超图范畴与余跨代数之间的等价

我们现在准备证明该等价关系。

定理 4.13.命题 4.1 和 4.7 中的函子定义了一个范畴等价：

原文链接：https://arxiv.org/pdf/1806.08304