The Unapologetic Mathematician

Mathematics for the interested outsider

Spans and Cospans

I was busy all yesterday with my talk at George Washington, so today I’ll make up for it by explaining one of the main tools that went into the talk. Coincidentally, it’s one of my favorite examples of a weak 2-category.

We start by considering a category \mathcal{C} with pullbacks. A span in \mathcal{C} is a diagram of the form A_1\leftarrow B\rightarrow A_2. We think of it as going from A_1 to A_2. It turns out that we can consider these to be the morphisms in a weak 2-category \mathbf{Span}(\mathcal{C}), whose objects are just the objects of \mathcal{C}.

Now since this is supposed to be a 2-category we need 2-morphisms to go between spans. Given spans A_1\leftarrow B\rightarrow A_2 and A_1\leftarrow B'\rightarrow A_2 a 2-morphism from the first to the second will be an arrow from B to B' making the triangles on the sides of the following diagram commute:
A 2-morphism between spans
We compose 2-morphisms in the obvious way, stacking these diamond diagrams on top of each other and composing the arrows down the middle.

The composition for 1-morphisms is where it gets interesting. If we have spans A_1\leftarrow B_1\rightarrow A_2 and A_2\leftarrow B_2\rightarrow A_3 we compose them by overlapping them at A_2 and pulling back the square in the middle, as in the following diagram:
Composition of Spans
where the middle square is a pullback. Then the outer arrows form a span A_1\leftarrow C\rightarrow A_3.

Notice that this composition is not in general associative. If we have three spans A_1\leftarrow B_1\rightarrow A_2, A_2\leftarrow B_2\rightarrow A_3, and A_3\leftarrow B_3\rightarrow A_4, we could pull back on the left first, then on the right, or the other way around:
Associativity of Span Composition 1
Associativity of Span Composition 2
But the object D at the top of each diagram is a limit for the A_1\leftarrow B_1\rightarrow A_2\leftarrow B_2\rightarrow A_3\leftarrow B_3\rightarrow A_4 along the bottom of the diagram. And thus the two of them must be isomorphic, and the isomorphism must commute with all the arrows from D to an object along the bottom. In particular, it commutes with the arrows from D to A_1 and to A_4, and thus gives a canonical “associator” 2-morphism. I’ll leave the straightforward-but-tedious verification of the pentagon identity as an exercise.

What is the identity span? It’s just A\leftarrow A\rightarrow A, where the arrows are the identity arrows on A. When we pull back anything along the identity arrow on A, we get the same arrow again. Thus the 2-morphisms we need for the left and right unit are just the identities, and so the triangle identity is trivially true. Thus we have constructed a 2-category \mathbf{Span}(\mathcal{C}) from any category with pullbacks.

The concept of a cospan is similar, but the arrows (predictably) run the other way. A cospan in a category \mathcal{C} with pushouts (instead of pullbacks) is a diagram of the form A_1\rightarrow B\leftarrow A_2. Everything else goes the same way — 2-morphisms are arrows in the middle making the side triangles commute, and composition of cospans goes by pushing out the obvious square.

Unusual as it is for this weblog, I’d like to make one historical note. Spans and cospans were introduced by Bénabou in the early 1960s. This was first pointed out to me by Eugenia Cheng (of The Catsters) and John Baez (of The n-Category Café) at a conference at Union College two years ago. Until that point I’d been calling cospans “\Lambda-diagrams” because I’d invented them out of whole cloth to solve a problem that I’ll eventually get around to explaining. The name seemed appropriate because I tend to draw them (as I have in the above diagrams) as wedges with the arrows on the sides pointing up into the center, sort of like a capital lambda. They’ve shown up in a number of contexts, but as far as I can tell I’m the first (and so far only) to use them in knot theory like I do. However, Jeff Morton has noted that cobordisms are a sort of cospan, and my use of tangles is analogous to that.


October 6, 2007 Posted by | Category theory | 6 Comments

