# Yoneda lemma

1. Apr 26, 2005

### Hurkyl

Staff Emeritus
This thing still confuses me. And it seems every reference I look at states it entirely differently.

I guess I've heard it stated in words -- there is a full embedding of C in Funct(Cop, Set). I know what all of the words mean, but I'm not sure if that helps yet.

There's one particular application of it that interests me, and I can't really see how to use it: there's a proof that shows the existance of a natural transformation Hom(_, A) --> Hom(_, B).

From this, they then conclude (by the Yoneda lemma!) that this natural transformation must come from a uniquely determined map A --> B. (The existance of this map is what interests me)

How does that follow?

2. Apr 27, 2005

### matt grime

I agree Yoneda is quite confusing, at least I thought so (I think I may still think so).

I'm not sure I can adequately explain the lemma itself, but the corollary is easy.

Yoneda states that if F is a covariant function, and G a representable functor, say G=(X,?)=Hom(X,?), then the natural trans from G to F are in bijection with F(X).

So, given two representable functors (A,?) and (B,?) the natural transformations are in bijection with (A,B), ie a map A to B uniquely determines a natural transformation.

Actually you have the contravariant statement, but it doesn't matter.

The bijection Nat( (X,?), F) comes about from the fact that the universality properties say it is sufficient to consider what the image of Id in (X,X) is sent to in F(X) by the natural transformation, and that this assignment is sufficient to determine the transformation.

But I admit freely that I don't really *get* Yoneda. Perhaps this would be a good discussion topic? Anyone sufficiently well versed in Mac Lane to explain pages 59-61 without having to read pages 1-58?

3. Apr 28, 2005

### Hurkyl

Staff Emeritus
Well, a way to prove the lemma struck me to work today -- you can show that any natural transformation η: Hom(_, A) --> K is completely determined by its action on the identity morphism of A, ηHom(A, A)(1A). Since this object function takes values in K(A), we get the natural isomorphsim.

This isn't entirely enlightening, though.

Wikipedia describes the Yoneda lemma as a vast generalization of Cayley's theorem, so maybe understanding will come from looking at it from that perspective?

I'm using the convention that fg is in arrow order. That is, codom f = dom g. (Writing this, I'm beginning to feel like I should also write function application on the right too! Ah well)

If C is a category that is a group, then the content of the Yoneda lemma is:

K : C --> Set is simply a group representation of C. That is, C acts on the set K(1) through the group action described by K.

Hom(_, 1) amounts to the Cayley representation of a group. Hom(1, 1) is simply the elements of the group, and Hom(f, 1) is simply the set function that gives right multiplication by f.

So, the Yoneda lemma says that the set of natural transformations Hom(_, 1) --> K is isomorphic to the set K(1). A natural transformation, here, is simply a function from Hom(1, 1) --> K(1) that respects the group action. There is a clear 1-1 correspondence between the natural transformations and the set K(1): the identity can go anywhere, and the rest is determined by the group action.

Categories, Allegories (Freyd, Scedrov) describes a concept of category action, and a Cayley representation for categories.

A (right-)category action of C on a set S is just like a group action. There's a "target" function S --> C, and any morphism f is a partial operation f^ on S. The domain of f^ is precisely those elements of S whose target is f's source.

So, you can think of each element of S as being labelled with an object of C, and any morphism A --> B maps any object labelled as A to an object labelled with B.

The Cayley representation is a functor C --> Set given by:
Cayley(A) is the set of all morphisms whose target is A
Given f:A-->B, Cayley(f) is a set function Cayley(A) --> Cayley(B) which is defined by right multiplication. IOW, Cayley(f)(g) = gf

In other words, it's just the category acting on itself! (on the right)

This is a faithful embedding, BTW.

So now, let's consider a functor K : C --> Set. Let's assume the objects in the image of K are all disjoint. Then, K gives rise to a right C-set. (That is, a set with a right action by C)
The set is simply the union of all the objects in the image of K.
The target operation is simply the inverse of K. That is, the target of any element of K(A) is A.
The action is given by K. If the target of x is A, and f:A-->B, then xf := K(f)(x)

So, K is describing a category action on some set.

Hom(_, A) is also describing a category action... on the set of all morphisms whose target is A. Note that this is a subset of the Cayley representation!

