Structured and decorated cospans from the viewpoint of double category theory

Applied Category Theory 2023

Evan Patterson

evan@topos.institute

Topos Institute

2023-08-04

Open systems as cospans

Mathematical modeling of open systems as cospans goes back 25+ years.

\[ a \rightarrow x \leftarrow b \]

Apex $x$ of cospan is the system itself
Feet $a,b$ of cospan are boundary or interface of system

Usually the system itself is “more structured” than its boundary:

restrict the feet relative to the apex $\leadsto$ structured cospans
extend the apex with extra data $\leadsto$ decorated cospans

Evolution of open systems as cospans (1)

Open systems should form a categorical structure, most obviously a category:

Example: Category of cospans

Given a category $\mathsf{S}$ with pushouts, there is a category $\mathsf{Csp}(\mathsf{S})$ having

as objects, the objects of $\mathsf{S}$;
as morphisms, isomorphism classes of cospans in $\mathsf{S}$.

Cospans compose by pushout in $\mathsf{S}$.

Problems:

In software, we work with representatives of isomorphism classes
What happened to the morphisms between systems?

Evolution of open systems as cospans (2)

Both problems are solved by moving to a 2-dimensional categorical structure, traditionally a bicategory:

Example: Bicategory of cospans

Given a category $\mathsf{S}$ with pushouts, there is bicategory $\mathbf{Csp}(\mathsf{S})$ having

as objects, the objects of $\mathsf{S}$;
as morphisms $a \to b$, cospans $a \rightarrow x \leftarrow b$ in $\mathsf{S}$;
as 2-morphisms $(a \rightarrow x \leftarrow b) \Rightarrow (a \rightarrow y \leftarrow b)$, maps $h \colon x \to y$ in $\mathsf{S}$ making the diagram commute:

Evolution of open systems as cospans (3)

New problem: We need a monoidal structure for “parallel composition.”

Monoidal categories are straightforward enough to work with
Monoidal bicategories are much more complicated, perhaps “irreducibly” three-dimensional:

monoidal bicategory = tricategory with one object
However, monoidal double categories can be defined using only 2-categorical concepts:

monoidal double category = pseudomonoid in $\mathbf{Dbl}$
Moreover, monoidal bicategories can sometimes be obtained from monoidal double categories (Shulman 2010)

Evolution of open systems as cospans (4)

So, for technical reasons, people started using double categories.

Example: Double category of cospans

Given a category $\mathsf{S}$ with pushouts, there is a double category $\mathbb{C}\mathsf{sp}(\mathsf{S})$ having

as objects, objects of $\mathsf{S}$;
as arrows, morphisms of $\mathsf{S}$;
as proarrows $m: a \mathrel{\mkern 3mu\vcenter{\hbox{$\scriptstyle+$}}\mkern-10mu{\to}}b$, cospans $a \rightarrow x \leftarrow b$ in $\mathsf{S}$;
as cells, maps of cospans in $\mathsf{S}$:

Is this double category really so different from the bicategory? Yes!

Double categories

Definition: A double category is a pseudocategory in $\mathbf{Cat}$.

So, a double category $\mathbb{D}$ consists of

category of objects $\mathbb{D}_0$ and category of morphisms $\mathbb{D}_1$
source and target functors $\mathop{\mathrm{src}}, \mathop{\mathrm{tgt}}: \mathbb{D}_1 \rightrightarrows \mathbb{D}_0$
external composition $\odot: \mathbb{D}_1 \times_{\mathbb{D}_0} \mathbb{D}_1 \to \mathbb{D}_1$ and identity $\mathop{\mathrm{id}}: \mathbb{D}_0 \to \mathbb{D}_1$

obeying the category laws up to coherent isomorphism.

Philosophy behind double category theory

Terminology: In a double category $\mathbb{D}$,

objects of $\mathbb{D}_0$ = objects of $\mathbb{D}$
morphisms of $\mathbb{D}_0$ = arrows of $\mathbb{D}$
objects of $\mathbb{D}_1$ = proarrows of $\mathbb{D}$
morphisms of $\mathbb{D}_1$ = cells of $\mathbb{D}$

Interpretation: First and foremost, proarrows are objects, not morphisms.

Slogan:

