Limits of sets and Creation of limits

We know that the category 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 , a functor is a collection of sets and functions . We can take the product of all the sets in the collection , consisting of all lists of elements with each . It comes with projections , but the triangles formed by these projections might not commute — is not equal to in general.

So take the subset of the product consisting of all those lists with for all morphisms of . Then we have functions defined by which do make the required triangles commute, giving a cone on . If is any other cone on then each determines a list which lies in , which determines a unique function .

Now such a list is a list of elements of the various , 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 of a set , we can talk about an arrow , where is a terminal object in — a set with one point. So what we really have here is a list of arrows with , which is a cone on !

So here’s the result of our calculation: The limit set is the set of all cones from to in . Further, we see that this set always exists, so is complete.

We could do a similar calculation in another category like , but we actually don’t have to reproduce all this work. Instead, we can consider the functor which assigns to every group its underlying set. If is a functor, then the composite has a limit . I claim that there is a unique group structure on this set so that the arrows are actually group homomorphisms to the groups , and that this cone in is a limiting cone.

Since the projection just reads off the component from the list, we see that for it to be a homomorphism we have to use the product from . That is, , so the component of the product must be , using the product from . Similarly the component of must be , using the inversion from .

Now if is any cone in then is a cone in , so for some unique function . We can check that

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

In general we say that a functor creates a limit for a functor if for every limiting cone in there exists a unique cone in with and , and further this cone is a limiting cone. The above theorem can then be stated that the functor creates all limits. As a consequence, is complete.

A similar proof to the preceding theorem can be given to show that the “underlying set” functors from , , , , 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.

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 , 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 has finite products and equalizers of pairs then it has limits for all functors from finite categories . 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.

So let’s unpack it. We’re in a category and are considering a functor , where 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 and the product over all the morphisms of of the images of their target objects. Now towards the top we have a projection from the second product onto each factor, and since each factor is in the image of we also have morphisms from the first product. There’s actually a triangle at the top for each morphism in the category , but we only draw one. Now by the universal property of the second product there exists a unique arrow 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 there’s a projection from the first product onto the image of its source, and then there’s an arrow 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 , but we only draw one. Again, by the universal property of the second product there exists a unique arrow 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 , so we can compose to get an arrow for each object . I claim that this is the limit we seek.

First we need to check that this is a cone on . For an arrow in we need to see that . The lower commuting square for tells us that . The upper commuting square tells us that . So we calculate as desired.

Now if is any other cone on then the arrows in the cone combine to give a unique arrow . Since this is a cone, we can check that . Thus factors uniquely through , 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 , , , , and 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.

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 the limit of (if it exists) is a couniversal cone on — a terminal object in the comma category . That is, it consists of an object and arrows for each object , and for any other object with arrows there is a unique arrow with for all . We often write to denote the limit of the functor from the category . As usual, limits are unique up to isomorphism.

Dually, the colimit of (if it exists) is a universal cocone on — an initial object in the comma category . It’s given by an object and arrows so that for any other object and arrows there is a unique arrow with for all . We often write to denote the colimit of the functor from the category .

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

If consists of two objects with a set of parallel arrows from one to the other, then a functor from to is a collection of parallel morphisms in . 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 are pullbacks, while colimits over the category are pushouts.

If the category has an initial object then we have a unique arrow for every object . Now for any functor we see that . Indeed, we can just use for the required arrows, which are compatible with all the other arrows from because is a functor. Any other cone on must have an arrow , and compatibility requires that any other arrow in the cone is the composition . So if has an initial object then limits are trivial.

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

Dually, if has a terminal object then . If doesn’t have a terminal object, we can add one to get a category , and colimits tell us when and how we can extend a functor “universally” to a functor .

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

Cones and cocones

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

Now, for every object there is a constant functor that sends every object of to , and every morphism to the identity on . Actually, this assignment of the constant functor to an object of is a functor from to . Indeed, given a morphism we get a natural transformation from the one constant functor to the other, whose component at each object of is . We call this the “diagonal” functor . That is, is the constant functor with value .

