The Unapologetic Mathematician

Mathematics for the interested outsider

Monoidal Functors and Natural Transformations

Now that we’ve got monoidal categories as the category-level analogue of monoids we need the category-level analogue of monoid homomorphisms. Recall that a monoid homomorphism is a function from the underlying set of one monoid to that of another that preserves the monoid compositions and identities. Since functors are the category-level version of functions, the natural thing to do is to ask for functors that preserves the monoidal category structure.

Of course it can’t be just that simple. As usual, we want to only ask for things to work out “up to isomorphism”. That is, given monoidal categories \mathcal{C} and \mathcal{D} — I’ll write \otimes and \mathbf{1} for both monoidal products and both identities and trust context to make clear which is which — we don’t want to insist that a functor F:\mathcal{C}\rightarrow\mathcal{D} satisfies F(\mathbf{1})=\mathbf{1} and F(A\otimes B)=F(A)\otimes F(B) and so on. Instead we want natural isomorphisms to replace these equations.

So there should be an isomorphism F_*:\mathbf{1}\rightarrow F(\mathbf{1}) in \mathcal{D}. As specified objects of \mathcal{D}, both \mathbf{1} and F(\mathbf{1}) are given by functors from the category \bullet to \mathcal{D}, and an isomorphism between the objects is automatically a natural isomorphism between these functors.

There should also be a natural isomorphism F_{(--)}:F(\underline{\hphantom{X}})\otimes F(\underline{\hphantom{X}})\rightarrow F(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}). That is, for every pair of objects A and B of \mathcal{C} there’s an isomorphism F_{(A,B)}:F(A)\otimes F(B)\rightarrow F(A\otimes B) in \mathcal{D}, and these commute with arrows A\rightarrow A' and B\rightarrow B' in \mathcal{C}.

And, strictly speaking, we need such a natural isomorphism for every functor built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1}. For example, there should be a natural isomorphism F_{(-((1-)-))}:F(\underline{\hphantom{X}})\otimes((F(\mathbf{1})\otimes F(\underline{\hphantom{X}}))\otimes F(\underline{\hphantom{X}}))\rightarrow F(\underline{\hphantom{X}}\otimes((\mathbf{1}\otimes\underline{\hphantom{X}})\otimes\underline{\hphantom{X}})). And, of course, all these isomorphisms should fit together well. This makes for a lot of data, and how are we going to manage it all?

The Coherence Theorem will come to our rescue! There’s a unique natural isomorphism built from \alphas, \lambdas, and \rhos taking (say) \underline{\hphantom{X}}\otimes((\mathbf{1}\otimes\underline{\hphantom{X}})\otimes\underline{\hphantom{X}}) to \underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}) in \mathcal{C} (call it \gamma) and another unique such isomorphism in \mathcal{D} (call it \delta). So we can build the above isomorphism F_{(-((1-)-))} as F(\gamma^{-1})\circ F_{(-(--))}\circ\delta. Now all we need is the natural isomorphisms for completely right-parenthesized products with no slots filled with identity objects.

And we can build these from the natural isomorphisms F_{(--)} and F_* (and make sure all the isomorphisms fit together well) — as long as these satisfy a few coherence conditions to make sure they play well with the associator and other structural isomorphisms:
Coherence Conditions for Monoidal Functors

Similarly to the terminology for monoidal categories, if the natural isomorphisms F_* and F_{(--)} are actually identities (and thus so are all the others built from them) then we call F a “strict monoidal functor”. Alternatively, some prefer to call what I’ve defined above a “weak monoidal functor”.

We aren’t quite done yet, though. At the level of sets we have sets and functions between them. Up at the category level we have categories, functors, and now also natural transformations, so we should also focus on the natural transformations that preserve monoidal structures. A monoidal natural transformation between monoidal functors \eta:F\rightarrow G is a natural transformation satisfying G_{(A,B)}\circ(\eta_A\otimes\eta_B)=\eta_{A\otimes B}\circ F_{(A,B)} and G_*=\eta_\mathbf{1}\circ F_*.

Now we have all the analogous tools for monoidal categories as we used for just plain categories to define equivalence. We say that two monoidal categories \mathcal{C} and \mathcal{D} are monoidally equivalent if there are monoidal functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} with monoidal natural isomorphisms \eta:1_\mathcal{C}\rightarrow G\circ F and \epsilon:F\circ G\rightarrow1_\mathcal{D}.

