Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

August 11, 2017

A Graphical Calculus for Proarrow Equipments

Posted by John Baez

guest post by David Myers

Proarrow equipments (which also go by the names “fibrant double categories” and “framed bicategories”) are wonderful and fundamental category-like objects. If categories are the abstract algebras of functions, then equipments are the abstract algebras of functions and relations. They are a fantastic setting to do formal category theory, which you can learn about in Mike’s post about them on this blog!

For my undergraduate thesis, I came up with a graphical calculus for working with equipments. I wasn’t the first to come up with it (if you’re familiar with both string diagrams and equipments, it’s basically the only sort of thing that you’d try), but I did prove it sound using a proof similar to Joyal and Street’s proof of the soundness of the graphical calculus for monoidal categories. You can see the full paper on the arXiv, or see the slides from a talk I gave about it at CT2017 here. Below the fold, I’ll show you the diagrams and a bit of what you can do with them.

What is a Double Category?

A double category is a category internal to the category of categories. Now, this is fun to say, but takes a bit of unpacking. Here is a more elementary definition together with the string diagrams:

Definition: A double category has

  • Objects AA, BB, C,C, \ldots, which will be written as bounded plane regions of different colors , , , \ldots.
  • Vertical arrows f:f : \rightarrow , \ldots, which we will just call arrows and write as vertical lines , directed downwards, dividing the plane region from .
  • Horizontal arrows JJ, KK, H:H : \to , \ldots, which we will just call proarrows and write as horizontal lines dividing the plane region from .
  • 2-cells ,\ldots, are represented as beads between the arrows and proarrows ,\ldots

The usual square notation is on the left, and the string diagrams are on the right.

There are two ways to compose 2-cells: horizontally, and vertically. These satisfy and interchange law saying that composing horizontally and then vertically is the same as composing vertically and then horizontally.

Note that when we compose 2-cells horizontally, we must compose the vertical arrows. Therefore, the vertical arrows will form a category. Similary, when we compose 2-cells vertically, we must compose the horizontal proarrows. Therefore, the horizontal proarrows will form a category. Except, this is not quite true; in most of our examples in the wild, the composition of proarrows will only commute up to isomorphism, so they will form a bicategory. I’ll just hand wave this away for the rest of the post.

This is about all there is to the graphical calculus for double categories. Any deformation of a double diagram that keeps the vertical arrows vertical and the horizontal proarrows horizontal will describe an equal composite in any double category.

Here are some examples of double categories:

In many double categories that we meet “in the wild”, the arrows will be function-like and the proarrows relation-like. These double categories are called equipments. In these cases, we can turn functions into relations by taking their graphs. This can be realized in the graphical calculus by bending vertical arrows horizontal.

Companions, Conjoints, and Equipments

An arrow has a companion if there is a proarrow together with two 2-cells and such that

= and = .

I call these the “kink identities”, because they are reminiscent of the “zig-zag identities” for adjunctions in string diagrams. We can think of as the graph of as a subset of its domain times its codomain.

Similarly, is said to have a conjoint if there is a proarrow together with two 2-cells and such that

== and == .

Definition: A proarrow equipment is a double category where every arrow has a conjoint and a companion.

The prototypical example of a proarrow equipment, and also the reason for the name, is the equipment of categories, functors, profunctors, and profunctor morphisms. In this equipment, companions are the restriction of the hom of the codomain by the functor on the left, and conjoints are the restriction of the hom of the codomain by the functor on the right.

In the equipment with objects sets, arrows functions, and proarrows relations, the companion and conjoint are the graph of a function as a relation from the domain to codomain or from the codomain to domain respectively.

The following lemma is a central elementary result of the theory of equipments:

Lemma (Spider Lemma): In an equipment, we can bend arrows. More formally, there is a bijective correspondence between diagrams of form of the left, and diagrams of the form of the right:

\approx .

