# The Unapologetic Mathematician

## Yoneda’s Lemma

Okay, time to roll up our sleeves and get into one of the bits that makes category theory so immensely tweaky: Yoneda’s Lemma.

First, let’s lay out a bit of notation. Given a category $\mathcal{C}$ and an object $A\in\mathcal{C}$ we’ll use $h_A$ to denote the covariant functor represented by $A$ and $h'_A$ to denote the contravariant one. That is, $h_A(B)=\hom_\mathcal{C}(A,B)$ and $h'_A(B)=\hom_\mathcal{C}(B,A)$.

Now given a covariant functor $F:\mathcal{C}\rightarrow\mathbf{Set}$, we’re interested in the set of natural transformations $\mathrm{Nat}(h_A,F)$. Note that not all of these are natural isomorphisms. Indeed, $F$ may not be representable at all. Still, there can be natural transformations going in one direction.

The Yoneda Lemma is this: there is a bijection between $\mathrm{Nat}(h_A,F)$ and $F(A)$.

Seriously.

And the proof is actually pretty clear too. One direction leaps out when you think of it a bit. A natural transformation $\Phi:h_A\rightarrow F$ has components $\Phi_B:\hom_\mathcal{C}(A,B)\rightarrow F(B)$, sending morphisms of $\mathcal{C}$ to elements of certain sets. Now, given any category and any object, what morphism do we know to exist for certain? The identity on $A$! So take $1_A$ and stick it into $\Phi_A$ and we get an element $\Phi_A(1_A)=x_\Phi\in F(A)$. The really amazing bit is that this element completely determines the natural transformation!

So let’s start with a category $\mathcal{C}$, an object $A$, a functor $F:\mathcal{C}\rightarrow\mathbf{Set}$, and an element $x\in F(A)$. From this data we’re going to build the unique natural transformation $\Phi^x:h_A\rightarrow F$ so that $\Phi^x_A(1_A)=x$. We must specify functions $\Phi^x_B:\hom_\mathcal{C}(A,B)\rightarrow F(B)$ so that for every arrow $f:B\rightarrow C$ in $\mathcal{C}$ we satisfy the naturality condition. For now, let’s focus on the naturality squares for morphisms $f:A\rightarrow B$, and we’ll show that the other ones follow. This square is:

$\begin{matrix}\hom_\mathcal{C}(A,A)&\rightarrow&\hom_\mathcal{C}(A,B)\\\downarrow{\Phi^x_A}&&\downarrow{\Phi^x_B}\\F(A)&\rightarrow&F(B)\end{matrix}$

where the horizontal arrows are $\hom_\mathcal{C}(A,f)$ and $F(f)$, respectively. Now this square must commute no matter what we start with in the upper-left corner, but let’s see what happens when we start with $1_A$. Around the upper right this gets sent to $f\in\hom_\mathcal{C}(A,B)$, and then down to $\Phi^x_B(f)$. Around the lower left we first send $1_A$ to $\Phi^x_A(1_A)=x\in F(A)$, which then gets sent to $\left[F(f)\right](x)$. So, in order for these chosen naturality squares to commute for this specific starting value we must define $\Phi^x_B:\hom_\mathcal{C}(A,B)\rightarrow F(B)$ so that $\Phi^x_B(f)=\left[F(f)\right](x)$.

Now I say that these definitions serve to make all the naturality squares commute. Let $f:B\rightarrow C$ be any arrow in $\mathcal{C}$ and write out the square:

$\begin{matrix}\hom_\mathcal{C}(A,B)&\rightarrow&\hom_\mathcal{C}(A,C)\\\downarrow{\Phi^x_B}&&\downarrow{\Phi^x_C}\\F(B)&\rightarrow&F(C)\end{matrix}$

Now, starting with $g\in\hom_\mathcal{C}(A,B)$ we send it right to $f\circ g\in\hom_\mathcal{C}(A,C)$, and then down to $\left[F(f\circ g)\right](x)\in F(C)$. On the other side we send $g$ down to $\left[F(g)\right](x)\in F(B)$, and then right to $\left[F(f)\right](\left[F(g)\right](x))=\left[F(f)\circ F(g)\right](x)=\left[F(f\circ g)\right](x)$. And thus the square commutes.

So, for every natural transformation $\Phi:h_A\rightarrow F$ we have an element $x_\Phi\in F(A)$, for every element $x\in F(A)$ we have a natural transformation $\Phi^x:h_A\rightarrow F$, and these two functions are clearly inverses of each other.

Almost identically, there’s a contravariant Yoneda Lemma, saying that $\mathrm{Nat}(h'_A,F)\cong F(A)$ for every contravariant functor $F$. You can verify that you’ve understood the proof I’ve given above by adapting it to the proof of the contravariant version.

There’s a lot here, and although it’s very elegant it may not be clear why it’s so interesting. I’ll come back tomorrow to try explaining what the Yoneda Lemma means.