2007 October « The Unapologetic Mathematician

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

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 John Armstrong | 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 John Armstrong | Category theory | 3 Comments

Homology

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 John Armstrong | 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
$\mathbf{0}\rightarrow\mathrm{Ker}(f)\rightarrow\mathrm{Ker}(g)\rightarrow\mathrm{Ker}(h)\rightarrow\mathrm{Cok}(f)\rightarrow\mathrm{Cok}(g)\rightarrow\mathrm{Cok}(h)\rightarrow\mathbf{0}$
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 John Armstrong | Category theory | 6 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 John Armstrong | Category theory | Leave a Comment

Next Entries »

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects
Archives

October 2007

M T W T F S S

« Sep Nov »

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider

Spans and Cospans

Weak 2-Categories

Homology

The Snake Lemma

The Five Lemma

About this weblog

Recent Posts

Blogroll

Art

Astronomy

Computer Science

Education

Mathematics

Me

Philosophy

Physics

Politics

Science

RSS Feeds

Feedback

Subjects

Archives

Site info

Follow “The Unapologetic Mathematician”

M	T	W	T	F	S	S
« Sep				Nov »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31