译米田嵌入

上一篇：米田引理

原文地址：https://bartoszmilewski.com/2...

我们之前已经看到，固定范畴C的一个对象，映射C(a, -)是一个从C到Set的（协变）函子。

x -> C(a, x)

(上域是Set是因为hom集C(a, x)是个集合。)我们把这个映射叫hom函子——我们之前也已经定义了它在态射上的行为。

现在让我们变化这个映射中的a。我们得到了一个新的映射：给任意的a分配一个hom函子C(a, -)。

a -> C(a, -)

这是个从范畴C的对象到函子的映射，而函子是函子范畴的对象（参见自然变换有关函子范畴的部分）。让我们用记号[C, Set]表示从C到Set的函子范畴。你也可能会回忆起hom函子就是那些原本的可表函子。

我们每有一个两范畴的对象之间的映射的时候，就会很自然地问它是否是个函子。换句话说我们是否可以把一个范畴的态射提升到另一个范畴。C的态射就只是一个C(a, b)的元素，但函子范畴[C, Set]的态射是自然变换。所以我们想要找一个从态射到自然变换之间的映射。

让我们看看能否根据一个态射f :: a->b找到一个自然变换。首先，我们得看看a和b被映为了什么。它们被映为了两个函子：C(a, -)和C(b, -)。我们需要这两个函子间的一个自然变换。

接下来就是技巧了：我们使用米田引理：

[C, Set](C(a, -), F) ≅ F a

把一般的F带成hom函子C(b, -)，我们就得到了：

[C, Set](C(a, -), C(b, -)) ≅ C(b, a)

这恰好就是我们要找的那两个函子间的自然变换，不过有点扭曲：我们得到了一个自然变换和态射间的映射——这个态射是C(b, a)的一个元素——这家伙的方向“错”了。但这没有什么问题；这只是意味着我们处理的这个函子是逆变的。

实际上，我们比所希求的得到了更多。这个从C到[C, Set]的映射可不只是个逆变函子——它是个完全忠实函子。完全性和忠实性是描述函子映射hom集时的性质。

忠实函子是说它在hom集上表现为单射，也就是它把不同的态射映为不同的态射。换句话说，它不会合并它们。

完全函子是说它在hom集上表现为满射，也就是它把一个hom集满映为另一个，完全覆盖后者。

数学中的满射在英文中有两种表达：一种是 surjective（满射），另一种是maps A onto B。也就是 onto在数学中有特殊的含义。这一句话就是作者把两种说法都说了一遍，以解释地更清楚。译者注。

完全忠实函子是说F在hom集上表现为双射——一个两集合元素间的一一映射。对于源范畴C的每一对对象a和b，都有一个C(a, b)和D(F a, F b)间的双射，其中D是F的靶范畴（我们这里就是函子范畴[C, Set]）。注意这并不是说F就是个对象间的双射。可能会有些D中的对象并不在F的像里，从而我们不能对这些对象的hom集说任何事情。

嵌入

我们刚刚所说的这个把C的对象映为了[C, Set]的函子的（逆变）函子：

a -> C(a, -)

就定义了米田嵌入。它把一个范畴C(严格地说，是范畴C^op，因为它是逆变的)嵌入到了函子范畴[C, Set]。这不仅仅是把C的对象映为了函子，而且它忠实地维持了它们之间的所有联系。

因为数学家们对函子范畴了解的很多，尤其是那些上域为Set的函子，所以这是个非常有用的结果。我们可以通过把任意范畴C嵌入它的函子范畴而得到很多关于它的洞见。

当然米田嵌入也有一个对偶版本，它有时叫做逆米田嵌入。注意我们可以从固定每个hom集的靶对象（而不是源对象）开始，也就是C(-, a)。这给了我们一个逆变的hom函子。从C到Set的逆变函子就是我们熟悉的预层（例如参见极限与余极限）。逆米田嵌入定义了范畴C到预层范畴的嵌入。它在态射上的行为由下式给出：

[C, Set](C(-, a), C(-, b)) ≅ C(a, b)

同样地，数学家们对预层范畴也了解很多，所以能把任意范畴嵌入其中实在是个好事。

在Haskell中的应用

Haskell中，米田嵌入被表示成reader函子间的自然变换和（反向）函数的同构：

forall x . (a -> x) -> (b -> x) ≅ b -> a

（记住，reader函子等价于((->) a)。）

等价的左边是个多态函数，给定一个a到x的函数和一个b类型的值，就能得到一个类型x的值（我没有用柯里化——也就是去掉了函数b -> x上的那个括号）。要对所有的x都能做这件事，唯一的方式就是我们的函数知道如何把一个b类型的值转换成一个a类型的值。这必然就隐晦地使用了函数b -> a。

给定这样的一个转换，btoa，就可以定义左边了，让我们叫它fromY：

fromY :: (a -> x) -> b -> x
fromY :: f b = f (btoa b)

反过来，给定一个函数fromY，我们可以通过用fromY调用恒等函数重构出这个转换：

fromY id :: b -> a

这构建了类型为fromY的函数到btoa的双射。

审视这个同构的另一个可能的方式就是它是一个从b到a的函数的CPS编码。参数a->x就是延继（那个处理器）。结果是个从b到x的函数，它需要一个b类型的值，它执行的是延继前复合上被编码的那个函数。

米田嵌入也解释了一些Haskell中数据结构的其他可能的表示方式。尤其是，它根据Control.Lens库提供了一种非常有用的representation of lenses。

