Open Systems: A Double Categorical Perspective (Part 2)

Back to Kenny Courser’s thesis:

• Kenny Courser, Open Systems: A Double Categorical Perspective, Ph.D. thesis, U. C. Riverside, 2020.

One thing Kenny does here is explain the flaws in a well-known framework for studying open systems: decorated cospans. Decorated cospans were developed by my student Brendan Fong. Since I was Brendan’s advisor at the time, a hefty helping of blame for not noticing the problems belongs to me! But luckily, Kenny doesn’t just point out the problems: he shows how to fix them. As a result, everything we’ve done with decorated cospans can be saved.

The main theorem on decorated cospans is correct; it’s just less useful than we’d hoped! The idea is to cook up a category where the morphisms are open systems. The objects of this category could be something simple like sets, but morphisms from to could be something more interesting, like ‘open graphs’:

Here and are mapped into a third set in the middle, but this set in the middle is the set of nodes of a graph. We say the set in the middle has been ‘decorated’ with the structure of a graph.

Here’s how the original theory of decorated cospans seeks to make this precise.

Fong’s Theorem. Suppose is a category with finite colimits, and make into a symmetric monoidal category with its coproduct as the tensor product. Suppose is a symmetric lax monoidal functor. Define an F-decorated cospan to be a cospan

in together with an element of Then there is a symmetric monoidal category with

• objects of as objects,
• isomorphism classes of -decorated cospans as morphisms.

I won’t go into many details, but let me say how to compose two decorated spans, and also how this ‘isomorphism class’ business works.

Given two decorated cospans we compose their underlying cospans in the usual way, via pushout:

We get a cospan from to To decorate this we need an element of So, we take the decorations we have on the cospans being composed, which together give an element of and apply this composite map:

Here the first map, called the laxator, comes from the fact that is a lax monoidal functor, while the second comes from applying to the canonical map

Since composing cospans involves a pushout, which is defined via a universal property, the composite is only well-defined up to isomorphism. So, to get an actual category, we take isomorphism classes of decorated cospans as our morphisms.

Here an isomorphism of cospans is a commuting diagram like this:

where is an isomorphism. If the first cospan here has a decoration and the second has a decoration then we have an isomorphism of decorated cospans if

So, that’s the idea. The theorem is true, and it works fine for some applications—but not so well for others, like the example of open graphs!

Why not? Well, let’s look at this example in more detail. Given a finite set let’s define a graph on to be a finite set together with two functions We call the set of nodes, the set of edges, and the functions and map each edge to its source and target, respectively. So, a graph on is a way of choosing a graph whose set of nodes is

We can try to apply the above theorem taking

and letting

be the functor sending each finite set to the set of all graphs on

The first problem, which Brendan and I noticed right away, is that there’s not really a set of graphs on There’s a proper class! ranges over all possible finite sets, and there’s not a set of all finite sets.

This should have set alarm bells ringing right away. But we used a standard dodge. In fact there are two. One is to replace with an equivalent small category, and define a graph just as before but taking and to be objects in this equivalent category. Another is to invoke the axiom of universes. Either way, we get a set of graphs on each

Then Fong’s theorem applies, and we get a decorated cospan category with:

• ‘finite sets’ as objects,
• isomorphism classes of open graphs as morphisms.

Here I’m putting ‘finite sets’ in quotes because of the trickery I just mentioned, but it’s really not a big deal so I’ll stop now. An open graph has a finite set of nodes, a finite set of edges, maps saying the source and target of each edge, and two maps and

These last two maps are what make it an open graph going from to

Isomorphism classes of open graphs from to are the morphisms from to in our decorated cospan category.

But later, Kenny and I noticed a second problem. The concept of ‘isomorphic decorated cospan’ doesn’t behave well in this example: the concept of isomorphism is too narrowly defined!

Suppose you and I have isomorphic decorated cospans:

In the example at hand, this means you have a graph on the finite set and I have a graph on the finite set Call yours and mine

We also have a bijection such that

What does this mean? I haven’t specified the functor in detail so you’ll have to take my word for it, but it should be believable. It means that my graph is exactly like yours except that we replace the nodes of your graph, which are elements of by the elements of that they correspond to. But this means the edges of my graph must be exactly the same as the edges of yours. It’s not good enough for our graphs to have isomorphic sets of edges: they need to be equal!.

For a more precise account of this, with pictures, read the introduction to Chapter 3 of Kenny’s thesis.

So, our decorated cospan category has ‘too many morphisms’. Two open graphs will necessarily define different morphisms if they have different sets of edges.

This set Kenny and I to work on a new formalism, structured cospans, that avoids this problem. Later Kenny and Christina Vasilakopoulou also figured out a way to fix the decorated cospan formalism. Kenny’s thesis explains all this, and also how structured cospans are related to the ‘new, improved’ decorated cospans.

But then something else happened! Christina Vasilakopoulou was a postdoc at U.C. Riverside while all this was going on. She and my grad student Joe Moeller wrote a paper on something called the monoidal Grothendieck construction, which plays a key role in relating structured cospans to the new decorated cospans. But the anonymous referee of their paper pointed out another problem with the old decorated cospans!

Briefly, the problem is that the functor

that sends each to the set of graphs having as their set of vertices cannot be made lax monoidal in the desired way. To make lax monoidal, we must pick a natural transformation called the laxator:

I used this map earlier when explaining how to compose decorated cospans.

The idea seems straightforward enough: given a graph on and a graph on we get a graph on their disjoint union This is true, and there is a natural transformation that does this.

But the definition of lax monoidal functor demands that the laxator make a certain hexagon commute! And it does not!

I won’t draw this hexagon here; you can see it at the link or in the intro to Chapter 3 of Kenny’s thesis, where he explains this problem. The problem arises because when we have three sets of edges, say we typically have

There is a sneaky way to get around this problem, which he also explains: define graphs using a category equivalent to where is strictly associative, not just up to isomorphism!

This is good enough to make lax monoidal. But Kenny noticed yet another problem: is still not symmetric lax monoidal. If you try to show it is, you wind up needing two graphs to be equal: one with as its set of edges, and another with as its set of edges. These aren’t equal! And at this point it seems we hit a dead end. While there’s a category equivalent to where is strictly associative, there’s no such category where is also strictly commutative.

In the end, by going through all these contortions, we can use a watered-down version of Fong’s theorem to get a category with open graphs as morphisms, and we can make it lax monoidal—but not symmetric lax monoidal.

It’s clear that something bad is going on here. We are not following the tao of mathematics. We keep wanting things to be equal, that should only be isomorphic. The problem is that we’re treating a graph on a set as extra structure on that set, when it’s actually extra stuff.

Structured cospans, and the new decorated cospans, are the solution! For example, the new decorated cospans let us use a category of graphs with a given set of nodes, instead of a mere set. Now is a category rather than a set. This category lets us talk about isomorphic graphs with the same set of vertices, and all our problems evaporate.

---

• 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.