Franklin's Notes


The Yoneda lemma

The Yoneda lemma is as follows:

Yoneda lemma. For any functor $F:\mathsf C\to\mathsf{Set}$ whose domain $\mathsf C$ is locally small and any object $c\in\mathsf C$, there is a bijection that associates each natural transformation $\alpha:\mathsf C(c,-)\implies F$ to the element $\alpha_c(1_c)\in Fc$. This correspondence is natural in both $c$ and $F$.

Proof. Let $\alpha:\mathsf C(c,-)\implies F$ be a natural transformation and $f:c\to x$ be a morphism in $\mathsf C$. Consider the following diagram, which commutes by naturality of $\alpha$:

Because it commutes, we have that or, equivalently, Thus, the values of all components $\alpha_x$ at all elements $f\in\mathsf C(c,x)$ are determined by the values of $F$ and $\alpha_c (1_c)$.

Now suppose that $\alpha$ has not yet been determined, and we choose $\alpha_c (1_c)$ to be some arbitrary element of $Fc\in\mathsf Set$, and define the rest of the values of $\alpha$ via the formula $\alpha_x(f)=Ff\circ \alpha_c(1_c)$. To verify that $\alpha$ is actually a natural transformation by this definition, we must check that the following diagram commutes:

In other words, we must check that, for each $f:c\to x$ and $g:x\to y$, the equality or but this is simply a consequence of the functoriality of $F$.

Therefore, we have that every natural transformation $\alpha:\mathsf C(c,-)\implies F$ is uniquely determined by the value of $\alpha_c(1_c)$, and furthermore every possible choice of $\alpha_c(1_c)$ from the set $Fc$ induces a viable natural transformation. Hence the claimed bijection. $\blacksquare$

The Yoneda lemma has the following consequence regarding natural transformation between representable functors :

Proposition 1. The only natural transformations between representable functors $\mathsf C(x,-)\implies\mathsf C(y,-)$ are those given by pre-composition of some morphism $g:y\to x$.

Proof. Follows immediately from the above proof, letting $F=\mathsf C(y,-)$, in which case we have so that $\alpha_z$, when applied to some $f$, simply pre-composes it with $\alpha_x(1_x)=g:y\to x$. $\blacksquare$

The above descriptions of the Yoneda Lemma are a bit cryptic, so here's my attempt at a more intuitive explanation. A representable functor represented by $c$, when applied to some object $x$, essentially collects all instances of $c$ as a substructure of $x$ into a set. A natural transformation between representable functors represented by $c$ and $d$, which we would denote by $\alpha:\mathsf{C}(c,-)\implies\mathsf{C}(d,-)$, is basically a way of mapping instances of $c$ as a substructure of $x$ to instances of $d$ as a substructure of $x$, for all $x\in\mathsf{C}$.

According to this description, it's clear that it's impossible to find a natural transformation $\alpha:\mathsf{C}(c,-)\implies\mathsf{C}(d,-)$ if there exists some object $x\in\mathsf{C}$ such that $\mathsf{C}(c,x)$ is nonempty (i.e. $c$ is a substructure of $x$) and $\mathsf{C}(d,x)$ is empty (i.e. $d$ is not a substructure of $x$). If this were true for some $x$, there would be no way of putting substructures of type $c$ in correspondence with substructures of type $d$ - because there would be no instances of $d$ in $x$ to make the instances of $c$ in $x$ correspond to! So the following condition is necessary for a natural transformation $\alpha:\mathsf{C}(c,-)\implies\mathsf{C}(d,-)$ to exist:

It turns out that this is also a sufficient condition! For if the above implication is true, then we have that $\mathsf{C}(d,c)$ is nonempty (because $\mathsf{C}(c,c)$ contains $1_c$ and is therefore nonempty) meaning that there is a morphism $g:d\to c$, and the natural transformation $\alpha=-\circ g$, defined by post-composition with $g$, is an example of a natural transformation $\alpha:\mathsf{C}(c,-)\implies\mathsf{C}(d,-)$!

Proposition 2. There exists a natural transformation $\alpha:\mathsf{C}(c,-)\implies\mathsf{C}(d,-)$ if and only if for all $x\in\mathsf{C}$, which is true if and only if $\mathsf{C}(d,c)\ne\varnothing$.

What does this mean philosophically? It can be interpreted as saying that there exists a way of assigning each substructure of shape $c$ to a substructure of shape $d$ if and only if $c$ has a substructure of shape $d$!

category-theory

functors

back to home page