Weak 2-Categories

I’d like to step aside from homology because I’m on the road and I can throw off a post about weak 2-categories in my sleep by now.

When we were talking about enriched categories we mentioned the case of 2-categories, where between each pair of objects we have a hom-category and so on. We also mentioned that if a 2-category has only one object it’s the same thing as a strict monoidal category. But monoidal categories aren’t generally strict! That is, the monoidal product isn’t associative “on the nose”, but only up to a natural isomorphism. And so we should look for the same sort of thing to happen in the case of more general 2-categories.

So, a (weak) 2-category \mathcal{C} will have a collection of objects. Between each pair of objects C,D\in\mathcal{C} there will be a category \hom_\mathcal{C}(C,D) whose objects we call 1-morphisms from C to D. Between two such 1-morphisms f,g:C\rightarrow D we have a set of “2-morphisms” \hom_{\hom_\mathcal{C}(C,D)}(f,g).

We can “vertically” compose 2-morphisms using the composition from a given hom-category. That is, given \phi:f\rightarrow g and \psi:g\rightarrow h we have \psi\bullet\phi:f\rightarrow h. Of course, there is an “identity” 2-morphism 1_f on any 1-morphism f, and the composition is associative. At this top level, everything is just like any other category.

Down at the level of 1-morphisms, things get hairier. For each triple of objects A,B,C\in\mathcal{C} we have a functor \circ:\hom_\mathcal{C}(B,C)\times\hom_\mathcal{C}(A,B)\rightarrow\hom_\mathcal{C}(A,C). This functor is not required to be associative in the usual sense, nor to have identities. Instead, for every triple of 1-morphisms f:A\rightarrow B, g:B\rightarrow C, and h:C\rightarrow D, there is a 2-isomorphism \alpha_{f,g,h}\in\hom_{\hom_\mathcal{C}(A,D)}((h\circ g)\circ f,h\circ(g\circ f)) which replaces the associative law. Similarly, for each object we have a 1-morphism 1_C\in\hom_\mathcal{C}(C,C) and for each 1-morphism f:C\rightarrow D we have 2-morphisms \lambda_f\in\hom_{\hom_\mathcal{C}(C,D)}(1_D\circ f,f) and \rho_f\in\hom_{\hom_\mathcal{C}(C,D)}(f\circ1_C,f) to replace the left and right unit laws.

Now because \circ is a functor, it also acts on 2-morphisms. That is, if we have 1-morphisms f_1,g_1:A\rightarrow B and f_2,g_2:B\rightarrow C, and 2-morphisms \phi:f_1\rightarrow g_1 and \psi:f_2\rightarrow g_2, then we have a “horizontal” composition \psi\circ\phi:f_2\circ f_1\rightarrow g_2\circ g_1.

Functoriality says that this horizontal composition has to preserve the vertical composition inside each hom-category. So let’s take 1-morphisms f_1,g_1,h_1\in\hom_\mathcal{C}(A,B) and f_2,g_2,h_2\in\hom_\mathcal{C}(B,C). Then take 2-morphisms \phi_1:f_1\rightarrow g_1, \psi_1:g_1\rightarrow h_1, \phi_2:f_2\rightarrow g_2, and \psi_2:g_2\rightarrow h_2. We can vertically compose to get \psi_1\bullet\phi_1:f_1\rightarrow h_1 and \psi_2\bullet\phi_2:f_2\rightarrow h_2. These can then be horizontally composed to get (\psi_2\bullet\phi_2)\circ(\psi_1\bullet\phi_1):f_2\circ f_1\rightarrow h_2\circ h_1. On the other hand we could have composed horizontally before vertically and obtained (\psi_2\circ\psi_1)\bullet(\phi_2\circ\phi_1):f_2\circ f_1\rightarrow h_2\circ h_1. Functoriality tells us that these two 2-morphisms must be the same. We call this equation the “exchange identity”.