Proarrows are “objects that happen to have sources and targets.”

Also: open systems are systems that happen to have boundaries!

Transformations between double functors

Proarrows play the role of objects in all the main concepts. For example:

Definition: A natural transformation $\alpha: F \Rightarrow G$ between double functors $F, G: \mathbb{D} \to \mathbb{E}$ consists of

for each object $x$ in $\mathbb{D}$, an arrow $\alpha_x: Fx \to Gx$ in $\mathbb{E}$;
for each proarrow $m: x \mathrel{\mkern 3mu\vcenter{\hbox{$\scriptstyle+$}}\mkern-10mu{\to}}y$ in $\mathbb{D}$, a cell in $\mathbb{E}$ of form

that are natural with respect to arrows and cells in $\mathbb{D}$, respectively, and functorial with respect to external composition and identity.

Fact: There is a 2-category $\mathbf{Dbl}$ of double categories, double functors, and natural transformations.

Cocartesian double categories

Definition. A cocartesian double category is a cocartesian object in $\mathbf{Dbl}$, i.e., a double category $\mathbb{D}$ such that the diagonal $\Delta: \mathbb{D} \to \mathbb{D} \times \mathbb{D}$ and unique map $!: \mathbb{D} \to \mathbb{1}$ have left adjoints in $\mathbf{Dbl}$.

Proposition: Cocartesian double categories, concretely (Grandis 2019, Corollary 4.3.7)

A double category $\mathbb{D}$ is cocartesian if and only if

the categories $\mathbb{D}_0$ and $\mathbb{D}_1$ are cocartesian (have finite coproducts)
the functors $\mathop{\mathrm{src}}, \mathop{\mathrm{tgt}}: \mathbb{D}_1 \to \mathbb{D}_0$ are cocartesian (preserve finite coproducts)
the functors $\odot: \mathbb{D}_1 \times_{\mathbb{D}_0} \mathbb{D}_1 \to \mathbb{D}_1$ and $\mathop{\mathrm{id}}: \mathbb{D}_0 \to \mathbb{D}_1$ are also cocartesian, so that the canonical comparison cells are isomorphisms in $\mathbb{D}_1$:

Cocartesian double category of cospans

Example: cocartesian double category of cospans

For any category $\mathsf{X}$ with finite colimits, $\mathbb{C}\mathsf{sp}(\mathsf{X})$ is a cocartesian double category:

finite coproducts in $\mathbb{C}\mathsf{sp}(\mathsf{X})_0 = \mathsf{X}$ exist by assumption
finite coproducts in $\mathbb{C}\mathsf{sp}(\mathsf{X})_1 = \mathsf{X}^{\{\bullet \rightarrow \bullet \leftarrow \bullet\}}$ are computed pointwise in $\mathsf{X}$
source and target functors $\mathop{\mathrm{ft}}_L, \mathop{\mathrm{ft}}_R: \mathbb{C}\mathsf{sp}(\mathsf{X})_1 \rightrightarrows \mathsf{X}$ preserve coproducts
external composition and identity functors preserve coproducts because:
- colimits commute with colimits
- specifically, pushouts commute with coproducts

We expect “nice” double categories of open systems to be cocartesian
Double categories of structured cospans are cocartesian!

Structured cospans

Structured cospans are easy to use and include open systems such as:

open graphs
open Petri nets and reaction networks
open parameterized dynamical systems (Aduddell et al. 2023)

Structured cospans are implemented in Catlab.jl.

Structured cospans

Given a functor $L: \mathsf{A} \to \mathsf{X}$, an $L$-structured cospan consists of

a pair of objects $a,b \in \mathsf{A}$
a cospan in $\mathsf{X}$ of the form $La \rightarrow x \leftarrow Lb$.

Baez and Courser (2020) showed that when $\mathsf{X}$ has pushouts,

there is a double category ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})$ of $L$-structured cospans
under extra assumptions, ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})$ can be given the structure of a symmetric monoidal double category

Fact (1) is easy; (2) is more involved and has been given three different proofs.

Idea: Bypass monoidal structure using double-categorical universal property.

Monoidal structure from cocartesian property

Familiar fact: Any cocartesian category can be given the structure of symmetric monoidal category by making a choice of coproducts.