It’s useful to verify at this point that the set of isomorphism classes of objects of a monoidal category \mathcal{C} form a monoid C with \otimes as its composition and (the isomorphism class of) \mathbf{1} as identity, a monoidal functor F:\mathcal{C}\rightarrow\mathcal{D} induces a homomorphism of monoids f:C\rightarrow D, and an equivalence between \mathcal{C} and \mathcal{D} induces an isomorphism between the monoids C and D. These are all pretty straightforward, and they’re good for getting used to the feel of how equalities weaken to isomorphisms as we move from sets to categories.

June 30, 2007 Posted by | Category theory | 1 Comment

Mac Lane’s Coherence Theorem

Okay, as I promised yesterday, I’m going to prove the Coherence Theorem for monoidal categories today. That is, any two natural transformations built from \alpha, \lambda, and \rho between any two functors built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1} are equal once we know the pentagon and triangle identities are satisfied.

Here’s an example. Brace yourself for the diagram.
A Diagram for the Coherence Theorem

Okay, the outer pentagon is the pentagon identity for the quadruple (A,B,\mathbf{1},\mathbf{1}). The triangles in the upper-right and on the left are the triangle identity. The quadrilaterals are all naturality squares for \alpha and \rho. And the last triangle near the center is the identity we’re proving. It says that \rho_{A\otimes B}=(1_A\otimes\rho_B)\circ\alpha_{A,B,\mathbf{1}}. There’s a similar diagram to show that \lambda_A\otimes1_B=\lambda_{A\otimes B}\circ\alpha_{\mathbf{1},A,B}, which you should find.

Now we’re ready to really get down to work. We can get any functor built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1} by writing down a parenthesized sequence of multiplications like \underline{\hphantom{X}}\otimes((\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}))\otimes\underline{\hphantom{X}}) and filling some of the open slots with \mathbf{1}.

First, let’s get rid of those identity objects. Each of them shows up either to the right or to the left of some product symbol, so we can use either a \rho or a \lambda to remove it, but there’s some choice involved here. For example, near the \mathbf{1} we’re trying to get rid of the functor might look like (\underline{\hphantom{X}}\otimes\mathbf{1})\otimes\underline{\hphantom{X}}. We can either use a \rho right away, or we can hit it with an associator and then use a \lambda. The triangle identity says that these two ways of removing the \mathbf{1} are the same. Similarly, if nearby the functor looks like (\mathbf{1}\otimes\underline{\hphantom{X}})\otimes\underline{\hphantom{X}} or (\underline{\hphantom{X}}\otimes\underline{\hphantom{X}})\otimes\mathbf{1} we have some leeway, but the two new triangles we proved above say we’ll get the same natural transformation to remove the \mathbf{1} either way. The upshot is that any two natural transformations we use to reach a functor without any slots filled with identity objects are the same.

So now we just have to deal with functors built from monoidal products. Each of them is just a different way to parenthesize a multiplication of some number of variables, and the associator (or its inverse) lets us move between different ways of parenthesizing the same number of variables. One convenient way of parenthesizing is to have all pairs of parentheses at the end, like \underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}))), and what we’re going to do is try to make every functor look like this.

Now imagine a big diagram with all the different ways of parenthesizing a product of n terms as its vertices, and draw an arrow from one vertex to another if you can go from the first to the second by applying one associator. When n=4, this is just the pentagon diagram. Try actually drawing the one for n=5 (there should be 14 vertices). We’re allowed to walk forwards or backwards along the arrows, since the associator is an isomorphism. Every path is a natural isomorphism between the two functors at its ends, since it’s a composition of natural isomorphisms. What the Coherence Theorem says is that any two paths between the same two points give the same natural isomorphism.

Let’s say that we have a path from a vertex V in this diagram to a vertex W, which might consist of some forward arrows and some reverse arrows. Each time we change directions from forward to reverse we can pick a path using only forward arrows from the turning point to the vertex R, which has all its parentheses to the right. Here’s a sketch of what I’m talking about
Another Diagram for the Coherence Theorem
Each arrow here is a path consisting of only forward arrows. We start with the path along the top. At the two points where we change from walking forwards along the arrows to walking backwards, we pick a path made up of only forward arrows to the point R. Now the path we started with is the same as walking forwards a step from V, down to R, back the way we just came (undoing the isomorphism), forwards to the next juncture, down to R and back, and on to W.

