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.

January 24, 2021

Open Systems: A Double Categorical Perspective (Part 3)

Posted by John Baez

Back to Kenny Courser’s thesis:

Last time I explained the problems with decorated cospans as a framework for dealing with open systems. I vaguely hinted that Kenny’s thesis presents two solutions to these problems: so-called ‘structured cospans’, and a new improved approach to decorated cospans. Now let me explain these!

You may wonder why I’m returning to this now, after three months of silence. The reason is that Kenny, Christina Vasilakopolou, and I just finished a paper that continues this story:

We showed that under certain conditions, structured and decorated cospans are equivalent. So, I’m excited about this stuff again.

Last time I explained Fong’s theorem about decorated cospans:

Fong’s Theorem. Suppose A\mathsf{A} is a category with finite colimits, and make A\mathsf{A} into a symmetric monoidal category with its coproduct as the tensor product. Suppose F:(A,+)(Set,×)F\colon (\mathsf{A},+) \to (\mathsf{Set},\times) is a symmetric lax monoidal functor. Define an F-decorated cospan to be a cospan

       

in A\mathsf{A} together with an element xF(N)x\in F(N) called a decoration. Then there is a symmetric monoidal category with

  • objects of A\mathsf{A} as objects,
  • isomorphism classes of FF-decorated cospans as morphisms.

The theorem is true, but it doesn’t apply to all the examples we wanted it to. The problem is that it’s ‘not categorified enough’. It’s fine if we want to decorate the apex NN of our cospan with some extra structure: we do this by choosing an element of some set F(N).F(N). But in practice, we often want to decorate NN with some extra stuff, which means choosing an object of a category F(N).F(N). So we should really use not a functor

F:(A,+)(Set,×)F\colon (\mathsf{A},+) \to (\mathsf{Set},\times)

but something like a functor

F:(A,+)(Cat,×)F\colon (\mathsf{A},+) \to (\mathbf{Cat},\times)

What do I mean by ‘something like a functor?’ Well, Cat\mathbf{Cat} is not just a category but a 2-category: it has categories as objects, functors as morphisms, but also natural transformations as 2-morphisms. The natural notion of ‘something like a functor’ from a category to a 2-category is called a pseudofunctor. And just as we can define symmetric lax monoidal functor, we can define a symmetric lax monoidal pseudofunctor.

All these nuances really matter when we’re studying open graphs, as we were last time!

Here we want the feet of our structured cospan to be finite sets and the apex to be a finite graph. So, we have A=FinSet\mathsf{A} = \mathsf{FinSet} and for any NFinSetN \in \mathsf{FinSet} we want F(N)F(N) to be the set, or category, of finite graphs having NN as their set of nodes.

I explained last time all the disasters that ensue when you try to let F(N)F(N) be the set of finite graphs having NN as its set of nodes. You can try, but you will pay dearly for it! You can struggle and fight, like Hercules trying to chop all the heads off the Hydra, but you still can’t get a symmetric lax monoidal functor

F:(A,+)(Set,×)F\colon (\mathsf{A},+) \to (\mathsf{Set},\times)

that sends any finite set NN to the set of graphs having NN as their set of nodes.

But there is a perfectly nice category F(N)F(N) of all finite graphs having NN as their set of nodes. And you can get a symmetric lax monoidal pseudofunctor

F:(A,+)(Cat,×)F\colon (\mathsf{A},+) \to (\mathbf{Cat},\times)

that sends any any finite set to the category of finite graphs having it as nodes. So you should stop fighting and go with the flow.

Kenny, Christina and I proved an enhanced version of Fong’s theorem that works starting from this more general kind of F.F. And instead of just giving you a symmetric monoidal category, this theorem gives you a symmetric monoidal double category.

In fact, that is something you should have wanted already, even with Fong’s original hypotheses! The clue is that Fong’s theorem uses isomorphism classes of decorated cospans, which suggests we’d get something better if we used decorated cospans themselves. Kenny tackled this a while ago, getting a version of Fong’s theorem that produces a symmetric monoidal double category, and another version that produces a symmetric monoidal bicategory:

Over the years we’ve realized that the double category is better, because it contains more information and is easier to work with. So, in our new improved approach to decorated cospans, we go straight for the jugular and get a double category. And here’s how it works:

Theorem. Suppose A\mathsf{A} is a category with finite colimits, and make A\mathsf{A} into a symmetric monoidal category with its coproduct as the tensor product. Suppose F:(A,+)(Cat,×)F\colon (\mathsf{A},+) \to (\mathbf{Cat},\times) is a symmetric lax monoidal pseudofunctor. Then there is a symmetric monoidal double category FspF\mathbb{C}\!\mathbf{sp} in which

  • an object is an object of A\mathsf{A}
  • a vertical morphism is a morphism in A\mathsf{A}
  • a horizontal morphism is an F-decorated cospan, meaning a cospan in A\mathsf{A} together with a decoration:

             

  • a 2-morphism is a map of decorated cospans, meaning a commutative diagram in A\mathsf{A}:

             

together with a morphism τ:F(h)(x)x,\tau \colon F(h)(x) \to x', the map of decorations.

We call FspF\mathbb{C}\!\mathbf{sp} a decorated cospan double category. And as our paper explains, this idea lets us fix all the broken attempted applications of Fong’s original decorated cospan categories!

All this is just what any category theorist worth their salt would try, in order to fix the original problems with decorated cospans. It turns out that proving the theorem above is not so easy, mainly because the definition of ‘symmetric monoidal double category’ is rather complex. But if you accept the theorem—including the details of how you get the symmetric monoidal structure on the double category, which I have spared you here—then it doesn’t really matter much that the proof takes work.

Next time I’ll tell you about the other way to fix the original decorated cospan formalism: structured cospans. When these work, they are often easier to use.


  • Part 1: an overview of Courser’s thesis and related papers.

  • Part 2: problems with the original decorated cospans.

  • Part 3: the new improved decorated cospans.

Posted at January 24, 2021 12:44 AM UTC

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

2 Comments & 0 Trackbacks

Re: Open Systems: A Double Categorical Perspective (Part 3)

In the commutative diagram near the end it looks like you have mixed up NN' and YY'.

Posted by: RodMcGuire on January 24, 2021 3:24 PM | Permalink | Reply to this

Re: Open Systems: A Double Categorical Perspective (Part 3)

Thanks! It’s fixed now:

Posted by: John Baez on January 24, 2021 7:33 PM | Permalink | Reply to this

Post a New Comment