Let be some particular functor in . A cone is an object in the comma category . Let’s unpack this definition. Since has as its source, and is a fixed object — the same thing as a functor from the category to , we know what objects of this category look like.

An object of the category consists of an object of and an arrow from to . But an arrow in is a natural transformation of functors. That is, for each object of we need an arrow in from to . But for all objects . So we just need an object and an arrow for each .

Of course, there’s also naturality conditions to be concerned with. If is an arrow in , and and are the required arrows from , then naturality requires that . So we need a collection of arrows from to the objects in the image of that are compatible with the arrows from . Such a collection defines an object in the comma category — a cone on .

Cocones are defined similarly. A cocone on is an object in the comma category . That is, it’s an object and a collection of arrows from the objects in the image of that are compatible with the arrows from .

The description may seem a little odd, but try writing it out for some very simple categories . For example, let 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.

Diagram categories

A light post today, as I finish up my packing and get ready to head out tomorrow.

Diagram categories are one of those things that at first blush seem almost trivial, but they turn out to be very useful. In general, we start with some small category that describes the form of a diagram, and then we take the category of functors into the category we’re interested in studying.

An easy example is a set — a category with nothing but identity arrows. A functor from a set to just picks out one object of for each element of the set. A little more interesting is the category . This has two objects and two (nontrivial) morphisms. A functor from this category picks out two objects from and two (in general different) parallel arrows from one to the other in .

Even more useful is the category

Of course we can compose the arrows around the upper right or those around the lower left to get diagonal arrows, but we insist here that those two diagonal arrows are the same. A functor from this category picks out four objects and four morphisms that describe a commuting square in .

As a bit of a teaser, notice that the setup for finding a binary equalizer in is exactly a functor from the category to . Similarly, the setup for a binary product is a functor from the category . What categories give rise to diagram categories for the setups for multiple (co)products? (multiple) (co)equalizers? pushouts? pullbacks? How are the setups for pushouts and pullbacks different from the setups for equalizers and coequalizers, and why?

You cannot run from Carnival!

It’s up and running at MathNotations. And even running is a kind of dance!

Multiple products, coproducts, equalizers, coequalizers, pullbacks, pushouts…

We’ve got products and coproducts of two objects at a time, equalizers and coequalizers of two morphisms at a time, and pushouts and pullbacks of two objects at a time over a third. We can generalize all of these.

First let’s do equalizers. If we have three arrows , , and from an object to an object , the equalizer of all three will be an arrow so that . If we have regular equalizers we can build something to satisfy this property.

Let be the equalizer of and . That is, . Now we have and going from to , so we can take their equalizer . Now . And clearly . So we have as the equalizer of all three morphisms.

Of course we didn’t have to start with and . We could have started with and , taken their equalizer, and so on to get another equalizer . It’s important to note here that these two equalizers are not the same in general. Whatever category we’re working in will have some construction to give binary equalizers, and when we apply it twice in two different ways we’ll usually get two different results. But the two results are isomorphic, since each is a couniversal object in the category of arrows that equalize the three arrows we started with, and couniversal objects are unique up to isomorphism. Speaking roughly it’s not too much of a problem to talk about “the” equalizer, but it’s useful to keep in the back of your mind that we’re really talking about an isomorphism class of such objects.

We can similarly define equalizers of any finite number of parallel arrows, and if we have equalizers of pairs we have all of them. We can even define the equalizer of an infinite family of parallel arrows, though now we can’t show that they exist using only pairwise equalizers. And, of course, all this goes the same for coequalizers.

Now we’ll do multiple products. Pullbacks are a kind of product so they’ll come along for the ride, and pushouts and coproducts are dual.

If we have three objects , , and , their product will be an object with arrows that is couniversal among such objects. Again, if we have binary products we can define the product of three objects: has arrows , , and that go from the product to the three objects, and it’s straightforward to verify that it satisfies the universal property required. Again, we can also take the product with the obvious arrows, and this also satisfies the universal property. And again, these two may not be the same, but the universal property guarantees that they’re isomorphic.

