Steve Awodey の Category Theory を読む : Chapter 10

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

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
\[ (\mathcal{P}, \{-\}, \bigcup) \text{ is a monad on } {\bf{Sets}}. \] 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

任意の 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 \mathcal{S} に対して、証明するべきことは  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 \mathcal{S} に対して
\[\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) \\
&= \text{Hom} \left( \Delta_{B_{i}} \varinjlim_{n} D_{n}, \Delta_{I} X^{C_{i}} \right) \\
&\cong \text{Hom} \left( \varinjlim_{n} D_{n}, \prod_{B_{i}} \Delta_{I} X^{C_{i}} \right) \\
&\cong \varprojlim_{n} \text{Hom} \left( D_{n}, \prod_{B_{i}} \Delta_{I} X^{C_{i}} \right) \\
&\cong \varprojlim_{n} \text{Hom} \left( \Delta_{B_{i}} D_{n}, \Delta_{I} X^{C_{i}} \right) \\
&= \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) が成り立つ。

 \square

参考書籍

Category Theory (Oxford Logic Guides)

Category Theory (Oxford Logic Guides)

圏論 原著第2版

圏論 原著第2版