这一篇 representation of lenses我没有翻译。米田嵌入是该作者范畴论的第二部分的最后一篇，我尚不知道下一步是先翻译第三部分还是翻译一些这样的零散文章。在我翻译这一篇之后，我会把翻译之后的链接补过来。译者注。

预序的例子

这是Robert Harper所建议的一个例子。它是米田嵌入在由一个预序定义的范畴上的应用。一个预序就是带上一个顺序关系的集合，这个元素间的顺序关系通常写作<=（小于等于）。预序里之所以有个"预"字是因为我们只需要这个关系的传递性和自反性而不需要反对称性（所以它是可能成环的）。

一个带有预序关系的集合导出了一个范畴。集合中的元素就是对象，如果对象a和b没法比较或者a <= b是错的，那a到b的态射就没有，或者a <= b，那这个态射就存在，它由a指向b。一个对象到另一个的态射永远不会多于一个。因该范畴上的hom集要么就是空集，要么就是单例集。这样的范畴称为薄的。

你很容易就可以看出这的确构造了一个范畴：箭头是可复合的，因为如果a <= b并且b <= c那么a <= c；而且这个复合是结合的。我们还有恒等箭头，因为每个元素（小于或）等于自己（这个关系的自反性）。

现在我们可以把逆米田嵌入用到预序范畴上了。特别地，我们感兴趣的是它在态射上的行为：

[C, Set](C(-, a), C(-, b)) ≅ C(a, b)

右边的hom集是非空的，当且仅当a <= b——这时它是个单例集。因此，如果a <= b，就存在一个左边的自然变换。否则就没有这样的自然变换。

那么预序的hom函子间的自然变换究竟是什么？它应该是一个从集合C(-, a)到C(-, b)的函数族。在预序里，这些集合中的每一个要么是空的要么是单例集。让我们看看我们现在所处理的函数都是些什么家伙。

这里的表达略微混乱，不过不影响理解。“这些集合中的每一个要么是空的要么是单例集”应指像 C(x, a)和 C(x, b)这样的家伙，而不是 C(-, a)和 C(-, b)。译者注。

从空集到自身有一个函数（也就是空集上的恒等函数），从空集到单例集有个absurd函数(它什么也不做，因为这需要定义一个空集中的元素，但空集里什么也没有)，从单例集到自己也有个函数(单例集的恒等函数)。唯一不被允许的组合方式是把一个单例集映为空集（这个函数把那单个的元素究竟映为了什么呢？）。

所以我们的自然变换永远不能把单例集和空集连起来。换句话说，如果x <= a(C(x, a)是个单例hom集)那么C(x, b)就不能为空。一个非空的C(x, b)意味着x小于等于b。所以这个问题里自然变换的存在性就需要对于每个x来说，如果x <= a那么x <= b。

for all x, x ≤ a ⇒ x ≤ b

另一边，反米田嵌入告诉我们自然变换的存在性等价于C(a, b)是非空的，或者说a <= b。把这两者放到一起，就得到了:

a ≤ b if and only if for all x, x ≤ a ⇒ x ≤ b

我们可以直接得到这个结果。直观上说，如果a <= b那么所有比a小的元素都要比b小。反过来，把右边的x替换成a，就得到了a <= b。但你必须承认通过米田嵌入得到这个结果远让人更为兴奋。

自然性

米田引理构造了一个自然变换的集合和一个Set中对象的同构。自然变换是函子范畴[C, Set]的态射。两个函子间自然变换的集合是这个范畴的一个hom集。米田引理是下面这个同构：

[C, Set](C(a, -), F) ≅ F a

这个同构可以证明对于F和a都是自然的。换句话说，它在积范畴[C, Set] × C的序对(F, a)上是自然的。注意现在我们把F看成函子范畴的一个对象。

让我们考虑下这意味着什么。自然同构是两个函子间的可逆的自然变换。确实，我们的同构的右边是个函子。这是个从[C, Set] × C到Set的一个函子。它在序对(F, a)上作用的结果是个集合——就是给函子F带入对象a的执行结果。这样的函子叫执行函子。

左边也是个把(F, a)变到自然变换集合[C, Set](C(a, -), F)的一个函子。

为了证明它们是真正的函子，我们还应该定义它们在态射上的行为。但序对(F, a)和(G, b)之间的态射是什么？这是一对态射,(Φ，f)；第一个是函子间的态射——一个自然变换——第二个是C上的常规态射。

执行函子取序对(Φ, f)并把它映为一个集合F a到G b间的函数。我们可以轻易地通过Φ在a上的分量（它把F a映为G a）和被G提升后的态射f，构造出这样一个函数：

(G f) ∘ Φ_a

注意，由于Φ有自然性，所以这等同于:

Φ_b ∘ (F f)

我不会证明整个同构的自然性——在构建了函子之后，证明是非常机械化的。它利用了我们的同构是建立在函子和自然变换上的这样一件事。这很简单，没可能搞错。

挑战

1. 在Haskell中表达逆米田嵌入
2. 证明我们建立的fromY和btoa之间的双射是个同构（这两个映射是互逆的）。
3. 用米田嵌入处理幺半群。幺半群的那个单个对象对应的是什么函子？幺半群态射对应的是什么自然变换？
4. 协变的米田嵌入在预序上的应用是什么？（Gershom Bazerman所提出的问题）
5. 米田嵌入可以用来把任意函子范畴[C, D]嵌入到函子范畴[[C, D], Set]。指出它在态射（这里是自然变换）上的行为。

致谢

感谢Gershom Bazerman检查我的数学和逻辑。

下一篇：有关态射的一切