It seems we’ve made our lives more complicated by adding in these side-trips to R, just to undo them immediately, but something really nice happens. There are two paths here from the middle point of our original path down to R, and each of them consists only of forward arrows. If these two paths are the same, I can cut out that whole middle loop. Then our path walks straight down from V to R along forward arrows, then back up to W along backward arrows. If there are more changing points in the original path, then there are just more loops to cut out. So if any two paths from a vertex to R consisting of only forward arrows give the same isomorphism, then every path from V to W is the same as one passing through R. And even better, the paths from V and W to R themselves consist entirely of forward arrows, so there’s only one of each of them. That is, if we can show that any two paths made of forward arrows from an arbitrary vertex V to the fixed vertex R give the same natural isomorphism, then we’re done.

Now here’s where it gets a bit messy. We’ll need to use inductions on both the number of terms in our functors and on how close they are to R. We know the Coherence Theorem works up to n=4 terms, because that’s the pentagon identity. We’ll prove it for n terms assuming it’s known for fewer than n terms and work our way up. Similarly, for a fixed n we’ll start by establishing the result for the vertices closest to R and work our way out.

Let’s start with a functor V, which is the product of functors V_1 and V_2. Let \beta and \gamma be two arrows out of V to functors X and Y, respectively, which them continue on to paths to R. We need to find a Z and paths from X and Y to Z to make the square commute. Since X and Y are both closer than V to R, we can assume that both paths from X to R in the diagram give the same isomorphism, as do both paths from Y to R. Then since Z is even closer to R we can assume there’s only one transformation from Z to R, so the result follows for V. Here’s another sketch:
Yet Another Diagram for the Coherence Theorem

If \beta and \gamma are already the same there’s nothing to be done. Pick Z=X=Y and go home. Otherwise there are three possibilities for \beta

  • \beta applies an associator inside V_1
  • \beta applies an associator inside V_2
  • V_1=V_{11}\otimes V_{12}, and \beta:(V_{11}\otimes V_{12})\otimes V_2\rightarrow V_{11}\otimes(V_{12}\otimes V_2) is an associator

and the same three for \gamma.

If \beta and \gamma both act within V_1 or within V_2 then we’re done because of the induction on the number of terms. If \beta acts in one factor and \gamma in the other then they commute because \otimes is a functor of two variables. All that’s left to see is if \beta is an associator and \gamma acts in either V_1 or V_2.

If \gamma acts inside V_2, sending it to V_2', then we get (1_{V_{11}}\otimes(1_{V_{12}}\otimes\gamma))\circ\alpha_{V_{11},V_{12},V_2}=\alpha_{V_{11},V_{12},V_2'}\circ((V_{11}\otimes V_{12})\otimes\gamma) by the naturality of \alpha. A similar statement holds if \gamma acts inside V_{11} or V_{12}. Finally, if \gamma is itself the associator \alpha_{V_{111},V_{112},V_{12}}, then \beta and \gamma are actually the first steps around the pentagon identity, so we can use the far vertex of the pentagon as our Z.

And after all these cases, we’re done. If two paths start out differently from V we can guide them back together so that the square where they differed commutes, and we can keep doing this until we get to R. Thus there’s only one natural isomorphism built from associators taking a functor the the fully right-parenthesized functor on the same number of terms.

Thus there’s only one natural isomorphism built from associators between any two functors built from monoidal products on the same number of terms.

Thus any two natural transformations built from \alpha, \lambda, and \rho between any two functors built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1} are equal, given that the pentagon and the triangle identities are satisfied.

Now breathe.

June 29, 2007 Posted by | Category theory | 15 Comments

Monoidal categories

We know that monoids are one of the most basic algebraic structures on which many others are built. Naturally, they’re one of the first concepts we want to categorify. That is, we want to consider a category with some extra structure making its objects behave like a monoid.

So let’s charge ahead and try to write down what this means. We need some gadget that takes two objects and spits out another. The natural thing to use here is a functor \underline{\hphantom{X}}\otimes\underline{\hphantom{X}}:\mathcal{C}\times\mathcal{C}\rightarrow\mathcal{C}. We’re using the same symbol we did for tensor products — and for a good reason — but we don’t need it to be that operation.

Now we need this functor to satisfy a couple rules to make it like a monoid multiplication. It should be associative, so (A\otimes B)\otimes C=A\otimes(B\otimes C) for all objects A, B, and C in \mathcal{C}. There should be an “identity” object \mathbf{1} so that A\otimes\mathbf{1}=A=\mathbf{1}\otimes A for all objects A\in\mathcal{C}.