As an exercise, write all this out in the case where we just have one object. Then there’s only one hom-category to worry about. Verify that this restates the definition of a (weak) monoidal category, and show what the exchange identity means in this case.

October 4, 2007 Posted by | Category theory | 3 Comments


Today we can define homology before I head up to the Baltimore/DC area for the weekend. Anyone near DC who wants to hear about anafunctors can show up at George Washington University’s topology seminar on Friday.

As a preliminary, we need to know what quotients in an abelian category are. In \mathbf{Ab} we think of an abelian group G and a subgroup H and consider two elements of G to be equivalent if they differ by an element of H. This causes problems for us because we don’t have any elements to work with.

Instead, remember that H comes with an “inclusion” arrow H\rightarrow G, and that the quotient has a projection arrow G\rightarrow G/H. The inclusion arrow is monic, the projection is epic, and an element of the quotient is zero if and only if it comes from an element of G that is actually in H. That is, we have a short exact sequence \mathbf{0}\rightarrow H\rightarrow G\rightarrow G/H\rightarrow\mathbf{0}. But we know in any abelian category that this short exact sequence means that the projection is the cokernel of the inclusion. So in general if we have a monic m:A\rightarrow B we define B/A=\mathrm{Cok}(m).

Now we define a chain complex in an abelian category \mathcal{C} to be a sequence \cdots\rightarrow C_{i+1}\rightarrow C_i\rightarrow C_{i-1}\rightarrow\cdots with arrows d_i:C_i\rightarrow C_{i-1} so that d_{i-1}\circ d_i=0. In particular, an exact sequence is a chain, since the composition of two arrows in the sequence is the zero homomorphism. But a chain complex is not in general exact. Homology will be the tool to measure exactly how the chain complex fails to be exact.

So let’s consider the following diagram
Diagram for the Definition of Homology
where g\circ f=0. We can factor f as m\circ e for an epic e and a monic m=\mathrm{Im}(f). We can also construct the kernel \mathrm{Ker}(g) of g. Now g\circ m\circ e=g\circ f=0=0\circ e, so g\circ m=0 because e is epic. This means that m factors through \mathrm{Ker}(g), and the arrow \mathrm{Im}(f)\rightarrow\mathrm{Ker}(g) must be monic.

Now, if the sequence were exact then \mathrm{Im}(f) would be the same as \mathrm{Ker}(g), and the arrow we just constructed would be an isomorphism. But in general it’s just a monic, and so we can construct the quotient \mathrm{Ker}(g)/\mathrm{Im}(f). When the sequence is exact this quotient is just the trivial object \mathrm{0}, so the failure of exactness is measured by this quotient.

In the case of a chain complex we consider the above situation with f=d_{i+1} and g=d_i, so they connect through C_i. We define Z_i=\mathrm{Ker}(g) and B_i=\mathrm{Im}(f), which are both subobjects of C_i. Then the “homology object” H_i is the quotient H_i=Z_i/B_i. We can string these together to form a new chain complex \cdots\rightarrow H_{i+1}\rightarrow H_i\rightarrow H_{i-1}\rightarrow\cdots where all the arrows are zero. This makes sense because if we think of the case of abelian groups, H_i consists of equivalence classes of elements of Z_i, and when we hit any element of Z_i by d_i we get {0}. Thus the residual arrows when we pass from the original chain complex to its homology are all zero morphisms.

October 3, 2007 Posted by | Category theory | 8 Comments

The Snake Lemma

And now for what has to be the most popular theorem in all of homological algebra: the snake lemma.

This shows up in every first course in algebraic topology, and always with the same diagram-chasing proof (though not with the same semantic sugar as we’re using). And some grad student always raises the same objection halfway through (I did it in my class). And the follow-up is always the same. Weibel’s An Introduction to Homological Algebra points out that the proof is best seen visually, but I don’t have a video camera like The Catsters. Weibel also points out that a good visual presentation appears in the 1980 movie It’s My Turn. I looked around everywhere but couldn’t find a clip online. So, if you have access to the movie it’s old enough that I’m sure the producers wouldn’t mind a teensy clip posted for The Good of Mathematics. Call it “fair use”.

