The Unapologetic Mathematician

Mathematics for the interested outsider

What does Yoneda’s Lemma mean?

As I promised, today I’ll try to explain what Yoneda’s Lemma really does for us.

First off, let’s think about functions of two variables. To be very explicit, think of the function f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N} defined by f(x,y)=xy. We can turn this into a function of one variable that returns another function. Specifically, if we write \mathbb{N}^\mathbb{N} for the set of functions from the natural numbers to themselves, we can write \overline{f}:\mathbb{N}\rightarrow\mathbb{N}^\mathbb{N}, where \left[\overline{f}(x)\right](y)=xy. That is, \overline{f}(3) is the function that sends y to 3y. This method of “Currying” (named for Haskell Curry) a function should be familiar if you’ve worked with functional programming languages like LISP, ML, or Haskell. There’s really a lot to be said about it in general, and I’ll get back to exploring it in more depth another time.

Anyhow, a similar statement goes for functors of more than one variable. Since such functors are “functorial in each variable”, we can stick an object into all but one slot and be left with a functor of the last slot. The thing is, this assignment is itself functorial.

Let’s focus on a functor F:\mathcal{A}\times\mathcal{B}\rightarrow\mathcal{C}. Then for any object A\in\mathcal{A} we have a functor \overline{F}(A)=F(A,\underline{\hphantom{X}}):\mathcal{B}\rightarrow\mathcal{C}. Now when we change the object A by applying a morphism \alpha:A_1\rightarrow A_2 we get a natural transformation \overline{F}(\alpha):\overline{F}(A_1)\rightarrow\overline{F}(A_2). It should have components \overline{F}(\alpha)_B:F(A_1,B)\rightarrow F(A_2,B). The clear choice is \overline{F}(\alpha)_B=F(\alpha,1_B), and indeed this is natural since the morphisms from \mathcal{A} commute with those from \mathcal{B}.

Now, strictly speaking this \overline{F} may not be a functor since we only know that \mathcal{C}^\mathcal{B} is a category when at least one of \mathcal{B} and \mathcal{C} is small, but the general idea should be clear.

Now to the situation at hand: we know that any category \mathcal{C} comes equipped with a functor \hom_\mathcal{C}:\mathcal{C}^\mathrm{op}\times\mathcal{C}\rightarrow\mathbf{Set}. We apply this Currying operation on each slot to get two “functors” \mathbf{y}:\mathcal{C}\rightarrow\mathbf{Set}^{\mathcal{C}^\mathrm{op}} and \mathbf{y'}:\mathcal{C}^\mathrm{op}\rightarrow\mathbf{Set}^\mathcal{C}. Of course, the targets are only sure to be categories when \mathcal{C} (and thus \mathcal{C}^\mathrm{op} as well) is small, but we’ll gloss over that point. What the Yoneda Lemma says is that these functors are fully faithful!

To see this, notice that \mathbf{y'} sends an object A\in\mathcal{C}^\mathrm{op} to the covariant functor h_A=\hom_\mathcal{C}(A,\underline{\hphantom{X}}), while \mathbf{y} sends an object A\in\mathcal{C} to the contravariant functor h'_A=\hom(\underline{\hphantom{X}},A). Since the objects of \mathcal{C} and \mathcal{C}^\mathrm{op} are the same, I hope that using A for both won’t be too confusing.

Now let’s take the statement of the (covariant) Yoneda Lemma and apply it to the functor h_B for some object B\in\mathcal{C}. It says that \mathrm{Nat}(h_A,h_B)\cong h_B(A)=\hom_\mathcal{C}(B,A)=\hom_{\mathcal{C}^\mathrm{op}}(A,B). But notice that \mathrm{Nat}(h_A,h_B) is \hom_{\mathbf{Set}^\mathcal{C}}(h_A,h_B) — the set of morphisms from h_A to h_B in the functor category \mathbf{Set}^\mathcal{C}. Now since \mathbf{y'} is a functor from \mathcal{C}^\mathrm{op} to \mathbf{Set}^\mathcal{C}, it acts on the hom sets, sending \hom_{\mathcal{C}^\mathrm{op}}(A,B) to \hom_{\mathbf{Set}^\mathcal{C}}(\mathbf{y'}(A),\mathbf{y'}(B)). And the Yoneda Lemma tells us that this is a bijection — the functor \mathbf{y'} is fully faithful!

And the same argument goes through for \mathbf{y}. Now we apply the contravariant Yoneda Lemma to see that \hom_{\mathbf{Set}^{\mathcal{C}^\mathrm{op}}}(\mathbf{y}(A),\mathbf{y}(B))=\mathrm{Nat}(h'_A,h'_B)\cong h'_B(A)=\hom_\mathcal{C}(A,B). The functor \mathbf{y} induces a bijection on each hom set, so it’s fully faithful too!

Now remember what the point of fully faithful functors is: they’re all about full subcategories. This means that any (small) category \mathcal{C} can be seen as a full subcategory of \mathbf{Set}^{\mathcal{C}^\mathrm{op}}. And full subcategories are nice because they just restrict the objects we’re interested in without throwing out any morphisms between those objects. So, the objects of any category can be seen as a special kind of contravariant \mathbf{Set}-valued functor on that category.

And now: which contravariant \mathbf{Set}-valued functors on a category \mathcal{C} are so special that they constitute objects of \mathcal{C} under this embedding? Well, as usual in category theory we’re interested in things up to isomorphism, so we should ask, “What contravariant set-valued functors are (naturally) isomorphic to one in the image of \mathbf{y}?”

These are just the representable functors.

The representable, contravariant, \mathbf{Set}-valued functors on a category \mathcal{C} constitute a full subcategory of all contravariant \mathbf{Set}-valued functors on \mathcal{C}, which is equivalent to the category \mathcal{C} itself.

And that’s why Yoneda’s Lemma is so amazing.

June 7, 2007 Posted by | Category theory | 15 Comments