# The Unapologetic Mathematician

## 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

$\lambda_J(h(g_1g_2))=\gamma_J(g_1g_2)=\gamma_J(g_1)\gamma_J(g_2)=\lambda_J(h(g_1))\lambda_J(h(g_2))=\lambda_J(h(g_1)h(g_2))$

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.

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 | 9 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

## 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 $\mathcal{D}$ that describes the form of a diagram, and then we take the category of functors $\mathcal{C}^\mathcal{D}$ 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 $\mathcal{C}$ just picks out one object of $\mathcal{C}$ for each element of the set. A little more interesting is the category $\bullet\rightrightarrows\bullet$. This has two objects and two (nontrivial) morphisms. A functor from this category picks out two objects from $\mathcal{C}$ and two (in general different) parallel arrows from one to the other in $\mathcal{C}$.

Even more useful is the category
$\begin{matrix}\bullet&\rightarrow&\bullet\\\downarrow&&\downarrow\\\bullet&\rightarrow&\bullet\end{matrix}$
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 $\mathcal{C}$.

As a bit of a teaser, notice that the setup for finding a binary equalizer in $\mathcal{C}$ is exactly a functor from the category $\bullet\rightrightarrows\bullet$ to $\mathcal{C}$. Similarly, the setup for a binary product is a functor from the category $\bullet\qquad\bullet$. 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?

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

## 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 $f_1$, $f_2$, and $f_3$ from an object $A$ to an object $B$, the equalizer of all three will be an arrow $e:E\rightarrow A$ so that $f_1\circ e=f_2\circ e=f_3\circ e$. If we have regular equalizers we can build something to satisfy this property.

Let $e_{1,2}:E_{1,2}\rightarrow A$ be the equalizer of $f_1$ and $f_2$. That is, $f_1\circ e_{1,2}=f_2\circ e_{1,2}$. Now we have $f_1\circ e_{1,2}$ and $f_3\circ e_{1,2}$ going from $E_{1,2}$ to $B$, so we can take their equalizer $e_{1,2,3}:E_{1,2,3}\rightarrow E_{1,2}$. Now $f_1\circ e_{1,2}\circ e_{1,2,3}=f_3\circ e_{1,2}\circ e_{1,2,3}$. And clearly $f_1\circ e_{1,2}\circ e_{1,2,3}=f_2\circ e_{1,2}\circ e_{1,2,3}$. So we have $e_{1,2}\circ e_{1,2,3}:E_{1,2,3}\rightarrow A$ as the equalizer of all three morphisms.

Of course we didn’t have to start with $f_1$ and $f_2$. We could have started with $f_1$ and $f_3$, taken their equalizer, and so on to get another equalizer $e_{1,3}\circ e_{1,3,2}:E_{1,3,2}\rightarrow A$. 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 $A_1$, $A_2$, and $A_3$, their product $P=\prod\limits_{i=1}^3A_i$ will be an object with arrows $\pi_i:P\rightarrow A_i$ that is couniversal among such objects. Again, if we have binary products we can define the product of three objects: $(A_1\times A_2)\times A_3$ has arrows $\pi_{A_1}\circ\pi_{A_1\times A_2}$, $\pi_{A_2}\circ\pi_{A_1\times A_2}$, and $\pi_{A_3}$ 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 $A_1\times(A_2\times A_3)$ 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 $T$, since we don’t need any projection arrows out of it to the factors. For any other object $A$ (with no particular arrows out) there is a unique arrow from $A$ to $T$. That is, the product of no objects is a terminal object. Similarly, the coproduct of no objects is an initial object.

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

## Pushouts and pullbacks

