範疇論學習筆記21：單子（Monad）

04-28

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

前一篇：範疇論學習筆記20：伴隨

這是「類型論驛站」中發布的最後一份對於基礎範疇論的學習筆記。

這份筆記基於 E.L. Cheng 為 Peter Johnstone 在劍橋大學的講座所做的筆記。和上一次筆記一樣，這次筆記只能當作一些重要概念的梳理，不適合用來學習。

假設我們有伴隨 $Fdashv G:mathscr{D o C}$ ，將 $GF$ 集合起來，我們有 $T=GF:mathscr{C o C}$ 。我們可以得到下列自然變換：

$eta:1_mathscr{C}Rightarrow GF=T \ eta_X:X o TX\ Gepsilon F:GFGFRightarrow GF\ mu: T^2Rightarrow T\ mu_X:T^2X o TX$

我們可以將 $eta$ 視為單位（unit），將 $mu$ 視為乘法（multiplication）。

命題1

在上述條件下，對於所有的 $X$ ，下面的範疇圖是可交換的：

1. 單位律（unit law）：

2. 結合律（associativity）：

定義1（單子，monad）

範疇 $mathscr{C}$ 上的一個單子包括一個函子 $T:mathscr{C o C}$ 和兩個自然變換：1） $eta:1Rightarrow T$ （單位）；2） $mu:T^2Rightarrow T$ （乘法）。這兩個自然變換滿足命題 1 中的單位律和結合律。

單子又稱為三子（triple）。

設 $()^*: extsf{Set} o extsf{Set}$ ； $(A)^*= A^*$ ，其中 $A^*={lists(a_1,dots,a_n)mid nge 0, a_iin A}$ 。又設 $eta_A:A o TA=A^*, eta(a)=(a)$ ，以及 $mu_A:A^{**} o A$ ， $mu_A{((a_{11},dots,a_{1n_1}),dots,(a_{k1},dots,a_{kn_k}))}=(a_{11},dots,a_{1n_1},dots, a_{k_1},dots,a_{kn_k})$ 。那麼 $(()^*,eta,mu)$ 就構成了一個在範疇 Set 上的單子：自由幺半群單子（free monoid monad）。
恆等函子（identity functor）是一個單子。
設 $(M,e,cdot)$ 為一個幺半群，那麼我們有 $M imes underline{}:sf Set o Set$ ，設定 $eta_X o M imes X$ ， $eta_X(x)=(e,x)$ ， $mu_X: M imes (M imes X) o M imes X$ ， $mu_X(m_1,(m_2,x))=(m_1m_2,x)$ 。這也構成了一個單子。

定義2（余單子，comonad）

函子 $L$ ，加上滿足單子公理的對偶公理的 $1_mathscr{D}Leftarrow^{epsilon}L ^deltaRightarrow L^2$ ，就構成了一個余單子。

單子的代數

定義3

設 $(T,eta,mu)$ 為 $mathscr{C}$ 上的一個單子。 $T$ 的一個代數包括一個 $mathscr{C}$ 對象 $A$ ，以及一個 $mathscr{C}$ 箭頭 $TAxrightarrow{ heta}A$ ，使得下面的範疇圖可交換：

代數的映射（map of algebras） $(TAxrightarrow{ heta}A) o(TBxrightarrow{varphi}B)$ 是一個使得下面的範疇圖可交換的箭頭 $Axrightarrow{f}B$ ：

$T$ 代數及其映射構成了一個範疇，我們記為 $mathscr{C}^T$ 。

$T=()^*: extsf{Set} o extsf{Set}$ ， $T$ 代數就是一個幺半群。因為一個代數是一個集合 $A$ 加上函數 $A^*xrightarrow{ heta}A$ ，使得 $(a_1,a_2,dots,a_n)mapsto a_1a_2dots a_n$ ，以及 $()mapsto e$ 。
$T=id$ ，那麼 $mathscr{C}^Tcongmathscr{C}$ 。
$T=M imes underline{}.$ $T$ 代數是有著幺半群行動（monoid action） $M imes Axrightarrow{ heta}A$ 的集合。

自由代數（free algebra）

我們定義遺忘函子 $U:mathscr{C}^T o mathscr{C}$ ，其中 $U(TAxrightarrow{ heta}A)=A$ ， $U(Axrightarrow{f}B)=f$ 。

命題3

$U$ 有一個左伴隨 $F:mathscr{C o C}^T$ 。

命題4

伴隨 $Fvdash U$ 可以誘發單子 $(T,eta,mu)$ 。

單子性（monadicity）

定義4

對於單子 $T:mathscr{C o C}$ ，我們定義一個範疇 $ext{Adj} T$ ，其對象 $mathscr{C}egin{matrix} xrightarrow[ot]{F}\ xleftarrow[G]{} end{matrix} mathscr{D}$ 誘發 $T$ ，其箭頭

可以使得 $F_2=DF_1, G_1=G_2D$ 。

我們可以證明事實上 $F^Tdashv U^T$ 是 $ext{Adj} T$ 上的一個終對象，所以對於 $Fdashv G$ ，在 $ext{Adj} GF$ 中我們有唯一的箭頭 $K$ ：

Eilenberg-Moore 比較函子

定義5

對於伴隨 $Fdashv G:mathscr{D o C}$ ，Eilenberg-Moore 比較函子（comparison functor） $K$ 是在 $ext{Adj} GF$ 中唯一的箭頭：

對於對象：

對於箭頭：

定義6（單子性）

伴隨 $Fdashv G$ 被稱為是單子的（monadic），如果 Eilenberg-Moore 比較函子是範疇的一個等價。函子 $G$ 被稱為是單子的，如果它有一個左伴隨 $F$ ，使得 $Fdashv G$ 是單子的。範疇 $mathscr{D}$ 加上一個遺忘函子 $mathscr{D}xrightarrow[U]{}mathscr{C}$ 被稱為在 $mathscr{C}$ 上的是單子的，如果函子 $U$ 是單子的。

「是單子的」也可以譯為「具有單子性」。

Grp 在 Set 上有單子性。
Vect 在 Set 上有單子性。
Cpct Haus 在 Set 上有單子性。
Top 在 Set 上沒有單子性。
Poset 在 Set 上沒有單子性。

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

前一篇：範疇論學習筆記20：伴隨