Adjunction : two definitions and their equivalence

Let $\mathbf{C}, \mathbf{D}$ be locally small categories and let $F:\mathbf{C} \rightarrow \mathbf{D}, G:\mathbf{D}\rightarrow \mathbf{C}$ functors.

I will give what, in my view, is the more intuitive definition of an adjunction first.

We say that $F$ is left adjoint to $G$, written $F\dashv G$, when we have a natural isomorphism between the (bi)functors $\hom_\mathbf{D}(F\_,\_)$ and $\hom_{\mathbf{D}}(\_,G\_)$. Recall that these were defined in an earlier post.

This definition is easy to remember if you use the analogy between the inner product on a Hilbert space and representable functors as mentioned in an earlier post. If $F$ is a bounded linear map between Hilbert spaces and $G$ its adjoint, then $<F\_,\_>=<\_,G\_>$ is the defining property of the adjoint.

Now let's return to our our original setting with (locally small) categories $\mathbf{C}, \mathbf{D}$ and $F\dashv G$.

Let $\phi: \hom_\mathbf{D}(F\_,\_) \rightarrow \hom_{\mathbf{D}}(\_,G\_)$ be a natural isomorphism (which exists since $F\dashv G$).

Note that $\phi$ is a natural isomorphism in each variable separately.  That is we have natural isomorphisms $\phi_{A,\_}: \hom_\mathbf{D}(FA,\_) \rightarrow \hom_{\mathbf{C}}(A,G\_)$
and $\phi_{\_,C}: \hom_\mathbf{D}(F\_,C) \rightarrow \hom_{\mathbf{C}}(\_,GC)$ for each $\mathbf{C}$ object $A$ and each $\mathbf{D}$ object $C$. Moreover, as the notation suggests, the two agree with $\phi$ when defined on the same set, i.e.
\[ \phi_{A,\_}(C) = \phi_{A,C} = \phi_{\_,C}(A).\]
 Conversely, given such a pair with the above agreement property we can use them to define a natural isomorphism  $\hom_\mathbf{D}(F\_,\_) \rightarrow \hom_{\mathbf{C}}(\_,G\_)$ using the agreement property.

Note that for each $\mathbf{C}$ object $A$ and each $\mathbf{D}$ object $C, \phi_{A,C}:\mathbf{C}(FA,C) \overset{\sim}{\rightarrow}\hom_{\mathbf{C}}(A,GC)$. Hence to greatly simplify notation, for $f:FA\rightarrow C$ and $g:A\rightarrow GC$ define the transpose of $f$ under $\phi: \bar{f}: = \phi_{A,C}(f)\in \mathbf{C}(A,GC)$ and the transpose of $g$ under $\phi^{-1}: \hat{g}:= \phi^{-1}_{A,C} (g)= (\phi_{A,C})^{-1}(g) \in \mathbf{D}(FA,C)$. Then clearly we have $\bar{\hat{g}} = g$ and $\hat{\bar{f}}=f$.


For each $\mathbf{C}$ object $A$, define $\eta_A:= \phi_{A,FA}(1_ A) = \bar{1_A}:A\rightarrow GFA$ and for each $\mathbf{D}$ object $C$, define $\varepsilon_C: = \phi^{-1}_{FGA,C}(1_{GA}) = \hat{1_{GA}}.$

Let $g:C\rightarrow D, f^{op}:B\rightarrow A$ be arrows in $\mathbf{D}, \mathbf{C}^{op}$, respectively. Then naturality of $\phi_{A,\_}$ implies \begin{equation}Gg\bar{(\_)} = \bar{(g\_)} \end{equation} and naturality of $\phi^{-1}_{A,\_}$ implies \begin{equation} \hat{(Gg\_)} = g\hat{(\_)}. \end{equation}
Then taking $C=FA$ in the first equation and evaluating at $1_{FA}$, recalling $\bar{1_{FA}} = \eta_A$, yields
\[ (eq.1) \;\;\;\;\; Gg\eta_A = \bar{g}  ,\]
and taking $A=GC$ in the second equation and evaluating at $1_{GC}$, recalling $\hat{1_{GC}} = \epsilon_C$, yields
\[(eq.2) \;\;\;\;\; \hat{Gg} = g\varepsilon_C.\]
Similarly, naturality of $\phi_{\_,C}$ implies \begin{equation}\bar{(\_)}f = \bar{(\_Ff)} \end{equation} and naturality of $\phi^{-1}_{\_,C}$ implies \begin{equation} \hat{(\_f)} = \hat{(\_)}Ff. \end{equation}
Then taking $C=FA$ in the first equation and evaluating at $1_{FA}$, recalling $\bar{1_{FA}} = \eta_A$, yields
\[ (eq.3) \;\;\;\;\;  \eta_Af = \bar{Ff},\]
and taking $A=GC$ in the second equation and evaluating at $1_{GC}$, recalling $\hat{1_{GC}} = \varepsilon_C$, yields
\[(eq.4) \;\;\;\;\; \hat{f} = \epsilon_CFf.\]