If we have two sets $X$ and $Y$ we can take their union $X\cup Y$: 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 $X$ and $Y$ are both subsets of $X\cup Y$. That is, there are arrows $X\rightarrow X\cup Y$ and $Y\rightarrow X\cup Y$. 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 $X$ and $Y$. Let’s say we have one, called $p$. I could take functions $f_X:X\rightarrow Z$ and $f_Y:Y\rightarrow Z$ with $f_X(p)\neq f_Y(p)$. But any function from $X\cup Y$ has to send $p$ 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 $p$ 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 $X\cap Y$. This is a subset of each of $X$ and $Y$, so we have arrows $X\cap Y\rightarrow X$ and $X\cap Y\rightarrow Y$. Now we can take the disjoint union (coproduct) $X\uplus Y$, which comes with arrows $X\rightarrow X\uplus Y$ and $Y\rightarrow X\uplus Y$. We compose these with the two from before to get a pair of arrows $X\cap Y\rightrightarrows X\uplus Y$. Now we take the coequalizer of those arrows. This takes the disjoint union of $X$ and $Y$ 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 $A$ and $B$, each with an arrow into it from the object $C$. We want to put in an object to complete the commuting square, so that for any other object $D$ and arrows that complete the square there exists a unique arrow from our object to $D$. The object $A\amalg_CB$ (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 $(C\downarrow\mathcal{C})$. That is, we start with two arrows from $C$. Then the pushout $A\amalg_CB$ also has an arrow from $C$ — both paths around the square are the same — so it’s another object in the comma category. The arrows from $A$ and $B$ to $A\amalg_CB$ are compatible with the arrows from $C$, 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 $\mathcal{C}$ has an initial object $I$? Then every other object $A$ has a unique arrow $I\rightarrow A$, and all morphisms in $\mathcal{C}$ are compatible with these arrows from $I$. That is, $\mathcal{C}$ is isomorphic to the comma category $(I\downarrow\mathcal{C})$. Then if $\mathcal{C}$ has pushouts we know that $(I\downarrow\mathcal{C})$ in particular has coproducts, and so $\mathcal{C}$ 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 $\mathbf{Grp}$. 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 $R-\mathbf{mod}$.

Here’s one that we haven’t considered directly: let $R$ be a commutative ring with unit and let $A$ be an algebra over $R$ with unit. Then we have a homomorphism $R\rightarrow A$ of rings sending $r\in R$ to $r\cdot 1\in A$ — the action of $r$ on the unit of $A$. That is, an $R$-algebra is an object in the comma category $(R\downarrow\mathbf{Ring})$. Now if we have two such algebras, show that their tensor product $A_1\otimes_RA_2$ is a coproduct in this comma category, or equivalently a pushout in $\mathbf{Ring}$.

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 $C$ is the same as a product in the comma category $(\mathcal{C}\downarrow C)$. Now consider the category $\mathbf{Gpd}$ of groupoids. Verify that if the functors from $A$ and $B$ to $C$ are both faithful, then the arrow from $A\times_CB$ to $C$ is faithful. In particular, if $C$ is a a group, then $A$ and $B$ are both (equivalent to) group actions, and their pullback will be another one. Check that if $A$ is equivalent to the action groupoid of $C$ acting on $S$ and $B$ is equivalent to the action groupoid of $C$ acting on $T$ then $A\times_CB$ is equivalent to the action groupoid of $C$ acting on $S\times T$ 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.

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

## Zero objects, Kernels, and Cokernels

A zero object in a category $\mathcal{C}$ is, simply put, both initial and terminal. Usually we’ll write $\mathbf{0}$ for a zero object, but sometimes $Z$, or even $\mathbf{1}$ 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 $\hom_\mathcal{C}(X,\mathbf{0})$ for each object $X$. Since it’s initial, there’s a unique morphism in $\hom_\mathcal{C}(\mathbf{0},Y)$ for each object $Y$. Now we can put these together: for any two objects $X$ and $Y$ there is a unique morphism $0:X\rightarrow Y$ which factors through $\mathbf{0}$. Take the unique arrow from $X$ to $\mathbf{0}$, then the unique arrow from $\mathbf{0}$ to $Y$. This picks out a special element of each hom set, just for having a zero object.

We saw that the trivial group $\mathbf{1}$ in the category of groups is both initial and terminal, so it’s a zero object. If we’re just looking in the category $\mathbf{Ab}$ we usually call the trivial abelian group $\mathbf{0}$, and it’s a zero object. The initial and terminal object in $\mathbf{Set}$ 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 $(X,x)$ where $X$ is a set and $x\in X$ is any element of the set. A morphism of pointed sets is a function $f:X\rightarrow Y$ so that $f(x)=y$. The marked point has to go to the marked point. This gives us the category $\mathbf{pSet}$ of pointed sets. It’s easily checked that the pointed set $(\{x\},x)$ is both initial and terminal, so it is a zero object in $\mathbf{pSet}$.

If a category $\mathcal{C}$ 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 $f:X\rightarrow Y$ and the special zero arrow $0:X\rightarrow Y$, we can ask about their equalizer and coequalizer. In this special case we call them the “kernel” and “cokernel” of $f$, respectively. I’ll say more about the kernel, but you should also think about dualizing everything to talk about the cokernel.

Given a morphism $f:X\rightarrow Y$ its kernel is an morphism $k:\mathrm{Ker}(f)\rightarrow X$ so that $f\circ k=0$ as morphisms from $\mathrm{Ker}(f)$ to $Y$. Also, given any other morphism $h:H\rightarrow X$ with $f\circ h=0$ we have a unique morphism $g:H\rightarrow\mathrm{Ker}(f)$ with h=k\circ g\$. This is just the definition of equalizer over again. As with equalizers, the morphism $k$ is monic, so we can view $\mathrm{Ker}(f)$ as a subobject of $X$ and $k$ as the inclusion morphism.

Let’s look at this in the case of groups. If we have a group homomorphism $f:X\rightarrow Y$ the kernel will be group included into $X$ by the monomorphism $k$ — a subgroup. We also have that $f\circ k=0$, so everything that starts out in $\mathrm{Ker}(f)$ gets sent to the identity element in $Y$. If we have any other homomorphism $h:H\rightarrow X$ whose image gets sent to the identity in $Y$, then it factors through $\mathrm{Ker}(f)$, so the image of $h$ lands in the image of $k$. That is, $\mathrm{Ker}(f)$ picks out the whole subgroup of $X$ that gets sent to the identity in $Y$ under the homomorphism $f$. 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.

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

## Equalizers and coequalizers

Let’s consider another construction from set theory. If we have sets $S$ and $T$, and functions $f:S\rightarrow T$ and $g:S\rightarrow T$, then we can talk about the subset $E=\{s\in S|f(s)=g(s)\}$. 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 $e:E\rightarrow S$. Then we see that $f\circ e=g\circ e$. Furthermore, if any other function $h:X\rightarrow S$ satisfies $f\circ h=g\circ h$ then its image must land in $E$. That is, the function $h$ must factor through $e$.

So, given arrows $f$ and $g$, each from the object $S$ to the object $T$ in the category $\mathcal{C}$, we construct a new category. The objects are arrows $h:X\rightarrow S$ satisfying $f\circ h=g\circ h$, and a morphism from $(X_1,h_1)$ to $(X_2,h_2)$ is an arrow $m:X_1\rightarrow X_2$ so that $h_1=h_2\circ m$. Now we define the “equalizer” of $f$ and $g$ 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 $(E,e)$ so that for any other $(X,h)$ there is a unique arrow $X\rightarrow E$ making the triangle commute. We write it as $\mathrm{Equ}(f,g)$. 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 $\mathcal{C}$, we say that $\mathcal{C}$ “has equalizers”.

Now, as indicated above an equalizer is a monomorphism into $S$. Indeed, let’s say we’ve got two arrows $h_1:X\rightarrow E$ and $h_2:X\rightarrow E$ so that $e\circ h_1=e\circ h_2$. Then clearly $f\circ(e\circ h_1)=g\circ(e\circ h_1)$, since $e$ is the equalizer of $f$ and $g$. So there is a unique morphism $m:X\rightarrow E$ so that $e\circ m=e\circ h_1=e\circ h_2$, and both $h_1$ and $h_2$ must be this unique morphism. Since we can cancel $e$ on the left of $e\circ h_1=e\circ h_2$, $e$ 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 $\mathbf{Set}$, or show that $\mathbf{Set}$ does not have coequalizers.

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