[UPDATE]: Down in the comments, Graham points out that someone at Harvard has posted the clip here. Tough to see, though.

Now, down to business. We consider the following diagram:
Diagram for the Snake Lemma
We start with two short exact sequences and a morphism (f,g,h) from one to the other. We construct the kernel and cokernel of each arrow, and then use their universal properties to construct arrows between the kernels and cokernels. It is straightforward to show that the given rows are exact — in particular, m_0 is monic and e_1 is epic.

However, the upper and lower rows are not necessarily short exact sequences. That is, e_0 may fail to be epic and m_1 may fail to be monic. Amazingly, though, these two fail to happen in exactly the same way at exactly the same time! It turns out that there is a morphism \delta:\mathrm{Ker}(h)\rightarrow\mathrm{Cok}(f) so that the sequence
is exact.

Now, if you really want to see the chase you can get someone to walk you through it, try to construct it yourself, or beg Netflix to stock more early 1980s romances between Jill Clayburgh and Michael Douglas. Here I’ll do a much more insightful proof that gets to the heart of what the connecting morphism really is. The proof depends on this diagram:
Proof of the Snake Lemma
We start with the same middle rows as before and construct \mathrm{Ker}(h) and \mathrm{Cok}(f). Now we use one of our lemmas (and its dual) to construct the pullback D, the pushout D', and the two dashed arrows. Notice that here we’re using the (unshown) facts that m is monic and e' is epic. We have an arrow \delta_0=p'\circ g\circ k', which satisfies s'\circ\delta_0=h\circ k\circ u and \delta_0\circ s=u'\circ p\circ f. And then since u' is the kernel of s' and u is the cokernel of s, we see that \delta_0 factors as u'\circ\delta\circ u for some unique \delta:\mathrm{Ker}(h)\rightarrow\mathrm{Cok}(f).

What does this arrow do to a member x\in\mathrm{Ker}(h)? Well first it gets sent to k\circ x. Then because e is epic there must be a y\in_mB with e\circ y\equiv k\circ x. We calculate that e'\circ g\circ y=h\circ e\circ y\equiv h\circ k\circ x\equiv0. But then by exactness there must be z\in_mA' with m'\circ z\equiv g\circ y. This is the usual diagram chase given to construct the connecting morphism. Now I claim that \delta\circ x\equiv p\circ z.

This happens because D is a pullback, so there is a member x_0\in_mD with u\circ x_0\equiv x and k'\circ x_0\equiv y. Then
u'\circ\delta\circ x\equiv u'\circ\delta\circ u\circ x_0\equiv\delta_0\circ x_0\equiv p'\circ g\circ y\equiv u'\circ p\circ z
Since u' is monic we have \delta\circ x\equiv p\circ z, as desired. This also shows that the equivalence class of p\circ z is independent of the choices made in the construction of the last paragraph, which is the standard objection I mentioned earlier, now handled in a very slick (but not diagram-chasing) way.

So now we need to verify the exactness of the long sequence. We’ll show the exactness at \mathrm{Ker}(h), and that at \mathrm{Cok}(f) will follow by duality.

First of all we need to see that \delta\circ e_0=0. For this, we show that \delta\circ e_0\circ w=0 for any w\in_m\mathrm{Ker}(g). Now when we use the diagram chase our first step is to choose a y\in_mB with e\circ y\equiv k\circ e_0\circ w=e\circ j\circ w, where j:\mathrm{Ker}(g)\rightarrow B is the kernel map. This shows we can choose y=j\circ w. But then g\circ y=g\circ j\circ w\equiv0, and so we choose z=0 and find \delta\circ e_0\circ w=p\circ z=0.

