MathLabs

数学基础

米田引理

一个对象在同构意义下完全由从范畴中其他任何地方指向它的所有箭头的模式所确定——米田引理把这个观察变成一个精确的双射,而其推论,即嵌入 A↦Hom(−,A)A\mapsto\mathrm{Hom}(-,A) 是全忠实的,正是使"通过映射研究对象"从一句口号变成一种严谨方法的唯一事实。

直观一个对象就是它所做的事

要完全了解一个电子元件,你不需要看它内部——只需知道,对于每一种可能的外围电路,该元件恰好能以怎样的方式接入其中即可。在范畴中,类似的事实是:一个对象 AA 在同构意义下完全由知道 Hom(X,A)\mathrm{Hom}(X,A)——映射进入 AA 的所有方式构成的集合——对每一个对象 XX 同时成立所确定。

一个对象网络的交互式图,其中所有态射都指向一个特定对象A。
把从每一个对象 XX 指向 AA 的每一条箭头一次性收集起来——这正是预层 hAh_A 所记录的数据。

大学可表预层

定义: 预层 hAh_A

对 C\mathcal{C} 的一个对象 AA,可表预层 hA=HomC(−,A)h_A=\mathrm{Hom}_{\mathcal{C}}(-,A) 把每个对象 XX 送到集合 hA(X)=HomC(X,A)h_A(X)=\mathrm{Hom}_{\mathcal{C}}(X,A),把每个态射 g:X→Yg:X\to Y 送到前合成映射 hA(g):Hom(Y,A)→Hom(X,A),f↦f∘gh_A(g):\mathrm{Hom}(Y,A)\to\mathrm{Hom}(X,A),\quad f\mapsto f\circ g。这使得 hAh_A 成为一个函子 Cop→Set\mathcal{C}^{\mathrm{op}}\to\mathbf{Set}——它是反变的,因为在右边与 gg 合成会颠倒指派的方向。

hA(X)=HomC(X,A)h_A(X) = \mathrm{Hom}_{\mathcal{C}}(X,A)

对任意函子 F:Cop→SetF:\mathcal{C}^{\mathrm{op}}\to\mathbf{Set},米田引理说从 hAh_A 到 FF 的自然变换与单个集合 F(A)F(A) 的元素一一对应:Nat(HomC(−,A),F)≅F(A)\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A)。这个双射由两个方向相反的映射 Φ\Phi 与 Ψ\Psi 构成。

Nat(HomC(−,A),F)≅F(A)\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A), F) \cong F(A)
米田双射的两个方向
映射方向公式
Φ\PhiNat(hA,F)→F(A)\mathrm{Nat}(h_A,F)\to F(A)Φ(η)=ηA(1A)\Phi(\eta)=\eta_A(1_A)
Ψ\PsiF(A)→Nat(hA,F)F(A)\to\mathrm{Nat}(h_A,F)Ψ(x)X(f)=F(f)(x)\Psi(x)_X(f)=F(f)(x)

进阶双射,逐步证明

Φ\Phi 在可能的最经济输入——单位元 1A∈hA(A)=Hom(A,A)1_A\in h_A(A)=\mathrm{Hom}(A,A)——处求值自然变换 η:hA⇒F\eta:h_A\Rightarrow F,产生 F(A)F(A) 的元素 ηA(1A)\eta_A(1_A)。反方向上,Ψ\Psi 从一个元素 x∈F(A)x\in F(A) 出发,对每个对象 XX 与每个 f∈Hom(X,A)f\in\mathrm{Hom}(X,A),通过沿 F(f)F(f) 把 xx 向前推来重构 F(X)F(X) 的一个元素:Ψ(x)X(f)=F(f)(x)\Psi(x)_X(f)=F(f)(x)。η\eta 的自然性正是使 Ψ(Φ(η))\Psi(\Phi(\eta)) 恢复出 η\eta 的原因,下一个定理将完整证明这一点。

Φ(η)=ηA(1A)\Phi(\eta) = \eta_A(1_A)
Ψ(x)X(f)=F(f)(x)\Psi(x)_X(f) = F(f)(x)
定理: 米田引理

对任意函子 F:Cop→SetF:\mathcal{C}^{\mathrm{op}}\to\mathbf{Set} 与对象 AA,上面的映射 Φ\Phi 与 Ψ\Psi 互为逆,因此 Nat(HomC(−,A),F)≅F(A)\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A) 是一个真正的集合双射。

