Yoneda Electric Boogaloo

Yoneda’s lemma is likely the cornerstone of modern mathematics, not exactly because of how bombastic or impressive it is, but precisely because of how neatly it ties things together and how natural and elegant it is. \(\require{amscd} \newcommand\dual[1]{{#1}^{\mathrm{op}}} \newcommand{\cat}{\mathcal} \newcommand{\proto}{\nrightarrow} \newcommand{\Set}{\mathbf{Set}} \newcommand{\To}{\Rightarrow} \newcommand{\dinat}{\mathrel{\dot\To}} \newcommand{\yoneda}{よ} \newcommand{\iso}{\cong} \newcommand{\id}{\mathbf{id}} \renewcommand{\phi}{\varphi} \newcommand{\nat}{\mathbf{Nat}}\)

Yoneda Lemma

Statement

Given a small category \(\cat C\) , we write \([\dual{\cat C}, \Set]\) for the category of contravariant functors from \(\cat C\) to \(\Set\) . These are also very frequently known as presheaves. The claim is that there is a functor \[ \yoneda:\cat C\to[\dual{\cat C}, \Set] \] such that there is a natural isomorphism \[ [\dual{\cat C}, \Set](\yoneda(x), F) \iso F(x) \] which is to say, the contents of any functor are coherently determined – or conversely, determine coherently – all the natural transformations from representable functors into it.

Proof

Let’s first see the definition of \(\yoneda\) . Yoneda take an object to its represented presheaf, which is the functor that takes an object \(c\) of \(\cat C\) and sends it to the set of arrows \(c\to x\) and sends and arrow \(f:b\to c\) to the natural transformation \(\_\circ f\) . \[ \yoneda(x) = \cat C(\_, x) \]

It is immediate to see that it actually defines a functor, since the identity acts on the endormophisms as well the identity, and it’s clearly functorial in nature since we are literally composing things — it works out.

Consider some natural transformation \(\alpha:\yoneda(x)\to F\) ; we ought to show it corresponds naturally to one and only one element of \(F(x)\) . Take the commutative square corresponding to the component \(x\) of \(\alpha\) : given \(f:y\to x\) , \[ \begin{CD} \cat C(x,x) @>\alpha_x>> F(x)\\ @V{\cat C(f, x)}VV @V{F(f)}VV\\ \cat C(y,x) @>\alpha_y>> F(y) \end{CD} \]

The trick is to chase the identity, start with \(\id_x\) on the top left, \[ F(f)(\alpha_x(\id_x)) = \alpha_y(\id_x\circ f) = \alpha_y(f) \] and immediately something ought to pop out of the screen and catch your attention: the right side is arbitrary, we may pick any \(y\) and any \(f\) ; whereas the left-hand side is the application of our choice on a fixed element \(\alpha_x(\id_x)\) .

Thus, we have a map \[ \begin{aligned} \phi:[\dual{\cat C},\Set](\yoneda(x), F)&\to F(x)\\ \alpha &\mapsto \alpha_x(\id_x) \end{aligned} \] which we must invert both sides of, take \(\psi\) to be \[ \begin{aligned} \psi: F(x)&\to[\dual{\cat C},\Set](\yoneda(x), F)\\ \xi&\mapsto\beta^\xi \end{aligned} \] where \(\beta^\xi\) is the natural transformation whose component \(y\) takes \(u\in F(y)\) to \(F(-)(u):\cat C(y,x) \to F(y)\) . We ought to verify both are natural transformations and that one is the inverse of the other.

One is the inverse of the other

Naturality of \(\psi\)

Both \(\phi\) and \(\psi\) have an implicit \(x\) component, that need not be. We can look at their definition and extract indexed maps in the obvious way; now we prove them to be natural in that parameter: Given \(f:y\to x\)

What exactly is the morphism on the right? It takes a natural transformation \(\eta:\yoneda(x)\to F\) and gives you \(\eta\circ f\) – well, really it gives you \(\eta\circ\yoneda(f)\) – \[ (\eta\circ\yoneda(f))_z(g:z\to y) = \eta_z(f\circ g) \]

Thus, take \(u\in F(x)\) , \[ (\psi_x(u))_z = F(-:z\to x)(u) \] and so the Right-Down path is: \[ \begin{aligned} ((\psi_x(u))\circ\yoneda(f))_z(g:z\to y) &= (\psi_x(u))_z(\yoneda(f)(g)) \\ &= (\psi_x(u))_z(f\circ g) \\ &= F(f\circ g)(u) \\ \end{aligned} \]

Whereas, the other path is: \[ \begin{aligned} (\psi_y \circ F(f)(u))_z(g:z\to y) &= (\psi_y(F(f)(u)))_z(g:z\to y)\\ &= (F(-)(F(f)(u)))_z(g:z\to y)\\ &= (F(g)(F(f)(u)))\\ &= (F(g)\circ F(f)(u))\\ &= F(f\circ g)(u) \end{aligned} \]

So \(\psi\) really is a natural transformation.

Naturality of \(\phi\)

Take a natural transformation

\[ \begin{aligned} (F(f)\circ\phi_x)(\eta) = F(f)(\eta_x(\id_x)) = \eta_y(f) \end{aligned} \] \[ \begin{aligned} \phi_y(\eta\circ\yoneda(f)) = (\eta\circ\yoneda(f))_y(\id_y) = \eta_y(\yoneda(f)_y(\id_y)) = \eta_y(f\circ\id_y) = \eta_y(f) \end{aligned} \]

Conclusion

As we have shown, \(\psi\) and \(\phi\) are natural isomorphisms witnessing the fact that \[ [\dual{\cat C}, \Set](\yoneda(x), F) \iso F(x) \]

Consequences

Fully Faithfulness of よ

Let’s abbreviate \([\dual{\cat C}, \Set](-, -)\) to simply \(\nat(-,-)\) . Then \[ \nat(\yoneda(x),\yoneda(y)) \iso \cat C(x,y) \] which implies that \(\yoneda\) is full and faithful.

Conservativeness of よ

Since \(\yoneda\) is fully faithful, it reflects isomorphisms, thus: \[ \yoneda(x)\iso\yoneda(y)\iff x\iso y \]

Ninja Yoneda Lemma

Take some functor \(F:\dual{\cat C}\to\Set\) and let \(a\in\cat C\)
\[ \int^x \cat C(x, y) \times F(x) \iso F(y) \]

Proof

All of this is natural in \(G\) , since we don’t even touch it. Which tells us that \[ \nat\left( \int^y\cat C(\_,y)\times F(y), \_ \right)\iso \nat(F,\_) \]