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.

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

Annoying technology

WordPress’ native anti-spam measure Akismethas gone on the blink. Every comment I try posting to other WordPress sites is getting eaten. In particular, if the Angry Physicist reads this I hope he’ll try finding my recent attempt at commenting in his spam queue.

Anyhow, I’ll be doing some testing here to see if I can even comment on my own weblog. I do know that a few days ago one of my own posts’ trackbacks to an earlier post of mine got flagged, but I’d made numerous comments on other WordPress sites since then. Still, maybe Dr. Kaczynski had the right idea about technology.

[UPDATE]: Fifty tries of commenting last night and marking them as “not spam” and still nothing. WordPress uses this spam catcher which is allowed to capriciously decide that my IP address is a spammer with no notice, recourse for me, or accountability on their part. Akismet is broken and needs to be fixed.

June 6, 2007 Posted by | Uncategorized | 12 Comments