We know that the natural numbers \mathbb{N} form a monoid under multiplication with 1 as the identity, and we know that the category \mathbf{FinSet} of finite sets categorifies the natural numbers with Cartesian products standing in for multiplication. So let’s look at it to verify that everything works out. We use \times as our monoidal structure and see that (A\times B)\times C=A\times(B\times C)… but it doesn’t really. On the left we have the set \{((a,b),c)|a\in A,b\in B,c\in C\}, and on the right we have the set \{(a,(b,c))|a\in A,b\in B,c\in C\}, and these are not the same set. What happened?

The problem is that the results are not the same, but are only isomorphic. The monoid conditions are equations

  • (a\cdot b)\cdot c=a\cdot(b\cdot c)
  • a\cdot1=a=1\cdot a

So when we categorify the concept we need to replace these by natural isomorphisms

  • \alpha_{A,B,C}:(A\otimes B)\otimes C\rightarrow A\otimes(B\otimes C)
  • \lambda_A:\mathbf{1}\otimes A\rightarrow A
  • \rho_A:A\otimes\mathbf{1}\rightarrow A

These say that while the results of the two functors on either side of the arrow might not be the same, they are isomorphic. Even better, the isomorphism should commute with arrows in \mathcal{C}, as described by the naturality squares. For instance, if we have an arrow f:A_1\rightarrow A_2 in \mathcal{C} then we can apply it before or after \lambda: \lambda_{A_2}\circ(1_\mathbf{1}\otimes f)=f\circ\lambda_{A_1} as arrows from \mathbf{1}\otimes A_1 to A_2.

As a side note, the isomorphism \alpha is often called the “associator”, but I don’t know of a similarly catchy name for the other two isomorphisms. When we’ve “weakened” the definition of a monoidal category like this we sometimes call the result a “weak monoidal category”. Alternatively — and this is the convention I prefer — we call these the monoidal categories, and the above definition with equalities instead of just isomorphisms gives “strict monoidal categories”.

Unfortunately, we’re not quite done with revising our definition yet. We’ll be taking our tensor products and identity objects and stringing them together to make new functors, and similarly we’ll be using these natural isomorphisms to relate these functors, but we need to make sure that the relationship doesn’t depend on how we build it from the basic natural isomorphisms. An example should help make this clearer.

Pentagon Diagram

This is the pentagon diagram. The vertices of the pentagon are the five different ways of parenthesizing a product of four different objects. The edges are single steps, each using one associator. Around the left, we apply the associator to the first three factors and leave D alone (use the identity arrow 1_D), then we apply the associator to A, B\otimes C, and D, and finally we apply the associator to the last three factors and leave A alone. Around the right, we apply the associator twice, first to A\otimes B, C, and D, and then to A, B, and C\otimes D. So we have two different natural isomorphisms from ((\underline{\hphantom{X}}\otimes\underline{\hphantom{X}})\otimes\underline{\hphantom{X}})\otimes\underline{\hphantom{X}} to \underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}})). And we have to insist that they’re the same.

Here’s another example:
Triangle Diagram

This triangle diagram is read the same as the pentagon above: we have two different natural transformations from (\underline{\hphantom{X}}\otimes\mathbf{1})\otimes\underline{\hphantom{X}} to \underline{\hphantom{X}}\otimes\underline{\hphantom{X}}, and we insist that they be the same.

What’s happened is we’ve replaced equations at the level of sets with (natural) isomorphisms at the level of the category, but these isomorphisms are now subject to new equations. We’ve seen two examples of these new equations, and it turns out that all the others follow from these two. I’ll defer the justification of this “coherence theorem” until later.

For now, let’s go back to \mathbf{FinSet} We can use the universal property of the product to give an arrow \alpha_{A,B,C}:(A\times B)\times C\rightarrow A\times(B\times C), and we can verify that these form the components of a natural isomorphism. Similarly, we can use the singleton * as an identity object and determine isomorphisms \lambda_A:*\times A\rightarrow A and \rho_A:A\times *\rightarrow A. They do indeed satisfy the pentagon and triangle identities above, making \mathbf{FinSet} into a monoidal category.

In fact, you could establish the associator and other isomorphisms for \mathbf{FinSet} by looking at the elements of the sets and defining particular functions, but if we do it all by the universal properties of products and terminal objects we get a great generalization: any category with finite products (in particular, pairwise products and a terminal object) can use them as a monoidal structure. Dually, any category with finite coproducts can use them as a monoidal structure.

