yoneda.tex

\chapter{Lema de Yoneda}

El lema de Yoneda es uno de los resultados más importante, pues el relacionado embebimiento de Yoneda es una herramienta poderosa para demostrar otros resultados.

En este capítulo, siempre estaremos trabajando con categorías localmente pequeñas.

\section{Hom-Functores}
Consideremos la categoría de functores de una categoría $\cat$ a $\Set$, que podemos denotar como $\Set^\cat$.
En esta categoría, los objetos son functores y los morfismos son transformaciones naturales entre functores.

Como estamos bajo la hipótesis que $\cat$ es localmente pequeña, entonces $C(A,B)$ es un conjunto para todo $A \in \cat$ y $B \in \cat$.
Entonces, $C(A,B) \in \Set$.
De este hecho, podemos crear el functor contravariante:
\[ C(A,-) \colon \cat \to \Set \]
que a cada objeto $X \in \cat$ le asocia el conjunto $C(A,X)$.
A cada morfismo $f \colon X \to Y$ en $\cat$, $C(A,f)$ será un morfismo entre los conjuntos $C(A,X)$ y $C(A,Y)$.
La forma natural de asociar estos conjuntos es por la composición $g \mapsto f \circ g$.
A dicho functor le damos el nombre de \newterm{hom-functor}.

Veamos que el hom-functor es realmente un functor.

\[ C(A,\id_B)(g) = g \circ \id = g \Rightarrow C(A,\id_B) = \id_{C(A,B)} \]
\begin{align*}
C(A,g \circ f)(h) & = (g \circ f) \circ h = g \circ (f \circ h)\\
& = g \circ C(A,f)(h) = C(A,g)(C(A,f)(h))\\
& = C(A,g) \circ C(A,f)\ (h)
\end{align*}

Luego $C(A,-)$ respeta el morfismo unidad y la composición de morfismos, luego es efectivamente un functor de $\cat \to \Set$.
Equivalentemente, tenemos que $C(A,-)$ es un objeto de $\Set^\cat$.

Digamos que tenemos un objeto isomorfo a $C(A,-)$ en $\Set^\cat$.
Esto quiere decir que entre el objeto, visto como un functor, y $C(A,-)$ hay una transformación natural invertible, que también llamamos \newterm{isomorfismo natural}.
De aquí procede la siguiente definición: 

\begin{definition}
Un functor $F \colon \cat \to \Set$ es \newterm{representable} si es isomorfo naturalmente a un hom-functor.
\end{definition}

Es decir, un functor representable puede identificarse con $C(A,-)$ para algún $A$.

\subsection{Functores representables en Haskell}
% Milewski
En la categoría $\Hask$, el hom-functor recibe a menudo el nombre de \code{Reader}
\begin{minted}{haskell}
type Reader a x = a -> x
\end{minted}
Es decir, $C(A,-)$ es equivalente a \code{Reader a}, que es equivalente a \code{(->) a}.
Para que un functor \code{F} sea representable necesitamos una transformación natural invertible a \code{Reader a}, es decir, necesitamos:
\begin{minted}{haskell}
functorAreader :: f x -> (a -> x)
readerAfunctor :: (a -> x) -> f x
\end{minted}
tal que cada una sea la inversa de la otra.

Vamos a tomar de la librería para Haskell \textit{adjunctions} de Edward Kmett la siguiente implementación de functores representables:
\begin{minted}{haskell}
class (Functor f) => Representable f where
  type Rep f :: *
  index :: f x -> Rep f -> x
  tabulate :: (Rep f -> x) -> f x
\end{minted}
Nuestra función \code{functorAreader} es aquí \code{index}, \code{readerAfunctor} se convierte en \code{tabulate}.
El tipo \code{a} pasa a depender del functor \code{f} a través de \code{Rep f}.
Además, se establece que se deben cumplir:
\begin{minted}{haskell}
tabulate . return = return
tabulate . index  = id
index . tabulate  = id
\end{minted}
Las primera condición establece que \code{tabulate} sea una transformación natural. 
Las otras dos condiciones son equivalentes a dicha transformaión natural sea invertible con \code{index}.

\section{Inmersión de Yoneda}
Primero definamos qué es un inmersión.