Proof. The correspondence is given by composing the outermost vertical or horizontal arrows by their companion or conjoint (co)units, as suggested by the slight bends in the arrows above. The kink identities then ensure that these two processes are inverse to each other, giving the desired bijection.

In his post, Mike calls this the “fundamental lemma”. This is the engine humming under the graphical calculus; in short, the Spider Lemma says that we can bend vertical wires horizontal. We can use this bending to prove a classical result of category theory in a very general setting.

Hom-Set and Zig-Zag Adjunctions

It is a classical fact of category theory that an adjunction fg:ABf \dashv g : A \rightleftarrows B may be defined using natural transformations η:idfg\eta: \id \rightarrow fg and ϵ:gfid\epsilon: gf \rightarrow \id (which we will call a zig-zag adjunction, after the coherence conditions they have to satisfy – also called the triangle equations), or by giving a natural isomorphism ψ:B(f,1)A(1,g)\psi : B(f, 1) \cong A(1, g). This equivalence holds in any proarrow equipment, which we can now show quickly and intuitively with string diagrams.

Suppose we have an adjunction \dashv , given by the vertical cells and , satisfying the zig-zag identities

= and = .

By bending the unit and counit, we get the horizontal cells and . Bending the zig-zag identities shows that these maps are inverse to each other

= = = ,

and are therefore the natural isomorphism \cong we wanted.

Going the other way, suppose is a natural isomorphism with inverse . That is,

= and = .

Then we can define a unit and counit by bending. These satisfy the zig-zag identities by pulling straight and using (1):

= = = ,

= = = .

Though this proof can be discovered graphically, it specializes to the usual argument in the case that the equipment is an equipment of enriched categories!

And Much, Much More!

In the paper, you’ll find that every deformation of an equipment diagram gives the same composite – the graphical calculus is sound. But you’ll also find an application of the calculus: a “Yoneda-style” embedding of every equipment into the equipment of categories enriched in it. The paper still definitely needs some work, so I welcome any feedback in the comments!

I hope these string diagrams make using equipments easier and more fun.

Posted at August 11, 2017 6:15 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2976

20 Comments & 0 Trackbacks

Re: A Graphical Calculus for Proarrow Equipments

Cool stuff! Are there any ‘power users’ of proarrow equipments—people who use them a lot?—who might benefit from this technology?

My friend Paul-André Melliès leaps to mind.

Posted by: John Baez on August 12, 2017 7:20 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

I sure hope so!

Mike Shulman’s been using them a lot, and Emily Riehl and Dominic Verity have recently shown that you can get a “homotopy equipment” of oo-categories, functors, and modules from an oo-cosmos.

At CT2017, Christina Vasilakopoulou and Evangelia Aleiferi (who I was in the Kan seminar with) gave very cool talks on monoidal/cartesian fibrant double categories. I hope they can find some use for the diagrams, especially if it means working in 3 dimensions.

Speaking of 3 dimensional diagrams, those slides by Paul-André Melliès are gorgeous and very interesting! I’ve had a hunch that you can ‘topologize’ Girard’s Logic of Unity with equipment diagrams, associating the polarities to the possible directions of vertical arrows: down (neutral), left, and right. Paul-André sounds like the right sort of person to tell me if this makes any sense!

Posted by: David Jaz Myers on August 12, 2017 5:42 PM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

This is very cool! I’m looking forward to making use of it.

One minor note: I think your use of the words “vertical” and “horizontal” is potentially confusing. Of course your “vertical arrows” are being drawn as vertical lines, but if you think of them as a morphism from one plane region to the other, they actually travel horizontally, so in the usual Poincare dual “arrow diagrams” they would be called the “horizontal arrows”. Personally, I generally find it helpful to orient my string diagrams and arrow diagrams so that Poincare duality makes them correspond, so I would call your “vertical” arrows “horizontal” and vice versa.