For any ring R, the category R\mathbf{-mod-}R of all R-R bimodules has a monoidal structure given by \otimes_R, and because of this monoidal categories are often called “tensor categories” and the monoidal structure a tensor product.

June 28, 2007 Posted by | Category theory | 22 Comments

This Week’s Finds #253

I haven’t been flagging the new postings of >TWF for a while, though I really should have. Anyhow, this “week” Baez talks about what exceptional Lie algebras have to do with elementary particles.

June 28, 2007 Posted by | Uncategorized | Leave a comment


Categorification is a big, scary word that refers to a much simpler basic idea than you’d expect, and it’s also huge business right now. There’s a lot of this going on at The n-Category Café, for instance. Both knot Floer homology and Khovanov homology are examples of categorifications that seem to be popular with the crew at the Secret Blogging Seminar. John Baez has a bunch of papers circling around “higher-dimensional algebra”, which is again about categorification.

So what is categorification? Well, as I said the core idea’s not really that hard to grasp, but it’s even easier to understand by first considering the reverse process: decategorification. And decategorification is best first approached through an example.

Since this post will be going to this fortnight’s Carnival, I’ll be saying a fair amount that I’ve said before and linking back to definitions most regular readers should know offhand. It might seem slower, but I’ll be back up to the regular rhetorical pace tomorrow. Or you could take it as a bit of review, just to make sure you’re on top of things. Because of this, the post is going to get long, so I’ll put it behind a jump.
Continue reading

June 27, 2007 Posted by | Category theory | 13 Comments

Representations and Universals and Colimits (oh, my!)

Let’s look at universal arrows a bit more closely. If we have a functor F:\mathcal{D}\rightarrow\mathcal{C}, an object C\in\mathcal{C}, and a universal arrow u:C\rightarrow F(U), then we can take any arrow f:U\rightarrow D and form the composition F(f)\circ u:C\rightarrow F(D). The universal condition says that to every arrow d:C\rightarrow F(D) corresponds a unique f:U\rightarrow D so that d=F(f)\circ u. That is, there is a bijection \eta_D:\hom_\mathcal{C}(C,F(D))\cong\hom_\mathcal{D}(U,D) for every D\in\mathcal{D}.

It’s even better than that, though: these bijections commute with arrows in \mathcal{D}. That is, if we have f:D_1\rightarrow D_2 then the naturality condition f\circ\eta_{D_1}(d)=\eta_{D_2}(F(f)\circ d) holds for all d:C\rightarrow D_1. This makes the \eta_D into the components of a natural isomorphism \eta:\hom_\mathcal{C}(C,F(\underline{\hphantom{X}}))\rightarrow\hom_\mathcal{D}(U,\underline{\hphantom{X}})=h_U. That is, a universal arrow from C to F is a representation of the functor \hom_\mathcal{C}(C,F(\underline{\hphantom{X}})):\mathcal{D}\rightarrow\mathbf{Set}.

Conversely, let’s say we have a representable functor K:\mathcal{D}\rightarrow\mathbf{Set}, with representation \eta_D:h_U\rightarrow K(D). Yoneda’s lemma tells us that this natural transformation corresponds to a unique element of K(U), which as usual we think of as an arrow u:*\rightarrow K(U). So a representation of a functor is a universal arrow in \mathbf{Set}.

So, representations of functors are the same as universal arrows. Colimits are special kinds of universal arrows, and since a universal arrow is an initial object in an apropriate comma category it is a colimit. Representations are universals are colimits.

If we swap the category \mathcal{C} for the dual category \mathcal{C}^\mathrm{op}, we change limits into colimits, couniversals into universals, and contravariant representations into covariant ones. All the reasoning above applies just as well to \mathcal{C}^\mathrm{op}. Thus, we see that in \mathcal{C} representations of contravariant functors are couniversals are limits.

There’s actually yet another concept yet to work into this story, but I’m going to take a break from it to flesh out another area of category theory for a while.

June 26, 2007 Posted by | Category theory | Leave a comment

Universal arrows and universal elements

Remember that we defined a colimit as an initial object in the comma category (F\downarrow\Delta), and a limit as a terminal object in the comma category (\Delta\downarrow F). It turns out that initial and terminal objects in more general comma categories are also useful.

