函子範疇與 Yoneda Lemma（一）

談完範疇的基礎後，可以理解到數學基礎亂七八糟放心地討論範疇論實用的部分：函子（functor）、自然轉換（natural transformation），函子範疇（functor category）以及 Yoneda 引理。

範疇不是發明來研究函子；我是為了研究自然轉換才發明函子的。

S. Mac Lane (範疇論的創始者), Categories for Working Mathematician §I.4, 1988

從 Mac Lane 的話來說，範疇論最重要的部分是自然轉換，而此概念也會反覆用在函數編程（functional programming）上，尤其是 monad 在 Categories for Working Mathematician （CWM）定義由函子與自然轉換所構成，並且等價於 Haskell 中的定義。這兩者定義，在近年來討論 "effectful" programming 跟 algebraic effect 發揮相當的影響力。

函子（functor）

近代數學中我們先探討何種「操作」跟「特別的元素」（抽象上，操作跟特別的元素是一樣的）是我們所關心的，而結構間的態射就定義為相容於操作的函數。舉例來說，可以對字串作「串接」：將字串 $s = s_1 \dots s_n$跟字串 $t = t_1 \dots t_m$ 接在一起變成字串 $st = s_0 \dots s_n t_0 \dots t_m$，我們說一字串上的函數「保持串街」若先將字串 $s, t$ 作串街再套用函數，其結果跟先套用函數於字串再作串街會是一樣的。而範疇我們所定義的操作，只有態射間的合成，因此我們有以下的定義： 給定兩個範疇 $C, D$，一個函子（functor）$F : C \rightarrow D$ 組成有

1. 對每個物件的對應：$F_{Obj} : Obj(C) \rightarrow Obj(D)$
2. 對每個態射的對應：$F_{Mor} : Mor(C) \rightarrow Mor(D)$

（通常省略下標 $Mor$ 跟 $Obj$）並滿足以下的條件

1. 保持定義域與值域：$F$ 作用於態射 $f : a \rightarrow b$ 為一個從 $Fa$ 到 $Fb$ 的態射。因此，我們可以將 $F_{Mor}$ 寫成對所有物件 $a, b$ 的態射對應 $F_{a, b} : hom(a, b) \rightarrow hom(Fa, Fb)$。
2. 保持單位態射：對每個單位態射 $id_a : a \rightarrow a$ 其對應仍是單位態射 $F(id_a) = id_{Fa} : Fa \rightarrow Fa$。
3. 保持態射間的合成：對態射 $f : a \rightarrow b, g : b \rightarrow c$ 有 $F(g \circ f) = Fg \odot Ff : Fa \rightarrow Fc$ 其中 $\circ$ 表示 $C$ 上的合成，後者 $\odot$ 代表 $D$ 上的合成（通常範疇上的考慮的合成只有一個時，統一用 $\circ$ 作為合成的符號）。

第一個條件說函子保持態射的「定義域」與「值域」，不論我們先取態射的值域跟定義域再套用 $F$，或者先套用 $F$ 再算值域跟定義域都會得到一樣的東西。第二個條件說函子保持單位態射。第三個條件說函子保持態射的合成。因此，函子其實只是作為保持範疇結構的對應。一般的定義會直接使用將態射的對應寫成 $f : a \rightarrow b \mapsto Ff : Fa \rightarrow Fb$，但之後我們談「範疇內的範疇」時，常見的定義就沒那麼好用了。接下來我們來看點簡單的範例：

1. 固定一個集合 $A$，我們都可以定義一個函子 $A\times(-) : \mathbf{Set} \rightarrow \mathbf{Set}$ 如下。每個集合 $X$ 都對應到 $A \times X = \{ (a, x) : a \in A, x \in X \}$ ；每個函數 $f : X \rightarrow Y$  對應到一個函數 $A \times X \rightarrow A \times Y$ 將 $(a, x)$ 送到 $(a, f(x))$。同樣地，我們也可以定義 $(-) \times A$ 函子，將集合 $X$ 對應到 $X \times A$。注意，這兩個函子並不相同，對應到的集合根據定義是不一樣的。
2. 同樣如上固定一個集合，可以另外定義函子 $K_A : \mathbf{Set} \rightarrow \mathbf{Set}$ 將所有的集合都對應到集合 $A$，且任意函數 $f : X \rightarrow Y$ 到 $A$ 的單位函數 $id_A : A \rightarrow$。像這樣的函子，我們通常稱為常數函子（constant functor）。
3. 給定任意集合 $X$，將其對應到 $X \times X = \{ \langle x, y\rangle \in X \times X \}$。任意函數 $f : X \rightarrow Y$ 可以對應到 $f \times f : \langle x, y\rangle \mapsto \langle fx, fy\rangle$。一般會說這是一個對角函子（diagonal functor） $\Delta : \mathbf{Set} \rightarrow \mathbf{Set}$。

自然轉換（natural transformation）

接下來談函子之間的態射：自然轉換（natural transformation）。前面說到，函子是範疇間保持範疇結構的對應，同樣地，對於函子我們也有類似的概念，保持函子間的結構。

給定兩個函子 $F, G : C \rightarrow D$，我們說一個從 $F$ 到 $G$ 的自然轉換 $\tau : F \rightarrow$ 為一系列在 $D$ 的態射 $(\tau_c : Fc \rightarrow Gc)_{c \in Obj(C)}$ 滿足條件：對每個態射 $f : c \rightarrow d$，式子 $\tau_d \circ Ff = Gf \circ \tau_c$ 成立，或者用箭頭表示態射，用以下的交換圖（commutative diagram）代表等式成立：
$$\xymatrix{   Fc \ar[r]^{\tau_c} \ar[d]_{Ff}& Gc \ar[d]^{Gf}\\ Fd \ar[r]_{\tau_d} & Gd }$$

