The Unapologetic Mathematician

Mathematics for the interested outsider

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.

About these ads

June 6, 2007 - Posted by | Category theory

7 Comments »

  1. [...] does Yoneda’s Lemma mean? As I promised, today I’ll try to explain what Yoneda’s Lemma really does for [...]

    Pingback by What does Yoneda’s Lemma mean? « The Unapologetic Mathematician | June 7, 2007 | Reply

  2. [...] language and it looks pretty. So what? Hold on tight, because now I’m going to hit it with Yoneda’s Lemma (and its [...]

    Pingback by Groups and group actions — categorically « The Unapologetic Mathematician | June 8, 2007 | Reply

  3. [...] Weak Yoneda Lemma The Yoneda Lemma is so intimately tied in with such fundamental concepts as representability, universality, limits, [...]

    Pingback by The Weak Yoneda Lemma « The Unapologetic Mathematician | September 3, 2007 | Reply

  4. A question about Yoneda’s Lemma:

    You gave good motivation of the importance of Yoneda’s lemma by using it to deduce that the Yoneda map of a category C into Set^C is fully faithfull. However that result only seems to use a special case of Yoneda’s lemma, where both contravariant functors from C to Set are representable. Why is the general version of Yoneda’s lemma important?

    dan

    Comment by Dan | October 8, 2007 | Reply

  5. (after moving a comment over here.. there’s gotta be a better way of doing that)

    Well, that’s just one application. In general, Yoneda tells us a lot about representable functors, both covariant and contravariant. One thing it tells us is that any two representations of a functor are given by isomorphic objects.

    There’s really a lot more to it, the more you look. I tried to construct some sort of category analogue of bimodules over rings a while back, and all the associativities I needed turned out to be applications of Yoneda’s Lemma. It never really went anywhere, and I don’t remember where I put the notes, but I might dig it out for a post sometime.

    Comment by John Armstrong | October 8, 2007 | Reply

  6. thank you
    can you give me an example about Yonedas Lemma

    Comment by heshamtorkmanee | April 24, 2008 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 392 other followers

%d bloggers like this: