2007 October « The Unapologetic Mathematician

Hiatus

I think I’m done with categories qua categories for now, and am ready to move on to another subject for a little while. But before I do, I’m going to take a little break and finally get down to this restructuring of the subjects listed on the right. It’ll also give me some time to catch up on some stuff in the real world that needs doing.

The RSS feed will probably be going nuts with updates to posts as I crawl through the archives and relabel things. My apologies in advance.

[UPDATE]: I’ve finished the group theory archives. Unfortunately, the “category” bar on the right seems to not indent nested categories in this theme. Sort of annoying…

[UPDATE]: There seems to be a bug with subcategories on WordPress today, and I’m not the only one having it. So I’ll have to hold off on refining the rings and categories topics until later. In the meantime, I’ve reworked the sidebars a bit, including a search field!

October 22, 2007 Posted by John Armstrong | Uncategorized | 12 Comments

Chalk is a “Feelie”

Okay, so I’ll pile on with the interactive fiction chatter. I really should, since I’ve been playing IF games since I was a wee lad.

First someone pointed out that a long calculation is like a computer game where you have to save and keep backtracking to your saved states. Isabel at God Plays Dice then drew the more specific connection to interactive fiction. Then Mark at Inductio Ex Machina contributed this sample transcript of such a “game”.

I’d like to point out an unintended analogy here. It’s pretty well accepted within the IF community that any puzzle should be solvable at a first pass. That is, if you’ve done everything right you’ll have all you need to solve a given puzzle without guessing, failing, and backtracking. In fact, it’s the height of bad writing to include a puzzle that requires you to attempt it and fail to gain information needed to pass.

I think that the same holds true in mathematics. If you find that you must do a hard calculation with attendant backtracking, you’re asking the wrong question. When properly viewed, the solution to any problem should be inherent in the problem itself. Of course, it might be more convenient in context to bash your head against a wall than to look for the hidden doorway, but it’s really not the best way to go about things in the long run. I come back to my favorite passage from Grothendieck’s Récoltes et Semailles.

Prenons par exemple la tâche de démontrer un théorème qui reste hypothétique (à quoi, pour certains, semblerait se réduire le travail mathématique). Je vois deux approches extrêmes pour s’y prendre. L’une est celle du marteau et du burin, quand le problème posé est vu comme une grosse noix, dure et lisse, dont il s’agit d’atteindre l’intérieur, la chair nourricière protégée par la coque. Le principe est simple: on pose le tranchant du burin contre la coque, et on tape fort. Au besoin, on recommence en plusieurs endroits différents, jusqu’à ce que la coque se casse — et on est content. Cette approche est surtout tentante quand la coque présente des aspérités ou protubérances, par où “la prendre”. Dans certains cas, de tels “bouts” par où prendre la noix sautent aux yeux, dans d’autres cas, il faut la retourner attentivement dans tous les sens, la prospecter avec soin, avant de trouver un point d’attaque. Le cas le plus difficile est celui où la coque est d’une rotondité et d’une dureté parfaite et uniforme. On a beau taper fort, le tranchant du burin patine et égratigne à peine la surface — on finit par se lasser à la tâche. Parfois quand même on finit par y arriver, à force de muscle et d’endurance.

Je pourrais illustrer la deuxième approche, en gardant l’image de la noix qu’il s’agit d’ouvrir. La première parabole qui m’est venue à l’esprit tantôt, c’est qu’on plonge la noix dans un liquide émollient, de l’eau simplement pourquoi pas, de temps en temps on frotte pour qu’elle pénètre mieux, pour le reste on laisse faire le temps. La coque s’assouplit au fil des semaines et des mois — quand le temps est mûr, une pression de la main suffit, la coque s’ouvre comme celle d’un avocat mûr à point ! Ou encore, on laisse mûrir la noix sous le soleil et sous la pluie et peut-être aussi sous les gelées de l’hiver. Quand le temps est mûr c’est une pousse délicate sortie de la substantifique chair qui aura percé la coque, comme en se jouant — ou pour mieux dire, la coque se sera ouverte d’elle-même, pour lui laisser passage.

L’image qui m’était venue il y a quelques semaines était différente encore, la chose inconnue qu’il s’agit de connaître m’apparaissait comme quelque étendue de terre ou de marnes compactes, réticente à se laisser pénétrer. On peut s’y mettre avec des pioches ou des barres à mine ou même des marteaux-piqueurs: c’est la première approche, celle du “burin” (avec ou sans marteau). L’autre est celle de la mer. La mer s’avance insensiblement et sans bruit, rien ne semble se casser rien ne bouge l’eau est si loin on l’entend à peine… Pourtant elle finit par entourer la substance rétive, celle-ci peu à peu devient une presqu’île, puis une île, puis un îlot, qui finit par être submergé à son tour, comme s’il s’était finalement dissous dans l’océan s’étendant à perte de vue…

Le lecteur qui serait tant soit peu familier avec certains de mes travaux n’aura aucune difficulté à reconnaître lequel de ces deux modes d’approche est “le mien” — et j’ai eu occasion déjà dans la première partie de Récoltes et Semailles de m’expliquer à ce sujet, dans un contexte quelque peu différent. C’est “l’approche de la mer”, par submersion, absorption, dissolution — celle où, quand on n’est très attentif, rien ne semble se passer à aucun moment: chaque chose à chaque moment est si évidente, et surtout, si naturelle, qu’on se ferait presque scrupule souvent de la noter noir sur blanc, de peur d’avoir l’air de combiner, au lieu de taper sur un burin comme tout le monde… C’est pourtant là l’approche que je pratique d’instinct depuis mon jeune âge, sans avoir vraiment eu à l’apprendre jamais.

In case you haven’t yet passed your French language qualifier, I’ll give a rough translation.

