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.

July 1, 2019

Structured Cospans

Posted by John Baez

My grad student Kenny Courser gave a talk at the 4th Symposium on Compositional Structures. He spoke about his work with Christina Vasilakopolou and me. We’ve come up with a theory that can handle a broad class of open systems, from electrical circuits to chemical reaction networks to Markov processes and Petri nets. The idea is to treat open systems as morphisms in a category of a particular kind: a ‘structured cospan category’.

Here is his talk:

In July 11th I’m going to talk about structured cospans at the big annual category theory conference, CT2019:

I borrowed more than just the title from Kenny’s talk… but since I’m an old guy, they’re giving me time to say more stuff. For full details, try Kenny’s thesis:

This thesis is not quite in its final form, so I won’t try to explain it all now. But it’s full of great stuff, so I hope you look at it! If you have any questions or corrections please let us know.

We’ve been working on this project for a couple of years, so there’s a lot to say… but right now let me just tell you what a ‘structured cospan’ is.

Suppose you have any functor L:AX.L \colon \mathsf{A} \to \mathsf{X}. Then a structured cospan is a diagram like this:

\qquad

For example if L:AXL \colon \mathsf{A} \to \mathsf{X} is the functor from sets to graphs sending each set to the graph with that set of vertices and no edges, a structured cospan looks like this:

\qquad

It’s a graph with two sets getting mapped into its set of vertices. I call this an open graph. Or if L:AXL \colon \mathsf{A} \to \mathsf{X} is the functor from sets to Petri nets sending each set to the Petri having that set of places and nothing else, a structured cospan looks like this:

\qquad

You can read a lot more about this example here:

It illustrates many ideas from the general theory of structured cospans: for example, what we do with them.

You may have heard of a similar idea: ‘decorated cospans’, invented by Brendan Fong. You may wonder what’s the difference!

Kenny’s talk explains the difference pretty well. Basically, decorated cospans that look isomorphic may not be technically isomorphic. For example, if we have an open graph like this:

\qquad

and its set of edges is {a,b,c,d},\{a,b,c,d\}, this is not isomorphic to the identical-looking open graph whose set of edges is {b,c,d,e}.\{b,c,d,e\}. That’s right: the names of the edges matter!

This is an annoying glitch in the formalism. As Kenny’s talk explains, structured cospans don’t suffer from this problem.

My talk at CT2019 explains another way to fix this problem: using a new improved concept of decorated cospan! This new improved concept gives results that match those coming from structured cospan in many cases. Proving this uses some nice theorems proved by Kenny Courser, Christina Vasilakopoulou and also Daniel Cicala.

But I think structured cospans are simpler than decorated cospans. They get the job done more easily in most cases, though they don’t handle everything that decorated cospans do.

I’ll be saying more about structured cospans as time goes on. The basic theorem, in case you’re curious but don’t want to look at my talk, is this:

Theorem. Let A\mathsf{A} be a category with finite coproducts, X\mathsf{X} a category with finite colimits, and L:AXL \colon \mathsf{A} \to \mathsf{X} a functor preserving finite coproducts. Then there is a symmetric monoidal category LCsp(X){}_L \mathsf{Csp}(\mathsf{X}) where:

  • an object is an object of A\mathsf{A}
  • a morphism is an isomorphism class of structured cospans:

\qquad

Here two structured cospans are isomorphic if there is a commutative diagram of this form:

\qquad

If you don’t want to work with isomorphism classes of structured cospans, you can use a symmetric monoidal bicategory where the 1-morphisms are actual structured cospans. But following ideas of Mike Shulman, it’s easier to work with a symmetric monoidal double category. So:

Theorem. Let A\mathsf{A} be a category with finite coproducts, X\mathsf{X} a category with finite colimits, and L:AXL \colon \mathsf{A} \to \mathsf{X} a functor preserving finite coproducts. Then there is a symmetric monoidal double category Lsp(X){_L \mathbb{C}\!\mathbf{sp}(\mathsf{X})} where:

  • an object is an object of A\mathsf{A}

  • a vertical 1-morphism is a morphism of A\mathsf{A}

  • a horizontal 1-cell is a structured cospan

\qquad

  • a 2-morphism is a commutative diagram

\qquad

Posted at July 1, 2019 7:39 PM UTC

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

5 Comments & 0 Trackbacks

Re: Structured Cospans

Where’s the nlab pages for Decorated and Structured Cospans? I only see them mentioned on Comma Double Category (which I added myself).

Posted by: Max S. New on July 2, 2019 8:36 PM | Permalink | Reply to this

Re: Structured Cospans

Max S. New wrote:

Where’s the nLab pages for Decorated and Structured Cospans?

Somewhere in the future, I guess. I suppose creating them would be an ingenious way for me to procrastinate on finishing the first paper on structured cospans. But I should really finish that, so maybe someone else can start the nLab pages.

Posted by: John Baez on July 4, 2019 8:46 PM | Permalink | Reply to this

Re: Structured Cospans / Decorated cospans

This seems a nice definition. Thanks for the link to Kenny’s thesis, which looks really thorough.

I can’t shake off the following attempt at understanding decorated cospans. Maybe it is totally wrong, or maybe it connects to your perspective or something in Brendan or Kenny’s theses. I’m just trying to match it all to something more familiar.

Let CC have sums. The main ingredient for decorated cospans, a lax monoidal functor F:CSetF:C\to \mathbf{Set}, is the same thing as a monoid FF in Set C\mathbf{Set}^C. A monoid in any reasonable category induces a monad (free module), so in particular we have a monad F×()F\times (-) on Set C\mathbf{Set}^C. It extends to a monad on Span(Set C)\mathrm{Span}(\mathbf{Set}^C) for some general reason, so we can consider the Kleisli (bi)-category for the monad. Now I think the category of FF-decorated spans embeds faithfully in this Kleisli category, by the Yoneda embedding. That’s to say, to give a decorated cospan

(1)cad1F(a) c \to a \leftarrow d\quad 1\to F(a)

is to give a span in Set C\mathbf{Set}^C

(2)ycya(F×yd) y c \leftarrow y a \rightarrow (F\times y d)

and the fancy composition of decorated spans is just Kleisli composition. (Here yc=C(c,)y c=C(c,-) is the Yoneda embedding.) Is that right / reasonable?

Posted by: Sam Staton on July 4, 2019 10:10 AM | Permalink | Reply to this

Re: Structured Cospans / Decorated cospans

Interesting. I’d have to do some calculating to check this. My first question is this. In the usual approach, it’s really obvious that the category of decorated cospans is a dagger-category. That is, there’s an obvious symmetry in the whole formalism, which maps cadc \leftarrow a \rightarrow d to dacd \leftarrow a \rightarrow c. The Kleisli approach you describe obscures that. Is the symmetry still there, just hiding?

Posted by: John Baez on July 4, 2019 8:42 PM | Permalink | Reply to this

Re: Structured Cospans / Decorated cospans

It’s a good question. It’s clear that the morphisms turn around, because a span caF×dc \leftarrow a \rightarrow F\times d is the same thing as a morphism ac×F×da\to c\times F\times d. But there’s a little bit of work to show that the composition is respected by this switch. Incidentally I think this is also a reasonable intuition towards showing that it’s also a compact closed category.

Posted by: Sam Staton on July 7, 2019 10:33 PM | Permalink | Reply to this

Post a New Comment