The Unapologetic Mathematician

Mathematics for the interested outsider


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

Limits of sets and Creation of limits

We know that the category \mathbf{Set} has equalizers and all (small) products, so by the existence theorem we know it is complete. However, it will be useful to have an explicit calculation of all small limits at hand. We’ll find this by walking through the existence theorem in this category.

Given any small category \mathcal{J}, a functor F:\mathcal{J}\rightarrow\mathbf{Set} is a collection of sets F(J) and functions F(u):F(J)\rightarrow F(K). We can take the product of all the sets in the collection \prod_JF(J), consisting of all lists of elements x=\{x_J\}_{J\in\mathrm{Ob}(\mathcal{J})} with each x_J\in F(J). It comes with projections \pi_J:\prod_KF(K)\rightarrow F(J), but the triangles formed by these projections might not commute — \pi_K is not equal to F(u)\circ \pi_J in general.

So take the subset L of the product consisting of all those lists \{x_J\}_{J\in\mathrm{Ob}(\mathcal{J})} with \left[F(u)\right](x_J)=x_K for all morphisms u of \mathcal{J}. Then we have functions \lambda_J:L\rightarrow F(J) defined by \lambda_J(x)=x_J which do make the required triangles commute, giving a cone on F. If \mu_J:M\rightarrow F(J) is any other cone on F then each m\in M determines a list x(m)=\{\mu_J(m)\} which lies in L, which determines a unique function x:M\rightarrow L.

Now such a list \{x_J\} is a list of elements of the various F(J), and when it comes right down to it we just don’t like thinking about elements if we don’t have to. Instead of talking about an element x of a set X, we can talk about an arrow x:*\rightarrow X, where {*} is a terminal object in \mathbf{Set} — a set with one point. So what we really have here is a list of arrows x_J:*\rightarrow F(J) with F(u)\circ x_J=x_K, which is a cone on F!

So here’s the result of our calculation: The limit set \varprojlim_\mathcal{J}F is the set \mathrm{Cone}(*,F) of all cones from {*} to F in \mathbf{Set}. Further, we see that this set always exists, so \mathbf{Set} is complete.

We could do a similar calculation in another category like \mathbf{Grp}, but we actually don’t have to reproduce all this work. Instead, we can consider the functor U:\mathbf{Grp}\rightarrow\mathbf{Set} which assigns to every group its underlying set. If F:\mathcal{J}\rightarrow\mathbf{Grp} is a functor, then the composite U\circ F:\mathcal{J}\rightarrow\mathbf{Set} has a limit L=\mathrm{Cone}(*,U\circ F). I claim that there is a unique group structure on this set so that the arrows \lambda_J:L\rightarrow U(F(J)) are actually group homomorphisms to the groups F(J), and that this cone in \mathbf{Grp} is a limiting cone.

Since the projection \lambda_J:L\rightarrow F(J) just reads off the J component from the list, we see that for it to be a homomorphism we have to use the product from F(J). That is, \lambda_J(\{x_J\}\{y_J\})=\lambda_J(\{x_J\})\lambda_J(\{y_J\})=x_Jy_J, so the J component of the product must be x_Jy_J, using the product from F(J). Similarly the J component of \{x_J\}^{-1} must be x_J^{-1}, using the inversion from F(J).

Now if \gamma_J:G\rightarrow F(J) is any cone in \mathbf{Grp} then U(\gamma_J):U(G)\rightarrow U(F(J)) is a cone in \mathbf{Set}, so U(\gamma_J)=\lambda_J\circ h for some unique function G\rightarrow L. We can check that


so h must also be a group homomorphism, proving the required universal property.

In general we say that a functor G:\mathcal{C}\rightarrow\mathcal{D} creates a limit for a functor F:\mathcal{J}\rightarrow\mathcal{C} if for every limiting cone \lambda_J:L\rightarrow G(F(J)) in \mathcal{D} there exists a unique cone \mu_J:M\rightarrow F(J) in \mathcal{C} with L=G(M) and \lambda_J=G(\mu_J), and further this cone is a limiting cone. The above theorem can then be stated that the functor U:\mathbf{Grp}\rightarrow\mathbf{Set} creates all limits. As a consequence, \mathbf{Grp} is complete.

