Yoneda's Lemma

So, at last, we can get to Yoneda's lemma, as I [promised earlier][yoneda-promise]. What Yoneda's lemma does is show us how for many categories (in fact, most of the ones that are interesting) we can take the category C, and understand it using a structure formed from the functors from C to the category of sets. (From now on, we'll call the category of sets **Set**.)

So why is that such a big deal? Because the functors from C to the **Set** define a *structure* formed from sets that represents the properties of C. Since we have a good intuitive understanding of sets, that means that Yoneda's lemma
gives us a handle on how to understand all sorts of difficult structures by looking at the mapping from those structures onto sets. In some sense, this is what category theory is really all about: we've taken the intuition of sets and functions; and used it to build a general way of talking about structures. Our knowledge and intuition for sets can be applied to all sorts of structures.

As usual for category theory, there's yet another definition we need to look at, in order to understand the categories for which Yoneda's lemma applies.

If you recall, a while ago, I talked about something called *[small categories][smallcats]*: a small category is a categories for which the class of objects is a set, and not a proper class. Yoneda's lemma applies to a a class of categories slightly less restrictive than the small categories, called the *locally small categories*.

The definition of locally small categories is based on something called the Hom-classes of a category. Given a category C, the hom-classes of C are a partition of the morphisms in the category. Given any two objects a and b in Obj(C), the hom-class **Hom**(a,b) is the class of all morphisms f : a → b. If **Hom**(a,b) is a set (instead of a proper class), then it's called the hom-set of a and b.

A category C is *locally small* if/f all of the hom-classes of C are sets: that is, if for every pair of objects in Obj(C), the morphisms between them form a set, and not a proper class.

So, on to the lemma.

Suppose we have a locally small category C. Then for each object a in Obj(C), there is a *natural functor* corresponding to a mapping to **Set**. This is called the hom-functor of A, and it's generally written: *h*_a = **Hom**(a,-). *h*_a is a functor which maps from a object X in C to the set of morphisms **Hom**(a,x).

If F is a functor from C to **Set**, then for all a ∈ Obj(C), the set of natural transformations from *h*_a to F have a one-to-one correspondence with the elements of F(A): that is, the natural transformations - the set of all structure preserving mappings - from hom-functors of C to **Set** are isomorphic to the functors from C to **Set**.

So the functors from C to **Set** provide all of the structure preserving mappings from C to **Set**.

Yesterday, we saw a way how mapping *up* the abstraction hierarchy can make some kinds of reasoning easier. Yoneda says that for some things where we'd like to use our intuitions about sets and functions, we can also *map down* the abstraction hierarchy.

(If you saw my posts on group theory back at GM/BMs old home, this is a generalization of what I wrote about [the symmetric groups][symmetry]: the fact that every group G is isomorphic to a subgroup of the symmetric group on G.)

Coming up next: why computer science geeks like me care about this abstract nonsense? What does all of this gunk have to do with programming and programming languages? What the heck is a Monad? and more.

[symmetry]: http://goodmath.blogspot.com/2006/04/permutations-and-symmetry-groups.h…
[yoneda-promise]: http://scienceblogs.com/goodmath/2006/06/category_theory_natural_transf…
[smallcats]: http://scienceblogs.com/goodmath/2006/06/more_category_theory_getting_i…