We may define natural transformations $\eta: 1_\mathbf{C} \rightarrow GF$ and $\varepsilon :FG \rightarrow 1_\mathbf{D}$ by defining them on components by $\eta(A) = \eta_A$ and $\varepsilon(C) = \epsilon_C$. We must check that these assignments do indeed define natural transformations.

First let's check $\eta:1_{\mathbf{C}} \rightarrow GF$. Let $f:A\rightarrow B$ be a $\mathbf{C}$ arrow. Then we must show that the naturality square commutes, i.e. that $(GFf)\eta_A = \eta_Bf$. But using $Ff$ in (eq.1) yields $G(Ff)\eta_A = \hat{Ff}$. Similarly using $f$ in (eq. 3) yields $\eta_Bf=\bar{Ff}.$ So $(GFf)\eta_A = \eta_Bf$, as desired.

Now let's check $\varepsilon: FG\rightarrow 1_\mathbf{D}$. Let $g:C\rightarrow D$ be a $\mathbf{D}$ arrow. Then we must show that the naturality square commutes, i.e. that $g\varepsilon_C = \varepsilon_D(FGg)$. However, by (eq. 2) $g\varepsilon_C = \hat{(Gg)}$ and using $Gg$ in (eq. 4) gives $\varepsilon_DF(Gg) = \hat{(Gg)}$. So $g\varepsilon_C = \varepsilon_D(FGg)$, as desired. Hence $\eta, \varepsilon$ are natural transformations. See the Catster's video Adjunctions 4 for a similar argument (with the diagrams drawn).

The natural transformations $\eta:1_{\mathbf{C}} \rightarrow GF, \varepsilon: FG\rightarrow 1_\mathbf{D}$ are called the unit and co-unit, respectively, of the adjunction.

Next we show that $\eta$ and $\varepsilon$ satisfy the so-called triangle identities:
\[(\varepsilon F)\circ(F\eta) = 1_F  \;\;\;\;\;\;\;\;\; (G\varepsilon)\circ (\eta G) = 1_G,\]
where the $\circ$ has only been written as a reminder that composition of natural transformations is involved.
Let $A$ a $\mathbf{C}$ object, $C$ a $\mathbf{D}$ object. Then \[((\varepsilon F)\circ(F\eta) )(A) = (\varepsilon F)_A(F\eta)_A =
\varepsilon_{FA}(F\eta_A) = \hat{\eta_A} = 1_{FA} = 1_F(A)\] by (eq. 4) and
\[((G\varepsilon)\circ (\eta G))(C) = (G\varepsilon)_C(\eta G)_C = (G\varepsilon_C)\eta_{GC} = \bar{\epsilon_C} = 1_{GC} = 1_G(C)\] by (eq. 1). Therefore the triangle identities hold.

This leads us to the second, more abstract, defintion of adjunction. Let $F:\mathbf{C} \rightarrow \mathbf{D}, G:\mathbf{D} \rightarrow \mathbf{C}$ be functors. Then we say $F$ is left adjoint to $G$ ($F\dashv G$) if there exist natural transformation $\eta:1_\mathbf{C} \rightarrow GF, \varepsilon : FG\rightarrow 1_\mathbf{D}$ called the unit and co-unit, respectively, satisfying the triangle identities. Note that for this definition it is not necessary for the categories involved to be locally small.

We have shown already that if $\mathbf{C}, \mathbf{D}$ are locally small categories then the first definition implies the second. Now let's show that in the case that if $\mathbf{C}, \mathbf{D}$ are locally small then also the second definition implies the first, so that in that case the two definitions are equivalent.

Let $F,G, \eta, \varepsilon$ as in the second definition of adjunction, with $\mathbf{C}, \mathbf{D}$ locally small. Moreover assume $\eta, \varepsilon$ satisfy the triangle identities. Let's show that the first definition of adjunction is satisfied.

We will use an argument completely analogous to that used in the proof of the Yoneda Lemma to define the natural isomorphism $\phi$. Essentially $\phi$ will be completely determined by its action on the identity.