Now take x\in_m\mathrm{Ker}(h) with \delta\circ x\equiv0, meaning that we construct p\circ z\equiv0. By the definition of the cokernel there will be w\in_mA with f\circ w\equiv z, so g\circ m\circ w=m'\circ z\equiv g\circ y. The “subtraction” rule gives us a y_0\in_mB with e\circ y_0\equiv e\circ y=k\circ x and g\circ y_0. But now by the definition of \mathrm{Ker}(g) we have x_0\in_m\mathrm{Ker}(g) with j\circ x_0\equiv y_0. Then k\circ e_0\circ x_0=e\circ y_0\equiv k\circ x, and so x\equiv e_0\circ x_0 because k is monic. And thus the sequence is exact at \mathrm{Ker}(h).

Incidentally, what the setup of the snake lemma tells us is that the category \mathbf{Ses}(\mathcal{C}), while always enriched over \mathbf{Ab}, is not generally abelian itself. If it were an abelian category the upper and lower rows of the first diagram would have to be short exact sequences themselves. That doesn’t quite happen, but we can exactly capture the obstruction to existence of kernels and cokernels in a single connecting morphism. If this morphism \delta is the zero morphism, then we can insert \mathbf{0} into the long exact sequence and then break it into the two short exact sequences, and thus we have a kernel and a cokernel for the triple (f,g,h).

Notice here that \delta\in\hom_\mathcal{C}(\mathrm{Ker}(h),\mathrm{Cok}(f), so the obstruction lives in this abelian group, which is determined by f and h. Thus in a sense a morphism of short exact sequences has or fails to have a kernel and a cokernel on g alone. I’ll leave this to you to ponder: if we’ve given f and h, must there exist a g so that (f,g,h) has a kernel and a cokernel — so that \delta=0? And if so, how can we find it?

October 2, 2007 Posted by | Category theory | 7 Comments

The Five Lemma

Today I’ll prove the “five lemma”, using the diagram chasing rules I outlined last time. This is an extension of the short five lemma from last week.

We consider the following commutative diagram with exact rows:
Diagram for the Five Lemma
The five lemma states that if f_1 is epic, and f_2 and f_4 are monic, then f_3 is monic. By our chasing rules this means that for all x\in_m A_3, f_3\circ x\equiv0 implies that x\equiv0. So let’s start with a member x of A_3 and assume that f_3\circ x\equiv0.

First off we can tell that f_4\circ g_3\circ x=h_3\circ f_3\circ x\equiv0, and since f_4 is monic this means g_3\circ x\equiv0. Now the upper row is exact at A_3, so there must exist a member y\in_mA_2 with g_2\circ y\equiv x. We find h_2\circ f_2\circ y=f_3\circ g_2\circ y\equiv f_3\circ x\equiv0, so by the exactness of the lower row at B_2 there must be a member z\in_mB_1 with h_1\circ z\equiv f_2\circ y. Because f_1 is epic, there is a member w\in_mA_1 with f_1\circ w\equiv z. Then f_2\circ g_1\circ w=h_1\circ f_1\circ w\equiv h_1\circ z\equiv f_2\circ y, and so g_1\circ w\equiv y. Then x\equiv g_2\circ y\equiv g_2\circ g_1\circ w, but exactness tells us that g_2\circ g_1\equiv0, which leads us to conclude that x\equiv0. Therefore f_3 is monic.

Dually, if f_2 and f_4 are epic while f_5 is monic we conclude that f_3 is epic. And then if f_1 is epic, f_2 and f_4 are isomorphisms, and f_5 is monic, then f_3 is an isomorphism.

It’s instructive to run through the above chase in both languages. First read \in_m as denoting an element of an abelian group, while \equiv denotes equality of elements. Then go back and reconstruct the proof in terms of morphisms between objects of general abelian categories. Thinking of members as behaving like actual elements allows us to create a proof that works for any abelian category we happen to be considering.

October 1, 2007 Posted by | Category theory | Leave a comment