Take, for example, the task of proving a theorem. I see two extreme approaches one could take. The first is that of hammer and chisel, wherein the problem posed is seen as a large nut, hard and smooth, which contains a nourishing meat protected by the shell. The principle is simple: one puts the edge of the chisel against the shell and hits it hard. If necessary, one tries again in many different places, until the shell cracks — and one is happy. This approach is especially appealing when the shell shows a rough or bumpy patch where it can be grasped. In some cases, such places to grab the nut jump to the eye. In other cases, one must use all one’s senses and search carefully before finding a point of attack. The most difficult case is that where the shell is perfectly round and evenly firm. When hit strongly, the edge of the chisel just scratches the surface — one ends up merely tired. Sometimes the nut will finally crack through mere strength and stamina.

I can illustrate the second approach with the same metaphor of a nut to be opened. The first explanation that comes to mind is to immerse the nut in some softening liquid — water, for instance — and to rub it from time to time to allow the water to penetrate better, but otherwise to leave it alone. Over weeks and months, the shell softens — when the time is right, a flick of the wrist is sufficient, and the shell opens to it like a ripe avocado! Or again, one can leave the nut out in the sun and the rain and even through the icy winter. When the time is right, it is a delicate touch that breaks the shell — or to say it better, the shell will open itself to let one through.

The pictur that came to me recently was again different. The unknown thing one is trying to undertand seems to me like a stretch of land or a hard patch of earth, hard to dig into. One might go at it with picks or mining tools, or even with jackhammers: this is the first approach, that of “chisels” (with or without hammer). The other is that of the sea. The sea advances imperceptibly and noiselessly. Nothing seems to break, nothing moves… Yet eventually it surrounds the land. It slowly becomes a peninsula, then an island, then an islet, and finally it is submerged completely, dissolved into the ocean which stretches as far as the eye can see…

The reader who is familiar with some of my work will have no difficuly determining which of these two approaches is “mine” — and I have had occasion already in the first part of these “Reapings and Sowings” to explain myself on this subject, in a slightly different context. It is “the method of the sea”, by submersion, absorption, dissolution — that where, if one does not pay close attention, nothing seems to happen at any given moment: everything is at each moment so evident and so natural that one feels nervous to write it down in black and white for fear of being others’ disapproval, rather than banging away at a chisel like everyone else… Yet this is the approach that I instinctively took since I was young, never having really noticed it.

As for the title of this post, a feelie is a physical object — often some document — that was packaged with a game and containing information crucial to some puzzle you’d need to solve. That is, if you didn’t buy the game and get the feelie, you couldn’t get past a certain point. It provided a crude level of copy-protection back in the good old days, under the pretense of extending the game experience (more common in non-IF games was asking the user to type in some specified word from the documentation). Thus, a feelie was all too often a hack — a puzzle relying on them was awkward and inelegant, pulling you out of the experience of the game rather than immersing you in it as was hoped.

Blackboards full of equations serve the same obscuring purpose. True understanding never lies in a calculation. The chalk on the board should not be a map, but a lens, and the mathematics is not in the equations, but behind them.

October 19, 2007 Posted by John Armstrong | rants | 5 Comments

Chain Homotopies and Homology

Sorry about going AWOL yesterday, but I got bogged down in writing another exam.

Okay, so we’ve set out chain homotopies as our 2-morphisms in the category $\mathbf{Kom}(\mathcal{C})$ of chain complexes in an abelian category $\mathcal{C}$ . We also know that each of these 2-morphisms is an isomorphism, so decategorifying amounts to saying that two chain maps are “the same” if they are chain-homotopic.

Many interesting properties of chain maps are invariant under chain homotopies, which means that they descend to properties of this decategorified version. Alternately, some properties are defined by 2-functors, which means that if we apply a chain homotopy we change our answer by a 2-morphism in the target 2-category, which must itself be an isomorphism. I like to call these “homotopy covariants”, rather than “invariants”. Anyway, then the decategorification of this property is an invariant, and what I said before applies.

The big one of these properties we’re going to be interested in is the induced map on homology. Let’s consider chain complexes $A$ and $B$ , chain maps $f$ and $g$ from $A$ to $B$ , and let’s say there’s a chain homotopy $\alpha:f\Rightarrow g$ . The chain maps induce maps $\widetilde{f}:H_\bullet(A)\rightarrow H_\bullet(B)$ and $\widetilde{g}:H_\bullet(A)\rightarrow H_\bullet(B)$ . I assert that $\widetilde{f}=\widetilde{g}$ .

To see this, first notice that passing to the induced map is linear. That is, $\widetilde{f}-\widetilde{g}=\widetilde{f-g}$ . So all we really need to show is that a null-homotopic map induces the zero map on homology. But if $\alpha:f\Rightarrow0$ makes $f$ null-homotopic, then $f_n=d^B_{n+1}\circ\alpha_n+\alpha_{n-1}\circ d^A_n$ . When we restrict $f_n$ to the kernel of $d^A_n$ , this just becomes $d^B_{n+1}\circ\alpha_n$ , which clearly lands in the image of $d^B_{n+1}$ , which is zero in $H_n(B)$ , as we wanted to show.

Now if we have chain maps $f:A\rightarrow B$ and $g:B\rightarrow A$ along with chain homotopies $g\circ f\Rightarrow1_A$ and $f\circ g\Rightarrow1_B$ , we say that $A$ and $B$ are “homotopy equivalent”. Then the induced maps on homology $\widetilde{f}:H_\bullet(A)\rightarrow H_\bullet(B)$ and $\widetilde{g}:H_\bullet(B)\rightarrow H_\bullet(A)$ are inverses of each other, and so the homologies of $A$ and $B$ are isomorphic.

This passage from covariance to invariance is the basis for why Khovanov homology works. We start with a 2-category $\mathcal{T}ang$ of tangles (which I’ll eventually explain fore thoroughly). Then we pick a ring $R$ and consider the 2-category $\mathbf{Kom}(R\mathbf{-mod})$ of chain complexes over the abelian category of $R$ -modules. We construct a 2-functor $K:\mathcal{T}ang\rightarrow\mathbf{Kom}(R\mathbf{-mod})$ that picks a chain complex for each number of free ends, a chain map for each tangle, and a chain homotopy for each ambient isotopy of tangles. Then two isotopic tangles are assigned homotopic chain maps — the chain map is a “tangle covariant”. When we pass to homology, we get tangle invariants, which turn out to be related to well-known knot invariants.