Recordemos de la definición de functor, que un functor consistía en un par $F_O$ y $F_M$ que actúan sobre los objetos y morfismos respectivamente.
Dado un functor $F \colon \cat \to \mathcal{D}$ y dos objetos $A, B \in \cat$, denotamos por $F_M|_{\cat(A,B)}$ o, sencillamente, $F_{A,B}$ a la \textquote{restricción} de $F_M$ a la colección de morfismos $\cat(A,B)$.
Como $F_M$ respeta el dominio y codominio, tenemos que $F_{A,B}$ es una aplicación:
\[ F_{A,B} \colon \cat(A,B) \to \mathcal{D}(F A, F B) \]
Con esto en mente, definimos las siguientes clases de functores:

\begin{definition}
Un functor $F \colon \cat \to \mathcal{D}$ es 
\begin{itemize}
  \item \index{functor!lleno}\emph{lleno} si para cada $A,B \in \cat$, $F_{A,B}$ es sobreyectiva.
  \item \index{functor!fiel}\emph{fiel}, si para cada $A,B \in \cat$, $F_{A,B}$ es inyectiva.
  \item \index{functor!{inyectivo en objetos}}\emph{inyectivo en objetos} si $F_O$ es inyectivo.
\end{itemize}
\end{definition}

Obsérvese que no es lo mismo que $F$ sea lleno o fiel a que $F_M$ sea inyectiva y sobreyectiva.
Podríamos decir que la propiedad de ser lleno y fiel es una propiedad \textquote{local}.

\begin{definition}
Un functor es una \newterm{inmersión} si es fiel e inyectivo en objetos.
Si además es lleno, decimos que es una \newterm{inmersión llena}. 
\end{definition}

\begin{definition}
Dada una categoría $\cat$, una \newterm{subcategoría} es un par $(\mathcal{D}, F)$ donde $\mathcal{D}$ es una categoría y $F \colon \mathcal{D} \to \cat$ es una inmersión.

Si además, $F$ es llena, decimos que $(\mathcal{D}, F)$ es una \index{subcategoría!llena}\emph{subcategoría llena}.
\end{definition}

\begin{lemma}[Lema de Yoneda]
Sea $\cat$ una categoría localmente pequeña, un functor $F \colon \cat \to \Set$ y un objeto $A \in \cat$.
Denotemos por $Nat(\cat(A,-), F)$ a la colección de transformaciones naturales de $\cat(A,-) \Rightarrow F$.
Hay una biyección:
\[ Nat(\cat(A,-), F) \cong F A \]
que es natural en $A$ y en $F$.
\end{lemma}
% Category theory in context + Awodey
Vamos a precisar:
\begin{itemize}
  \item Hemos visto previamente que $\cat(A,-) \colon \cat \to \Set$ es un functor, luego puede haber una colección de transformaciones naturales de $\cat(A,-)$ al functor $F \colon \cat \to \Set$.
  \item  En la categoría de functores $\Set^{\cat}$, donde $\cat(A,-)$ y $F$ son objetos, $Nat(\cat(A,-),F)$ es precisamente la colección de morfismos $\Set^{\cat}(\cat(A,-),F)$.
  \item La naturalidad en $F$ quiere decir que para toda transformación natural $\theta \colon F \Rightarrow G$, se tiene que el siguiente diagrama es conmutativo:
\[
\begin{tikzcd}
  {Nat(\cat(A,-),F)} \arrow[rr,"\cong"] \arrow[dd,"{Nat(\cat(A,-),\theta)}" left] & & F A \arrow[dd,"\theta_A"]\\
  &\\
  {Nat(\cat(A,-),G)} \arrow[rr,"\cong"] & & G A
\end{tikzcd}
\]
  \item La naturalidad en $A$ quiere decir que para todo $f \colon A \to B$, se tiene que el siguiente diagrama conmuta:
  \[
\begin{tikzcd}
  {Nat(\cat(A,-),F)} \arrow[rr,"\cong"] \arrow[dd,"{Nat(\cat(f,-),F)}" left] & & F A \arrow[dd,"F f"]\\
  &\\
  {Nat(\cat(B,-),F)} \arrow[rr,"\cong"] & & F B
\end{tikzcd}
\]
  donde para una transformación natural $\mu \colon \cat(A,-) \Rightarrow F$ y morfismo $h \colon B \to C$:
  \[ (Nat(\cat(f,-),F)\mu)_C(h) = \mu_C \circ \cat(f,C)(h) = \mu_C (h \circ f) \]