That said, overall I’ve been getting rather fed up with the terminological mess of “horizontal” versus “vertical” in double categories. Half the community draws the arrows horizontal and the proarrows vertically and the other half does it the other way. So if you hear a double category theorist say “horizontal arrow” and you don’t know to which school they belong, you have to ask “are those the arrows or the proarrows”? And just in general, naming things after their notations is a bad practice. Of course in an equipment we can say “arrows” and “proarrows”, but in a general double category that seems less appropriate, yet we still want to distinguish between the “strict” direction and the “weak” one. My current proposal is to say “tight arrow” and “loose arrow”, borrowing the terminology of F-categories.

Posted by: Mike Shulman on August 12, 2017 8:30 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

It makes a lot of sense to draw the ‘strict’ arrows as straight arrows and the ‘weak’ arrows as wiggly or barred arrows. Recently on Twitter Emily Riehl asked “when does it make sense to draw a morphism as a wiggly arrow?”, and I said something like “when the morphism takes its time getting there, or is somewhat indirect”. I think a profunctor or span or cospan is indirect in exactly this sense.

Since ‘straight arrow’ has a standard meaning in slang, which is compatible with what we’re talking about here, I’d be happy to use ‘straight arrow’ for what you’re now calling a ‘tight arrow’. I don’t love the term ‘tight arrow’ because I have trouble imagining what it would mean for an arrow to be ‘tight’ (and I don’t know the math you’re using to get that term).

Unfortunately if someone is not a straight arrow we don’t call them a ‘wiggly arrow’.

But anyway, all these terms seem more evocative than ‘vertical’ and ‘horizontal’ arrow, so I applaud your general idea here.

Posted by: John Baez on August 12, 2017 8:38 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

I like the terminology of a “straight arrow” because if you ask it a question (apply it to an element) you get a single answer.

But it doesn’t play so well with the string diagrams, because you then have the law “you can bend straight arrows”. This seems like a contradiction. Also, if you do call the proarrows “wiggly arrows”, then you “can’t bend wiggly arrows”!

I like the name “loose arrow” for a proarrow, since we can often think of them as smeared out functions of a sort. But to me, “tight arrow” sounds like a loose arrow with a left adjoint – usually called a “map” in bicategory theory. This is because a “tight arrow” is not quite an “arrow”, but suggests (to me) a loose arrow that happens to be tight.

So, if we called maps between metric spaces “arrows”, then a “loose arrow” would be a map that associates to each point a “distance function” to its “image” (an arrow loosened by distance), and then a “tight arrow” would be a loose arrow where all the “images” are limits of Cauchy sequences in the codomain.

I think I may have missed the point here. Are they called “tight” and “loose” because one forms a category and the other a bicategory?

Posted by: David Jaz Myers on August 12, 2017 6:10 PM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

“Straight arrow” and “wiggly arrow” is still naming things after their notation, which I don’t think is a good idea in general. In particular, it’s very far from standard to draw the proarrows as wiggly; in fact I can’t think offhand of anyone who does it that way. Most people write them with a bar or a slash or a dot in the middle.

But to me, “tight arrow” sounds like a loose arrow with a left adjoint – usually called a “map” in bicategory theory. This is because a “tight arrow” is not quite an “arrow”, but suggests (to me) a loose arrow that happens to be tight.

I don’t quite get your point here. For F-categories, “loose” was chosen as a word that might encompass both “lax”, “colax”, and “pseudo” but be free of any existing meaning, and then “tight” was the obvious counterpart. In an F-category, as in an equipment, a tight arrow is indeed a special case of a loose one. But that doesn’t imply the tight arrows have to be the maps; a representable profunctor is also a special case of a profunctor. And more generally I don’t think the terminology implies to me that every tight arrow should be loose; in ordinary language something that’s tight is not usually also loose.

Posted by: Mike Shulman on August 12, 2017 10:56 PM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

For F-categories, “loose” was chosen as a word that might encompass both “lax”, “colax”, and “pseudo” but be free of any existing meaning, and then “tight” was the obvious counterpart.