A similar proof to the preceding theorem can be given to show that the “underlying set” functors from \mathbf{Ab}, \mathbf{Ring}, R\mathbf{-mod}, \mathbf{mod-}R, and other algebraic categories all create all (small) limits, and thus those categories are complete. This also shows that the group (ring, module, etc.) structure on a product (equalizer, pullback) is completely determined by the limit on the underlying sets.

June 21, 2007 Posted by | Category theory | 8 Comments

The Existence Theorem for Limits

Of course, though we’ve defined limits, we don’t know in general whether or not they exist. Specific limits in specific categories have been handled in an ad hoc manner. We show that the Cartesian product is a product in \mathbf{Set}, or that there is a subset which equalizes a pair of morphisms, but we have been doing this all by hand and there are so many different kinds of limits that it’s impossible to handle them all like this. Luckily, we can build complicated limits out of simpler ones in many cases.

In fact, we’ve already seen this: we built pullbacks from products and equalizers. Actually we explicitly built pushouts from coproducts and coequalizers, but the pullback construction is just the dual. Anyhow, that construction shows the general idea. If a category \mathcal{C} has finite products and equalizers of pairs then it has limits for all functors from finite categories \mathcal{J}. If it has all products (indexed by arbitrary sets) as well as pairwise equalizers then it is complete. Conversely, since products and equalizers are examples of limits completeness of a category implies their existence. That is, once we have these kinds of limits all the others come for free.

The proof is summed up in this somewhat arcane diagram.
Existence of Limits Diagram
So let’s unpack it. We’re in a category \mathcal{C} and are considering a functor F:\mathcal{J}\rightarrow\mathcal{C}, where \mathcal{J} is either a small or a finite category.

Starting in the middle row we’ve got the product of all the objects in the image of F and the product over all the morphisms of \mathcal{J} of the images of their target objects. Now towards the top we have a projection \pi_u from the second product onto each factor, and since each factor is in the image of F we also have morphisms from the first product. There’s actually a triangle at the top for each morphism u in the category \mathcal{J}, but we only draw one. Now by the universal property of the second product there exists a unique arrow f from the first product to the second that makes all these triangles commute.

We do a similar thing on the bottom. We again have the projections from the second product to its factors. For each morphism in \mathcal{J} there’s a projection from the first product onto the image of its source, and then there’s an arrow F(u) from the image of the source to the image of the target. Again, there’s one such square at the bottom for each morphism in \mathcal{J}, but we only draw one. Again, by the universal property of the second product there exists a unique arrow g from the first product to the second that makes all of these squares commute.

So now we have two parallel arrows from the first product to the second, and we take their equalizer, which gives an arrow into the first product. We also have an arrow out of the product for each object of \mathcal{J}, so we can compose to get an arrow \mathrm{Equ}(f,g)\rightarrow F(J) for each object J\in\mathcal{J}. I claim that this is the limit we seek.

First we need to check that this is a cone on F. For an arrow u:J\rightarrow K in \mathcal{J} we need to see that \pi_K\circ e=F(u)\circ\pi_J\circ e. The lower commuting square for u tells us that F(u)\circ\pi_J=\pi_u\circ g. The upper commuting square tells us that \pi_K=\pi_u\circ f. So we calculate \pi_K\circ e=\pi_u\circ f\circ e=\pi_u\circ g\circ e=F(u)\circ\pi_J\circ e as desired.

Now if (L,\{\lambda_J\}_{J\in\mathrm{Ob}(\mathcal{J})}) is any other cone on F then the arrows in the cone combine to give a unique arrow h:L\rightarrow\prod_{J\in\mathrm{Ob}(\mathcal{J})}F(J). Since this is a cone, we can check that f\circ h=g\circ h. Thus h factors uniquely through e, giving the universal property we need.

