標籤：

範疇論學習筆記10：函子

04-24

目錄：類型論驛站寫作計劃

前一篇：範疇論學習筆記9：群對象和自然數對象

後一篇：範疇的範疇

學習材料：Category Theory: A Gentle Introduction - Logic Matters，最近更新（2018年1月29日）的版本。這份筆記對應的是第 15 章。

範疇有兩種數據：對象和箭頭。範疇之間的函子也需要有兩個構成部分。

定義77（函子，functor）

對於範疇 mathscr{C} 和 mathscr{D} ，函子 F:mathscr{C} omathscr{D} 包括下列數據：

  1. 運算/映射 A o F_{ob}A ，其中 A 為 mathscr{C} 對象， F_{ob} A 為 mathscr{D} 對象
  2. 運算/映射 f o F_{arw} f ，其中 f:A o B 為 mathscr{C} 箭頭， F_{arw} f:F_{ob} A o F_{ob} B 為 mathscr{D} 箭頭

在實際書寫的時候，下標通常省略，在有歧義的時候，參數可以用括弧括起來。

除此以外，函子還需滿足下列兩個條件：

  1. 保存單元對象：對於任何 mathscr{C} 對象 A , F 1_A = 1_{F A}
  2. 維護複合：對於任何 mathscr{C} 箭頭 f, g ，如果存在複合 gcirc f ，那麼 F(gcirc f) = F gcirc F f

一些例子

  • F1：（遺忘函子，forgetful functor） F: sf Mon o Set ， F_{ob} (M,cdot,1_M)= M ；設 f:(M,cdot, 1_M) o (N, imes ,1_N) ，即一個幺半群同態，那麼 F_{arw} f=underline{f}:M o N 。其他遺忘函子包括 F:sf Grp o Set 等。遺忘函子有時被稱為底層函子（underlying functor）。
  • F2 ： F:sf Set o Rel ，遺忘函數性。
  • F3： F:{sf Rng o Grp}, F:sf Ab o Grp
  • F4：（冪集函子，powerset functor） P:sf Set o Set ， PX = mathscr{P}(X)
  • F5：（幺半群同態函子）取幺半群 (M,cdot,1_M) 和 (N, imes,1_N) ，構建範疇 mathscr{M,N} 。 mathscr{M} 只有一個對象 star_mathscr{M} ，它的箭頭就是 M 里的元素，其複合就是元素的二元運算 cdot ，單位元就是 1_M 。同樣地，我們可以定義範疇 mathscr{N} 。函子 F:mathscr{M o N} 需要確保：
  1. F(star_mathscr{M})=star_mathscr{N}
  2. F(1_M)=1_N
  3. F(m_1circ m_2) = Fm_1circ Fm_2 ， F 得是一個幺半群同態。
  • F6：（單調函子，monotone functor）取兩個偏序集合 (S,preccurlyeq),(T,sqsubseteq) ，將它們視為範疇 mathscr{S,T} 。單調函數 f:S o T 引出函子 F:mathscr{S o T} 。
  • F7：取群 G=(G,cdot,e) ，將其視為範疇 mathcal{G} 。可以有函子 F:mathcal{G}sf o Set
  • F8：（列表函子，list functor） List:sf Set o Set
  • F9：（瘦身函子，thinning functor）設 mathscr{S} 是一個苗條（thin）的預序範疇，即任何源和目標之間只有一個箭頭，設 mathscr{C} 是一個發福（fat）的範疇，對象和 mathscr{S} 完全一致，但源和目標之間可能有多個箭頭。我們可以構造 F:mathscr{C} o mathscr{S} ，作為一個瘦身函子。
  • F10：（常函子，constant functor）設 mathscr{C} 和 mathscr{D} 是任意函子， D 是 mathscr{D} 中的任意對象，那麼存在一個常函子，使得 forall Cin Obj(mathscr{C}).Delta_D(C)=D ， forall fin Arrow(mathscr{C}).Delta_D f=1_D .
  • F11：對於 mathscr{C} 中的每一個對象 C ，都對應著一個函子 C_F:1 o mathscr{C} ，將 1 中唯一的對象發送給 C ，又有 C_F f_1 = 1_C 。
  • F12：（包含函子，inclusion functor）設 mathscr{S} 是 mathscr{C} 的一個子範疇，那麼存在一個包含函子 F:mathscr{S o C} ，將 mathscr{S} 中的對象和箭頭映射到 mathscr{C} 中同樣的對象和範疇上。
  • F13：（自由函子，free functor） F:sf Set o Mon . F_{ob}: S o (List(S),^cap,1 ); F_{arw}:(f:S o S) o(phi:(List(S),^cap,1) o(List(S),^cap,1))

函子保存和反映的分別是什麼？

函子 F:mathscr{C} o mathscr{D} 將每一個 mathscr{C} 對象 C 映射到像（image） F(C) 上，又將每一個 mathscr{C} 箭頭 f:C o C 映射到像 F(f):FC o FC 上。 mathscr{C} 在 mathscr{D} 中的總體像究竟和其本身有多大的差距？函子究竟保存或反映了源頭範疇的哪些特徵呢？

定理76

mathscr{C} 在 mathscr{D} 中由函子 F:mathscr{C} o mathscr{D} 構成的像不一定是 mathscr{D} 的一個子範疇。

定義78（保存和反映）

設函子 F:mathscr{C} o mathscr{D} ， P 是箭頭的某個特性。那麼

  1. F 保存（preserves） P ，當且僅當對於每一個 mathscr{C} 箭頭 f ， PfRightarrow P F(f)
  2. F 反映（reflects） P ，當且僅當對於每一個 mathscr{C} 箭頭 f ， P F(f)Rightarrow P f

定義79（保守性，conservativity）