We can do the same thing to define the product of any finite number of objects, or even an infinite family (though now we can’t build them from finite products). One interesting case is when we take the product of no objects. This is just an object , since we don’t need any projection arrows out of it to the factors. For any other object (with no particular arrows out) there is a unique arrow from to . That is, the product of no objects is a terminal object. Similarly, the coproduct of no objects is an initial object.

Pushouts and pullbacks

If we have two sets and we can take their union : the set of all elements in at least one of the two. We can also characterize this in categorical terms without reference to elements.

One thing we can see right off is that and are both subsets of . That is, there are arrows and . So maybe the union is the coproduct of the two sets. Well, it’s a good guess, but there’s a problem. There may be some elements in both and . Let’s say we have one, called . I could take functions and with . But any function from has to send to only one point, so we can’t satisfy the coproduct property with the union. In fact the coproduct is the disjoint union, where the two copies of have different images. We need some way to equalize the two images.

And indeed, we have such a way: the coequalizer (you thought I was going to say “equalizer”, right?). The set of points we have the be careful about is the intersection . This is a subset of each of and , so we have arrows and . Now we can take the disjoint union (coproduct) , which comes with arrows and . We compose these with the two from before to get a pair of arrows . Now we take the coequalizer of those arrows. This takes the disjoint union of and and identifies the two copies of each point that came from the intersection, giving the union.

Now let’s back up a bit and draw a diagram as usual.

We have objects and , each with an arrow into it from the object . We want to put in an object to complete the commuting square, so that for any other object and arrows that complete the square there exists a unique arrow from our object to . The object (along with its arrows!) is called the “pushout” of the square. We also sometimes label the square “p.o.” to remember that it’s not just any commuting square, but a pushout square. If you’ve followed the discussion of products, coproducts, equalizers, and coequalizers, you should be able to write down a category in which this is a universal object.

If whenever we have the left side of this square (the three objects and two arrows) in a category we can find a pushout, then we say the category “has pushouts”. The discussion in the case of sets above generalizes, and we see that if a category has coproducts and has coequalizers then it has pushouts. In this case, the pushout is constructed exactly as we did before. However, it’s possible to have pushouts on their own.

Pushouts are closely related to coproducts, as you might guess. In fact, notice that the setup here — the three objects and two arrows — is actually the same thing as two objects in the comma category . That is, we start with two arrows from . Then the pushout also has an arrow from — both paths around the square are the same — so it’s another object in the comma category. The arrows from and to are compatible with the arrows from , so they’re morphisms in the comma category. The upshot is that the pushout of the above diagram is the coproduct in the comma category.

On the other hand, what if our category has an initial object ? Then every other object has a unique arrow , and all morphisms in are compatible with these arrows from . That is, is isomorphic to the comma category . Then if has pushouts we know that in particular has coproducts, and so does too: coproducts are pushouts over an initial object when one exists.

We’ve already seen a few more places that coproducts come up. The amalgamated free product of two groups over a third is a coproduct in . In particular, this means that free products of groups are coproducts, since they’re amalgamated over the trivial group. Also the amalgamated direct sum of modules is a pushout in .

Here’s one that we haven’t considered directly: let be a commutative ring with unit and let be an algebra over with unit. Then we have a homomorphism of rings sending to — the action of on the unit of . That is, an -algebra is an object in the comma category . Now if we have two such algebras, show that their tensor product is a coproduct in this comma category, or equivalently a pushout in .

The dual notion to a pushout is a pullback. Here we use the diagram:

As for the other dual notions, you should go through the discussion of pushouts and write down the dualized versions explicitly.

As a (somewhat complicated) exercise in pullbacks, note first that a pullback over is the same as a product in the comma category . Now consider the category of groupoids. Verify that if the functors from and to are both faithful, then the arrow from to is faithful. In particular, if is a a group, then and are both (equivalent to) group actions, and their pullback will be another one. Check that if is equivalent to the action groupoid of acting on and is equivalent to the action groupoid of acting on then is equivalent to the action groupoid of acting on by the product action. This may be a bit difficult, but just working at it for a while should give some insights into how these things work.