为什么成立?

这正是让范畴论学者能够把一个无限、难以把握的自然变换族,换成 F(A)F(A) 的一个具体元素——关于从可表预层 hAh_A 出发的映射的每一个问题,都归结为关于一个集合的问题。

证明

我们先验证对每个 x∈F(A)x\in F(A) 都有 Φ(Ψ(x))=x\Phi(\Psi(x))=x。展开定义:把 Ψ\Psi 的公式特殊化到 X=AX=A、f=1Af=1_A,得到 Ψ(x)A(1A)=F(1A)(x)\Psi(x)_A(1_A)=F(1_A)(x)。因为 FF 是函子,它把恒等态射 1A1_A 送到 F(A)F(A) 上的恒等函数,所以 F(1A)(x)=xF(1_A)(x)=x。因此 Φ(Ψ(x))=Ψ(x)A(1A)=x\Phi(\Psi(x))=\Psi(x)_A(1_A)=x,正如所需——这一方向只用到了函子的恒等律。

现在验证更难的方向,对每个自然变换 η:hA⇒F\eta:h_A\Rightarrow F 都有 Ψ(Φ(η))=η\Psi(\Phi(\eta))=\eta。两边都是自然变换 hA⇒Fh_A\Rightarrow F,所以只需说明它们在每个对象 XX 与每个元素 f∈hA(X)=Hom(X,A)f\in h_A(X)=\mathrm{Hom}(X,A) 处的分量一致。

用 x:=Φ(η)=ηA(1A)x:=\Phi(\eta)=\eta_A(1_A) 展开 Ψ(Φ(η))X(f)\Psi(\Phi(\eta))_X(f) 的 Ψ\Psi 公式,得到它等于 F(f)(ηA(1A))F(f)(\eta_A(1_A))。

现在用 η\eta 本身的自然性,以 ηY(f∘g)=F(g)(ηX(f))\eta_Y(f\circ g)=F(g)(\eta_X(f)) 的形式,取 g:=f:X→Ag:=f:X\to A、另一个变量取为 AA:在该自然性方块中取 f:=1A∈hA(A)f:=1_A\in h_A(A),恰好给出 ηX(1A∘f)=F(f)(ηA(1A))\eta_X(1_A\circ f)=F(f)(\eta_A(1_A)),即由 1A∘f=f1_A\circ f=f 得 ηX(f)=F(f)(ηA(1A))\eta_X(f)=F(f)(\eta_A(1_A))。

结合最后两式:Ψ(Φ(η))X(f)=F(f)(ηA(1A))=ηX(f)\Psi(\Phi(\eta))_X(f)=F(f)(\eta_A(1_A))=\eta_X(f)。由于 XX 与 ff 是任意的,两个自然变换处处一致,所以 Ψ(Φ(η))=η\Psi(\Phi(\eta))=\eta。结合第一段,Φ\Phi 与 Ψ\Psi 是互逆的双射。

米田嵌入 y:C↪[Cop,Set]y:\mathcal{C}\hookrightarrow[\mathcal{C}^{\mathrm{op}},\mathbf{Set}],y(A)=hAy(A)=h_A,是全忠实的:对每个 A,B∈CA,B\in\mathcal{C},Nat(hA,hB)≅HomC(A,B)\mathrm{Nat}(h_A,h_B)\cong\mathrm{Hom}_{\mathcal{C}}(A,B),且该双射把态射 f:A→Bf:A\to B 送到由与 ff 后合成给出的自然变换 hA⇒hBh_A\Rightarrow h_B。

为什么成立?

全忠实性正是保证翻译 A↦hAA\mapsto h_A 不丢失任何信息:C\mathcal{C} 中不同的态射变成不同的自然变换,而两个可表预层之间的每一个自然变换都来自 C\mathcal{C} 中一个真实的态射,这正是纯粹通过映射到对象来研究对象这一方法的正当性所在。

证明

把目标函子取为 F:=hBF:=h_B 应用米田引理。该引理给出双射 Nat(hA,hB)≅hB(A)\mathrm{Nat}(h_A,h_B)\cong h_B(A),展开定义 hB(A)=HomC(A,B)h_B(A)=\mathrm{Hom}_{\mathcal{C}}(A,B) 恰好得到 Nat(hA,hB)≅HomC(A,B)\mathrm{Nat}(h_A,h_B)\cong\mathrm{Hom}_{\mathcal{C}}(A,B)。