\end{itemize}
\begin{proof}
Primero miramos que para una transformación natural $\mu \in Nat(\cat(A,-),F)$, es decir, $\mu \colon \cat(A,-) \Rightarrow F$, su componente en $A \in \cat$ es una función entre conjuntos
\[ \mu_A \colon \cat(A,A) \to F A \]
Sabemos además que $\cat(A,A)$ es un conjunto no vacío, pues al menos contiene $\id_A$

Consideramos la función $\phi \colon Nat(\cat(A,-),F) \to F A$ definida por:
\begin{align*}
  \phi \colon Nat(\cat(A,-),F) & \to F A\\
  \alpha & \mapsto \alpha_A(\id_A)
\end{align*}

Dado cualquier $x \in F A \in \Set$, definimos la transformación natural 
\[ \psi(x) \colon \cat(A,-) \Rightarrow F \]
estableciendo su componente para $B \in \cat$ cualquiera:
\begin{align*}
  \psi(x)_B \colon \cat(A,B) & \to F B\\
  \psi(x)_B (f) & \mapsto (F f)(x)
\end{align*}

Veamos que $\psi(x)$ cumple la naturalidad. Para un $f \colon B \to C$:
\begin{equation}\label{psi-diagrama}
\begin{tikzcd}
  {\cat(A,B)} \arrow[rr,"\psi(x)_B"] \arrow[dd,"{\cat(A,f)}"] & & F B \arrow[dd,"F f"]\\
  &\\
  {\cat(A,C)} \arrow[rr,"\psi(x)_C"] & & F C
\end{tikzcd}
\end{equation}
Tenemos que para todo $h \colon A \to B$:
\begin{align*}
(\psi(x)_C \circ \cat(A,f)) (h) & = \psi(x)_C (f \circ h)\\
& = (F (f \circ h))(x)\\
& = (F f) \circ (F h)(x)\\
& = (F f)(\psi(x)_B(h))\\
& = (F f) \circ (\psi(x)_B)(h)
\end{align*}
Luego el diagrama \ref{psi-diagrama} conmuta.

Veamos que $\phi$ y $\psi$ son inversas. Para $x \in F A$:
\begin{align*}
 \phi(\psi(x)) & = \psi(x)_A(\id_A)\\
 & = (F (\id_A))(x)\\
 & = \id_{F A}(x) & \text{por definición de functor}\\
 & = x
\end{align*}
Para $\mu \colon \cat(A,-) \Rightarrow F$, $B \in \cat$ y $h \colon A \to B$:
\begin{align*}
 \psi(\phi(\mu))_B(h) & = \psi(\mu_A(\id_A))_B(h)\\
 & = (F h)(\mu_A(\id_A))\\
 & = (\mu_B)(C(A,h)(\id_A)) & \text{por naturalidad de }\mu\\
 & = \mu_B(h\circ \id_A)\\
 & = \mu_B(h)
\end{align*}
Luego $\phi$ y $\psi$ son inversas y $Nat(\cat(A,-),F) \cong F A$.
Veamos la naturalidad en $F$ y en $A$:
\begin{equation}\label{diagrama-F}
\begin{tikzcd}
  {Nat(\cat(A,-),F)} \arrow[rr,"\phi_F"] \arrow[dd,"{Nat(\cat(A,-),\theta)}" left] & & F A \arrow[dd,"\theta_A"]\\
  &\\
  {Nat(\cat(A,-),G)} \arrow[rr,"\phi_G"] & & G A
\end{tikzcd}
\end{equation}
Sea $B \in \cat$ y $\mu \colon \cat(A,-) \Rightarrow F$:
\begin{align*}
 \theta_A(\phi_F(\mu)) & = \theta_A(\mu_A(\id_A))\\
 & = (\theta \circ \mu)_A(\id_A)\\
 & = \phi_G(\theta \circ \mu)
\end{align*}
que demuestra que el diagrama \ref{diagrama-F} conmuta.