October 19, 2007 Posted by John Armstrong | Category theory | 3 Comments

Chain Homotopies

We’ve defined chain complexes in an abelian category, and chain maps between them, to form an $\mathbf{Ab}$ -category $\mathbf{Kom}(\mathcal{C})$ . Today, we define chain homotopies between chain maps, which gives us a 2-category.

First, we say that a chain map $f:A\rightarrow B$ given by $f_n:A_n\rightarrow B_n$ is “null-homotopic” if we have arrows $h_n:A_n\rightarrow B_{n+1}$ such that $f_n=d^B_{n+1}\circ h_n+h_{n-1}\circ d^A_n$ . Here’s the picture:
Chain Homotopy
In particular, the zero chain map with $f_n=0$ for all $n$ is null-homotopic — just pick $h_n=0$ .

Now we say that chain maps $f$ and $g$ are homotopic if $f-g$ is null-homotopic. That is, $f_n-g_n=d^B_{n+1}\circ h_n+h_{n-1}\circ d^A_n$ . We call the collection $h=\{h_n\}$ a chain homotopy from $f$ to $g$ . Then a chain map is null-homotopic if and only if it is homotopic to the zero chain map. We can easily check that this is an equivalence relation. Any chain map is homotopic to itself because $f_n-f_n=0$ and the zero chain map is null-homotopic. If $f$ and $g$ are homotopic by a chain homotopy $h$ , then $-h$ is a chain homotopy from $g$ to $f$ . Finally, if $f-f'$ is null-homotopic by $h$ and $f'-f''$ is null-homotopic by $h'$ , then $f-f''=(f-f')+(f'-f'')$ is null-homotopic by $h+h'$ .

Another way to look at this is to note that we have an abelian group $\hom_{\mathbf{Kom}(\mathcal{C})}(A,B)$ of chain maps from $A$ to $B$ , and the null-homotopic maps form a subgroup. Then two chain maps are homotopic if and only if they differ by a null-homotopic chain map, which leads us to consider the quotient of $\hom_{\mathbf{Kom}(\mathcal{C})}(A,B)$ by this subgroup. We will be interested in properties of chain maps which are invariant under chain homotopies — properties that only depend on this quotient group.

In the language of category theory, the homotopies $h:f\Rightarrow g$ are 2-morphisms. Given 1-morphisms (chain maps) $f$ , $f'$ , and $f''$ from $A$ to $B$ , and homotopies $h:f\Rightarrow f'$ and $h':f'\Rightarrow f''$ , we compose them by simply adding the corresponding components to get $h+h':f\Rightarrow f''$ .

On the other hand, if we have 1-morphisms $f$ and $g$ from $A$ to $B$ , 1-morphisms $f'$ and $g'$ from $B$ to $C$ , and 2-morphisms $h:f\Rightarrow g$ and $h':f'\Rightarrow g'$ , then we can “horizontally” compose these chain homotopies to get $h'\circ h:f'\circ f\Rightarrow g'\circ g$ with components $(h'\circ h)_n=h'_n\circ f_n+g'_{n+1}\circ h_n$ . Indeed, we calculate
$d^C_{n+1}\circ(h'_n\circ f_n+g'_{n+1}\circ h_n)+(h'_{n-1}\circ f_{n-1}+g'_n\circ h_{n-1})\circ d^A_n=$
$d^C_{n+1}\circ h'_n\circ f_n+d^C_{n+1}\circ g'_{n+1}\circ h_n+h'_{n-1}\circ f_{n-1}\circ d^A_n+g'_n\circ h_{n-1}\circ d^A_n=$
$d^C_{n+1}\circ h'_n\circ f_n+h'_{n-1}\circ d^B_n\circ f_n+g'_n\circ d^B_{n+1}\circ h_n+g'_n\circ h_{n-1}\circ d^A_n=$
$(d^C_{n+1}\circ h'_n+h'_{n-1}\circ d^B_n)\circ f_n+g'_n\circ(d^B_{n+1}\circ h_n+h_{n-1}\circ d^A_n)=$
$(f'_n-g'_n)\circ f_n+g'_n\circ(f_n-g_n)=$
$f'_n\circ f_n-g'_n\circ g_n$

We could also have used $h_n\circ f'_n+g_{n+1}\circ h'_n$ and done a similar calculation. In fact, it turns out that $h'_n\circ f_n+g'_{n+1}\circ h_n$ and $h_n\circ f'_n+g_{n+1}\circ h'_n$ are themselves homotopic in a sense, and so we consider them to be equivalent. If we pay attention to this homotopy between homotopies, we get a structure analogous to the tensorator. I’ll leave you to verify the exchange identity on your own, which will establish the 2-categorical structure of $\mathbf{Kom}(\mathcal{C})$ .

One thing about this structure that’s important to note is that every 2-morphism is an isomorphism. That is, if two chain maps are homotopic, they are isomorphic as 1-morphisms. Thus if we decategorify this structure by replacing 1-morphisms by isomorphism classes of 1-morphisms, we are just passing from chain maps to homotopy classes of chain maps. In other words, we pass from the abelian group $\hom_{\mathbf{Kom}(\mathcal{C})}(A,B)$ of chain maps to its quotient by the null-homotopic subgroup.

October 17, 2007 Posted by John Armstrong | Category theory | 5 Comments

Chain maps

As promised, something lighter.

Okay, a couple weeks ago I defined a chain complex to be a sequence $\cdots\rightarrow C_{i+1}\stackrel{d_{i+1}}{\rightarrow}C_i\stackrel{d_i}{\rightarrow}C_{i-1}\rightarrow\cdots$ with the property that $d_{i-1}\circ d_i=0$ . The maps $d_i$ are called the “differentials” of the sequence. As usual, these are the objects of a category, and we now need to define the morphisms.

Consider chain complexes $C=\cdots\rightarrow C_{i+1}\rightarrow C_i\rightarrow C_{i-1}\rightarrow\cdots$ and $D=\cdots\rightarrow D_{i+1}\rightarrow D_i\rightarrow D_{i-1}\rightarrow\cdots$ . We will write the differentials on $C$ as $d^C_i$ and those on $D$ as $d^D_i$ . A chain map $f:C\rightarrow D$ is a collection of arrows $f_i:C_i\rightarrow D_i$ that commute with the differentials. That is, $f_{i-1}\circ d^C_i=d^D_i\circ f_i$ . That these form the morphisms of an $\mathbf{Ab}$ -category should be clear.

Given two chain complexes with zero differentials — like those arising as homologies — any collection of maps will constitute a chain map. These trivial complexes form a full $\mathbf{Ab}$ -subcategory of the category of all chain complexes.

We already know how the operation of “taking homology” acts on a chain complex. It turns out to have a nice action on chain maps as well. Let’s write $Z_i(C)$ for the kernel of $d^C_i$ and $B_i(C)$ for the image of $d^C_{i+1}$ , and similarly for $D$ . Now if we take a member (in the sense of our diagram chasing rules) $x\in_mC_i$ so that $d^C_i\circ x=0$ , then clearly $d^D_i\circ(f_i\circ x)=f_{i-1}\circ d^C_i\circ x=0$ . That is, if we restrict $f_i$ to $Z_i(C)$ , it factors through $Z_i(D)$ . Similarly, if there is a $y\in_mC_{i+1}$ with $d^C_{i+1}\circ y=x$ , then $f_i\circ x=d^D_{i+1}(\circ f_{i+1}\circ y)$ , and thus the restriction of $f_i$ to $B_i(C)$ factors through $B_i(D)$ .

So we can restrict $f_i$ to get an arrow $f_i:Z_i(C)\rightarrow Z_i(D)$ which sends the whole subobject $B_i(C)$ into the subobject $B_i(D)$ . Thus we can pass to the homology objects to get arrows $\widetilde{f}_i:H_i(C)\rightarrow H_i(D)$ . That is, we have a chain map from $H(C)$ to $H(D)$ . Further, it’s straightforward to show that this construction is $\mathbf{Ab}$ -functorial — it preserves addition and composition of chain maps, along with zero maps and identity maps.

October 16, 2007 Posted by John Armstrong | Category theory | 4 Comments

A New Definition of Spans

I was trying to add in duals to the theory, and I ran into some trouble. The fix seems to be something I’d considered a little earlier for a possible generalization, but it seems that duals force the issue. We need to tweak our definition of spans.

Now, most of the definition is fine as it stands. Our objects are just the same as in $\mathcal{C}$ , and our 1-morphisms are spans $A\stackrel{f_l}{\leftarrow}X\stackrel{f_r}{\rightarrow}B$ . When I first (re)invented these things, I stopped at this level. I handled the associativity not with 2-morphisms, but with defining two spans $A\stackrel{f_l}{\leftarrow}X\stackrel{f_r}{\rightarrow}B$ and $A\stackrel{g_l}{\leftarrow}Y\stackrel{g_r}{\rightarrow}B$ to be equivalent if there was an isomorphism $\alpha:X\rightarrow Y$ so that $f_l=g_l\circ\alpha$ and $f_r=g_r\circ\alpha$ . Then I said that the 1-morphisms were equivalence classes of spans, giving me a 1-category.

Now $\mathcal{C}$ still sits inside this category I’ll call $\mathbf{Span}_1(\mathcal{C})$ . Indeed, if we use the same inclusion as before, the only way two arrows of $\mathcal{C}$ can be isomorphic in $\mathbf{Span}(\mathcal{C})$ (and thus equal in $\mathbf{Span}_1(\mathcal{C})$ ) is for them to be equal already in $\mathcal{C}$ .

But we want to pay attention to those 2-morphisms, and that’s where things start to get interesting. See, those arrows $\alpha:X\rightarrow Y$ are nice as 2-morphisms, but they’re not very.. “spanny”. Instead, let’s define a 2-morphism from $A\stackrel{f_l}{\leftarrow}X\stackrel{f_r}{\rightarrow}B$ to $A\stackrel{g_l}{\leftarrow}Y\stackrel{g_r}{\rightarrow}B$ to be itself a span $X\stackrel{\alpha_l}{\leftarrow}M\stackrel{\alpha_r}{\rightarrow}Y$ satisfying $f_l\circ\alpha_l=g_l\circ\alpha_r$ and $f_r\circ\alpha_l=g_r\circ\alpha_r$ . Here’s the picture:
The New Definition of a 2-morphism

Now, we handle the associativity at the 2-morphism level by cutting off the same way we did in $\mathbf{Span}_1(\mathcal{C})$ and say that a 2-morphism is really an equivalence class of spans. This makes the vertical composition of 2-morphisms just the same pullback construction as for the composition of 1-morphisms.

The horizontal composition of these 2-morphisms gets tricky. Here’s another picture:
Composition of 2-Morphisms
Here we have our two 2-morphisms and we’ve already pulled back to get the 1-morphisms for the source and target of the composition. We write $\alpha:M\rightarrow A'$ for the composite $f_r\circ\alpha_l=g_r\circ\alpha_r$ , and similarly $\alpha'$ on the other side.

Now we can pull back the diagram $M\stackrel{\alpha}{\rightarrow}A'\stackrel{\alpha'}{\leftarrow}M'$ to get an object $M''$ with arrows to $M$ and $M'$ . If we follow these arrows, then up to $X$ and $X'$ (respectively) the universal property of $X''$ gives us a unique arrow from $M''$ to $X''$ . Similarly, we have a unique arrow from $M''$ to $Y''$ . These arrows make the required squares commute, and so define a span from $X''$ to $Y''$ which is our composite 2-morphism.

When we compose two spans, again we only have associativity up to isomorphism. In $\mathbf{Span}_1(\mathcal{C})$ , this becomes an equality, so we’re fine. In $\mathbf{Span}(\mathcal{C})$ we made this isomorphism a 2-morphism between the two composite spans. Now in $\mathbf{Span}_2(\mathcal{C})$ we can make this isomorphism into one leg of a span 2-morphism, and everything works out as before. The exchange identity for the two compositions of 2-morphisms also works out, but it’s even more complicated than the definition of horizontal composition.

Seriously, does anyone know of a tool that will render commutative diagrams in 3-D, like with Java or something? This is getting ridiculous.

Anyhow, I think now I can throw away the request that the monoidal structures on $\mathcal{C}$ play nice with the pullbacks. Unfortunately, it’s getting a lot more complicated now and I have other real-world obligations I’ve got to attend to. So I think I’ll back-burner this discussion and move back to something old rather than spend too much time working this stuff out live as I have been doing.

October 15, 2007 Posted by John Armstrong | Category theory | 6 Comments

Braidings on Span 2-Categories

Now that we can add a monoidal structure to our 2-category of spans, we want to add something like a braiding.

So, what’s a braided monoidal 2-category? Again, we need some data:

For any objects $A$ and $B$ an equivalence $R_{A,B}:A\otimes B\rightarrow B\otimes A$ called the “braiding” of $A$ and $B$ .
For any 1-morphism $f:A\rightarrow A'$ and object $B$ , a 2-isomorphism $R_{f,B}:R_{A',B}\circ(f\otimes B)\Rightarrow(B\otimes f)\circ R_{A,B}$ called the braiding of $f$ and $B$ .
For any object $A$ and morphism $g:B\rightarrow B'$ , a 2-isomorphism $R_{A,g}:R_{A,B'}\circ(A\otimes g)\Rightarrow(g\otimes A)\circ R_{A,B}$ called the braiding of $A$ and $g$ .
For any objects $A$ , $B$ , and $C$ , 2-isomorphisms $\tilde{R}_{(A|B,C)}:(B\otimes R_{A,C})\circ(R_{A,B}\otimes C)\Rightarrow R_{A,B\otimes C}$ and $\tilde{R}_{(A,B|C)}:(R_{A,C}\otimes B)\circ(A\otimes R_{B,C})\Rightarrow R_{A\otimes B,C}$ called the “braiding coherence 2-morphisms”.

