Steve Awodey の Category Theory を読む : Chapter 10

Steve Awodey の Category Theory を読むシリーズトップ

10.2 Monads and adjoints
- Example 10.5
10.3 Algebras for a monad
- Example 10.7
10.4 Comonads and coalgebras
10.5 Algebras for endofunctors
- Lemma 10.10
- Corollary 10.13
参考書籍

10.2 Monads and adjoints

Example 10.5

Exercise 6 と同様の表記を採用すると、任意の $f \colon X \to Y$ と任意の $U \in \mathcal{P}(X)$ に対して $\mathcal{P}(f)(U) = \left\{ f(x) \in Y \,\middle|\, x \in U \right\}$ と表せる。また任意の $\alpha \in \mathcal{PP}(X)$ に対して $\bigcup(\alpha) = \left\{ x \in X \,\middle|\, \exists U \in \alpha,\, x \in U \right\}$ と表せることに注意して以下を証明する。

$Lemma$
\begin{align*}
(\mathcal{P}, \{-\}, \bigcup) \text{ is a monad on } {\bf{Sets}}.
\end{align*}

$Proof.$

$\eta \colon 1 \to \mathcal{P}$ が natural であること

任意の $f \colon X \to Y$ に対して以下の diagram を考える。
f:id:hitotakuchan:20161102131405p:plain

すると、任意の $x \in X$ に対して $\left( \mathcal{P}(f) \circ \eta_{X} \right)(x) = \left\{ f(x) \right\} = \left( \eta_{Y} \circ f \right)(x)$ が成り立つ。よって diagram は可換になる。

$\mu \colon \mathcal{PP} \to \mathcal{P}$ が natural であること

任意の $f \colon X \to Y$ に対して以下の diagram を考える。
f:id:hitotakuchan:20161102132128p:plain

任意の $\alpha \in \mathcal{PP}(X)$ に対して

\begin{align*}
\left( \mathcal{P}(f) \circ \mu_{X} \right)(\alpha) &= \mathcal{P}(f) \left( \left\{ x \in X \,\middle|\, \exists U \in \alpha,\, x \in U \right\} \right) \\
&= \left\{ f(x) \in Y \,\middle|\, \exists U \in \alpha,\, x \in U \right\}
\end{align*}

が成り立つ。一方、

\begin{align*}
\left( \mu_{Y} \circ \mathcal{PP}(f) \right)(\alpha) &= \mu_{Y} \left( \left\{ \mathcal{P}(f)(U) \,\middle|\, U \in \alpha \right\} \right) \\
&= \left\{ y \in Y \,\middle|\, \exists U' \in \left\{ \mathcal{P}(f)(U) \,\middle|\, U \in \alpha \right\},\, y \in U' \right\} \\
&= \left\{ y \in Y \,\middle|\, \exists U \in \alpha,\, y \in \mathcal{P}(f)(U) \right\} \\
&= \left\{ y \in Y \,\middle|\, \exists U \in \alpha,\, y \in \left\{ f(x) \in Y \,\middle|\, x \in U \right\} \right\} \\
&= \left\{ f(x) \in Y \,\middle|\, \exists U \in \alpha,\, x \in U \right\}
\end{align*}

が成り立つ。よって diagram は可換になる。

結合則を満たすこと

任意の $X \in {\bf{Sets}}$ に対して以下の diagram が可換になることを示せばよい。
f:id:hitotakuchan:20161103072530p:plain

任意の $\beta \in \mathcal{PPP}(X)$ に対して

\begin{align*}
\left( \mu_{X} \circ \mathcal{P}\mu_{X} \right)(\beta) &= \mu_{X} \left( \left\{ \mu_{X}(\alpha) \,\middle|\, \alpha \in \beta \right\} \right) \\
&= \left\{ x \in X \,\middle|\, \exists U \in \left\{ \mu_{X}(\alpha) \,\middle|\, \alpha \in \beta \right\},\, x \in U \right\} \\
&= \left\{ x \in X \,\middle|\, \exists \alpha \in \beta,\, x \in \mu_{X}(\alpha) \right\} \\
&= \left\{ x \in X \,\middle|\, \exists \alpha \in \beta,\, U \in \alpha,\, x \in U \right\}
\end{align*}

