You are currently browsing the daily archive for July 12, 2008.
In our last post on category theory, we continued our exploration of universal properties, showing how they can be used to motivate the concept of natural transformation, the “right” notion of morphism between functors . In today’s post, I want to turn things around, applying the notion of natural transformation to explain generally what we mean by a universal construction. The key concept is the notion of representability, at the center of a circle of ideas which includes the Yoneda lemma, adjoint functors, monads, and other things — it won’t be possible to talk about all these things in detail (because I really want to return to Stone duality before long), but perhaps these notes will provide a key of entry into more thorough treatments.
Even for a fanatic like myself, it’s a little hard to see what would drive anyone to study category theory except a pretty serious “need to know” (there is a beauty and conceptual economy to categorical thinking, but I’m not sure that’s compelling enough motivation!). I myself began learning category theory on my own as an undergraduate; at the time I had only the vaguest glimmerings of a vast underlying unity to mathematics, but it was only after discovering the existence of category theory by accident (reading the introductory chapter of Spanier’s Algebraic Topology) that I began to suspect it held the answer to a lot of questions I had. So I got pretty fired-up about it then, and started to read Mac Lane’s Categories for the Working Mathematician. I think that even today this book remains the best serious introduction to the subject — for those who need to know! But category theory should be learned from many sources and in terms of its many applications. Happily, there are now quite a few resources on the Web and a number of blogs which discuss category theory (such as The Unapologetic Mathematician) at the entry level, with widely differing applications in mind. An embarrassment of riches!
Anyway, to return to today’s topic. Way back when, when we were first discussing posets, most of our examples of posets were of a “concrete” nature: sets of subsets of various types, ordered by inclusion. In fact, we went a little further and observed that any poset could be represented as a concrete poset, by means of a “Dedekind embedding” (bearing a familial resemblance to Cayley’s lemma, which says that any group can be represented concretely, as a group of permutations). Such concrete representation theorems are extremely important in mathematics; in fact, this whole series is a trope on the Stone representation theorem, that every Boolean algebra is an algebra of sets! With that, I want to discuss a representation theorem for categories, where every (small) category can be explicitly embedded in a concrete category of “structured sets” (properly interpreted). This is the famous Yoneda embedding.
This requires some preface. First, we need the following fundamental construction: for every category there is an opposite category , having the same classes of objects and morphisms as , but with domain and codomain switched (, and ). The function is the same in both cases, but we see that the class of composable pairs of morphisms is modified:
[is a composable pair in ] if and only if
and accordingly, we define composition of morphisms in in the order opposite to composition in :
Observation: The categorical axioms are satisfied in the structure if and only if they are in ; also, .
This observation is the underpinning of a Principle of Duality in the theory of categories (extending the principle of duality in the theory of posets). As the construction of opposite categories suggests, the dual of a sentence expressed in the first-order language of category theory is obtained by reversing the directions of all arrows and the order of composition of morphisms, but otherwise keeping the logical structure the same. Let me give a quick example:
Definition: Let be objects in a category . A coproduct of and consists of an object and maps , (called injection or coprojection maps), satisfying the universal property that given an object and maps , , there exists a unique map such that and .
This notion is dual to the notion of product. (Often, one indicates the dual notion by appending the prefix “co” — except of course if the “co” prefix is already there; then one removes it.) In the category of sets, the coproduct of two sets may be taken to be their disjoint union , where the injections are the inclusion maps of into (exercise).
Exercise: Formulate the notion of coequalizer (by dualizing the notion of equalizer). Describe the coequalizer of two functions (in the category of sets) in terms of equivalence classes. Then formulate the notion dual to that of monomorphism (called an epimorphism), and by a process of dualization, show that in any category, coequalizers are epic.
Principle of duality: If a sentence expressed in the first-order theory of categories is provable in the theory, then so is the dual sentence. Proof (sketch): A proof of a sentence proceeds from the axioms of category theory by applying rules of inference. The dualization of proves the dual sentence by applying the same rules of inference but starting from the duals of the categorical axioms. A formal proof of the Observation above shows that collectively, the set of categorical axioms is self-dual, so we are done.
Next, we introduce the all-important hom-functors. We suppose that is a locally small category, meaning that the class of morphisms between any two given objects is small, i.e., is a set as opposed to a proper class. Even for large categories, this condition is just about always satisfied in mathematical practice (although there is the occasional baroque counterexample, like the category of quasitopological spaces).
Let denote the category of sets and functions. Then, there is a functor
which, at the level of objects, takes a pair of objects to the set of morphisms (in ) between them. It takes a morphism of (that is to say, a pair of morphisms of ) to the function
Using the associativity and identity axioms in , it is not hard to check that this indeed defines a functor . It generalizes the truth-valued pairing we defined earlier for posets.
Now assume is small. From last time, there is a bijection between functors
and by applying this bijection to , we get a functor
This is the famous Yoneda embedding of the category . It takes an object to the hom-functor . This hom-functor can be thought of as a structured, disciplined way of considering the totality of morphisms mapping into the object , and has much to do with the Yoneda Principle we stated informally last time (and which we state precisely below).
- Remark: We don’t need to be small to talk about ; local smallness will do. The only place we ask that be small is when we are considering the totality of all functors , as forming a category .
Definition: A functor is representable (with representing object ) if there is a natural isomorphism of functors.
The concept of representability is key to discussing what is meant by a universal construction in general. To clarify its role, let’s go back to one of our standard examples.
Let be objects in a category , and let be the functor ; that is, the functor which takes an object of to the set . Then a representing object for is a product in . Indeed, the isomorphism between sets simply recapitulates that we have a bijection
between morphisms into the product and pairs of morphisms. But wait, not just an isomorphism: we said a natural isomorphism (between functors in the argument ) — how does naturality figure in?
Enter stage left the celebrated
Yoneda Lemma: Given a functor and an object of , natural transformations are in (natural!) bijection with elements .
Proof: We apply the “Yoneda trick” introduced last time: probe the representing object with the identity morphism, and see where takes it: put . Incredibly, this single element determines the rest of the transformation : by chasing the element around the diagram
phi_c hom(c, c) -----> Fc | | hom(f, c) | | Ff V V hom(b, c) -----> Fb phi_b
(which commutes by naturality of ), we see for any morphism in that . That the bijection
is natural in the arguments we leave as an exercise.
Returning to our example of the product as representing object, the Yoneda lemma implies that the natural bijection
is induced by the element , and this element is none other than the pair of projection maps
In summary, the Yoneda lemma guarantees that a hom-representation of a functor is, by the naturality assumption, induced in a uniform way from a single “universal” element . All universal constructions fall within this general pattern.
Example: Let be a category with products, and let be objects. Then a representing object for the functor is an exponential ; the universal element is the evaluation map .
Exercise: Let be a pair of parallel arrows in a category . Describe a functor which is represented by an equalizer of this pair (assuming one exists).
Exercise: Dualize the Yoneda lemma by considering hom-functors . Express the universal property of the coproduct in terms of representability by such hom-functors.
The Yoneda lemma has a useful corollary: for any (locally small) category , there is a natural isomorphism
between natural transformations between hom-functors and morphisms in . Using as alternate notation for the hom-set, the action of the Yoneda embedding functor on morphisms gives an isomorphism between hom-sets
the functor is said in that case to be fully faithful (faithful means this action on morphisms is injective for all , and full means the action is surjective for all ). The Yoneda embedding thus maps isomorphically onto the category of hom-functors valued in the category .
It is illuminating to work out the meaning of this last statement in special cases. When the category is a group (that is, a category with exactly one object in which every morphism is invertible), then functors are tantamount to sets equipped with a group homomorphism , i.e., a left action of , or a right action of . In particular, is the underlying set of , equipped with the canonical right action , where . Moreover, natural transformations between functors are tantamount to morphisms of right -sets. Now, the Yoneda embedding
identifies any abstract group with a concrete group , i.e., with a group of permutations — namely, exactly those permutations on which respect the right action of on itself. This is the sophisticated version of Cayley’s theorem in group theory. If on the other hand we take to be a poset, then the Yoneda embedding is tantamount to the Dedekind embedding we discussed in the first lecture.
Tying up a loose thread, let us now formulate the “Yoneda principle” precisely. Informally, it says that an object is determined up to isomorphism by the morphisms mapping into it. Using the hom-functor to collate the morphisms mapping into , the precise form of the Yoneda principle says that an isomorphism between representables corresponds to a unique isomorphism between objects. This follows easily from the Yoneda lemma.
But far and away, the most profound manifestation of representability is in the notion of an adjoint pair of functors. “Free constructions” give a particularly ubiquitous class of examples; the basic idea will be explained in terms of free groups, but the categorical formulation applies quite generally (e.g., to free monoids, free Boolean algebras, free rings = polynomial algebras, etc., etc.).
If is a set, the free group (q.v.) generated by is, informally, the group whose elements are finite “words” built from “literals” which are the elements of and their formal inverses, where we identify a word with any other gotten by introducing or deleting appearances of consecutive literals or . Janis Joplin said it best:
Freedom’s just another word for nothin’ left to lose…
— there are no relations between the generators of beyond the bare minimum required by the group axioms.
Categorically, the free group is defined by a universal property; loosely speaking, for any group , there is a natural bijection between group homomorphisms and functions
where denotes the underlying set of the group. That is, we are free to assign elements of to elements of any way we like: any function extends uniquely to a group homomorphism , sending a word in to the element in .
Using the usual Yoneda trick, or the dual of the Yoneda trick, this isomorphism is induced by a universal function , gotten by applying the bijection above to the identity map . Concretely, this function takes an element to the one-letter word in the underlying set of the free group. The universal property states that the bijection above is effected by composing with this universal map:
where the first arrow refers to the action of the underlying-set or forgetful functor , mapping the category of groups to the category of sets ( “forgets” the fact that homomorphisms preserve group structure, and just thinks of them as functions ).
- Remark: Some people might say this a little less formally: that the original function is retrieved from the extension homomorphism by composing with the canonical injection of the generators . The reason we don’t say this is that there’s a confusion of categories here: properly speaking, belongs to the category of groups, and to the category of sets. The underlying-set functor is a device we apply to eliminate the confusion.
In different words, the universal property of free groups says that the functor , i.e., the underlying functor followed by the hom-functor , is representable by the free group : there is a natural isomorphism of functors from groups to sets:
Now, the free group can be constructed for any set . Moreover, the construction is functorial: defines a functor . This is actually a good exercise in working with universal properties. In outline: given a function , the homomorphism is the one which corresponds bijectively to the function
i.e., is defined to be the unique map such that .
Proposition: is functorial (i.e., preserves morphism identities and morphism composition).
Proof: Suppose , is a composable pair of morphisms in . By universality, there is a unique map , namely , such that . But also has this property, since
(where we used functoriality of in the first equation). Hence . Another universality argument shows that preserves identities.
Observe that the functor is rigged so that for all morphisms ,
That is to say, that there is only one way of defining so that the universal map is (the component at of) a natural transformation !
The underlying-set and free functors , are called adjoints, generalizing the notion of adjoint in truth-valued matrix algebra: we have an isomorphism
natural in both arguments . We say that is left adjoint to , or dually, that is right adjoint to , and write . The transformation is called the unit of the adjunction.
Exercise: Define the construction dual to the unit, called the counit, as a transformation . Describe this concretely in the case of the free-underlying adjunction between sets and groups.
What makes the concept of adjoint functors so compelling is that it combines representability with duality: the manifest symmetry of an adjunction means that we can equally well think of as representing as we can as representing . Time is up for today, but we’ll be seeing more of adjunctions next time, when we resume our study of Stone duality.
[Tip of the hat to Robert Dawson for the Janis Joplin quip.]
I wish to bring the attention of our readers to the Carnival of Mathematics hosted by Charles at Rigorous Trivialities. I guess most of you already know about it. Among other articles/posts, one of Todd’s recent post Basic Category Theory I is part of the carnival. He followed it up with another post titled Basic Category Theory II. There will be a third post on the same topic some time soon. This sub-series of posts on basic category theory, if you recall, is part of the larger series on Stone Duality, which all began with Toward Stone Duality: Posets and Meets. Hope you enjoy the Carnival!