Ah, I see. So “loose” is not necessarily talking about how “spread out” the image of the “(multi)function” is (as in the case of a relation/profunctor), but could refer to how strictly the “function” preserves structure (e.g. laxly, oplaxly, etc.). I like the idea that lax monoidal functors preserve the tensor product loosely.

I’ve gone to the nnLab page, and now I see that the 2-algebra examples are usually taking the tight arrows to be strict/pseudo morphisms and the loose ones to be lax/oplax/etc. In this case it’s clear what it means to be tight and what it means to be loose and why they both deserve to be called “arrows”. I was thinking of the double categories of 2-algebras where one kind of arrows is the lax ones and the other is the oplax ones (so that companions are pseudo, and conjunctions are doctrinal adjunctions). In that double category, it isn’t clear which direction should be tight and which should be loose.

And more generally I don’t think the terminology implies to me that every tight arrow should be loose; in ordinary language something that’s tight is not usually also loose.

Yeah, I think you’re right about this. I guess what I felt was that when you mention that an arrow is tight, it feels like it could be loosened, so that it has an underlying loose arrow, whereas I might not feel that way if you just called it an arrow.

On a side note, how do you feel about calling a double category with all companions a “company”?

Posted by: David Jaz Myers on August 12, 2017 11:44 PM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

I was thinking of the double categories of 2-algebras where one kind of arrows is the lax ones and the other is the oplax ones… In that double category, it isn’t clear which direction should be tight and which should be loose.

Right. I wasn’t proposing tight/loose as general terminology for all double categories, only those in which there is a strict direction and a weak direction. If both directions are equally strict (or weak) then I don’t have a suggestion that’s better than “horizontal” and “vertical”. I suppose one could try “left” and “right”, maybe. Or “morphism” and “comorphism”?

On a side note, how do you feel about calling a double category with all companions a “company”?

