自由单子 [自由单子]

定义

单子是自函子范畴中的结合代数; 自由单子就是这种代数中的自由代数.

例

树的自由单子

树上的自由单子通过如下具体过程给出. 对于树 $$ T = (I\overset{s}{\leftarrow} E \overset{p}{\to} B \overset{t}{\to} I), $$ 记

  • $\operatorname{Sub}(T) := \mathsf{TEmb}_{/T}^{\simeq}$ 为 $T$ 的子树的集合 ($\mathsf{TEmb}$ 为树及含入构成的范畴),
  • $\operatorname{Sub}'(T)$ 为 $T$ 的带一个标记叶的子树的集合.

那么树 $T$ (对应的多项式函子)的自由单子即是如下多项式函子: $$ \overline{T} = (I \leftarrow \operatorname{Sub}'(T) \to \operatorname{Sub}(T) \to I). $$

事实上, 上述构造对一般的多项式函子也是成立的.

多项式的自由单子

对于多项式 $$ P = (I\overset{s}{\leftarrow} E \overset{p}{\to} B \overset{t}{\to} I), $$ 记

  • $\operatorname{tr}(P) := \mathsf{TEmb}_{/P}^{\simeq}$ 为 $P$-树的生象, 映射 $\operatorname{tr}(P)\to I$ 将 $P$-树映射到其根的标记;
  • $\operatorname{tr}'(P)$ 为带一个特殊标记叶的 $P$-树的生象, 映射 $\operatorname{tr}'(P)\to I$ 将 $P$-树映射到其特殊标记叶的标记.

命题 (Kock, 命题 1.2.8). 多项式函子 $P$ 的自由单子即是如下多项式函子: $$ \overline{P} = (I \leftarrow \operatorname{tr}'(P) \to \operatorname{tr}(P) \to I). $$

证明. 由定义, 对于 $(X\to I)\in\mathsf{Ani}_{/I}$, $$ \overline{P}(X)_i = \sum_{T\in\operatorname{tr}(P)_i}\prod_{\ell\in\ell(T)}X_\ell, $$ 其中 $\ell(T)$ 表示树 $T$ 的叶的集合; 换言之, $\overline{P}(X)$ 是每个叶带 $X$ 标记的树的生象 (更准确地说, 每个带 $i\in I$ 标记的叶, 都额外带一个 $X_i$ 中的标记).

于是 $\overline{P}(X)$ 就是自函子 $X + P\colon \mathsf{Ani}_{X/}\to\mathsf{Ani}_{X/}$, $(X\to Y)\mapsto (X+P(Y))$ 的始代数, 也即 $X$ 上的自由 $P$-Lambek 代数. 这说明 $\overline{P}$ 是 $P$ 的自由单子 (见下文 “自函子的自由单子”). $\square$

自函子的自由单子

命题 (参考 GHK 4.2 节). 设范畴 $\mathcal C$ 具有滤余极限和二元和, 自函子 $P\colon \mathcal C\to\mathcal C$ 保持滤余极限. 记 $\mathsf{alg}_P(\mathcal C)$ 为 $P$-Lambek 代数 (即对象 $X$ 带有态射 $\alpha\colon P(X)\to X$ 的结构) 的范畴. 那么有单子性的自由–遗忘伴随 $$ F\colon \mathcal C \rightleftarrows \mathsf{alg}_{P}(\mathcal C)\colon U, $$ 且这对伴随给出的单子 $\overline{P}$ 正是自函子 $P$ 上的自由单子. 进一步有 $$ \mathsf{Alg}_{\overline{P}}(\mathcal C) \simeq \mathsf{alg}_P(\mathcal C). $$

自由单子还可更显式地写出: 定义 $P_0 = \mathrm{id}$, $P_{n+1} = \mathrm{id} + PP_n$, 有一列自然变换 $P_0\to P_1\to\cdots$, 那么 $$ \overline{P} =\operatorname{colim}_n P_n. $$