So, say we have a categories \mathcal{C} and \mathcal{D}, an object C\in\mathcal{C}, and a functor F:\mathcal{D}\rightarrow\mathcal{C}, so we can set up the category (C\downarrow F). Recall that an object of this category consists of an object D\in\mathcal{D} and an arrow f:C\rightarrow F(D), and a morphism from f_1:C\rightarrow F(D_1) to f_2:C\rightarrow F(D_2) is an arrow d:D_1\rightarrow D_2 such that f_2=F(d)\circ f_1.

Now an initial object in this category is an object U of \mathcal{D} and an arrow u:C\rightarrow F(U) so that for any other arrow f:C\rightarrow F(D) there is a unique arrow d:U\rightarrow D satisfying f=F(d)\circ u. We call such an object, when it exists, a “universal arrow from C to F“. For example, a colimit of a functor F is a universal arrow (in \mathcal{C}^\mathcal{J}) from F to \Delta.

Dually, a terminal object in (F \downarrow C) consists of an object U\in\mathcal{D} and an arrow u:F(U)\rightarrow C so that for any other arrow f:F(D)\rightarrow C there exists a unique arrow d:D\rightarrow U satisfying f=u\circ F(d). We call this a “couniversal arrow from F to C“. A limit of a functor F is a couniversal arrow from \Delta to F.

Here’s another example of a universal arrow we’ve seen before: let’s say we have an integral domain D and the forgetful functor U:\mathbf{Field}\rightarrow\mathbf{Dom} from fields to integral domains. That is, U takes a field and “forgets” that it’s a field, remembering only that it’s a ring with no zerodivisors. An object of (D\rightarrow U) consists of a field F and a homomorphism of integral domains D\rightarrow U(F). The universal such arrow is the field of fractions of D.

As a more theoretical example, we can consider a functor F:\mathcal{C}\rightarrow\mathbf{Set} and the comma category (*\downarrow F). Since an arrow x:*\rightarrow X in \mathbf{Set} is an element of the set X, we call a universal arrow from * to F a “universal element” of F. It consists of an object U\in\mathcal{C} and an element u\in F(U) so that for any other element c\in F(C) we have a unique arrow f:U\rightarrow C with \left[F(f)\right](u)=c.

As an example, let’s take N to be a normal subgroup of a group G. For any group H we can consider the set of group homomorphisms f:G\rightarrow H that send every element of N to the identity element of H. Verify for yourself that this gives a functor F:\mathbf{Grp}\rightarrow\mathbf{Set}. Any such homomorphism factors through the projection \pi_{(G,N)}:G\rightarrow G/N, so the group G/N and the projection \pi_{(G,N)} constitute a universal element of F. We used cosets of N to show that such a universal element exists, but everything after that follows from the universal property.

Another example: let M_1 be a right module over a ring R, and M_2 be a left R-module. Now for any abelian group A we can consider the set of all R-middle-linear functions from M_1\times M_2 to A — functions f which satisfy f(m_1+m_1',m_2)=f(m_1,m_2)+f(m_1',m_2), f(m_1,m_2+m_2')=f(m_1,m_2)+f(m_1,m_2'), and f(m_1r,m_2)=f(m_1,rm_2). This gives a functor from \mathbf{Ab} to \mathbf{Set}, and the universal element is the function M_1\times M_2\rightarrow M_1\otimes_RM_2 to the tensor product.

The concept of a universal element is a special case of a universal arrow. Very interestingly, though, when \mathcal{C} is locally small (as it usually is for us)$ the reverse is true. Indeed, if we’re considering an object C\in\mathcal{C} and a functor F:\mathcal{D}\rightarrow\mathcal{C} then we could instead consider the set * and the functor \hom_\mathcal{C}(C,F(\underline{\hphantom{X}})):\mathcal{D}\rightarrow\mathbf{Set}. Universal arrows for the former setup are equivalent to universal elements in the latter.

June 25, 2007 Posted by | Category theory | 2 Comments

Taking limits is functorial

It turns out that in that happy situation where a category \mathcal{C} has \mathcal{J}-limits for some small category \mathcal{J}, the assignment of a limit \varprojlim_\mathcal{J}F to a functor F is itself a functor from \mathcal{C}^\mathcal{J} to \mathcal{C}. That is, given functors F and G from \mathcal{C} to \mathcal{J} and a natural transformation \eta:F\rightarrow G we get an arrow \varprojlim_\mathcal{J}\eta:\varprojlim_\mathcal{J}F\rightarrow\varprojlim_\mathcal{J}G, and composition of natural transformations goes to composition of the limit arrows.