Zero objects, Kernels, and Cokernels

A zero object in a category is, simply put, both initial and terminal. Usually we’ll write for a zero object, but sometimes , or even in certain circumstances. While initial objects and terminal objects are both nice, zero objects are even nicer.

Since a zero object is terminal, there is a unique morphism in for each object . Since it’s initial, there’s a unique morphism in for each object . Now we can put these together: for any two objects and there is a unique morphism which factors through . Take the unique arrow from to , then the unique arrow from to . This picks out a special element of each hom set, just for having a zero object.

We saw that the trivial group in the category of groups is both initial and terminal, so it’s a zero object. If we’re just looking in the category we usually call the trivial abelian group , and it’s a zero object. The initial and terminal object in are different, so this category does not have a zero object.

It’s often useful to remedy this last case by considering the category of “pointed” sets. A pointed set is a pair where is a set and is any element of the set. A morphism of pointed sets is a function so that . The marked point has to go to the marked point. This gives us the category of pointed sets. It’s easily checked that the pointed set is both initial and terminal, so it is a zero object in .

If a category has a zero object then we have a special morphism in each hom set, as I noted above. If we have two morphisms between a given pair of objects we can ask about their equalizer and coequalizer. But now we have one for free! So given any arrow and the special zero arrow , we can ask about their equalizer and coequalizer. In this special case we call them the “kernel” and “cokernel” of , respectively. I’ll say more about the kernel, but you should also think about dualizing everything to talk about the cokernel.

Given a morphism its kernel is an morphism so that as morphisms from to . Also, given any other morphism with we have a unique morphism with h=k\circ g$. This is just the definition of equalizer over again. As with equalizers, the morphism is monic, so we can view as a subobject of and as the inclusion morphism.

Let’s look at this in the case of groups. If we have a group homomorphism the kernel will be group included into by the monomorphism — a subgroup. We also have that , so everything that starts out in gets sent to the identity element in . If we have any other homomorphism whose image gets sent to the identity in , then it factors through , so the image of lands in the image of . That is, picks out the whole subgroup of that gets sent to the identity in under the homomorphism . And that’s exactly what we called the kernel of a group homomorphism way back in February.

Often enough we aren’t really interested in all equalizers — just kernels will do. So, if a category has a zero object and if every morphism has a kernel, we say that the category “has kernels”. Dually, we say it “has cokernels”. Having a zero object and having equalizers clearly implies having kernels, but it’s possible to have kernels without having all equalizers.

Equalizers and coequalizers

Let’s consider another construction from set theory. If we have sets and , and functions and , then we can talk about the subset . This is what we want to generalize.

First off, we know that subsets are subobjects, which are monomorphisms. More to the point, we can look at this subset and take its inclusion function . Then we see that . Furthermore, if any other function satisfies then its image must land in . That is, the function must factor through .

So, given arrows and , each from the object to the object in the category , we construct a new category. The objects are arrows satisfying , and a morphism from to is an arrow so that . Now we define the “equalizer” of and to be a couniversal object in this category, if one exists.

To be a bit more explicit, look at this diagram:

The equalizer is the pair so that for any other there is a unique arrow making the triangle commute. We write it as . Since it’s defined by a universal property, the equalizer is unique up to isomorphism when it exists. If it exists for all pairs of morphisms between the same two objects in the category , we say that “has equalizers”.

Now, as indicated above an equalizer is a monomorphism into . Indeed, let’s say we’ve got two arrows and so that . Then clearly , since is the equalizer of and . So there is a unique morphism so that , and both and must be this unique morphism. Since we can cancel on the left of , is a monomorphism.

The dual notion of an equalizer is a coequalizer. This uses the following diagram:

Go through the above discussion of equalizers and dualize it. Describe a category whose universal object will be the coequalizer. Give an interpretation to this diagram. Prove that the coequalizer of two morphisms is an epimorphism. Try to give a description of coequalizers in , or show that does not have coequalizers.