が成り立つ。一方、

\begin{align*}
\left( \mu_{X} \circ \mu_{\mathcal{P}X} \right)(\beta) &= \mu_{X} \left( \left\{ U \in \mathcal{P}(X) \,\middle|\, \exists \alpha \in \beta,\, U \in \alpha \right\} \right) \\
&= \left\{ x \in X \,\middle|\, \exists U' \in \left\{ U \in \mathcal{P}(X) \,\middle|\, \exists \alpha \in \beta,\, U \in \alpha \right\},\, x \in U' \right\} \\
&= \left\{ x \in X \,\middle|\, \exists \alpha \in \beta,\, U \in \alpha,\, x \in U \right\}
\end{align*}

が成り立つので diagram は可換になる。

単位則を満たすこと

任意の $X \in {\bf{Sets}}$ に対して以下の diagram が可換になることを示せばよい。
f:id:hitotakuchan:20161103074643p:plain

任意の $U \in \mathcal{P}(X)$ に対して左の triangle に関して

\begin{align*}
\left( \mu_{X} \circ \eta_{\mathcal{P}X} \right)(U) &= \mu_{X} \left( \left\{ U \right\} \right) \\
&= \left\{ x \in X \,\middle|\, \exists U' \in \left\{ U \right\},\, x \in U' \right\} \\
&= U
\end{align*}

が成り立つ。次に右の triangle に関して

\begin{align*}
\left( \mu_{X} \circ \mathcal{P}\mu_{X} \right)(U) &= \mu_{X} \left( \left\{ \left\{ x \right\} \,\middle|\, x \in U \right\} \right) \\
&= \left\{ x' \in X \,\middle|\, \exists U' \in \left\{ \left\{ x \right\} \,\middle|\, x \in U \right\},\, x' \in U' \right\} \\
&= \left\{ x \in X \,\middle|\, x \in U \right\} \\
&= U
\end{align*}

が成り立つので diagram は可換になる。

$\square$

10.3 Algebras for a monad

Example 10.7

free monoid adjunction に対する monad を $(T, \eta, \mu)$ とすると、 ${\bf{Mon}} \cong {\bf{Sets}}^{T}$ が成り立つことを示します。

$Lemma$
${\bf{Mon}} \cong {\bf{Sets}}^{T}$

$Proof.$
はじめに $\Phi \colon {\bf{Mon}} \to {\bf{Sets}}^{T}$ を定義する。
任意の monoid $(M, u_{M}, \cdot_{M})$ に対して $\Phi\left( (M, u_{M}, \cdot_{M}) \right) = (M, \alpha)$ と定義する。ただし $\alpha$ は $\alpha( [ m_{1}, \dots , m_{n}] ) = m_1 \cdot_{M} \dots \cdot_{M} m_{n}$ を満たす関数とする。このとき書籍にあるように $(M, \alpha)$ は $T$ -algebra となる。
また任意の monoid homomorphism $h \colon (M, u_{M}, \cdot_{M}) \to (N, u_{N}, \cdot_{N})$ に対して以下の diagram を考える。
f:id:hitotakuchan:20161106133829p:plain

任意の $[m_{1}, \dots, m_{n}] \in TM$ に対して $(\beta \circ Th)( [m_{1}, \dots, m_{n}] ) = h(m_{1}) \cdot_{N} \dots \cdot_{N} h(m_{n})$ が成り立つ。一方、 $(h \circ \alpha)([m_{1}, \dots, m_{n}]) = h(m_{1} \cdot_{M} \dots \cdot_{M} m_{n})$ が成り立つが $h$ が monoid homomorphism であることから両者は等しい。
そこで $\Phi(h) = h \colon (M, \alpha) \to (N, \beta)$ で定義する。すると $\Phi$ が functor の条件を満たすことは明らかである。