Umm… not very good? (-:O Does such a thing really need a special name? (It’s basically equivalent to an \mathcal{F}-category…)

Posted by: Mike Shulman on August 13, 2017 5:36 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

Mike wrote:

“Straight arrow” and “wiggly arrow” is still naming things after their notation, which I don’t think is a good idea in general.

Okay, so let’s stop calling 1-morphisms “arrows”.

Posted by: John Baez on August 13, 2017 1:10 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

Thanks!

I agree with all this. In the paper I try to more consistently refer to things as “arrows” and “proarrows” alone. I’ll keep the thread about naming going below though.

I chose to flip the conventions because in most of the papers I was reading (e.g. yours) the “functions” are vertical. I wanted the “functions” to be vertical as well (even if they act horizontally), since I like being able to remember the rule “they can bend any way, so long as they flow down”. But it is very far from standard, and isn’t helped that there can also be different conventions on how to orient the equipments themselves (for example, is a profunctor J:ABJ : A \to B a functor J:A op×BSetJ : A^{\text{op}} \times B \to \text{Set} or J:A×B opSetJ : A \times B^{\text{op}} \to \text{Set}?)

Posted by: David Jaz Myers on August 12, 2017 5:52 PM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

Great post! A question: for Chow motives I see the arrows XX to YY should be correspondences XΣYX \leftarrow \Sigma \rightarrow Y and proarrows should be things in the Chow ring Ch(X×Y).Ch(X \times Y). What are the 22-cells here?

Posted by: Jacob Gross on August 12, 2017 7:01 PM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

As a preliminary to answering your question it would help to find a good notion of a 2-morphism between two correspondences from XX to YY, which seems very easy to do, and a good notion of a 2-morphism between two elements of the Chow ring Ch(X×Y)Ch(X \times Y), which is not so easy to do.

However, there should be a way to fix this: the Chow ring Ch(X)Ch(X) consists of equivalence classes, namely equivalence classes of linear combinations of algebraic cycles in XX modulo rational equivalence. So, we should be able to work instead with a groupoid having linear combinations of algebraic cycles as objects and some sort of morphism between two such cycles whenever they are rationally equivalent.

The most boring option would be simply to formally insert a single 1-morphism between two linear combinations of algebraic cycles whenever they are rationally equivalent: then we’d get a groupoid with at most one morphism between any two objects — which is just a fancy way of thinking about an equivalence relation.

It would be more interesting if we could sometimes find several different things that ‘witness’ the rational equivalence of two fixed algebraic cycles. And maybe we can, since rational equivalence is witnessed by the existence of a suitable divisor, and sometimes two different functions have the same divisor.

If we could get this to work and get something else to work, I think I could answer your question.

Posted by: John Baez on August 13, 2017 1:37 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

Thanks for this!

I noticed that Harris and Eisenbud’s book uses a different (but equivalent) definition of rational equivalence than Fulton:

Definition. Let Rat(X)Z(X)Rat(X) \hookrightarrow Z(X) be the subgroup generated by differences of the form Φ({t 0}×X)Φ({t 1}×X)\langle \Phi \cap (\{t_0\} \times X) \rangle - \langle \Phi \cap (\{t_1\} \times X)\rangle where t 0,t 1 1t_0,t_1 \in \mathbb{P}^1 and Φ\Phi is a subvariety of 1×X\mathbb{P}^1 \times X not contained in any fiber {t}×X\{t\} \times X We say that two cycles are rationally equivalent if their difference is in Rat(X)(X).

e.g. there is some family of subvarieties interpolating between them. Maybe we could take the “Chow groupoid” whose objects are algebraic cycles and whose morphisms are choices of interpolations between them?

Posted by: Jacob Gross on August 13, 2017 1:50 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

I don’t know much about these objects, so this is a total guess.

I’d think we’d want our arrows to be regular maps of varieties, and our proarrows to be correspondences. Then a 2-cell could be a rational map between correspondences making the diagram you’d write down commute.

Then the Chow ring would be recovered I think by looking at subterminal proarrows up to isomorphism; in other words, we take subvarieties of X×YX \times Y and quotient by rational equivalence. These aren’t quite algebraic cycles though, because you can’t take formal linear combinations of them.

I think that you can get the intersection product from composition of proarrows but I’m really not sure.

Posted by: David Jaz Myers on August 13, 2017 2:04 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

I think that’s a great idea.

I like this definition of rational equivalence better than what I see on Wikipedia. It seems to lend itself toward creating a Chow groupoid where morphisms are things like these ‘interpolations’. One problem is that I don’t see how, in general, to compose two interpolations and get another interpolation. (Sometimes you can, but it seems you have to be lucky.) So, one may need to create a category where the morphisms are formal composites of interpolations, and then make that into a groupoid (if one wants) by formally decreeing that ‘running an interpolation backward in time’ (from t 1t_1 back to t 0t_0) gives the inverse of an interpolation.

(When one is forced to do a lot of ‘formal’ stuff like this to get a groupoid, it’s often because one is secretly dealing not with a mere groupoid but a higher structure: I can imagine using 2\mathbb{P}^2 to define ‘interpolations between interpolations’, or 2-simplexes in a simplicially enriched category where the 1-simplexes are interpolations. Has anyone done this?)

Anyway, once one has sorted this out, the question is whether one can compose an object of the Chow groupoid of X×YX \times Y (i.e. an algebraic cycle in X×YX \times Y) and a correspondence from YY to ZZ (i.e. some suitably nice span of varieties YΣZY \leftarrow \Sigma \rightarrow Z to get a correspondence from XX to ZZ. And it seems the answer is yes, since an algebraic cycle in X×YX \times Y is a special sort of correspondence from XX to YY.

If all this works well, I believe one is on track for defining 2-cells of the sort you originally asked about.

Posted by: John Baez on August 13, 2017 2:12 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

If these 2-cells are to fill a square, how do they play with the correspondences?

Posted by: David Jaz Myers on August 13, 2017 2:39 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

David wrote:

If these 2-cells are to fill a square, how do they play with the correspondences?

I keep flip-flopping on whether composing a correspondence from XX to YY and an object in a ‘Chow groupoid’ CH(Y×Z)CH(Y \times Z) should give

  1. a correspondence from XX to ZZ or

  2. an object in the Chow groupoid CH(X×Z)CH(X \times Z).

In case 1 a square should be a map between correspondences. In case 2 a square should be a morphism in a Chow groupoid. You know this, even if you don’t know what any of these things are, just by knowing a bunch of examples of double categories.

(It’s also possible that correspondences and objects of Chow groupoids are both special cases of some more general thing, and composing a correspondence and an object in a Chow groupoid gives that more general thing. Then a square could be a morphism between those more general things.)

To figure out which case we’re in, it would help a lot to make up our minds what a ‘Chow groupoid’ is!

I guess it’s time to look up some definitions and make some wild guesses.

A correspondence from XX to YY is something like a map of varieties ΣX×Y\Sigma \to X \times Y. I hear that in Fulton’s book Intersection Theory he defines it to be a Zariski closed subset ΣX×Y\Sigma \subseteq X \times Y. (I’m so bad at algebraic geometry that I don’t know if this is different from a subvariety!) Other people use definitions that treat XX and YY asymmetrically, but let’s not get into that just now.

An element in the good old Chow group is an equivalence class of linear combinations of subvarieties ΣX×Y\Sigma \hookrightarrow X \times Y. So, a reasonable definition of Chow groupoid (or really 2-group) might take linear combinations of subvarieties as objects, and some sort of ‘homology’ or ‘linear combination of interpolations’ (see above) as morphisms.

To keep the technical details to a minimum, let’s say a correspondence from XX to YY is a subvariety of X×YX \times Y. Then every correspondence from XX to YY should give an object in the Chow 2-group CH(X×Y)CH(X \times Y). So, it’s looking like we’re in case 2.

But we’re not out of the woods yet; there’s stuff to check and I think it will require tweaking some things.

Posted by: John Baez on August 13, 2017 10:59 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

John wrote:

I can imagine using 2\mathbb{P}^2 to define ‘interpolations between interpolations’, or 2-simplexes in a simplicially enriched category where the 1-simplexes are interpolations. Has anyone done this?

Sort of. 𝔸 1\mathbb{A}^1 homotopy theory works a lot like this, except it uses the affine line 𝔸 1\mathbb{A}^1 to parametrize homotopies instead of the projective line 1\mathbb{P}^1, and so on for these higher homotopies.

I’m not sure how Harris and Eisenbud’s definition of rational equivalence would change if we used 𝔸 1\mathbb{A}^1 instead of 1\mathbb{P}^1.

Posted by: John Baez on August 13, 2017 2:20 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

I see the analogy to usual homotopy here. If you have two subspaces VV and WW of an ambient space XX, and you want to say that VV and WW are homotopic “within XX”, one way to do it would be to get a “tube” Φ[0,1]×X\Phi \subseteq [0, 1] \times X with Φ{0}×X=V\Phi \cap \{0\} \times X = V and Φ{1}×X=W\Phi \cap \{1\} \times X = W interpolating between them.

Posted by: David Jaz Myers on August 13, 2017 2:37 AM | Permalink | Reply to this

Re: A Graphical Calculus for Proarrow Equipments

Great, I would love to get my hands on an equipment of Chow motives.

I don’t think it would work with 𝔸 1\mathbb{A}^1. To show the Eisenbud-Harris definition is equivalent to the usual one you take the projection Φ 1\Phi \to \mathbb{P}^1 and then take the preimages of 0, 10, \infty \in \mathbb{P}^1 to get a divisor of zeros and poles, rationally equivalent to 00. It looks like point at \infty is essential.

Posted by: Jacob Gross on August 13, 2017 2:47 AM | Permalink | Reply to this

Post a New Comment