Sea $f \colon A \to B$ y $\mu \colon \cat(A,-) \Rightarrow F$:
\begin{equation}\label{diagrama-A}
\begin{tikzcd}
  {Nat(\cat(A,-),F)} \arrow[rr,"\phi_A"] \arrow[dd,"{Nat(\cat(f,-),F)}" left] & & F A \arrow[dd,"F f"]\\
  &\\
  {Nat(\cat(B,-),F)} \arrow[rr,"\phi_B"] & & F B
\end{tikzcd}
\end{equation}
\begin{align*}
 (F f)(\phi_A(\mu)) & = (F f)(\mu_A(\id_A))\\
 & = (\mu_B)(C(A,f)(\id_A)) & \text{por naturalidad de }\mu\\
 & = (\mu_B)(f \circ \id_A)\\
 & = (\mu_B)(\id_B \circ f)\\
 & = (\mu_B)(C(f,B)(\id_B))\\
 & = (\mu \circ C(f,-))_B(\id_B)\\
 & = (\phi_B)(\mu \circ C(f,-))
\end{align*}
que demuestra que el diagrama \ref{diagrama-A} conmuta y acaba la demostración.
\end{proof}

\begin{remark}
Considerando la categoría opuesta, se tiene que para todo objeto $A \in \cat$ y functor contravariante $F \colon \cat^{op} \to \Set$ hay una biyección
\[ Nat(\cat(-,A), F) \cong F A\]
natural en $A$ y $F$.
\end{remark}

Nuestra primera aplicación del lema de Yoneda es usando $F = \cat(B,-)$.
Se tiene que:
\[ Nat(\cat(A,-),\cat(B,-)) \cong \cat(B,A) \]
Análogamente:
\[ Nat(\cat(-,A),\cat(-,B)) \cong \cat(A,B) \]
Esto motiva la inmersión de Yoneda:
\begin{definition}
Las \index{inmersión de Yoneda}\emph{inmersiones de Yoneda} covariante y contravariante son los morfismos:
\begin{align*} 
  Y \colon \cat & \to \Set^{\cat^{op}}\\
  A & \mapsto \cat(-,A)\\
  f \colon A \to B & \mapsto \cat(-,f) \colon \cat(-,A) \to \cat(-,B)
\end{align*}
\begin{align*} 
  K \colon \cat^{op} & \to \Set^{\cat}\\
  A & \mapsto \cat(A,-)\\
  f \colon A \to B & \mapsto \cat(f,-) \colon \cat(B,-) \to \cat(A,-)
\end{align*}
es decir, las \index{currificación}currificaciones del bifunctor $\cat(-,-) \colon \cat^{op} \times \cat \to \Set$.
\end{definition}
Obsérvese que $K$ es un functor contravariante y que $K A$ es un functor covariante $\cat^{op} \to \Set$.
Análogamente, $Y$ es un functor covariante a los functores contravariantes $\cat^{op} \to \Set$.

Veremos ahora que el uso de \textquote{inmersión} está justificado:
\begin{proposition}
Las inmersiones de Yoneda son inmersiones llenas.
\end{proposition}
\begin{proof}
Lo probamos para $Y$.
La inyectividad sobre objetos es evidente.
Observamos que, por definición, $\cat(A,B) = (Y B)A$.
Aplicando el lema de Yoneda:
\[ \cat(A,B) = (Y B)A \cong \Set^{\cat^{op}}(Y A, Y B)\]
Luego $Y$ es inmersión llena.
La prueba para $K$ es análoga.
\end{proof}

Un functor contravariante en $\Set^{\cat^{op}}$ recibe el nombre de \newterm{prehaz}.
Una consecuencia de la anterior proposición es que toda categoría localmente pequeña es una subcategoría llena de la categoría de prehaces.

\begin{proposition}
\end{proposition}
\section{Referencias}
\begin{itemize}
  \item Milewski, B. (2014). \emph{Category Theory for Programmers}, Capítulos 14-16.
  \item Riehl, E. (2014). \emph{Category Theory in Context}, Capítulo 2.
  \item Awodey, S. (2006). \emph{Category Theory}, Capítulo 8. 
\end{itemize}