次に $\Psi \colon {\bf{Sets}}^{T} \to {\bf{Mon}}$ を定義する。
任意の $(A, \alpha)$ に対して $u_{A} = \alpha([])$ 、 $\cdot_{A} = \alpha([-,-])$ とするとき、 $\Psi\left( (A, \alpha) \right) = (A, u_{A}, \cdot_{A})$ で定義する。このとき $(A, u_{A}, \cdot_{A})$ が monoid となることを示す。
任意の $a,b,c \in A$ に対して
$\begin{align*} a \cdot_{A} (b \cdot_{A} c) &= \alpha \left( \left[ a, \alpha( [b, c] ) \right] \right) \\ &= \alpha \left( \left[ \alpha([a]), \alpha( [ b, c ] ) \right] \right) \\ &= ( \alpha \circ T\alpha) \left( \left[ [ a ], [b, c] \right] \right) \\ &= (\alpha \circ \mu) \left( \left[ [ a ], [b, c] \right] \right) \\ &= \alpha \left( [ a, b, c ] \right) \end{align*}$

一方、

$\begin{align*} (a \cdot_{A} b) \cdot_{A} c &= \alpha \left( \left[ \alpha( [a, b]), c \right] \right) \\ &= \alpha \left( \left[ \alpha( [a, b]), \alpha([c]) \right] \right) \\ &= (\alpha \circ T\alpha) \left( \left[ [a, b], [c] \right] \right) \\ &= (\alpha \circ \mu) \left( \left[ [a, b], [c] \right] \right) \\ &= \alpha \left([a, b, c] \right) \end{align*}$

が成り立つので、 $\cdot_{A}$ は結合則を満たす。また

$\begin{align*} u_{A} \cdot_{A} a &= \alpha \left( \left[ \alpha([]), a \right] \right) \\ &= \alpha \left( \left[ \alpha([ ]), \alpha([a]) \right] \right) \\ &= (\alpha \circ T\alpha) \left( \left[ [ ], [a] \right] \right) \\ &= (\alpha \circ \mu) \left( \left[ [ ], [a] \right] \right) \\ &= \alpha ([a]) \\ &= a \end{align*}$

が成り立つ。同様に $a \cdot_{A} u_{A} = a$ が成り立つので $\cdot_{A}$ は単位則を満たす。以上より $(A, u_{A}, \cdot_{A})$ は monoid となる。
また任意の $h \colon (A, \alpha) \to (B, \beta)$ と任意の $a, b \in A$ に対して、

$\begin{align*} h(a \cdot_{A} b) &= h \left( \alpha([ a,b]) \right) \\ &= (h \circ \alpha)([a, b]) \\ &= (\beta \circ Th)([a,b]) \\ &= h(a) \cdot_{B} h(b) \end{align*}$

が成り立ち、同様に $h(u_{A}) = u_{B}$ が成り立つので、 $h$ は monoid homomorphism となる。そこで $\Psi(h) = h \colon (A, u_{A}, \cdot_{A}) \to (B, u_{B}, \cdot_{B})$ とすれば $\Psi$ は明らかに functor の条件を満たす。

最後に、 $\Psi \circ \Phi = 1_{\bf{Mon}}$ かつ $\Phi \circ \Psi = 1_{{\bf{Sets}}^{T}}$ が成り立つので ${\bf{Mon}} \cong {\bf{Sets}}^{T}$ が成り立つ。

$\square$

10.4 Comonads and coalgebras

任意のadjoint pair $F \dashv U$ に対して unit を $\eta \colon 1_{\bf{C}} \to UF$ 、counit を $\epsilon \colon FU \to 1_{\bf{D}}$ とするとき、 $(G = FU, \epsilon, \delta = F\eta_{U})$ が comonad となることを確認します。

$Lemma$
$(G, \epsilon, \delta) \text{ is a comonad}.$

$Proof.$
10.2 節と同様に証明する。

coassociativity law が成り立つこと

任意の $f \colon X \to Y \in {\bf{C}}$ に対して $\eta$ が natural であることより、以下の diagram が可換になる。
f:id:hitotakuchan:20161107125109p:plain

$Y$ を $UFX$ 、 $f$ を $\eta_{X}$ で置き換えると、以下の diagram を得る。
f:id:hitotakuchan:20161107125424p:plain

$X$ を $UD$ として、全体に $F$ を適用すると以下の diagram を得る。
f:id:hitotakuchan:20161107125820p:plain