剩下要确定的是,在这个双射下,自然变换 η:hA⇒hB\eta:h_A\Rightarrow h_B 对应到 C\mathcal{C} 中的哪个态射,并验证它就是后合成。按 Φ\Phi 的公式,η\eta 对应元素 Φ(η)=ηA(1A)∈Hom(A,B)\Phi(\eta)=\eta_A(1_A)\in\mathrm{Hom}(A,B);把这个态射记为 ff。

现在用 Ψ(Φ(η))=η\Psi(\Phi(\eta))=\eta(上面的定理,应用于 F=hBF=h_B)从 ff 恢复 η\eta 的每一个分量:对任意对象 XX 与任意 g∈hA(X)=Hom(X,A)g\in h_A(X)=\mathrm{Hom}(X,A),Ψ(f)X(g)=hB(g)(f)\Psi(f)_X(g)=h_B(g)(f)。展开 hBh_B 在态射上的反变作用——前合成——得到 hB(g)(f)=f∘gh_B(g)(f)=f\circ g。所以 ηX(g)=f∘g\eta_X(g)=f\circ g:η\eta 的每个分量都字面意义上就是与 ff 后合成。

因为 Φ\Phi 与 Ψ\Psi 互为逆双射(上面已证明),而与 ff 后合成恰好就是 Ψ(f)\Psi(f),所以把 ff 送到与 ff 后合成的这个指派本身就是一个双射 Hom(A,B)→Nat(hA,hB)\mathrm{Hom}(A,B)\to\mathrm{Nat}(h_A,h_B)——这正是 yy 全忠实这一命题。

大学应用:模空间与延续传递风格

在代数几何中,某种几何对象(曲线、向量丛……)的模空间首先通过写出一个函子 FF 来定义,它把测试对象 XX 送到该几何结构在 XX 上的所有族构成的集合;模空间(如果存在)是表示 FF 的一个对象 MM,即 F≅hMF\cong h_M。米田嵌入是全忠实的,恰恰是这样的 MM(当它存在时)在唯一同构意义下唯一的原因——Grothendieck的"点的函子"哲学把每个概形都仅仅看作它的可表预层。在函数式编程中,延续传递风格函数的类型 ∀r. (a→r)→r\forall r.\ (a\to r)\to r,按其构造,正是从协变Hom函子 Hom(a,−)\mathrm{Hom}(a,-) 到恒等函子的自然变换的类型;(协变、对偶的)米田引理恰好说明 ∀r. (a→r)→rcong a\forall r.\ (a\to r)\to r \\cong\ a,这与一个经过CPS变换的值不过是重新打包的普通值这一日常事实相吻合。

例题: 在两对象范畴上检验双射

设 C\mathcal{C} 有两个对象 0,10,1、恒等态射,以及一个非恒等态射 ι:0→1\iota:0\to1。取 A=1A=1,F=h1F=h_1 本身。通过直接枚举验证对这个 FF 有 Nat(HomC(−,A),F)≅F(A)\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A),即 Nat(h1,h1)\mathrm{Nat}(h_1,h_1) 的元素个数恰好等于 h1(1)=Hom(1,1)h_1(1)=\mathrm{Hom}(1,1) 的元素个数。

解答

首先明确计算 h1h_1:h1(0)=Hom(0,1)={ι}h_1(0)=\mathrm{Hom}(0,1)=\{\iota\}(一个元素),h1(1)=Hom(1,1)={11}h_1(1)=\mathrm{Hom}(1,1)=\{1_1\}(一个元素,因为 C\mathcal{C} 中没有其他从 11 到 11 的态射)。所以 F(A)=h1(1)F(A)=h_1(1) 恰好有一个元素 111_1。

按米田引理,Nat(h1,h1)\mathrm{Nat}(h_1,h_1) 也应恰好有一个元素。直接验证:自然变换 η:h1⇒h1\eta:h_1\Rightarrow h_1 需要分量 η0:{ι}→{ι}\eta_0:\{\iota\}\to\{\iota\} 与 η1:{11}→{11}\eta_1:\{1_1\}\to\{1_1\}。这些集合各只有一个元素,所以每个对象处恰好只有一个可能的函数——恒等函数——总共恰好给出一个候选 η\eta。

