Applied Category Theory 2023

2023-08-04

% https://tex.stackexchange.com/a/269194

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

Some early references: (Katis, Sabadini, and Walters 1997), (Rosebrugh, Sabadini, and Walters 2005)

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?

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:

**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)

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!

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

For us, double categories and double functors are pseudo by default.

**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!

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.

**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\):

For cartesian double categories, see the PhD thesis (Aleiferi 2018).

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

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

**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}\))

**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:

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

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?

**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}. \]

The double Grothendieck construction is due to Cruttwell, Lambert, Pronk, and Szyld (2022).

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

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

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

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.