Works for double categories too! Outline of argument:

Structured cospans are a cocartesian double category
(cocartesian object in $\mathbf{Dbl}$)
Abstract nonsense: for any 2-category $\mathbf{C}$ with finite 2-products, a cartesian object in $\mathbf{C}$ can be given the structure of a symmetric pseudomonoid in $\mathbf{C}$
Hence, structured cospans are a symmetric monoidal double category
(symmetric pseudomonoid in $\mathbf{Dbl}$)

Cocartesian double cat. of structured cospans

Theorem

Let $\mathsf{A}$ be a category with finite coproducts, $\mathsf{X}$ be a category with finite colimits, and $L: \mathsf{A} \to \mathsf{X}$ be a functor that preserves finite coproducts. Then ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})$ is a cocartesian double category.

Proof sketch

By assumption, ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})_0 = \mathsf{A}$ has finite coproducts.
Also by assumption, the canonical comparison maps are isomorphisms in $\mathsf{X}$: \[ L_{a,b}: L(a)+L(b) \xrightarrow{\cong} L(a+b), \qquad L_0: 0_{\mathsf{X}} \xrightarrow{\cong} L(0_{\mathsf{A}}) \]
Coproducts in ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})_1$ are given by restricting coproducts in $\mathbb{C}\mathsf{sp}(\mathsf{X})_1$ along inverse comparisons:

Decorated cospans

Not all double categories of open systems are cocartesian.

Example: double category of open dynamical systems

Can use decorated cospans instead, which is:

A more elaborate theory
But does not assume cocartesianess

Decorated cospans

Given a category $\mathsf{A}$ with finite colimits and a lax monoidal functor $F: (\mathsf{A},+) \to (\mathbf{Cat},\times)$, an $F$-decorated cospan consists of

a cospan $a \rightarrow m \leftarrow b$ in $\mathsf{A}$
an object $x$ in $F(m)$, the decoration.

Baez, Courser, and Vasilakopoulou (2022) showed that there is a symmetric monoidal double category of $F$-decorated cospans.

Question: Recover decorated cospans using the Grothendieck construction?

Grothendieck construction decorates objects, not morphisms
Fortunately, cospans are objects according to double category theory!
So, use a double-categorical Grothendieck construction?

Double Grothendieck construction

Theorem (partial statement) (Cruttwell et al. 2022)

Given a lax double functor

\[ F: \mathbb{A} \to \mathbb{S}\mathsf{pan}(\mathbf{Cat}), \]

there is a double category $\int F$, the double Grothendieck construction of $F$, with underlying categories

\[ \textstyle (\int F)_0 = \int F_0 \qquad\text{and}\qquad (\int F)_1 = \int (\mathop{\mathrm{apex}}\circ F_1). \]

In the double category $\int F$,

objects are pairs $(a,x)$, where $a \in \mathbb{A}$ and $x \in F(a)$;
proarrows $(a,x) \mathrel{\mkern 3mu\vcenter{\hbox{$\scriptstyle+$}}\mkern-10mu{\to}}(b,y)$ are pairs $(m,s)$, where $m: a \mathrel{\mkern 3mu\vcenter{\hbox{$\scriptstyle+$}}\mkern-10mu{\to}}b$ is in $\mathbb{A}$ and $s \in \mathop{\mathrm{apex}}F(m)$ such that \[ \textstyle (\mathop{\mathrm{leg}}_L F(m))(s) = x \qquad\text{and}\qquad (\mathop{\mathrm{leg}}_R F(m))(s) = y. \]

Moreover, there is a canonical projection, a strict double functor

\[ \textstyle \pi_F: \int F \to \mathbb{A}. \]

Generalized decorated cospans

Corollary/Definition

Given a category $\mathsf{A}$ with pushouts and a lax double functor

\[ F: \mathbb{C}\mathsf{sp}(\mathsf{A}) \to \mathbb{S}\mathsf{pan}(\mathbf{Cat}), \]

there is a double category of $F$-decorated cospans given by $\int F$.

These decorated cospans are more general than the usual ones:

Decorations of a cospan depend on the whole cospan, not just its apex
Feet of cospans are also decorated, compatibly with cospan decorations