Now, any natural transformation Hom(_, A) --> K is simply a set function that respects the category action, and is again uniquely determined by its action on the identity morphism of A. So, we have the isomorphism Nat(Hom(_, A), K) ~ K(A). (It's K(A) because it has to respect the target operation!)

But the cool thing is that it's a natural isomorphism. (Right?) So we have this natural isomorphism Nat(Hom(_, ?), K) --> K(?). This is surely saying something important about the two representations of the category C! There's probably some really nice higher-dimensional picture that explains it all really nicely.

But for now, I think the key is understanding Nat(Hom(_, ?), K) --> K(?) as being natural in ?...

4. Apr 28, 2005

### mathwonk

here is an extract from my algebra book, which by the way is available in pdf format for the asking.

Our goal is the following converse assertion:
Theorem: Suppose the functors Hom(N,.) and Hom(M,.) are equivalent, via the isomorphisms ƒXom(N,X)-->Hom(M,X), for all modules X. Then N and M are isomorphic via a unique map a:M¨N such that for all X, ƒX = a*.
proof: How do we prove something so abstract and complicated? As usual, just look for a natural map a:M-->N, and then try to show it has an inverse. Now the only entirely naturally given maps are the identities 1N:N-->N, and 1M:M-->M. But we have by hypothesis an isomorphism ƒNom(N,N)-->Hom(M,N). This means we can transfer 1N over to a map a = ƒN(1N):M-->N. Since this is the only map obtainable from the assumptions, this must be it~ [Another way to guess the map a, is that if indeed ƒX = a*, then we can recover a as ƒN(1N) = a*(1N) = 1Noa = a. In particular this shows a is unique.]
The inverse map of course, should be (ƒM)^(-1)(1M):N-->M. To show these are indeed inverses, we must show their compositions are identities, using our hypotheses. The only hypotheses we have are those guaranteeing compatibility of ƒX and f*. That is, for each f:X-->Y, the two compositions: (f*oƒX)om(N,X)-->Hom(M,X)-->Hom(M,Y), and
(ƒYof*)om(N,X)-->Hom(N,Y)-->Hom(M,Y), are equal. Let's apply this to the case f = (ƒM)^(-1)(1M):N-->M. Then we have equality of the two compositions: (ƒM-1(1M)*0ƒN)om(N,N)¨Hom(M,N)¨Hom(M,M), and (ƒM)0(ƒM)^(-1)(1M)*)om(N,N)-->Hom(N,M)-->Hom(M,M). Applying the first of these compositions to the element 1N gives
(ƒM)^(-1)(1M)*oƒN)(1N) = (ƒM-1)(1M)o(ƒN(1N)). Applying the second composition gives (ƒM)0(ƒM-1)(1M)*)(1N) = ƒM(ƒM-1(1M)) = 1M. This proves that ƒM-1(1M) is left inverse to (ƒN(1N)). The proof it is also right inverse is similar.
To see that ƒN(1N)*(f) = ƒX(f) for all f in Hom(N,X), consider the two equal compositions: (ƒXof*)om(N,N)-->Hom(N,X)-->Hom(M,X), and
(f*oƒN)om(N,N)-->Hom(M,N)->Hom(M,X). Tracing 1N around both ways gives first (ƒXof*)(1N) = ƒX(1Nof) = ƒX(f), and then (f*oƒN)(1N) = f*(ƒN(1N)) = foƒN(1N) = (ƒN)(1N))*(f). QED.

actually i cant follow this myself as it is a flawed copy of my pdf file ina different font.

but the lemma is trivial.

as hurkyl guessed you just use the dientity map/

i.e. any map f:X--Y defines a map of functors from Hom(Y,.) to Hom(X,.) taking g to fog.

conversely any natural transformation from Hom(Y,.) to Hom(X,.) comes froma map f:X--<Y where f = the natural transformation applied to the identity map in Hom(Y,Y), yielding f in Hom(X,Y).

verifying this works is a trivial homework exercise in the definition of naturality, and it was a homework exercise in maurice auslanders class in first year aklgebra at brandeis in 1965.

I even got it right, which apparently is a great testimony to auslander's skill as a teacher. he made this incredibly abstract stuff look sooooo..... easy.

Last edited: Apr 28, 2005