In the finite case, our discussion of multiple products shows that all we need are binary products, a terminal object, and binary equalizers to have all finite products and binary equalizers, and thus to have all finite limits. In general, infinite products have to be dealt with on their own.

Many of our algebraic categories can now be shown to be complete. For examples, each of \mathbf{Set}, \mathbf{Grp}, \mathbf{Ab}, R-\mathbf{mod}, and \mathbf{mod}-R is complete.

Dually, a category is cocomplete if and only if it has all coproducts and pairwise coequalizers. It has all finite colimits if and only if it has all finite coproducts and pairwise coequalizers. You should determine which of the above list of categories are cocomplete.

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

Limits and Colimits

One of the big tools in category theory is the limit of a functor. In fact, depending on the source category, limits give whole families of useful constructions, including (multiple) equalizers, (multiple) products, (multiple) pullbacks, and more we haven’t talked about yet. The dual notion of a colimit similarly generalizes (multiple) coequalizers, (multiple) coproducts, (multiple) pushouts, and so on.

Given a functor F:\mathcal{J}\rightarrow\mathcal{C} the limit of F (if it exists) is a couniversal cone on F — a terminal object in the comma category (\Delta\downarrow F). That is, it consists of an object L and arrows \lambda_J:L\rightarrow F(J) for each object J\in\mathcal{J}, and for any other object X with arrows \xi_J:X\rightarrow F(J) there is a unique arrow \eta:X\rightarrow L with \xi_J=\lambda_J\circ\eta for all J\in\mathcal{J}. We often write L=\varprojlim_\mathcal{J}F to denote the limit of the functor F from the category \mathcal{J}. As usual, limits are unique up to isomorphism.

Dually, the colimit of F (if it exists) is a universal cocone on F — an initial object in the comma category (F\downarrow\Delta). It’s given by an object L and arrows \lambda_J:F(J)\rightarrow L so that for any other object X and arrows \xi_J:F(J)\rightarrow X there is a unique arrow \eta:L\rightarrow X with \xi_J=\eta\circ\lambda_J for all J\in\mathcal{J}. We often write L=\varinjlim_\mathcal{J}F to denote the colimit of the functor F from the category \mathcal{J}.

If \mathcal{J} is a set — a category with only identity arrows — then a functor from \mathcal{J} to \mathcal{C} is a collection of objects of \mathcal{C}, one for each element of \mathcal{J}. The limit of this functor is the product of these objects, and the colimit is their coproduct.

If \mathcal{J} consists of two objects with a set of parallel arrows from one to the other, then a functor from \mathcal{J} to \mathcal{C} is a collection of parallel morphisms in \mathcal{C}. The limit of this functor is the equalizer of the collection, and the colimit is their coequalizer.

Check for yourself that limits over the category \bullet\rightarrow\bullet\leftarrow\bullet are pullbacks, while colimits over the category \bullet\leftarrow\bullet\rightarrow\bullet are pushouts.

If the category \mathcal{J} has an initial object I then we have a unique arrow \iota_J:I\rightarrow J for every object J\in\mathcal{J}. Now for any functor F:\mathcal{J}\rightarrow\mathcal{C} we see that F(I)=\varprojlim_\mathcal{J}F. Indeed, we can just use F(\iota_J) for the required arrows, which are compatible with all the other arrows from \mathcal{J} because F is a functor. Any other cone on F must have an arrow \xi_I:X\rightarrow F(I), and compatibility requires that any other arrow \xi_J:X\rightarrow F(J) in the cone is the composition F(\iota_J)\circ\xi_I. So if \mathcal{J} has an initial object then limits are trivial.

The interesting case is when \mathcal{J} does not have an initial object. We can add a new object to \mathcal{J} with a unique arrow to every other object, getting a category \overline{\mathcal{J}} which does have an initial object. The question is whether a given functor F:\mathcal{J}\rightarrow\mathcal{C} can be extended to a functor \overline{F}:\overline{\mathcal{J}}\rightarrow\mathcal{C}. If it can, then the image of the new initial object is the vertex of a cone on F. If there is a couniversal such extension, that’s the limit of F.