仍需检查这个候选满足自然性(这里自动成立,因为自然性方块强制 η0(ι)=η0(11∘ι)=h1(ι)(η1(11))=h1(ι)(11)=11∘ι=ι\eta_0(\iota)=\eta_0(1_1\circ\iota)=h_1(\iota)(\eta_1(1_1))=h_1(\iota)(1_1)=1_1\circ\iota=\iota,而这总是成立,因为反正只有一个可用的值)。

所以 Nat(h1,h1)={idh1}\mathrm{Nat}(h_1,h_1)=\{\mathrm{id}_{h_1}\} 恰好有一个元素,与 F(A)={11}F(A)=\{1_1\} 恰好有一个元素相符——双射 Nat(HomC(−,A),F)≅F(A)\mathrm{Nat}(\mathrm{Hom}_{\mathcal{C}}(-,A),F)\cong F(A) 在这里具体成立,且 Φ(idh1)=(idh1)1(11)=11\Phi(\mathrm{id}_{h_1})=(\mathrm{id}_{h_1})_1(1_1)=1_1 直接恢复出这唯一的元素。

例题: 延续传递风格作为米田

在函数式语言中,类型 ∀r. (a→r)→r\forall r.\ (a\to r)\to r 的一个值,是一个函数 kk,给定任意一种消费 aa 的方式(一个函数 a→ra\to r),都能产生一个 rr。说明 kk 完全由一个类型为 aa 的普通值确定,并能恢复出该值。

解答

把 C=Set\mathcal{C}=\mathbf{Set}(或类型与函数的范畴)固定,固定对象 aa,令 F=IdF=\mathrm{Id} 为恒等函子。一个值 k:∀r. (a→r)→rk:\forall r.\ (a\to r)\to r,按定义,就是对每个类型 rr 选择一个函数 kr:(a→r)→rk_r:(a\to r)\to r——这恰好是从协变函子 Hom(a,−)\mathrm{Hom}(a,-) 到 Id\mathrm{Id} 的一个自然变换(这里的自然性正是"对所有 rr"所强制的参数化性)。

应用(协变、对偶的)米田引理中的 Φ\Phi:Φ(k)=k(ida)\Phi(k)=k(\mathrm{id}_a) 在 r:=ar:=a 处、对恒等函数 ida:a→a\mathrm{id}_a:a\to a 求值 kk,产生一个类型为 aa 的普通值。这就是"延续确定一个值"的方向。

反方向应用 Ψ\Psi:给定一个值 n:an:a,对每个 rr 与每个 g:a→rg:a\to r 定义 Ψ(n)r(g)=g(n)\Psi(n)_r(g)=g(n)——即 Ψ(n)r(g)=g(n)\Psi(n)_r(g)=g(n),这是一个值的标准CPS变换:"给定任意消费者 gg,就把 nn 交给它的那个延续"。

按应用于 F=IdF=\mathrm{Id} 的米田引理,这两个构造互为逆:Φ(Ψ(n))=Ψ(n)a(ida)=ida(n)=n\Phi(\Psi(n))=\Psi(n)_a(\mathrm{id}_a)=\mathrm{id}_a(n)=n 恢复出该值,而 Ψ(Φ(k))=k\Psi(\Phi(k))=k 由上面定理中自然性的论证特殊化到 F=IdF=\mathrm{Id} 得出。因此 ∀r. (a→r)→rcong a\forall r.\ (a\to r)\to r \\cong\ a,这证实了延续传递风格的值恰好携带一个普通值的信息,不多也不少。

Φ\Phi 对自然变换 η:hA⇒F\eta:h_A\Rightarrow F 做了什么?

Ψ(Φ(η))=η\Psi(\Phi(\eta))=\eta 中的关键步骤依赖于 η\eta 的哪个性质?

在延续传递风格中,类型 ∀r. (a→r)→r\forall r.\ (a\to r)\to r 与哪个类型自然同构?

米田嵌入是全忠实的,这让我们能得出模函子 FF 的表示对象 MM 是:

参考文献

  1. Saunders Mac Lane (1998). Categories for the Working Mathematician
  2. Emily Riehl (2016). Category Theory in Context
  3. Jacob Lurie (2009). Higher Topos Theory · arXiv:math/0608040