diff options
| -rw-r--r-- | ch1_cats.tex | 2 | ||||
| -rw-r--r-- | ch4_trans.tex | 2 | ||||
| -rw-r--r-- | ch5_adjoints.tex | 161 | ||||
| -rw-r--r-- | ch6_monads.tex | 159 |
4 files changed, 168 insertions, 156 deletions
diff --git a/ch1_cats.tex b/ch1_cats.tex index c8a2520..f2485ae 100644 --- a/ch1_cats.tex +++ b/ch1_cats.tex @@ -613,7 +613,7 @@ correspondiente para epimorfismos. suprayectivos. \item No en todas las variedades algebraicas los epimorfismos son suprayectivos. Por ejemplo, en $\bRing$, la inclusión $u:\sInt\to\sRat$ es - suprayectiva, pues si $f,g:\sRat\to R$ cumplen que + un monomorfismo, pues si $f,g:\sRat\to R$ cumplen que $f\circ u=g\circ u:\sInt\to R$, para $x,y\in\sInt$, $f(\frac xy)=\frac{f(x)}{f(y)}=\frac{(f\circ u)(x)}{(f\circ u)(y)}$, y lo mismo ocurre con $g$, luego $f=g$. diff --git a/ch4_trans.tex b/ch4_trans.tex index 2fa08c4..c58b5bb 100644 --- a/ch4_trans.tex +++ b/ch4_trans.tex @@ -14,7 +14,7 @@ basándonos principalmente en \cite[cap. 6]{joyofcats} y \cite[I.4 y II.4--5]{maclane}. \begin{definition} - Dados dos morfismos $S,T:\cC\to\cD$, una \conc{transformación natural} + Dados dos funtores $S,T:\cC\to\cD$, una \conc{transformación natural} $\tau:S\to T$, también escrita como \[\cC\natg{\downarrow\tau}{S}{T}\cD,\] es una función $\tau:\Ob{\cC}\to\Mor{\cD}$ que a cada objeto $c$ en $\cC$ le diff --git a/ch5_adjoints.tex b/ch5_adjoints.tex index 33d8e1d..991c313 100644 --- a/ch5_adjoints.tex +++ b/ch5_adjoints.tex @@ -36,15 +36,15 @@ funtores libres y otras estructuras relacionadas, basándonos principalmente en Las flechas universales suelen representar inmersiones de objetos en un cierto objeto completado o con estructura adicional. \begin{enumerate} - \item Un objeto libre sobre un conjunto $X$ en un constructo es una flecha - universal de $X$ al constructo. + \item En el caso de constructos, esta definición de objeto libre coincide con + la vista en el capítulo 1. \item Si $U:\bField\inTo\bDom$ es el funtor inclusión de la subcategoría completa de los cuerpos en la categoría de dominios, una flecha universal de - un dominio $D$ en $U$ es el conjunto cociente $Q(D)$ junto con la inclusión. + un dominio $D$ a $U$ es el conjunto cociente $Q(D)$ junto con la inclusión. \item Consideremos la categoría $\bMGrph$ de los \conc{multigrafos}, los grafos dirigidos (no necesariamente finitos) que admiten varios ejes entre dos mismos vértices. Si $U:\bCat\to\bMGrph$ es el funtor que <<olvida>> la - composición y la identidad, un objeto libre de un multigrafo $M$ a $U$ es + composición y las identidades, un objeto libre de un multigrafo $M$ a $U$ es una categoría cuyos objetos son los vértices de $M$ y cuyos morfismos entre dos objetos son los caminos entre ellos en $M$, tomando como composición la concatenación de caminos y como identidad el camino vacío. @@ -61,7 +61,7 @@ definir la categoría en la que <<viven>> estas flechas. \begin{definition} Si $U:\cC\to\cB$ es un funtor y $b$ es un objeto de $\cB$, la \conc{categoría de objetos $U$-bajo $b$}, $(b\downarrow U)$, tiene como objetos los pares - $(c,f)$ formados por un objeto $c$ de $\cC$ y un morfismo $f:b\to Uc$; como + $(c,f)$ formados por un objeto $c$ de $\cC$ y un morfismo $f:b\to Uc$, y como morfismos $h:(c,f)\to(c',f')$ los morfismos $h:c\to c'$ en $\cC$ tales que $f'=Uh\circ f$, y como composición e identidad las correspondientes en $\cC$. \end{definition} @@ -121,15 +121,19 @@ universal de un funtor a un objeto. \section{Lema de Yoneda} El lema de Yoneda es un resultado clásico sobre transformaciones naturales que -permite relacionar las mismas con transformaciones naturales. Antes de verlo -conviene definir algunos funtores útiles. +apunta a una relación entre estas y las flechas universales. Antes de verlo es +conveniente definir algunos funtores útiles. + +En esta discusión a veces requeriremos que las categorías tengan conjuntos hom +pequeños. Aunque este suele ser el caso, en general es posible obtener el mismo +resultado sustituyendo $\bSet$ por una categoría de conjuntos más grande. \begin{definition} Si $\cC$ es una categoría con conjuntos hom pequeños, definimos el \conc{bifuntor hom} $\hom_\cC:\dual{\cC}\times\cC$ sobre objetos $(a,b)$ como $\hom_\cC(a,b)$, y sobre morfismos $(f,g):(a,b)\to(a',b')$ como - $\hom_\cC(f,g)(h)\coloneqq g\circ h\circ f$. Dados dos funtores $S:\cA\to\cC$ - y $T:\cB\to\cC$, definimos el bifuntor + $\hom_\cC(f,g)(h)\coloneqq g\circ h\circ f$. Además, dados dos funtores + $S:\cA\to\cC$ y $T:\cB\to\cC$, definimos el bifuntor $\hom_\cC(S-,T-):\dual{\cA}\times\cB\to\cC$ como $\hom_\cC\circ(S\times T)$. \end{definition} @@ -148,16 +152,18 @@ conviene definir algunos funtores útiles. $\hom(f,-)_c(g)\coloneqq g\circ f$. \end{definition} -\begin{lemma}[Yoneda]\label{lem:yoneda} - Sea $\cC$ una categoría con conjuntos hom pequeños. Para cada funtor $T:\cC\to\bSet$ - y objeto $c$ de $\cC$, la función - \[ - \gamma_{T,c}:\hom_{\bSet^\cC}(\hom_\cC(c,-),T)\to Tc - \] - dada por $\gamma_{T,c}(\tau)\coloneqq\tau_c1_c$ es una biyección natural entre - el funtor $\hom(Y-,-)$ (con el orden de las entradas cambiado) y - el funtor de evaluación $\bSet^\cC\times\cC\to\bSet$. -\end{lemma} +\begin{samepage} + \begin{lemma}[Yoneda]\label{lem:yoneda} + Sea $\cC$ una categoría con conjuntos hom pequeños. Para cada funtor + $T:\cC\to\bSet$ y objeto $c$ de $\cC$, la función + \[ + \gamma_{T,c}:\hom_{\bSet^\cC}(\hom_\cC(c,-),T)\to Tc + \] + dada por $\gamma_{T,c}(\tau)\coloneqq\tau_c1_c$ es una biyección natural + entre el funtor $\hom(Y-,-)$ (con el orden de las entradas cambiado) y el + funtor de evaluación $\bSet^\cC\times\cC\to\bSet$. + \end{lemma} +\end{samepage} \begin{proof} \begin{figure} \hfil @@ -234,10 +240,10 @@ flechas universales. La definición de flecha universal equivale a esta biyección, que es natural ya que, para cada morfismo $g:x\to y$ en $\cC$ y $f:c\to x$, $\hom(b,Ug)(\tau_x(f))=Ug\circ Uf\circ u=U(g\circ f)\circ - u=U(\hom(c,g)(f))=\tau_y(\hom(c,g)(f))$. + u=U(\hom(c,g)(f))\circ u=\tau_y(\hom(c,g)(f))$. - Para el recíproco, si $\tau:\hom_\cC(c,-)\to\hom_\cB(b,U-)$ es un isomorfismo - natural, por el lema de Yoneda y la biyectividad de $\tau_x$ se tiene que todo + Para la segunda parte, si $\tau:\hom_\cC(c,-)\to\hom_\cB(b,U-)$ es un + isomorfismo natural, por el lema de Yoneda y la biyectividad de $\tau_x$, todo morfismo $b\to Ux$ se expresa de forma única como $\tau_xf=\hom(b,Uf)(\tau_c1_c)=Uf\circ\tau_c1_c$ para cierto $f:c\to x$, lo que significa precisamente que $\tau_c1_c$ es universal de $b$ a $U$. @@ -245,32 +251,35 @@ flechas universales. \section{Adjunciones} -Sea $U:\cC\to\cB$ un funtor tal que todo objeto $b$ en $\cB$ admite una flecha -universal $(Fb,u_b)$ de $b$ a $U$. Para cada morfismo $f:b\to b'$ en $\cB$, -siguiendo la figura \ref{fig:universal} existe un único morfismo $Ff:Fb\to Fb'$ -en $\cC$ tal que $UFf\circ u_b=u_{b'}\circ f$, y además claramente $F1_b=1_{Cb}$ -y $Fg\circ Ff=F(g\circ f)$, de modo que $F:\cB\to\cC$ es un funtor y -$u:1_\cB\to U\circ F$ es una transformación natural. +Sea $U:\cC\to\cB$ un funtor entre categorías con conjuntos hom pequeños y tal +que todo objeto $b$ en $\cB$ admite una flecha universal $(Fb,u_b)$ de $b$ a +$U$. Para cada morfismo $f:b\to b'$ en $\cB$, siguiendo la figura +\ref{fig:universal} existe un único morfismo $Ff:Fb\to Fb'$ en $\cC$ tal que +$UFf\circ u_b=u_{b'}\circ f$, y además claramente $F1_b=1_{Cb}$ y +$Fg\circ Ff=F(g\circ f)$, de modo que $F:\cB\to\cC$ así construido es un funtor +y $u:1_\cB\to U\circ F$ es una transformación natural. El que la imagen de $u$ esté formada por flechas universales permite obtener una -especie de inversa. Dados un objeto $b$ en $\cB$ y un objeto $c$ en $\cC$, para -cada morfismo $f:b\to Uc$ existe un único $\hat f:Fb\to c$ tal que -$f=U\hat f\circ u_b$, de modo que $\psi_{b,c}:\hom_\cC(Fb,c)\to\hom_\cB(b,Uc)$ -dada por $\psi_{b,c}(g)\coloneqq Ug\circ u_b$ es una biyección, y como $U$ es un -funtor y $u$ es natural, $\psi$ es un isomorfismo natural entre los funtores -$\hom_\cC\circ(F\times 1),\hom_\cB\circ(1\times U):\dual{\cB}\times\cC\to\bSet$ -(si los conjuntos hom no son siempre pequeños, basta sustituir $\bSet$ por una -clase de conjuntos más grande). Entonces $u_b\equiv\psi_{b,Fb}(1)$ y, del mismo +especie de transformación inversa. Dados un objeto $b$ en $\cB$ y un objeto $c$ +en $\cC$, para cada morfismo $f:b\to Uc$ existe un único $\hat f:Fb\to c$ tal +que $f=U\hat f\circ u_b$, de modo que +$\psi_{b,c}:\hom_\cC(Fb,c)\to\hom_\cB(b,Uc)$ dada por +$\psi_{b,c}(g)\coloneqq Ug\circ u_b$ es una biyección, y como $U$ es un funtor y +$u$ es natural, $\psi$ es un isomorfismo natural entre los funtores +$\hom_\cC\circ(F\times 1),\hom_\cB\circ(1\times +U):\dual{\cB}\times\cC\to\bSet$. Entonces $u_b\equiv\psi_{b,Fb}(1)$ y, del mismo modo, podemos definir la transformación natural $e:F\circ U\to 1_\cC$ como $e_c\coloneqq\psi_{Uc,c}^{-1}(1)$, de modo que para cada objeto $c$, $(Uc,e_c)$ es una flecha universal de $F$ a $c$. La relación entre las transformaciones naturales $u$ y $e$ es más estrecha que -esto. Para un objeto $c$, $1_{Uc}=\psi(e_c)=Ue_c\circ u_{Uc}$, y de forma dual, -para un objeto $b$, -$\psi(e_{Fb}\circ Fu_b)=Ue_{Fb}\circ Ue_{Fb}\circ UFu_b\circ u_b=Ue_{Fb}\circ -u_{UFb}\circ u_b=1_{UFb}\circ u_b=u_b$ y por tanto -$1_{Fb}=\psi^{-1}(u_b)=e_{Fb}\circ Fu_b$. +esto. Para un objeto $c$ en $\cC$, $1_{Uc}=\psi(e_c)=Ue_c\circ u_{Uc}$, y para +un objeto $b$ en $\cB$, +\[ + \psi(e_{Fb}\circ Fu_b) = Ue_{Fb}\circ UFu_b\circ u_b + = Ue_{Fb}\circ u_{UFb}\circ u_b = 1_{UFb}\circ u_b = u_b, +\] +y por tanto $1_{Fb} = \psi^{-1}(u_b) = e_{Fb}\circ Fu_b$. Estas dos identidades se pueden expresar más elegantemente con la notación adecuada. Si $\tau:R\to S$ es una transformación natural entre dos funtores @@ -278,10 +287,10 @@ $R,S:\cB\to\cC$ y $T:\cC\to\cD$ es otro funtor, podemos definir la transformación natural $T\tau:T\circ R\to T\circ S$ como $(T\tau)_b\coloneqq T(\tau_b)$ para cada objeto $b$ en $\cB$. Por otro lado, si $U:\cA\to\cB$ es otro funtor, podemos definir la transformación natural -$\tau U:R\circ U\to G\circ U$ como $(\tau U)_a\coloneqq\tau_{Ka}$ para cada +$\tau U:R\circ U\to G\circ U$ como $(\tau U)_a\coloneqq\tau_{Ua}$ para cada objeto $a$ en $\cA$. -Con todo esto en mente, definimos las adjunciones como sigue. +Con esto, podemos caracterizar la situación anterior como sigue. \begin{definition} Una \conc{adjunción} entre dos categorías $\cB$ y $\cC$ es una tupla @@ -349,16 +358,16 @@ teorema. \end{diagram} \hfil - Con esto $1_{Gc}=\psi(\eps_c)=G\eps_c\circ\eta_{Gc}$, y la otra identidad es - dual a esta y se demuestra de forma análoga. + Esto permite probar las dos identidades en la definición de adjunción como en + el texto al principio de la sección. Para (\ref{enu:adj-univ}), $(Fb,\eta_b)$ es una flecha universal, pues para cada objeto $x$ en $\cC$, $\psi_{b,x}(g)=Gg\circ\eta_b$ es una biyección $\hom(Fb,x)\to\hom(b,Ux)$ natural respecto a $x$ (\ref{prop:yoneda-prop}). Recíprocamente, si sólo tenemos $G$ y las flechas universales $(c_b,\eta_b)$, $F$ definido de esta forma es un funtor que hace a - $\eta$ natural y $\psi_{b,c}$ definido de esta forma es un isomorfismo por - (\ref{prop:yoneda-prop}) y es claramente natural. + $\eta$ natural, y $\psi_{b,c}$ es un isomorfismo por (\ref{prop:yoneda-prop}) + y es claramente natural. Finalmente, (\ref{enu:adj-couniv}) es dual a (\ref{enu:adj-univ}). \end{proof} @@ -366,21 +375,20 @@ teorema. \begin{example} Este teorema permite definir una gran variedad de adjunciones. \begin{enumerate} - \item El caso más sencillo de adjunción se da cuando todos los conjuntos - admiten un objeto libre en un cierto constructo $\cC$. Entonces tenemos una - adjunción $(F,U,\eta,\eps)$, donde $U:\cC\to\bSet$ es el funtor olvidadizo, - $F:\bSet\to\cC$ es el funtor libre, $\eta_X:X\inTo UFX$ es la inclusión de - la base en el conjunto subyacente del objeto y $\eps_c:FUc\epicTo c$ es el - epimorfismo que aparece al describir un objeto como cociente de un cierto - objeto libre, que resulta ser el que tiene los propios elementos de $c$ como - generadores. Por ejemplo, en el caso de $R\dash\bMod$, $\eps_M$ lleva sumas - formales $\sum_{i=1}^ka_im_i$, con cada $a_i\in R$ y cada $m_i\in M$, a su - evaluación en el módulo $M$. + \item Si $\cC$ es un constructo en el que todos los conjuntos admiten un + objeto libre, tenemos una adjunción $(F,U,\eta,\eps)$, donde $U:\cC\to\bSet$ + es el funtor olvidadizo, $F:\bSet\to\cC$ es el funtor libre, + $\eta_X:X\inTo UFX$ es la inclusión de la base en el conjunto subyacente del + objeto y $\eps_c:FUc\epicTo c$ es el epimorfismo que aparece al describir un + objeto como cociente de un cierto objeto libre, en concreto del que tiene + los propios elementos de $c$ como generadores. Por ejemplo, en el caso de + $R\dash\bMod$, $\eps_M$ lleva sumas formales $\sum_{i=1}^ka_im_i$, con cada + $a_i\in R$ y cada $m_i\in M$, a su evaluación en el módulo $M$. \item Entre $\bDom$ y $\bField$ hay una adjunción $(Q,U,\eta,\eps)$ formada por la creación de cuerpos de fracciones $Q:\bDom\to\bField$, la inclusión - de categorías $U:\bField\inTo\bDom$, la inclusión canónica $\eta_D:D\to UQX$ - y la identidad $\eps_K:QUK\to K$ (recordemos que el cuerpo de fracciones de - un cuerpo es el propio cuerpo). + $U:\bField\inTo\bDom$ de una subcategoría, la inclusión canónica + $\eta_D:D\to UQD$ y la identidad $\eps_K:QUK\to K$ (recordemos que el cuerpo + de fracciones de un cuerpo es el propio cuerpo). \item Si $\cC$ es una categoría que tiene colímites con diagrama $\cS$, entre $\cC^\cS$ y $\cC$ hay una adjunción $(\underrightarrow{\lim},\Delta,\eta,\eps)$, donde $\underrightarrow{\lim}$ @@ -392,9 +400,9 @@ teorema. copias de $c$>>. \item Análogamente, si $\cC$ tiene límites con diagrama $\cS$, tenemos una adjunción $(\Delta,\underleftarrow{\lim},\eta,\eps)$ donde - $\underleftarrow{\lim}$ lleva cada diagrama a su límite, $\eta_c$ es el - límite de $\Delta c$ (una potencia de $c$) y $\eps_D$ es el límite como - fuente. + $\underleftarrow{\lim}$ lleva cada diagrama a su límite, $\eps_D$ es el + límite como fuente y $\eta_c$ tiene un codominio de la forma $c^I$ para + cierto conjunto $I$ y actúa como <<morfismo diagonal>>. \end{enumerate} \end{example} @@ -414,7 +422,7 @@ teorema. en $X$ y $\eps_T:DUT\to T$ es la identidad hacia $T$ desde el mismo conjunto pero con la topología discreta. \item Por la derecha tiene el funtor $N:\bSet\to\bTop$ que asocia a cada - conjunto su topología discreta. Aquí $\eps_X:UNX\to X$ es la identidad en + conjunto su topología indiscreta. Aquí $\eps_X:UNX\to X$ es la identidad en $X$ y $\eta_T:T\to NUT$ es la identidad desde $T$ hacia el mismo conjunto pero con la topología indiscreta. \end{enumerate} @@ -452,19 +460,20 @@ teorema. \begin{proposition}\label{prop:adj-transform} Dadas dos adjunciones $(F,G,\eta,\eps)$ de $\cB$ a $\cC$ y - $(F',G',\eta',\eps')$ de $\cB'$ a $\cC'$ y dos funtores $B:\cB\to\cB'$ y - $C:\cC\to\cC'$ con $C\circ F=F'\circ B$ y $B\circ G=G'\circ C$, son + $(F',G',\eta',\eps')$ de $\cB'$ a $\cC'$, y dados dos funtores $B:\cB\to\cB'$ + y $C:\cC\to\cC'$ con $C\circ F=F'\circ B$ y $B\circ G=G'\circ C$, son equivalentes: \begin{enumerate} \item \label{enu:adjtr-true} $(B,C)$ es una transformación de la primera adjunción a la segunda. \item \label{enu:adjtr-eta} $B\eta=\eta'B$. \item \label{enu:adjtr-eps} $\eps'C=C\eps$. - \item \label{enu:adjtr-psi} Si $\psi:\hom(F-,-)\to\hom(-,G-)$ es la - transformación natural asociada a la primera adjunción por el teorema - \ref{thm:adjoint-elems} y $\psi':\hom(F'-,-)\to\hom(-,G'-)$ la + \item \label{enu:adjtr-psi} Si $\psi:\hom(F-,-)\to\hom(-,G-)$ es el + isomorfismo natural asociado a la primera adjunción por el teorema + \ref{thm:adjoint-elems} y $\psi':\hom(F'-,-)\to\hom(-,G'-)$ es el correspondiente a la segunda adjunción, para cada objeto $b$ de $\cB$ y $c$ - de $\cC$, $B|_{hom(b,Gc)}\circ\psi_{b,c}=\psi'_{Bb,Cc}\circ C|_{\hom(Fb,c)}$. + de $\cC$, + $B|_{hom(b,Gc)}\circ\psi_{b,c}=\psi'_{Bb,Cc}\circ C|_{\hom(Fb,c)}$. \end{enumerate} \end{proposition} \begin{proof} @@ -479,19 +488,19 @@ teorema. lo que nos da (\ref{enu:adjtr-psi}). Análogamente (\ref{enu:adjtr-eps})$\implies$(\ref{enu:adjtr-psi}). Para el recíproco, usando las fórmulas de $\eta$ y $\eta'$ en función de $\psi$ y $\psi'$ y - aplicando la fórmula en (\ref{enu:adjtr-psi}) a $1_{Fb}$, + aplicando (\ref{enu:adjtr-psi}) a $1_{Fb}$, \[ B\eta_b = B(\psi(1_{Fb})) = \psi'(C1_{Fb}) = \psi'(1_{CFb}) = \psi'(1_{F'Bb}) = \eta'_{Bb}, \] - con lo que se tiene (\ref{enu:adjtr-eta}) y, análogamente, - (\ref{enu:adjtr-eps}), y estas condiciones equivalen a - (\ref{enu:adjtr-true}). + con lo que (\ref{enu:adjtr-psi})$\implies$(\ref{enu:adjtr-eta}) y, + análogamente, (\ref{enu:adjtr-psi})$\implies$(\ref{enu:adjtr-eps}), y estas + condiciones equivalen a (\ref{enu:adjtr-true}). \end{proof} Esto nos da una categoría cuyos objetos son adjunciones entre categorías de un -cierto conjunto universal y cuyos morfismos son transformaciones de mónadas, que -se componen de la forma evidente. +cierto conjunto universal y cuyos morfismos son transformaciones de adjunciones, +que se componen de la forma evidente. %%% Local Variables: %%% mode: latex diff --git a/ch6_monads.tex b/ch6_monads.tex index da07c48..b07996c 100644 --- a/ch6_monads.tex +++ b/ch6_monads.tex @@ -5,21 +5,22 @@ se puede estudiar, por ejemplo, la relación de un objeto o morfismo con su imagen, o lo que ocurre al aplicar el endofuntor varias veces. Por ejemplo, tomemos el endofuntor $\power:\bSet\to\bSet$. Dado un conjunto $X$, -entre $X$ y $\power X$ podemos tomar una inyección $\eta_X:X\to\power X$ dada -por $\eta_X(x)\coloneqq\{x\}$, que es natural. Por otro lado, aunque podemos -aplicar este funtor a $X$ varias veces, siempre podemos volver de $\power^nX$ a +entre $X$ y $\power X$ existe un monomorfismo $\eta_X:X\to\power X$ dado por +$\eta_X(x)\coloneqq\{x\}$, que es natural. Por otro lado, aunque podemos aplicar +este funtor a $X$ varias veces, siempre podemos volver de $\power^nX$ a $\power X$ aplicando sucesivamente la unión, que podemos ver como una función $\mu_X:\power\power X\to\power X$ dada por $\mu_X(\cA)\coloneqq\bigcup\cA$. Esto -también define una transformación natural, que, además, <<da igual>> en qué -orden se aplique, en el sentido de que, si $S\in\power^3X$, aplicar primero +también define una transformación natural que, además, <<da igual>> en qué orden +se aplique, en el sentido de que, si $S\in\power^3X$, aplicar primero $\mu_{\power X}$ a $S$ y luego $\mu_X$ al resultado es lo mismo que aplicar $\mu_X$ a cada elemento de $S$ y a continuación aplicar $\mu_X$ al resultado. Además, intuitivamente $\mu$ se puede ver como una inversa por un lado de $\eta$, en tanto que $\mu_X(\eta_{\power X}(S))\equiv S$. -Muchos endofuntores relevantes admiten transformaciones naturales con -propiedades similares, y para estudiar estos casos existe el concepto de mónada. -Este capítulo se basa principalmente en \cite[VI]{maclane}. +Muchos endofuntores comunes admiten transformaciones naturales con estas +propiedades, y cuando esto ocurre hablamos de mónadas. En este capítulo +estudiamos las mónadas y sus principales propiedades, basándonos principalmente +en \cite[VI]{maclane}. \begin{definition} Una \conc{mónada} en una categoría $\cC$ es una tupla $(T,\eta,\mu)$ @@ -32,11 +33,11 @@ Este capítulo se basa principalmente en \cite[VI]{maclane}. \end{enumerate} \end{definition} -\begin{proposition} - Si $(T,\eta,\mu)$ es una mónada en $\cC$ y $c$ es un objeto de $\cC$, - $\eta_c:c\monicTo Tc$ es una sección y $\mu_c:TTc\epicTo Tc$ es una - retracción. -\end{proposition} +% \begin{proposition} +% Si $(T,\eta,\mu)$ es una mónada en $\cC$ y $c$ es un objeto de $\cC$, +% $\eta_c:c\monicTo Tc$ es una sección y $\mu_c:TTc\epicTo Tc$ es una +% retracción. +% \end{proposition} \begin{figure} \centering @@ -57,7 +58,7 @@ Este capítulo se basa principalmente en \cite[VI]{maclane}. \centering \begin{diagram} \path (0,2) node(IT){$1\circ T$} (2,2) node(TT){$T^2$} (4,2) node(TI){$T\circ 1$}; - \path (2,0) node(T){$T$}; + \path (2,0) node(T){$T$} node[below]{$\phantom{\mu}$}; \draw[->] (IT) -- node[above]{$\eta T$} (TT); \draw[->] (TI) -- node[above]{$T\eta$} (TT); \draw[->] (TT) -- node[right]{$\mu$} (T); @@ -72,8 +73,8 @@ Este capítulo se basa principalmente en \cite[VI]{maclane}. \begin{example}\; \begin{enumerate} - \item $\power:\bSet\to\bSet$ es una mónada con las operaciones indicadas en la - introducción del capítulo. + \item $\power:\bSet\to\bSet$ es una mónada, descrita en la introducción del + capítulo. \item Toda categoría admite una \conc{mónada identidad}, formada por el endofuntor identidad y dos transformaciones naturales identidad. \item Sea $(^*):\bSet\to\bSet$ el endofuntor que asocia a cada objeto $X$ el @@ -86,13 +87,14 @@ Este capítulo se basa principalmente en \cite[VI]{maclane}. \item \label{enu:monad-variety} Esto se puede generalizar a todas las variedades algebraicas. El álgebra libre sobre un conjunto $X$ es un conjunto cociente de árboles formados por operadores y elementos de $X$ - (\ref{prop:free-algebra}), y las funciones entre conjuntos se pueden llevar - a morfismos de álgebras libres operando sobre los elementos del dominio en - el árbol. Entonces el equivalente a la lista de un elemento sería (la clase - de equivalencia de) un árbol cuya raíz es dicho elemento, y el equivalente a - concatenar listas es sustituir cada elemento base del árbol, que es a su vez - una clase de equivalencia de árboles, por un representante de esta clase a - modo de subárbol. Claramente estas transformaciones son naturales y forman + (\ref{prop:free-algebra}), o de expresiones formales que involucran a dichos + operadores y elementos, y las funciones entre conjuntos se pueden llevar a + morfismos de álgebras libres que operan elemento a elemento sobre las + expresiones. Entonces la unidad $\eta_X$ llevaría cada elemento de $X$ a + (la clase de equivalencia de) la expresión formada sólo por dicho elemento, + y la unión $\mu_X$ tomaría árboles cuyas hojas son (clases de equivalencia + de) otros árboles y sustituiría las hojas por los subárboles que + representan. Es fácil ver que estas transformaciones son naturales y forman una mónada. \item Sean $\cC$ una categoría con coproductos finitos y $d$ un objeto de $\cC$. Sea $E:\cC\to\cC$ un endofuntor que a cada objeto $c$ le asocia @@ -150,11 +152,11 @@ un funtor libre. \end{proposition} \begin{proof} Al componer horizontalmente $\eps$ consigo mismo (\ref{def:comp-horiz}) - obtenemos que $\eps\circ\eps=\eps\cdot\eps FG=\eps\cdot FG\eps$, y añadiendo - $G$ al principio y $F$ al final obtenemos - $G\eps F\cdot G\eps FGF=G\eps F\cdot GFG\eps F$, que es la primera ley de las - mónadas. Para la segunda, basta añadir $F$ al final en la identidad - $G\eps\cdot\eta G=1$ y $G$ al principio en $\eps F\cdot F\eta=1$. + obtenemos que $\eps\circ\eps=\eps\cdot\eps FG=\eps\cdot FG\eps$, y componiendo + con $G$ por la izquierda y con $F$ por la derecha obtenemos + $G\eps F\cdot G\eps FGF=G\eps F\cdot GFG\eps F$, que es la primera condición + de coherencia. Para la segunda basta componer con $F$ por la derecha en la + identidad $G\eps\cdot\eta G=1$ y con $G$ por la izquierda en $\eps F\cdot F\eta=1$. \end{proof} \begin{definition} @@ -162,7 +164,7 @@ un funtor libre. categoría $\Mnd{\cC}$ cuyos objetos son las mónadas sobre $\cC$ y cuyos morfismos $(S,\eta,\mu)\to(T,\eta',\mu')$ son las transformaciones naturales $\tau:S\to T$ tales que los diagramas en la figura \ref{fig:monad-morph} - conmutan, con la composición vertical y la identidad evidente. + conmutan, con la composición vertical y las identidades evidentes. \begin{figure} \centering \begin{subfigure}{.45\linewidth} @@ -200,9 +202,9 @@ las comónadas es más limitada. \section{Categorías de Eilenberg-Moore} Hemos visto que toda adjunción genera una mónada, por lo que cabe preguntarse si -toda mónada es generada de esta manera por una adjunción. La respuesta es qué +toda mónada es generada de esta manera por una adjunción. La respuesta es que sí, y de hecho en general cada mónada se puede describir mediante dos -adjunciones distintas asociadas a dos categorías distintas, la categoría de +adjunciones asociadas a dos categorías distintas, la categoría de Eilenberg-Moore y la categoría de Kleisli. Empezamos viendo la primera, que generaliza el concepto de variedad algebraica. @@ -210,7 +212,7 @@ generaliza el concepto de variedad algebraica. Sea $T=(T,\eta,\mu)$ una mónada en una categoría $\cC$. \begin{enumerate} \item Una \conc{$T$-álgebra} es un morfismo $e:Tc\epicTo c$ para cierto objeto - $c$ en $\cC$ tales que los diagramas en la figura \ref{fig:T-algebra} + $c$ en $\cC$ tal que los diagramas en la figura \ref{fig:T-algebra} conmutan. Llamamos \conc{mapa de estructura} de la $T$-álgebra a $e$ y \conc{objeto subyacente} a $c$. \begin{figure} @@ -247,7 +249,7 @@ generaliza el concepto de variedad algebraica. \item La \conc{categoría de Eilenberg-Moore} asociada a $T$, escrita $\cC^{(T,\eta,\mu)}$ o simplemente $\cC^T$, es la que tiene como objetos las $T$-álgebras y como morfismos los morfismos de $T$-álgebras, con la - composición y la identidad de $\cC$. + composición y las identidades de $\cC$. \end{enumerate} \end{definition} @@ -263,13 +265,14 @@ generaliza el concepto de variedad algebraica. Para cada objeto $c$ en $\cC$, $1_{Tc}$ es la identidad de la $T$-álgebra $\mu_c$, y para cada morfismo $f:c\to c'$, $Tf:\mu_c\to\mu_{c'}$ es un morfismo de $T$-álgebras por la naturalidad de $\mu$, luego $F$ es un - funtor. Por otro lado, $G$ claramente es un funtor y - $e=\eps_e:\mu_{\cod e}\to e$ es una transformación natural. Además, dada una - $T$-álgebra $e:Tc\to c$, $G\eps_e\circ\eta_{Ge}=e\circ\eta_c=1$, y dado un - objeto $c$ de $\cC$, $\eps_{Fc}\circ F\eta_c=\mu_c\circ T\eta_c=1$, luego - $(F,G,\eta,\eps)$ es una adjunción. Finalmente, es obvio que $G\circ F=T$ - siguiendo su actuación sobre morfismos, y para un objeto $c$, - $G\eps_{Fc}=G\eps_{\eta_c}=\eta_c$ y por tanto $G\eps F=\eta$. + funtor. Por otro lado, $G$ claramente es un funtor y $\eps$, que viene dado + por $\eps_e\coloneqq e:\mu_c\to e$ para cada $e:Tc\to c$, es una + transformación natural. Además, dada una $T$-álgebra $e:Tc\to c$, + $G\eps_e\circ\eta_{Ge}=e\circ\eta_c=1$, y dado un objeto $c$ de $\cC$, + $\eps_{Fc}\circ F\eta_c=\mu_c\circ T\eta_c=1$, luego $(F,G,\eta,\eps)$ es una + adjunción. Finalmente, es obvio que $G\circ F=T$ siguiendo su actuación sobre + morfismos, y para un objeto $c$, $G\eps_{Fc}=G\eps_{\eta_c}=\eta_c$ y por + tanto $G\eps F=\eta$. \end{proof} La adjunción definida en este teorema es final en el sentido siguiente. @@ -282,30 +285,29 @@ La adjunción definida en este teorema es final en el sentido siguiente. $(F,G,\eta,\eps)$ a $(F',G',\eta,\eps')$. \end{theorem} \begin{proof} - Ya tenemos $1\eta=\eta1$, y debemos ver que $G=G'\circ K$ y $F'=K\circ F$. - Sea $(T,\eta,\mu)=(GF,\eta,G\eps F)$ la mónada. Para cada objeto $d$ de $\cD$, - $G\eps_d:GFGd\to Gd$ se puede ver como una $T$-álgebra en el objeto $Gd$, pues - la propiedad asociativa $G\eps_d\circ GFG\eps_d=\eps_d\circ G\eps_{FGd}$ es - por la identidad en la composición horizontal y la unitaria - $G\eps_d\circ\eta_{Gd}=1$ es una identidad de las adjunciones. Podemos - entonces definir $K$ sobre objetos como $Kd=G\eps_d$ y sobre morfismos como - $Kf=Gf$, $Kf$ es un morfismo de $T$-álgebras por la naturalidad de - $\eps$. Para cada objeto $c$ de $\cC$, $KFc=G\eps_{Fc}=\mu_c=F'c$, y para cada - morfismo $f$, $KFf=GFf=Tf=F'c$. Del mismo modo, para cada objeto $d$ de $\cD$, + Ya tenemos $1\eta=\eta1$, y queda ver las condiciones $G=G'\circ K$ y + $F'=K\circ F$. Sea $(T,\eta,\mu)=(GF,\eta,G\eps F)$ la mónada, para cada + objeto $d$ de $\cD$, podemos ver $G\eps_d:GFGd\to Gd$ como una $T$-álgebra en + el objeto $Gd$, pues la propiedad asociativa + $G\eps_d\circ GFG\eps_d=\eps_d\circ G\eps_{FGd}$ se deduce de la identidad en + la composición horizontal y la unitaria $G\eps_d\circ\eta_{Gd}=1$ es una + identidad de las adjunciones. Podemos entonces definir $K$ sobre objetos como + $Kd=G\eps_d$, y sobre morfismos como $Kf=Gf$, pues la naturalidad de $\eps$ + asegura que $Gf$ es un morfismo de $T$-álgebras. Para cada objeto $c$ de + $\cC$, $KFc=G\eps_{Fc}=\mu_c=F'c$, y para cada morfismo $f$, + $KFf=GFf=Tf=F'c$. Del mismo modo, para cada objeto $d$ de $\cD$, $G'Kd=G'G\eps_d=Gd$, y para cada morfismo $f$, $G'Kf=G'Gf=Gf$. - Queda ver que $K$ es única. Si $d$ es un objeto de $\cD$, $Kd$ es una - $T$-álgebra y $G'Kd=Gd$ implica que el objeto subyacente a $Kd$ es $Gd$, y si - $f$ es un morfismo, $G'Kf=Gf$ implica que $Kf=Gf$. Ahora bien, las dos - adjunciones consideradas tienen el mismo $\eta$, con lo que la caracterización + Queda ver que $K$ es único. Si $d$ es un objeto de $\cD$, $Kd$ debe ser una + $T$-álgebra con objeto subyacente $Gd$, pues $G'Kd=Gd$. Por otro lado, si $f$ + es un morfismo, $G'Kf=Gf$ implica que $Kf=Gf$. Ahora bien, la caracterización de las transformaciones de adjunciones (\ref{prop:adj-transform}) aplicada a - estas dos adjunciones y a los funtores $1:\cC\to\cC$ y $K:\cD\to\cC^T$ nos da - $K\eps=\eps'K$, y entonces, para un objeto $d$, el mapa de estructura de $Kd$ - es $Kd=\eps'_{Kd}=K\eps_d=G\eps_d$. + $(1_\cC,K)$ nos da $K\eps=\eps'K$, y entonces, para un objeto $d$, el mapa de + estructura de $Kd$ es $Kd=\eps'_{Kd}=K\eps_d=G\eps_d$. \end{proof} -El que estas categorías son una generalización de las variedades algebraicas -viene dado +La siguiente proposición muestra que, de hecho, estas categorías son una +generalización del concepto de variedad algebraica. \begin{proposition} Sean $(\Omega,E)\dash\bAlg$ una variedad algebraica y $T$ la mónada generada @@ -314,16 +316,17 @@ viene dado anterior es un isomorfismo de categorías. \end{proposition} \begin{proof} - Sean $s_1,\dots,s_k$ las operaciones en $\Omega$, con aridades respectivas - $n_1,\dots,n_k$, y sea $(F,U,\eta,\eps)$ la adjunción mencionada, de modo que - $T=(UF,\eta,G\eps F)$, queremos definir un isomorfismo - $K:(\Omega,E)\dash\bAlg\to\cC^T$ en las condiciones del teorema anterior. + Sean $s_1,\dots,s_k$ las operaciones en $\Omega$ y $n_1,\dots,n_k$ sus + aridades respectivas, y sea $(F,U,\eta,\eps)$ la adjunción mencionada, de modo + que $T=(UF,\eta,U\eps F)$. Si $(S,(\nu_1,\dots,\nu_k))$ es una $(\Omega,E)$-álgebra, con cada $\mu_i:S^{n_i}\to S$, los elementos de $UFS$ son las (clases de equivalencia - de) expresiones formales con operadores $s_1,\dots,s_k$ y elementos de $c$, - por lo que podemos definir $K(S,(\nu_i)_i)$ como la <<función de evaluación>> - $UFS\to S$ por los operadores $\nu_1,\dots,\nu_k$. + de) expresiones formales construidas a partir de los operadores + $s_1,\dots,s_k$ y los elementos de $c$, por lo que podemos definir + $K(S,(\nu_i)_i)$ como la <<función de evaluación>> $e:UFS\to S$ que lleva cada + elemento de $c$ a sí mismo y cada expresión $s_i(x_1,\dots,x_{n_i})$ a + $\nu_i(e(x_1),\dots,e(x_{n_i}))$. En este contexto, la propiedad asociativa de las $T$-álgebras nos dice que, dada una expresión formal sobre expresiones formales sobre elementos de $S$, @@ -337,7 +340,7 @@ viene dado $s_i(x_1,\dots,x_{n_i})$ con los $x_j\in S$, lo que nos da una serie de operaciones $\nu_i:S^{n_i}\to S$ que, además, cumplen las igualdades en $E$ al estar $e$ definida sobre clases de equivalencia, de modo que estas igualdades - definen una $(\Omega,E)$-álgebra y claramente $K$ es biyectiva sobre objetos. + definen una $(\Omega,E)$-álgebra y $K$ es biyectiva sobre objetos. Para los morfismos $f:(S,(\nu_i)_i)\to(S',(\nu'_i)_i)$, podemos definir $Kf:S\to S'$ como la propia $f$, que es un morfismo @@ -346,8 +349,8 @@ viene dado propiedad conmutativa que define los morfismos de $T$-álgebras es precisamente la que define los morfismos de $(\Omega,E)$-álgebras. - Así, $K$ es un isomorfismo, pero $K$ se ha definido de igual forma que en la - prueba del teorema anterior, por lo que es el mismo $K$. + Así, $K$ es un isomorfismo, y claramente esta definición de $K$ coincide con + la del teorema anterior. \end{proof} \section{Categorías de Kleisli} @@ -355,9 +358,9 @@ viene dado Hemos visto que, dada una mónada en una categoría $\cC$, la adjunción de Eilenberg-Moore asociada es un objeto final de la categoría de las adjunciones que definen dicha mónada junto con las transformaciones de mónadas que son la -identidad en $\cC$. Dicha categoría también tiene un objeto inicial, la -categoría de Kleisli, que como veremos en el siguiente capítulo es de gran -importancia en teoría de la computación. +identidad en $\cC$. Vamos a ver que esta categoría de adjunciones tiene también +un objeto inicial, la categoría de Kleisli, de gran importancia en teoría de la +computación. \begin{definition} Dada una mónada $(T,\eta,\mu)$ en $\cC$, llamamos \conc{categoría de Kleisli} @@ -378,8 +381,8 @@ importancia en teoría de la computación. % $f\hat\circ\eta_x=\mu_y\circ Tf\circ\eta_x=\mu_y\circ\eta_{Ty}\circ f=f$ y % $\eta_y\hat\circ f=\mu_y\circ T\eta_y\circ f=f$. -Es fácil comprobar que estas definiciones de composición e identidad son válidas -y definen una categoría. +Es rutinario comprobar que estas definiciones de composición e identidad definen +una categoría. \begin{theorem} Sea $(T,\eta,\mu)$ una mónada en $\cC$. Si $F:\cC\to\cC_T$ lleva los objetos a @@ -422,10 +425,10 @@ y definen una categoría. Queda ver que $L$ es única. Claramente lo es sobre objetos. Sobre morfismos, la caracterización de las transformaciones de adjunciones (\ref{prop:adj-transform}) nos da $L\eps'=\eps L$, por lo que para cada objeto - $c$, $L\eps'_c=\eps_{Lc}=\eps_{Fc}$. Ahora bien, si $L,L':\cC_T\to\cD$ son dos - funtores que cumplen la condición, por igualación $L\eps'_c=L'\eps'_c$ y, por - ser $\eps'_c$ una flecha universal desde un funtor, es un retracto y por tanto - un epimorfismo, con lo que $L=L'$. + $c$, $L\eps'_c=\eps_{Lc}=\eps_{Fc}$. Entonces, si $L,L':\cC_T\to\cD$ son dos + funtores que cumplen la condición, por igualación $L\eps'_c=L'\eps'_c$, pero + $\eps'_c$ una flecha universal desde un funtor y por tanto es un retracto y un + epimorfismo, con lo que $L=L'$. \end{proof} %%% Local Variables: |