一個函子 F 是保守（conservative）的，當且僅當它反映所有同構。

定理77

函子不一定保存或反映單態或滿態。

定理78

函子保存右逆，左逆和同構。函子不一定反映它們。

例如坍塌函子（collapse functor） F:mathscr{C} o 1 ，1 中唯一的箭頭是同構，但 mathscr{C} 中的相應箭頭（所有箭頭！）則不一定是同構。

忠實、全乎、和本質滿射函子

定義80（忠實、全乎）

函子 F:mathscr{C} o mathscr{D} 是忠實（faithful）的，當且僅當對於任何 mathscr{C} 對象 C,C ，以及任何一對平行箭頭 f,g:C o C ，如果 F(f)=F(g) ，那麼 f=g 。

函子 F:mathscr{C o D} 是全乎（full）的，當且僅當對於任何 mathscr{C} 對象 C,C ，以及任何箭頭 g:FC o FC ，都存在一個箭頭 f:C o C ，使得 g=F f 。

F 是全然忠實（fully faithful）的，當且僅當它既全乎又忠實。

忠實函子對於箭頭不一定是單射。

定義81

函子 F:mathscr{C} o mathscr{D} 在對象上是本質滿射（essentially surjective on objects, e.s.o.）的，當且僅當對於任何 mathscr{D} 對象 D ，存在 mathscr{C} 對象 C ，使得 FCcong D .

普通的滿射（存在 mathscr{C} 對象 C ，使得 FC= D ）意義不大。在範疇論理哦我們一般不在乎 mathscr{D} 是否有一些不同但同餘的對象副本。對象上的單射意義也不大。

  • 遺忘函子 F:sf Mon o Set 是忠實的，在對象上本質滿射的，但不是全乎的。
  • 遺忘函子 F:sf Ab o Grp 是忠實的，全乎的，但不是在對象上本質滿射的。
  • 瘦身函子 F:mathscr{C} o mathscr{S} 是全乎的，在對象上本質滿射的，但不是忠實的，除非 mathscr{C} 是一個預序範疇。
  • 基於滿射但不單射的幺半群同構的函子 F:mathscr{M o N} 是全乎的，但不是忠實的。
  • 完全坍塌函子 Delta_0:sf Set o 1 不是全乎的，也不是忠實的。
  • 包含函子F:mathscr{S o C} 是忠實的，但除非 mathscr{S} 是 mathscr{C} 的一個滿子範疇，該函子是不完全的；該函子通常不滿足在對象上本質滿射。

定理79

忠實函子 F:mathscr{C} o mathscr{D} 反映了單態和滿態。

定理80

全然忠實函子反映了右逆和左逆，因而是保守的。

積、指數、代數拓撲和函子

  • F14：（積函子，product functor）設 mathscr{C} 擁有所有的積， C 是 mathscr{C} 的一個對象，那麼存在一個函子 imes C:mathscr{C o C} ，使得 ( imes C) A=A imes C ， imes C(A o A)=A imes C o A imes C .
  • F15：（指數函子，exponentiation functor）設 mathscr{C} 擁有所有的指數，設 B 是一個 mathscr{C} 對象，那麼存在一個對應的指數函子 ()^B:mathscr{C o C} ，使得 ()^B C= C^B ， ()^B (C o C)=overline{fcirc ev}: C^B o C^B
  • F16：代數拓撲函子 pi_1:sf Top_* o Grp

使用代數拓撲函子可以證明下面的定理：

定理81（Brouwer 不定點定理，Brouwers Fixed Point Theorem）

從閉單位圓盤（closed unit disc）到其自身的任何連續映射都有一個不動點。

同變函子和逆變函子

定理82

函子 F:mathscr{C} o mathscr{D} 引出一個函子 F^{op}:mathscr{C^{op} o D^{op}} .

定義82（逆變函子，contravariant functor）

如果 F:mathscr{C^{op} o D} 是一個原始意義上的函子（即同變函子，covariant functor），那麼 F:mathscr{C o D} 是一個逆變函子，包含下列數據：

  1. F_{ob}:C o D;F_{ob} A=F(A)
  2. F_{arw}:Arw(mathscr{C}) o Arw(mathscr{D}) ， F(f:B o A)=FA o FB

上述數據滿足下列公理：

  1. 單位元保存：對於每一個 mathscr{C} 對象 A ， F(1_A)=1_{F(A)}
  2. 尊重複合：對於任何 mathscr{C} 箭頭 f,g ，如果它們的複合 gcirc f 存在，則有 F(gcirc f)=F fcirc F g .

在 Haskell 中，我們關注的是以類型為對象，以函數為箭頭的範疇 Hask，以及 Hask 的子範疇。Haskell 中的 Functor 就是在這些範疇上定義的函子。

"Prelude:" :i Functorclass Functor (f :: * -> *) where fmap :: (a -> b) -> f a -> f b (<$) :: a -> f b -> f a {-# MINIMAL fmap #-} -- Defined in 『GHC.Base』instance Functor (Either a) -- Defined in 『Data.Either』instance Functor [] -- Defined in 『GHC.Base』instance Functor Maybe -- Defined in 『GHC.Base』instance Functor IO -- Defined in 『GHC.Base』instance Functor ((->) r) -- Defined in 『GHC.Base』instance Functor ((,) a) -- Defined in 『GHC.Base』

目錄：類型論驛站寫作計劃

前一篇：範疇論學習筆記9：群對象和自然數對象

後一篇：範疇的範疇

推薦閱讀：

※範疇論學習筆記1：基本概念
※範疇論學習筆記3：箭頭的種類
※範疇論學習筆記12：函子和極限
※範疇論學習筆記5：積和余積

TAG:範疇論 | 數學 | 函數式編程 |