記号を置き換えると以下の diagram が可換となる。
f:id:hitotakuchan:20161107130311p:plain

counit law が成り立つこと

次の diagram が可換になることを示せばよいが、これは triangle identities より明らかである。
f:id:hitotakuchan:20161107131043p:plain

$\square$

10.5 Algebras for endofunctors

Lemma 10.10

任意の endofunctor $P \colon \mathcal{S} \to \mathcal{S}$ に関して次の事柄が成り立つことを証明します。

$Lemma$
$i \colon P(I) \to I \text{ is an initial } P\text{-algebra} \Rightarrow i \text{ is an isomorphism}.$

$Proof.$
$i$ が initial $P$ -algebra であることより、次の diagram が可換となるような $j \colon I \to P(I)$ がただ一つ存在する。
f:id:hitotakuchan:20161108142551p:plain

そこで以下の diagram を考える。
f:id:hitotakuchan:20161108142956p:plain

明らかに diagram は可換になるので、 $i$ が initial であることより $i \circ j = 1_{I}$ が成り立つ。
そこでもう一度以下の diagram を考えると
f:id:hitotakuchan:20161108142551p:plain

$j \circ i = P(i) \circ P(j) = P(1_{I}) = 1_{P(I)}$ が成り立つ。よって $i$ は isomorphism である。

$\square$

Corollary 10.13

任意の finite polynomial functor $P \colon {\bf{Sets}} \to {\bf{Sets}}$ が $\omega$ -colimit を保存することを証明します。

$Lemma$
$P \text{ preserves } \omega \text{-colimits}.$

$Proof.$
index category $\omega$ に対しては
$\varinjlim_{n} \dashv \Delta_{n} \dashv \varprojlim_{n}$

が成り立つこと、また、任意の集合 $J$ に対しては

$\sum_{J} \dashv \Delta_{J} \dashv \prod_{J}$

が成り立つことに注意する。
polynomial functor $P$ を $P(X) = \sum_{i \in I} C_{i} \times X^{B_{i}}$ で表すと、任意の $D \colon \omega \to \bf{Sets}$ に対して、証明するべきことは $P \left( \varinjlim_{n} D_{n} \right) = \sum_{I} C_{i} \times \left( \varinjlim_{n} D_{n} \right)^{B_{i}} \cong \varinjlim_{n} \left( \sum_{I} C_{i} \times D_{n}^{B_{i}} \right) = \varinjlim_{n} P(D_{n})$ である。
任意の $X \in \bf{Sets}$ に対して
\begin{align*}
\text{Hom}\left( \sum_{I} C_{i} \times \left( \varinjlim_{n} D_{n} \right)^{B_{i}}, X \right) &\cong \text{Hom} \left( C_{i} \times \left(\varinjlim_{n} D_{n} \right)^{B_{i}}, \Delta_{I} X \right) \\
&\cong \text{Hom} \left( \left(\varinjlim_{n} D_{n} \right)^{B_{i}}, \Delta_{I} X^{C_{i}} \right) \\
&\cong \text{Hom} \left( \varinjlim_{n} D_{n}^{B_{i}}, \Delta_{I} X^{C_{i}} \right) \\
&\cong \varprojlim_{n} \text{Hom} \left( D_{n}^{B_{i}}, \Delta_{I} X^{C_{i}} \right) \\
&\cong \varprojlim_{n} \text{Hom} \left( C_{i} \times D_{n}^{B_{i}}, \Delta_{I} X \right) \\
&\cong \varprojlim_{n} \text{Hom} \left( \sum_{I} C_{i} \times D_{n}^{B_{i}}, X \right) \\
&\cong \text{Hom} \left( \varinjlim_{n} \left( \sum_{I} C_{i} \times D_{n}^{B_{i}} \right), X \right) \\
\end{align*}

が成り立つ。これらの同型射は adjoint pair の同型射であるから Chapter8 で証明した内容と合わせると $X$ に関して natural である。
よって米田の補題より $\sum_{I} C_{i} \times \left( \varinjlim_{n} D_{n} \right)^{B_{i}} \cong \varinjlim_{n} \left( \sum_{I} C_{i} \times D_{n}^{B_{i}} \right)$ が成り立つ。