We define the braiding to be an equivalence rather than an isomorphism because we don’t want to ask it to be exactly invertible. That is, there will be another 1-morphism $R^*_{A,B}:B\otimes A\rightarrow A\otimes B$ with 2-isomorphisms $R^*_{A,B}\circ R_{A,B}\cong1_{A\otimes B}$ and $R_{A,B}\circ R^*_{A,B}\cong1_{B\otimes A}$ . The 2-isomorphisms braiding objects with 1-morphisms act in the place of naturality relations, allowing us to pull 1-morphisms back and forth through the object braiding. And then the hexagon identities from the definition of a braiding in a 1-category are now weakened to the braiding coherence 2-morphisms.

So, where are we going to find this structure for our bicategory $\mathbf{Span}(\mathcal{C})$ ? Well, let’s assume we have a braiding $\beta_{A,B}$ on $\mathcal{C}$ . Then we’ll just define $R_{A,B}$ to be the span $(A\otimes B)\stackrel{1_{A\otimes B}}{\leftarrow}(A\otimes B)\stackrel{\beta_{A,B}}{\rightarrow}(B\otimes A)$ . This is actually a 1-isomorphism, using the obvious inverse.

As we saw before with the tensorator, it turns out that we can set all of the $R_{f,B}$ and the $R_{A,g}$ to be the appropriate identities, as well as all the braiding coherence relations. Requiring the the monoidal product on $\mathcal{C}$ preserve pullbacks turns out to be an extremely powerful condition!