Modular reconstruction of decorated cospans

Corollary

Given a category $\mathsf{A}$ with finite colimits and a lax monoidal functor $F: (\mathsf{A},+) \to (\mathbf{Cat},\times)$, there is a double category of $F$-decorated cospans, as defined in the literature.

Proof sketch

Monoidal categories are double categories with trivial categories of objects, 2-functorially: \[ \mathbb{B}: \mathbf{MonCat}_{\mathrm{lax}} \to \mathbf{Dbl}_{\mathrm{lax}} \]
Apply the double Grothendieck construction to the composite lax double functor \[ \mathbb{C}\mathsf{sp}(\mathsf{A}) \xrightarrow{\operatorname{Apex}} \mathbb{B}(\mathsf{A}, +) \xrightarrow{\mathbb{B}(F)} \mathbb{B}(\mathbf{Cat}, \times) \xrightarrow{\operatorname{Apex}_*} \mathbb{S}\mathsf{pan}(\mathbf{Cat}) \]

Caveat

The symmetric monoidal structure on the double category is not recovered.

Conclusion

This talk is based on my paper:

Patterson, 2023. Structured and decorated cospans from the viewpoint of double category theory. arXiv:2304.00447.

References

Aduddell, Rebekah, James Fairbanks, Amit Kumar, Pablo S. Ocal, Evan Patterson, and Brandon T. Shapiro. 2023. “A Compositional Account of Motifs, Mechanisms, and Dynamics in Biochemical Regulatory Networks.” https://arxiv.org/abs/2301.01445.

Aleiferi, Evangelia. 2018. “Cartesian Double Categories with an Emphasis on Characterizing Spans.” PhD thesis, Dalhousie University. https://arxiv.org/abs/1809.06940.

Baez, John C., and Kenny Courser. 2020. “Structured Cospans.” Theory and Applications of Category Theory 35 (48): 1771–1822. http://www.tac.mta.ca/tac/volumes/35/48/35-48abs.html.

Baez, John C., Kenny Courser, and Christina Vasilakopoulou. 2022. “Structured Versus Decorated Cospans.” Compositionality 4 (3). https://doi.org/10.32408/compositionality-4-3.

Courser, Kenny. 2020. “Open Systems: A Double Categorical Perspective.” PhD thesis, University of California, Riverside. https://arxiv.org/abs/2008.02394.

Cruttwell, Geoffrey, Michael Lambert, Dorette Pronk, and Martin Szyld. 2022. “Double Fibrations.” Theory and Applications of Categories 38 (35): 1326–94. http://www.tac.mta.ca/tac/volumes/38/35/38-35abs.html.

Fiadeiro, José Luiz, and Vincent Schmitt. 2007. “Structured Co-Spans: An Algebra of Interaction Protocols.” In International Conference on Algebra and Coalgebra in Computer Science (CALCO 2007), 194–208. https://doi.org/10.1007/978-3-540-73859-6_14.

Fong, Brendan. 2015. “Decorated Cospans.” Theory and Applications of Categories 30 (33): 1096–1120. http://www.tac.mta.ca/tac/volumes/30/33/30-33abs.html.

Grandis, Marco. 2019. Higher Dimensional Categories: From Double to Multiple Categories. World Scientific. https://doi.org/10.1142/11406.

Katis, Piergiulio, Nicoletta Sabadini, and Robert F. C. Walters. 1997. “Span(Graph): A Categorical Algebra of Transition Systems.” In Algebraic Methodology and Software Technology. AMAST 1997, 307–21. Springer. https://doi.org/10.1007/BFb0000479.

Rosebrugh, Robert, Nicoletta Sabadini, and Robert F. C. Walters. 2005. “Generic Commutative Separable Algebras and Cospans of Graphs.” Theory and Applications of Categories 15 (6): 164–77. http://www.tac.mta.ca/tac/volumes/15/6/15-06abs.html.

Shulman, Michael. 2008. “Framed Bicategories and Monoidal Fibrations.” Theory and Applications of Categories 20 (18): 650–738. http://www.tac.mta.ca/tac/volumes/20/18/20-18abs.html.

———. 2010. “Constructing Symmetric Monoidal Bicategories.” https://arxiv.org/abs/1004.0993.