For any $\mathbf{C}$ object $A$ set $\phi_{A,FA}(1_{FA}) = \eta_A$. Then in order for $\phi$ to be a natural transformation, for any $g:FA\rightarrow C$ we must have $\phi_{A,C}(g) = \phi_{A,C}(g1_{FA}) = (Gg)(\phi_{A,FA}(1_{FA}) = (Gg)(\eta_A)$. Hence we must define $\phi_{A,C}$ by
\[\phi_{A,C}(g) = (Gg)(\eta_A)\].

Let's show that $\phi_{A,\_}$ is a natural transformation. Let $g: C\rightarrow D$, $h\in \mathbf{D}(FA,C)$. Then $Gg(\phi_{A,C})(h) = Gg(Gh\eta_A) = G(gh)\eta_A = \phi_{A,D}(gh)$. Hence
\[Gg(\phi_{A,C}\_) = \phi_{A,D}(g\_),\] which is the naturality condition.

Now for any $\mathbf{D}$ object $C$ set $\psi_{GC,C}(1_{GC}) = \varepsilon_C$. We wish to define $\psi$ in such a way that $\psi = \phi^{-1}$. In order for $\psi$ to be a natural transformation, for any $f: A\rightarrow GC (f^{op}:GC\rightarrow A)$ we must have $\psi_{A,C}(f) = \psi_{A,C}(1_{GC}f) = \psi_{GC,C}(1_{GC})Ff = \varepsilon_C(Ff)$. Hence we must define $\psi_{A,C}$ by
\[\psi_{A,C}(f) = \varepsilon_C(Ff)\].

Let's show that $\psi_{\_,C}$ is a natural transformation. Let $f^{op}:A\rightarrow B$, $h\in \mathbf{C}(A,GC)$. $\psi_{A,C}(h)Ff = \varepsilon_CFhFf= \varepsilon_CF(hf) = \psi_{B,C}(hf)$. Hence
\[\psi_{B,C}(\_f) = (\psi_{A,C}(\_Ff),\] which is the naturality condition.

Finally, we must show that $(\phi_{A,C})^{-1} = \psi_{A,C}$. From that it will follow that $\phi_{\_,C}$ is also a natural transformation (since $\psi_{\_,C} = \phi^{-1}_{\_,C}$ is a natural transformation). Then since $\phi_{A,\_}$ and $\phi_{\_,C}$ agree when defined on the same set, they will induce a natural isomorphism  $\phi: \hom_\mathbf{D}(F\_,\_) \rightarrow \hom_\mathbf{C}(\_,G\_)$.

Note that since $\eta: 1_{\mathbf{C}} \rightarrow GF, \varepsilon: FG\rightarrow 1_\mathbf{C}$ are natural transformations, by naturality, we have for any $f:A\rightarrow B, g:C\rightarrow D$,
\[(eq. a) \;\;\;\;\;\;\; GFf\eta_A = \eta_Bf\] and
\[(eq. b) \;\;\;\;\;\;\; g\varepsilon_C =\varepsilon_DFGg.\]

Moreover, we have the triangle identities \[ (\varepsilon F)\circ(F\eta) = 1_F  \;\;\;\;\;\;\;\;\; (G\varepsilon)\circ (\eta G) = 1_G.\]

Hence if $h:A\rightarrow GC$ then
\begin{equation}
\begin{split}
\phi_{A,C}\psi_{A,C}(h) &= \phi_{A,C}\varepsilon_CFh = G(\varepsilon_CFh)\eta_A = G\varepsilon_C(GFh)\eta_A \\ &= G\varepsilon_C\eta_{GC}(h) = (G\varepsilon\circ \eta G)(C)(h)=1_{GC}(h)=h
\end{split}
\end{equation} where the first equalities  hold by definition of $\phi$ and $\psi$, the third equality holds by functoriality of $G$, the fourth holds by (eq. b) and the last holds by the second triangle identity.

Similarly if $h:FA\rightarrow C$ then
\begin{equation}
\begin{split}
\psi_{A,C}\phi_{A,C}(h) &= \psi_{A,C}(Gh\eta_A) = \varepsilon_CF(Gh\eta_A) = \varepsilon_C(FGh)F\eta_A\\  &= h\varepsilon_{FA}F\eta_A = h(\varepsilon F\circ F\eta)(A) =h 1_{FA}=h,
\end{split}
\end{equation}
where the first equalities  hold by definition of $\phi$ and $\psi$, the third equality holds by functoriality of $F$, the fourth holds by (eq. a) and the last holds by the first triangle identity.

Therefore  $(\phi_{A,C})^{-1} = \psi_{A,C}$, from which our desired conclusion follows: the two definitions of adjunction are equivalent for locally small categories.

The Yoneda Embedding Theorem

Let $\mathbf{C}$ be a locally small category. Then for each object $A$ of $\mathbf{C}$ we define the contravariant representable functor $H^A:=hom_{\mathbf{C}}(\_,A):\mathbf{C}^{op}\rightarrow \mathbf{Set}$. Then by the Yoneda Lemma of the previous post we know that for any presheaf $F$ (functor from $\mathbf{C}^{op}$ to $\mathbf{Set}$) we have $Nat(H^A,F)\cong FA$ as sets under the map $Nat(H^A,F)\ni \eta \mapsto \eta_A(1_A)$. Thus, in particular, if we take $F=H^B$ then $Nat(H^A,H^B)\cong H^B(A) = \mathbf{C}(A,B)$.

A fuctor $F$ between categories $\mathbf{C}$ and $\mathbf{D}$ is called an embedding if it is injective on objects and full and faithful; where it is full when it induces a surjective maps from $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $A,B$, is faithful when it induces an injective map from $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $A,B$, and hence is full and faithful when it induces a bijection between $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $\mathbf{C}$ objects $A$ and $B$.

Again letting $\mathbf{C}$ be a small category, define the Yoneda Embedding $H: \mathbf{C} \rightarrow \mathbf{Set}^{\mathbf{C}^{op}}$ by the assignments
\[A\mapsto H^A,\;\;\;\;\;\;(f:A\rightarrow B)\mapsto Hf :: Hf_C = f\_.\]
That is $H(A) = H^A$ on objects and if $f:A\rightarrow B$ is an arrow, then $Hf$ is the natural transformation $H^A\rightarrow H^B$ with components $(Hf)_C = f\_$ for each object $C$.

We have two things that we need to check for this assignment; first, that $H$ is a functor, which includes checking that $Hf$ is a natural transformation, and, second, that $H$ is an embedding.

Let's check that $H$ is a functor. We begin by showing $Hf$ is actually a natural transformation. Let $C,D$ be two $\mathbf{C}$ objects and $g^{op}:C\rightarrow D$ an arrow in $\mathbf{C}^{op}$ (opposite of the arrow $g:D\rightarrow C$ in $\mathbf{C}$). We must then check that the naturality square commutes, i.e. $(H^Bg)(Hf)_C=((Hf)_D)H^Ag)$. So let $h\in H^AC = \mathbf{C}(C,A)$. Then \[(H^Bg)(Hf)_C(h) = (H^Bg)(fh) =fhg = ((Hf)_D)(hg) = ((Hf)_D)H^Ag)(h).\] Hence the square commutes as desired.

Clearly to show that $H$ respects function composition it suffices to show that for any $f:A\rightarrow B, g:B\rightarrow C$ and any $\mathbf{C}$ object $D$ we have $((Hg)_D)(Hf)_D = (H(gf))_D.$ So let $h\in H^AD = \mathbf{C}(D,A)$. Then
\[((Hg)_D)(Hf)_D(h) = gfh = H(gf))_D(h).\] So $H$ respects composition. Lastly, clearly we have $(H1_A)_C = 1_A\_ = \_ = 1_{H^AC} = (1_{H(A)})(C)$. Therefore $H$ is a functor.

Now let's complete the proof of the Yoneda Embedding Theorem by showing that $H$ is an embedding.

Well, clearly $H$ is 1-1 on objects since $H^A = H^B$ implies $H^AA = \mathbf{C}(A,A) = \mathbf{C}(B,A) = H^BA$. So, in particular, $1_A \in \mathbf{C}(B,A)$, which implies (by uniqueness on domain and codomain) that $A=B$.

For the rest, let $A,B$ be $\mathbf{C}$ objects. Then from the conclusion we drew from the Yoneda Lemma above, we have $Nat(H^A,H^B)\cong H^B(A) = \mathbf{C}(A,B)$.
But then $Nat(H^A,H^B) = \mathbf{Set}^{\mathbf{C}^{op}}(H^A,H^B) = \mathbf{Set}^{\mathbf{C}^{op}}(HA,HB)\cong \mathbf{C}(A,B)$ in set, i.e. $H$ is full and faithful. Hence $H$ is an embedding and the proof is complete.