Dually, if \mathcal{J} has a terminal object T then F(T)=\varinjlim_\mathcal{J}F. If \mathcal{J} doesn’t have a terminal object, we can add one to get a category \underline{\mathcal{J}}, and colimits tell us when and how we can extend a functor F:\mathcal{J}\rightarrow\mathcal{C} “universally” to a functor \underline{F}:\underline{\mathcal{J}}\rightarrow\mathcal{C}.

If there exists a limit in \mathcal{C} for any functor from a finite category \mathcal{J} we say that \mathcal{C} “has finite limits”. If there exists a limit for any functor from a small category \mathcal{J} we say that \mathcal{C} is “complete”. The dual conditions are that \mathcal{C} “has finite colimits” and that \mathcal{C} is “cocomplete”, respectively.

June 19, 2007 Posted by | Category theory | 11 Comments

Cones and cocones

There are a few auxiliary concepts we’ll need before the next major topic. Let’s start with two categories \mathcal{J} and \mathcal{C}, and the category of functors \mathcal{C}^\mathcal{J}. If the following seems very complicated, consider \mathcal{J} to be any particular toy category you’d like, so this category of functors is a diagram category.

Now, for every object C\in\mathcal{C} there is a constant functor that sends every object of \mathcal{J} to C, and every morphism to the identity on C. Actually, this assignment of the constant functor to an object of C is a functor from \mathcal{C} to \mathcal{C}^\mathcal{J}. Indeed, given a morphism f:C\rightarrow D we get a natural transformation from the one constant functor to the other, whose component at each object of \mathcal{J} is f. We call this the “diagonal” functor \Delta:\mathcal{C}\rightarrow\mathcal{C}^\mathcal{J}. That is, \Delta(C) is the constant functor with value C.

Let F:\mathcal{J}\rightarrow\mathcal{C} be some particular functor in \mathcal{C}^\mathcal{J}. A cone is an object in the comma category (\Delta\downarrow F). Let’s unpack this definition. Since \Delta has \mathcal{C} as its source, and F is a fixed object — the same thing as a functor from the category \mathbf{1} to \mathcal{C}^\mathcal{J}, we know what objects of this category look like.

An object of the category (\Delta\downarrow F) consists of an object C of \mathcal{C} and an arrow from \Delta(C) to F. But an arrow in \mathcal{C}^\mathcal{J} is a natural transformation of functors. That is, for each object J of \mathcal{J} we need an arrow in \mathcal{C} from \left[\Delta(C)\right](J) to F(J). But \left[\Delta(C)\right](J)=C for all objects J. So we just need an object C\in\mathcal{C} and an arrow C\rightarrow F(J) for each J\in\mathcal{J}.

Of course, there’s also naturality conditions to be concerned with. If j:J_1\rightarrow J_2 is an arrow in \mathcal{J}, and c_1:C\rightarrow F(J_1) and c_2:C\rightarrow F(J_2) are the required arrows from C, then naturality requires that c_2=F(j)\circ c_1. So we need a collection of arrows from C to the objects in the image of F that are compatible with the arrows from \mathcal{J}. Such a collection defines an object in the comma category (\Delta\downarrow F) — a cone on F.

Cocones are defined similarly. A cocone on F is an object in the comma category (F\downarrow\Delta). That is, it’s an object C\in\mathcal{C} and a collection of arrows from the objects in the image of F that are compatible with the arrows from \mathcal{J}.

The description may seem a little odd, but try writing it out for some very simple categories \mathcal{J}. For example, let \mathcal{J} be a set. Then try letting it be an ordinal, or another preorder. After you write down the definition of a cone and a cocone on some simple categories the general idea should seem to make more sense.

June 18, 2007 Posted by | Category theory | 4 Comments