Since the proof of this is so similar to how we established limits in categories of functors, I’ll just refer you back to that and suggest this as practice with those techniques.

June 24, 2007 Posted by | Category theory | 2 Comments

Limits in functor categories

Today I want to give a great example of creation of limits that shows how useful it can be. For motivation, take a set X, a monoid M, and consider the set M^X of functions from X to M. Then M^X inherits a monoid structure from that on M. Just define \left[f_1f_2\right](x)=f_1(x)f_2(x) and take the function sending every element to the identity of M as the identity of M^X. We’re going to do the exact same thing in categories, but with having limits instead of a monoid structure.

As a preliminary result we need to note that if we have a set of categories \mathcal{C}_s for s\in S each of which has \mathcal{J}-limits, then the product category \prod\limits_{s\in S}\mathcal{C}_s has \mathcal{J}-limits. Indeed, a functor from \mathcal{J} to the product consists of a list of functors from \mathcal{J} to each category \mathcal{C}_s, and each of these has a limiting cone. These clearly assemble into a limiting cone for the overall functor.

The special case we’re interested here is when all \mathcal{C} are the same category. Then the product category \prod\limits_S\mathcal{C} is equivalent to the functor category \mathcal{C}^S, where we consider S as a discrete category. If \mathcal{C} has \mathcal{J}-limits, then so does \mathcal{C}^S for any set S.

Now, any small category \mathcal{S} has a discrete subcategory |\mathcal{S}|: its set of objects. There is an inclusion functor i:\left|\mathcal{S}\right|\rightarrow\mathcal{S}. This gives rise to a functor \mathcal{C}^i:\mathcal{C}^\mathcal{S}\rightarrow\mathcal{C}^{|\mathcal{S}|}. A functor F:\mathcal{S}\rightarrow\mathcal{C} gets sent to the functor F\circ i:\left|\mathcal{S}\right|\rightarrow\mathcal{C}. I claim that \mathcal{C}^i creates all limits.

Before I prove this, let’s expand a bit to understand what it means. Given a functor F:\mathcal{J}\rightarrow\mathcal{C}^\mathcal{S} and an object S\in\mathcal{S} we can get a functor \left[F(\underline{\hphantom{X}})\right](S):\mathcal{J}\rightarrow\mathcal{C} that takes an object J\in\mathcal{J} and evaluates F(J) at S. This is an |\mathcal{S}|-indexed family of functors to \mathcal{C}, which is a functor to \mathcal{C}^{|\mathcal{S}|}. A limit of this functor consists of a limit for each of the family of functors. The assertion is that if we have such a limit — a \mathcal{J}-limit in \mathcal{C} for each object of \mathcal{S} — then these limits over each object assemble into a functor in \mathcal{C}^\mathcal{S}, which is the limit of our original F.

We have a limiting cone \lambda_{J,S}:L(S)\rightarrow[F(J)](S) for each object S\in\mathcal{S}. What we need is an arrow L(s):L(S_1)\rightarrow L(S_2) for each arrow s:S_1\rightarrow S_2 in \mathcal{S} and a natural transformation L\rightarrow F(J) for each J\in\mathcal{J}. Here’s the diagram we need:
Pointwise Limits Diagram

We consider an arrow j:J_1\rightarrow J_2 in \mathcal{J}. The outer triangle is the limiting cone for the object S_1, and the inner triangle is the limiting cone for the object S_2. The bottom square commutes because F is functorial in \mathcal{S} and \mathcal{J} separately. The two diagonal arrows towards the bottom are the functors F(J_1) and F(J_2) applied to the arrow s. Now for each J we get a composite arrow \left[F(J)\right](s)\circ\lambda_{J,S_1}:L(S_1)\rightarrow\left[F(J)\right](S_2), which is a cone on \left[F(\underline{\hphantom{X}})\right](S_2). Since \lambda_{J,S_2}:L(S_2)\rightarrow\left[F(J)\right](S_2) is a limiting cone on this functor we get a unique arrow L(s):L(S_1)\rightarrow L(S_2).

We now know how L must act on arrows of \mathcal{S}, but we need to know that it’s a functor — that it preserves compositions. To do this, try to see the diagram above as a triangular prism viewed down the end. We get one such prism for each arrow s, and for composable arrows we can stack the prisms end-to-end to get a prism for the composite. The uniqueness from the universal property now tells us that such a prism is unique, so the composition must be preserved.