函子範疇（functor category）

前面說自然轉換保持函子的結構，那麼保持了什麼東西呢？函子由兩個對應所組成，一個是物件上的對應，另一個是態射上的對應，而根據定義，$\tau : Obj(C) \rightarrow Mor(D)$ 保持了物件上的對應，使得我們有 $(\tau_c Fc \rightarrow Gc)_{c \in Obj(C)}$；另外，態射上的對應，自然性的交換圖說明了 $\tau$ 將 $Ff : Fc \rightarrow Fd$ 對應到 $Gf : Gc \rightarrow Gd$。

事實上，函子與自然轉換足以構成一個範疇，給定兩個範疇 $C, D$ 定義範疇 $Fun(C, D)$ 或寫成 $[C, D]$ 稱為函子範疇(functor category)：

1. 物件組成為所有 $C$到 $D$ 的函子
2. 態射組成為所有 $Fun(C, D)$ 上的自然轉換

不難檢查，對於每個函子 $F$，我們都有一個 identity  $Fa \xrightarrow{id} Fa$，以及根據 $D$ 上的合成函數來定義 $Fun(C, D)$ 上的合成函數。

用這個函子範疇我們可以表達很多其他的範疇，例如說：

1. 對任意的範疇 $C$，定義 $C^\rightarrow := [2, C]$ 一般稱為 arrow category。$2$ 我們用來代表一個只有兩個物件$0, 1$，以及除了單位態射以外只有一個態射 $0 \rightarrow 1$。這樣的範疇由 $C$ 上的態射構成，而 $C$-態射間的 $C^\rightarrow$-態射 $f \rightarrow g$ 由以下的交換圖構成： $$\xymatrix{a \ar[r] \ar[d]_f & c \ar[d]^g \\ b \ar[r] & d}$$ 備註：用數字來代表範疇可能有點突兀，不過在公設化集合論下，對任意自然數 $n$ 是一個包含 $n$ 個元素的集合 $\{0, ..., n-1\}$ 所以集合的屬於關係跟自然數的小於是一樣的，$2$ 可以看作是一個 preordered set，可以當作是一個範疇。因此上面的符號定義雖然很容易困惑，但並不是隨意拼湊出來的。
2. （給數學背景的人）給定群 $G$ 本身，可以看作是只有一個物件範疇：每個元素 $a \in G$ 可以看作是一個態射 $\cdot \xrightarrow{a} \cdot$，而單位態射是單位元素。而所謂群作用的 G-Set，其實是從 $G$ 到 $Set$ 的函子，而函子範疇 $[G, Set]$ 代表所有群作用構成的範疇。這個範例是 topos 重要的例子之一，有機會再說。
3. 給定任意範疇 $C$ ，每個從 $C^\mathrm{op}$ 到 $\mathbf{Set}$ 稱為 presheaf ，一個經典的例子是：對任意的局部小範疇（「局部小(locally small)」代表每個 $hom(c, d)$ 都是小集合）以及給定的物件 $c$，定義函子 $hom(-, c)$ 將任意物件 $d$ 對應到 $hom(d, c)$；而任意態射 $g : d \rightarrow d'$，可以將態射 $d' \rightarrow c$ 對應到態射 $d \rightarrow c$ 也就是 $hom(d', c) \rightarrow hom(d, c)$ 如下圖： $$\xymatrix{ d \ar[r]^{g\circ f} \ar[d]_{g} & c \\ d' \ar[ru]_{f}}$$  而由 presheaf 構成的函子範疇即為 the category of presheaves $[C^{\mathrm{op}}, \mathbf{Set}]$。

注意到，我們用到所謂的 opposite category：給定任意範疇，我們都可以用原本的物件跟態射構造新的範疇 $C^\mathrm{op}$ 但是將 domain 跟 codomain 對調 $f : a \rightarrow b$ 變成 $a \leftarrow b : f^\mathrm{op}$。

Yoneda 引理

最後我們來看看第一個有關範疇的重要結果：Yoneda lemma。許多範疇的基本概念可以由這個結果推得出來，在集合上我們說兩集合一樣，若他們有同樣的元素。在範疇論下我們沒辦法直接說物件的元素，但是我們可以將態射當作是元素，則物件決定於所有到該物件的態射，而我們可以將範疇嵌入在一個性質更豐富的範疇，使得我們能夠用更多工具去研究原本關心的範疇，稍後會把這點說得更精確。

給定一個局部小範疇 $C$ ，任意的 presheaf $K : C^\mathrm{op} \rightarrow \mathbf{Set}$ 以及任意物件 $c$ 以下成立 $$Nat(hom(-, c), K) \cong Kc$$ 其中 $Nat(hom(-, c), K)$ 代表所有從 $hom(-, c)$ 到 $K$ 的自然轉換。

證明：根據 naturality，對任意態射 $f : d \rightarrow c$ 每個自然轉換 $\tau$ 都有以下的交換圖
$$\xymatrix{ hom(c, c) \ar[r]^{\tau_c} \ar[d]_{-\circ f} & Kc \ar[d]^{Kf} \\ hom(d, c) \ar[r]_{\tau_d}& Kd}$$ 考慮 $c$ 上的 identity，我們有 $\tau_d(f) = Kf \circ \tau_c(id_c)$。因此 $\tau$ 只由 $\tau_c(id_c) \in Kc$ 決定，也就是說，對任意元素 $\sigma' \in Kc$ 我們定義 $\sigma_c(id) = \sigma'$ 則可以得到自然轉換 $\sigma : hom(-, c) \rightarrow K$。

（待續）