# Structured and decorated cospans from the viewpoint of double category theory

Applied Category Theory 2023

Evan Patterson

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:

## 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

## 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

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,

1. there is a double category ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})$ of $L$-structured cospans
2. 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:

1. Structured cospans are a cocartesian double category
(cocartesian object in $\mathbf{Dbl}$)
2. 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}$
3. 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

1. By assumption, ${}_{L}\mathbb{C}\mathsf{sp}(\mathsf{X})_0 = \mathsf{A}$ has finite coproducts.
2. 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}})$
3. 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)

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:

1. Decorations of a cospan depend on the whole cospan, not just its apex
2. 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

1. Monoidal categories are double categories with trivial categories of objects, 2-functorially: $\mathbb{B}: \mathbf{MonCat}_{\mathrm{lax}} \to \mathbf{Dbl}_{\mathrm{lax}}$
2. 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.

Other topics covered:

• structured cospans as cocartesian equipments
• cocartesian maps between cocartesian equipments of structured cospans
• application of generalized decorated cospans to theories of processes

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