Finally, for the natural transformations required to make this a cone, notice that the sides of the prism are exactly the naturality squares for a transformation from L to F(J_1) and F(J_2), so the arrows in the cones give us the components of the natural transformations we need. The proof that this is a limiting cone is straightforward, and a good exercise.

The upshot of all this is that if \mathcal{C} has \mathcal{J}-limits, then so does \mathcal{C}^\mathcal{S}. Furthermore, we can evaluate such limits “pointwise”: \left[\varprojlim_\mathcal{J}F\right](S)=\varprojlim_\mathcal{J}(F(S)).

As another exercise, see what needs to be dualized in the above argument (particularly in the diagram) to replace “limits” with “colimits”.

June 23, 2007 Posted by | Category theory | 9 Comments

Preservation of limits

Yesterday I talked about functors that create limits. It’s theoretically interesting, but a different condition that’s often more useful in practice is that a functor “preserve” limits.

Given a small category \mathcal{J}, a functor G:\mathcal{C}\rightarrow\mathcal{D} preserves \mathcal{J}-limits if whenever \lambda_J:L\rightarrow F(J) is a limiting cone for a functor F:\mathcal{J}\rightarrow\mathcal{C} then G(\lambda_J):G(L)\rightarrow G(F(J)) is a limiting cone for the functor G\circ F:\mathcal{J}\rightarrow\mathcal{D}. A functor is called “continuous” if it preserves all small limits. By the existence theorem, a functor is continuous if and only if it preserves all (small) products and pairwise equalizers.

As stated above, this condition is different than creating limits, but the two are related. If \mathcal{D} is a category which has \mathcal{J}-limits and G:\mathcal{C}\rightarrow\mathcal{D} is a functor which creates \mathcal{J}-limits, then we know \mathcal{C} also has \mathcal{J}-limits. I claim that \mathcal{G} preserves these limits as well. More generally, if \mathcal{D} is complete and G creates all small limits then \mathcal{D} is complete and G is continuous.

Indeed, let F:\mathcal{J}\rightarrow\mathcal{C} be a functor and let \mu_J:M\rightarrow G(F(J)) be a limiting cone for G\circ F. Then since G creates limits we know there is a unique cone \lambda_J:L\rightarrow F(J) in \mathcal{C} with G(\lambda_J)=\mu_J, and this is a limiting cone on F. But limiting cones are unique up to isomorphism, so this is the limit of F and G preserves it.

Now it’s useful to have good examples of continuous functors at hand, and we know one great family of such functors: representable functors. It should be clear that two naturally isomorphic functors are either both continuous or both not, so we just need to consider functors of the form \hom_\mathcal{C}(C,\underline{\hphantom{X}}).

First let’s note a few things down. A cone c_J:C\rightarrow F(J) in \mathcal{C} is a family of arrows (into a family of different objects) indexed by J, so we can instead think of it as a family of elements in the family of sets \hom_\mathcal{C}(C,F(J)). That is, it’s the same thing as a cone f_J:*\rightarrow\hom_\mathcal{C}(C,F(J)), with vertex a set with one element. Also, remember from our proof of the completeness of \mathbf{Set} that if we have a cone \mu_J:M\rightarrow F(J) then we get a function from M to the set of cones on F with vertex {*}. That is, \mathrm{Cone}(M,F)\cong\hom_\mathbf{Set}(M,\mathrm{Cone}(*,F)). Finally, we can read the definition of a limit as saying that the set of cones \mathrm{Cone}(C,F) is in bijection with the set of arrows \hom_\mathcal{C}(C,\varprojlim_\mathcal{J}F)

Now we see that
In the first bijection we use the equivalence of cones with vertex M and functions from M to the set of cones with vertex {*}. In the second we use the fact that a cone in \mathbf{Set} from {*} to a family of hom-sets is equivalent to a cone in \mathcal{C}. In the third bijection we use the definition of limits to replace a cone from C to F by an arrow from C to \varprojlim_\mathcal{J}F.

But now we can use the definition of limits again, now saying that
and since this holds for any set M we must have \varprojlim_\mathcal{J}\hom_\mathcal{C}(C,F(\underline{\hphantom{X}}))\cong\hom_\mathcal{C}(C,\varprojlim_\mathcal{J}F). Therefore \hom_\mathcal{C}(C,\underline{\hphantom{X}}) preserves the limit.

June 22, 2007 Posted by | Category theory | 12 Comments