And now what are the conditions that make this data into a braided monoidal 2-category?

For 1-morphisms $f:A\rightarrow A'$ and $g:B\rightarrow B'$ , we have
$(\bigotimes_{g,f}\circ R_{A,B})\bullet((g\otimes A')\circ R_{f,B})\bullet(R_{A',g}\circ(f\otimes B))=$
$((B'\otimes f)\circ R_{A,g})\bullet(R_{f,B'}\circ(A\otimes g))\bullet(R_{A',B'}\circ\bigotimes_{f,g}^{-1})$
For any 1-morphisms $f:A\rightarrow A'$ and $f':A\rightarrow A'$ , 2-morphism $\alpha:f\Rightarrow f'$ , and object $B$ , we have
$((B\otimes\alpha)\circ R_{A,B})\bullet R_{f,B}=R_{f',B}\bullet(R_{A',B}\circ(\alpha\otimes B))$
For any 1-morphisms $g:B\rightarrow B'$ and $g':B\rightarrow B'$ , 2-morphism $\beta:g\Rightarrow g'$ , and object $A$ , we have
$((A\otimes\beta)\circ R_{A,B})\bullet R_{A,g}=R_{A,g'}\bullet(R_{A,B'}\circ(\beta\otimes A))$
For any 1-morphisms $f:A\rightarrow A'$ and $f':A'\rightarrow A''$ and object $B$ , we have
$((B\otimes f')\circ R_{f,B})\bullet(R_{f',B}\circ(f\otimes B))=R_{f'\circ f,B}$
For any 1-morphisms $g:B\rightarrow B'$ and $g':B'\rightarrow B''$ and object $A$ , we have
$((A\otimes g')\circ R_{A,g})\bullet(R_{A,g'}\circ(A\otimes g))=R_{A,g'\circ g}$
For any objects $A$ , $B$ , and $C$ , and 1-morphism $f:C\rightarrow C'$ , we have
$R_{A,B\otimes f}\bullet(\tilde{R}_{(A|B,C')}\circ(A\otimes B\otimes f))=$
$((B\otimes f\otimes A)\circ\tilde{R}_{(A|B,C)})\bullet((B\otimes R_{A,f})\circ(R_{A,B}\otimes C))\bullet((B\otimes R_{A,C'})\circ\bigotimes_{R_{A,B},f})$
There are five more conditions like the last one, with the 1-morphism in other slots and different associations of the three terms.
For any objects $A$ , $B$ , $C$ , $D$ , we have
$\tilde{R}_{(A|B,C\otimes D)}\bullet((B\otimes\tilde{R}_{(A|C,D)})\circ(R_{A,B}\otimes C\otimes D))=$
$\tilde{R}_{(A|B\otimes C,D)}\bullet((B\otimes C\otimes R_{A,D})\circ(\tilde{R}_{(A|B,C)}\otimes D))$
There are two more conditions like the last one, corresponding to different ways of associating the four terms.
For any objects $A$ , $B$ , and $C$ , we have
$(\tilde{R}_{(A|B,C)}\circ(A\otimes R_{B,C}))\bullet R_{A,R_{B,C}}^{-1}\bullet((R_{B,C}\otimes A)\circ\tilde{R}_{(A|B,C)}^{-1})=$
$((C\otimes R_{A,B})\circ\tilde{R}_{(A,B|C)}^{-1})\bullet R_{R_{A,B},C}\bullet(\tilde{R}_{(A,B|C)}\circ(R_{A,B}\otimes C))$ .
$R_{\cdot,\cdot}$ , $\tilde{R}_{(\cdot|\cdot,\cdot)}$ , and $\tilde{R}_{(\cdot,\cdot|\cdot)}$ are each the identity whenever one of their slots is filled with the unit object $\mathbf{1}$ .

Now in our currrent situation, almost all the structure here is trivial, and we have proofs to match! Specifically, all of the 2-morphisms that show up here are just the identities for various 1-morphisms. That is, they move between different ways of writing the same 1-morphism. For example, the first condition just reduces to saying that the composite of three applications of the identity 2-morphism on the span $R_{A',B'}\circ g\circ f$ are the same as three other applications of the identity on the same span. And on and on they go, identities on identities, and there’s ultimately nothing to do here.

So the upshot is that if we have a braiding on $\mathcal{C}$ , then $\mathbf{Span}(\mathcal{C})$ is a braided monoidal 2-category. Dually, $\mathbf{CoSpan}(\mathcal{C})$ gets this structure if $\mathcal{C}$ is a braided monoidal category with pushouts preserved by the monoidal product.

October 12, 2007 Posted by John Armstrong | Category theory | 10 Comments

Monoidal Structures on Span 2-Categories II

As I just stated in my update to yesterday’s post, I’ve given the data for a monoidal structure on the 2-category $\mathbf{Span}(\mathcal{C})$ . Now we need some conditions on the data.

For any object $A$ , the maps $\underline{\hphantom{X}}\otimes A$ and $A\otimes\underline{\hphantom{X}}$ are 2-functors.
For $x$ any object, 1-morphism, or 2-morphism, $x\otimes\mathbf{1}=\mathbf{1}\otimes x=x$
For any object, 1-morphism, or 2-morphism, and any objects and , we have the equalities
- $A\otimes(B\otimes x)=(A\otimes B)\otimes x$
- $A\otimes(x\otimes B)=(A\otimes x)\otimes B$
- $x\otimes(A\otimes B)=(x\otimes A)\otimes B$
For any 1-morphisms , , and , we have the equalities
- $\bigotimes_{A\otimes g,h}=A\otimes\bigotimes_{g,h}$
- $\bigotimes_{f\otimes B,h}=\bigotimes_{f,B\otimes h}$
- $\bigotimes_{f,g\otimes C}=\bigotimes_{f,g}\otimes C$
For any objects $A$ and $B$ we have $1_A\otimes B=A\otimes 1_B=1_{A\otimes B}$
For any 1-morphisms $f:A\rightarrow A'$ and $g:B\rightarrow B'$ , we have $\bigotimes_{1_A,g}=1_{A\otimes g}$ and $\bigotimes_{f,1_B}=1_{f\otimes B}$
For any 1-morphisms $f:A\rightarrow A'$ , $g:B\rightarrow B'$ , and $h:B\rightarrow B'$ and any 2-morphism $\beta:g\Rightarrow h$ , we have $\bigotimes_{f,h}\bullet((f\otimes B')\circ(A\otimes\beta))=((A'\otimes\beta)\circ(f\otimes B))\bullet\bigotimes_{f,g}$
For any 1-morphisms $f:A\rightarrow A'$ , $g:A\rightarrow A'$ , and $h:B\rightarrow B'$ and any 2-morphism $\alpha:f\Rightarrow g$ , we have $\bigotimes_{g,h}\bullet((\alpha\otimes B')\circ(A\otimes h))=((A'\otimes h)\circ(\alpha\otimes B))\bullet\bigotimes_{f,h}$
For any 1-morphisms $f:A\rightarrow A'$ , $g:B\rightarrow B'$ , and $g':B'\rightarrow B''$ , we have $\bigotimes_{f,g'\circ g}=((A'\otimes g')\circ\bigotimes_{f,g})\bullet(\bigotimes_{f,g'}\circ(A\otimes g))$
For any 1-morphisms $f:A\rightarrow A'$ , $f':A'\rightarrow A''$ , and $g:B\rightarrow B'$ , we have $\bigotimes_{f'\circ f,g}=(\bigotimes_{f',g}\circ(f\otimes B))\bullet((f'\otimes B')\circ\bigotimes_{f,g})$

Okay, a bunch of conditions. Notice here that we have stated a bunch of equalities. Most of them are at the level of 2-morphisms, and everything at that level in a 2-morphism should hold on the nose. But some of them are equalities between 1-morphisms, which our philosophy says we should weaken.

Really what we’re laying out here is a semistrict monoidal 2-category, as described in Higher Dimensional Algebra I. Just like for monoidal categories, there’s a “coherence theorem” that tells us that once we specify a number of relations, all the others we want will follow. There’s also something like a “strictification theorem”, but now we can’t just wipe away all the structure morphisms. We can only “semi-strictify” an arbitrary monoidal 2-category. So that’s what we’re doing here and avoiding all the extra conditions that would be required if we had associators and other such things floating around.

Okay, enough of what everyone (who’s crazy enough to work on this stuff) already knows. Let’s get down to what (as far as I can tell) is being worked out for the first time as I’m writing it down here.

For condition 1, let’s just consider tensoring on the left with an object, since tensoring on the right is almost exactly the same. It clearly preserves identity 1-morphisms, since $A\otimes(B\stackrel{1_B}{\leftarrow}B\stackrel{1_B}{\rightarrow}B)$ is just $A\otimes B\stackrel{1_A\otimes 1_B}{\leftarrow}A\otimes B\stackrel{1_A\otimes 1_B}{\rightarrow}A\otimes B$ and we know that $1_A\otimes 1_B=1_{A\otimes B}$ in the monoidal structure on $\mathcal{C}$ . Similarly, an identity 2-morphism in $\mathbf{Span}(\mathcal{C})$ is given by an identity arrow in $\mathcal{C}$ , and tensoring it on the left with $1_A$ gives back the appropriate identity arrow.

Does tensoring on the left with $A$ preserve all three compositions? Sure. It preserves vertical composition of 2-morphisms straight off. It preserves composition of 1-morphisms becase we’re assuming that the tensor product on $\mathcal{C}$ preserves pullbacks. The horizontal composition of 2-morphisms is a little trickier, partly because I was never very explicit on how to compose 2-morphisms like this. Here’s how it looks:
Horizontal Composition of Span 2-morphisms
Start with spans $A\leftarrow X\rightarrow B$ , $A\leftarrow X'\rightarrow B$ , $B\leftarrow Y\rightarrow C$ , and $B\leftarrow Y'\rightarrow C$ . Throw in arrows $\alpha:X\rightarrow X'$ and $\beta:Y\rightarrow Y'$ making the appropriate triangles commute. Then pull back $X\rightarrow B\leftarrow Y$ and $X'\rightarrow B\leftarrow Y'$ to get $Z$ and $Z'$ , respectively. We can follow the arrow from $Z$ to $X$ and then by $\alpha$ on to $X'$ . Similarly we can get an arrow from $Z$ to $Y'$ . If we compose these with the arrows from $X'$ and $Y'$ down to $B$ , the square clearly commutes, so by the universal property of the pullback there is a unique arrow $Z\rightarrow Z'$ . This is the horizontal composite of $\alpha$ and $\beta$ . From here it’s straightforward to see that if I tensor everything in sight on the left with some object, everything will be preserved. And so we have shown condition 1.

Conditions 2 and 3 is all but trivial, since everything we to any object, 1-morphism, or 2-morphism to tensor it with an object is to invoke the monoidal product down on $\mathcal{C}$ , where these associativity and unit constraints hold automatically. Similarly, 5 also follows immediately from the monoidal structure on $\mathcal{C}$ .

If we look back at what we did last time, we see that we can have set up our pullbacks as in the diagram I showed then. In fact, I’m coming to think I was being overly cautious to even bring that up. That is, we can just take the tensorator to be the identity 2-morphism on the appropriate span. This immediately satisfies conditions 4 and 6. The remaining conditions 7, 8, 9, and 10 also fall in line once you write out the compositions in terms of the spans. But I won’t kid you, they look ugly. I took a picture of the diagram for condition 7. Above the center it’s the left of the equation and below the center it’s the right. I’ll eventually TeX these up, but for now suffice to say that if you actually draw out these span diagrams and set the tensorator to be the identity that everything works out smoothly.

So now we’ve proven that the data we laid out yesterday does, in fact, constitute the structure of a monoidal 2-category.

October 11, 2007 Posted by John Armstrong | Category theory | 1 Comment

Monoidal Structures on Span 2-Categories

Now we want to take our 2-categories of spans and add some 2-categorical analogue of a monoidal structure on it.

Here’s what we need:

An object $\mathbf{1}$ called the unit object.
For objects $A_1$ and $A_2$ , an object $A_1\otimes A_2$ .
For an object $A$ and a 1-morphism $f:B\rightarrow C$ , 1-morphisms $A\otimes f:A\otimes B\rightarrow A\otimes C$ and $f\otimes A:B\otimes A\rightarrow C\otimes A$ .
For an object $A$ and a 2-morphism $\alpha:f\Rightarrow g$ , 2-morphisms $A\otimes\alpha:A\otimes f\Rightarrow A\otimes g$ and $\alpha\otimes A:f\otimes A\Rightarrow g\otimes A$ .
For 1-morphisms $f:A\rightarrow A'$ and $g:B\rightarrow B'$ , a 2-morphism $\bigotimes_{f,g}:(f\otimes B')\circ(A\otimes g)\Rightarrow(A'\otimes g)\circ(f\otimes B)$ called the “tensorator”.

Notice that instead of defining the tensor product as a functor, we define its action on a single object and a single 1-morphism (in either order). Then if we have two 1-morphisms we have two ways of doing first one on one side of the tensor product, then the other on the other side. To say that $\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}$ is a functor would say that these two are equal, but we want to weaken this to say that there is some 2-morphism from one to the other.

Now let’s assume that we’ve got a regular monoidal structure on our category $\mathcal{C}$ , and further that this monoidal structure preserves the pullbacks we’re assuming exist in $\mathcal{C}$ . That is, if $D_1$ is a pullback of the diagram $A_1\rightarrow C_1\leftarrow B_1$ and $D_2$ is a pullback of the diagram $A_2\rightarrow C_2\leftarrow B_2$ , then $D_1\otimes D_2$ will be a pullback of the diagram $A_1\otimes A_2\rightarrow C_1\otimes C_2\leftarrow B_1\otimes B_2$ .

So what does this mean for $\mathbf{Span}(\mathcal{C})$ ? Well, the monoidal structure on $\mathcal{C}$ gives us a unit object $\mathbf{1}$ and monoidal product objects $A\otimes B$ . If we have a span $B\stackrel{f_1}{\leftarrow}X\stackrel{f_2}{\rightarrow}C$ and an object $A$ , we can form the spans $A\otimes B\stackrel{1_A\otimes f_1}{\leftarrow}A\otimes X\stackrel{1_A\otimes f_2}{\rightarrow}A\otimes C$ and $B\otimes A\stackrel{f_1\otimes 1_A}{\leftarrow}X\otimes A\stackrel{f_2\otimes 1_A}{\rightarrow}A\otimes C$ . If we have spans $B\stackrel{f_1}{\leftarrow}X\stackrel{f_2}{\rightarrow}C$ and $B\stackrel{g_1}{\leftarrow}Y\stackrel{g_2}{\rightarrow}C$ and an arrow $\alpha:X\rightarrow Y$ with $f_1=\alpha\circ g_1$ and $f_2=\alpha\circ g_2$ then the arrow $1_A\otimes\alpha:A\otimes X\rightarrow A\otimes Y$ satisfies $1_A\otimes f_1=1_A\otimes\alpha\circ1_A\otimes g_1$ and $1_A\otimes f_2=1_A\otimes\alpha\circ1_A\otimes g_2$ , and similarly the arrow $\alpha\otimes1_A:X\otimes A\rightarrow Y\otimes A$ satisfies $f_1\otimes1_A=\alpha\otimes1_A\circ g_1\otimes1_A$ and $f_2\otimes1_A=\alpha\otimes1_A\circ g_2\otimes1_A$ . And so we have our monoidal products of objects with 1- and 2-morphisms.

When we take spans $f=A\stackrel{f_1}{\leftarrow}A''\stackrel{f_2}{\rightarrow}A'$ and $g=B\stackrel{g_1}{\leftarrow}B''\stackrel{g_2}{\rightarrow}B'$ , we can form the following two composite spans:
The Source and Target of the Tensorator of Spans
where we use the assumption that the monoidal product preserves pullbacks to show that the squares in these diagrams are indeed pullback squares.

As we’ve drawn them, these two spans are the same. However, remember that the pullback in $\mathcal{C}$ is only defined up to isomorphism. That is, when we define the pullback as a functor, we choose some isomorphism class of cones, and these diagrams say that the pullbacks we’ve drawn are isomorphic to those defined by the pullback functor. But that means that whatever the “real” pullbacks $C_1$ and $C_2$ are, they’re both isomorphic to $A''\otimes B''$ , and that those isomorphisms play nicely with the other arrows we’ve drawn. And so there will be some isomorphism $\bigotimes_{f,g}:C_1\rightarrow C_2$ between the “real” pullbacks that make the required triangles commute, giving us our tensorator.

Therefore what we have shown is this: Given a monoidal category $\mathcal{C}$ with pullbacks such that the monoidal structure preserves those pullbacks, we get the data for the structure of a (weak) monoidal 2-category on $\mathbf{Span}(\mathcal{C})$ . Dually, we can show that given a monoidal category $\mathcal{C}$ with pushouts, such that the monoidal structure preserves them, we get the data for a monoidal 2-category $\mathbf{CoSpan}(\mathcal{C})$ .

[UPDATE]: In my hurry to get to my second class, I overstated myself. I should have said that we have the data of the monoidal structure. The next post contains the conditions the data must satisfy.

October 10, 2007 Posted by John Armstrong | Category theory | 3 Comments

Spans and Cospans II

There’s something we need to note about spans that will come in extremely handy as we start trying to add structure to our categories of spans.

Remember that we’re starting with a category $\mathcal{C}$ with pullbacks, and from this we construct the weak 2-category $\mathbf{Span}(\mathcal{C})$ . It turns out that we can find $\mathcal{C}$ inside $\mathbf{Span}(\mathcal{C})$ . First of all, we consider $\mathcal{C}$ as a 2-category itself by our usual trick of considering a set as a category — to every morphism in $\mathcal{C}$ , just add one identity 2-morphism and nothing else.

Now we’re going to need an inclusion 2-functor. We could just look for it to preserve compositions up to some natural 2-morphism, but we can actually get preservation on the nose. Just send $f:A\rightarrow B$ to the span $A\leftarrow A\rightarrow B$ , where the left arrow is the identity on $A$ and the right arrow is $f$ . The composite of two such spans looks like this:
Functoriality of the Inclusion
Clearly the identity arrow in $\mathcal{C}$ is sent to the identity span. Since there are only identity 2-morphisms in $\mathcal{C}$ , their image under the inclusion is obvious.

This inclusion has a number of nice properties. First off, it’s always faithful. Clearly two such spans are the same only if the original arrows were the same. But we can even go further to assert that if two spans in the image of the inclusion are even related by a 2-morphism, they have to be from the same arrow in $\mathcal{C}$ . Indeed, here’s the diagram:
Faithfulness of the Inclusion
The only possible arrow in the middle that makes the left triangle commute is the identity, and then the right triangle can only commute if $f=g$ .

On the other hand, the inclusion is almost never full, even if we only ask for “essential” fullness. Indeed, if there’s any non-identity arrow then we could use it on the left of a span to make something that can’t be in the image. On the other hand, if we ask that every span have a 2-morphism from something in the image we find the diagram:
The Inclusion is Not Full
Here we can always pick $h$ to make the right side commute as long as we can find an arrow in the middle that makes the left side commute. But that would mean that every arrow $f$ in $\mathcal{C}$ has an arrow $x$ with $f\circ x=1_A$ . That is, every single arrow in $\mathcal{C}$ would have to be a surjection, which is far too much to ask. And at the level of 2-morphisms there’s not nearly enough in the image to be full.

So the category $\mathcal{C}$ sits inside the 2-category $\mathbf{Span}(\mathcal{C})$ as a sub-2-category. This means (roughly) that if we get some structure on $\mathbf{Span}(\mathcal{C})$ there must be a corresponding structure on $\mathcal{C}$ itself by restriction. Then we can turn around and try to extend structures on $\mathcal{C}$ to the whole of $\mathbf{Span}(\mathcal{C})$ . I’ve worked out some of the basic examples, which I’ll start in on tomorrow. But some of the interesting ones I’ll be working out as I write them up, so this should prove interesting indeed.

October 9, 2007 Posted by John Armstrong | Category theory | Leave a comment

« Previous 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

Subjects
Archives

October 2007

M T W T F S S

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

« Sep Nov »
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider

Hiatus

Chalk is a “Feelie”

Chain Homotopies and Homology

Chain Homotopies

Chain maps

A New Definition of Spans

Braidings on Span 2-Categories

Monoidal Structures on Span 2-Categories II

Monoidal Structures on Span 2-Categories

Spans and Cospans II

About this weblog

Recent Posts

Blogroll

Art

Astronomy

Computer Science

Education

Mathematics

Me

Philosophy

Physics

Politics

Science

RSS Feeds

Feedback

Subjects

Archives

Site info