Categorical probability has recently seen significant advances through the formalism of Markov categories, within which several classical theorems have been proven in entirely abstract categorical terms. Closely related to Markov categories are gs-monoidal categories, also known as CD categories. These omit a condition that implements the normalization of probability. Extending work of Corradini and Gadducci, we construct free gs-monoidal and free Markov categories generated by a collection of morphisms of arbitrary arity and coarity. For free gs-monoidal categories, this comes in the form of an explicit combinatorial description of their morphisms as structured cospans of labeled hypergraphs. These can be thought of as a formalization of gs-monoidal string diagrams (\(=\)term graphs) as a combinatorial data structure. We formulate the appropriate 2-categorical universal property based on ideas of Walters and prove that our categories satisfy it. We expect our free categories to be relevant for computer implementations and we also argue that they can be used as statistical causal models generalizing Bayesian networks.
Notes
Communicated by S. Milius.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The categorical approach to probability theory has recently seen significant advances in the form of purely categorical proofs of a number of classical results in probability and theoretical statistics, such as the de Finetti theorem [1‐5]. This progress has been enabled by the advent of Markov categories. These provide a categorical framework for probability that seems to capture the qualitative1 intrinsic structure of probability remarkably accurately. The usual Markov category in which probability theory is considered to take place is \(\textsf{BorelStoch}\), the category with standard Borel measurable spaces as objects and Markov kernels as morphisms. But there are many other Markov categories [1, Sections 3–9], and one can instantiate the definitions and theorems of categorical probability in those as well, at least to the extent that they satisfy the relevant additional axioms.2
Closely related to Markov categories are gs-monoidal categories, which differ from Markov categories only by dropping an axiom which corresponds to the normalization of probability [6]. In the strict case, these go back to Gadducci’s thesis [7, Definition 3.9] and a corresponding paper of Corradini and Gadducci [8], where they were considered with a different motivation in the context of term graphs and term graph rewriting. Their intended application had suggested to study gs-monoidal categories freely generated by a given collection of morphisms, and indeed these had already been constructed and characterized in the single-sorted case with generators of coarity one [8] and later defined in general [9, 10]. Apparently unaware of the work of Corradini and Gadducci, free gs-monoidal categories made their first appearance in the probability context somewhat implicitly in the Master’s thesis of Fong [11], with the aim of providing a categorical framework for Bayesian networks: a Bayesian network on any directed acyclic graph G can be defined as a gs-monoidal functor from a gs-monoidal category associated to G to \(\textsf{FinStoch}\) if one has discrete variables, or to \(\textsf{BorelStoch}\) if one wants to allow continuous variables as well. Finally, another independent appearance of free gs-monoidal categories is in the recent thesis of Stein [12, Section 7.3], where a construction as syntactical categories was given.
Advertisement
In this paper, we improve on these previous works in several ways:
We explicitly construct free gs-monoidal categories generated by morphisms of arbitrary arity and coarity and with arbitrarily many sorts (Sect. 3).
Our construction defines the morphisms as certain structured cospans, which makes the connection with the recent categorical approach to network theory explicit. These cospans can be thought of as a combinatorial description of gs-monoidal string diagrams, which underlines their network-like nature.
We prove that our free gs-monoidal categories satisfy the “right” 2-categorical universal property—rather than merely a 1-categorical one—and without any strictness requirement on the target categories (Sect. 4).
We argue that morphisms in free gs-monoidal categories can themselves be considered as causal models generalizing the DAGs that underlie Bayesian networks (Sect. 7).
Moreover, in Sect. 5 we show that every free gs-monoidal category comes equipped with a canonical factorization system that we call the bloom-circuitry factorization: every gs-monoidal string diagram factors uniquely into a “pure bloom”, where all its boxes appear and every wire gets copied so as to connect to a unique output interface, followed by “pure circuitry” where wires get copied and discarded. In Sect. 6, we explain how our characterization can be adapted from free gs-monoidal categories to free Markov categories. Finally, Sect. 7 provides a sketch of how the morphisms in a free gs-monoidal category, or equivalently gs-monoidal string diagrams, can be viewed and utilized in statistics as causal models generalizing Bayesian networks. This has been explored in more detail in the follow-up paper [13].
1.1 Related Work
There has been independent and concurrent work by Milosavljevic and Zanasi [14], where free gs-monoidal categories have been constructed in the single-sorted case and a 1-categorical universal property has been considered (essentially the same as our Corollary Corollary 4.7); and by Yin [15], where a topological description of free Markov categories has been given.
Next, we discuss several points in a bit more detail.
1.2 Universal Property and Existence of Free Categories
As with free categories with extra structure in general, it is not obvious what a suitable universal property of a free gs-monoidal category or free Markov category should be. There are three meaningful choices, and we will prove that all of these properties hold. In increasing generality, these are:
A 1-categorical universal property characterizing the free gs-monoidal/Markov category as a universal object in a category of colored PROPs using strict symmetric monoidal identity-on-objects functors as morphisms (second part of Corollary 4.7). This is the type of universal property that has been considered for example in [16‐18] for free PROPs and in [19, 20] for free hypergraph categories.
Since colored PROPs with the relevant extra structure are the models of a multi-sorted algebraic theory, which is well-known to have free models, it is clear that free gs-monoidal categories and free Markov categories with this universal property exist: one simply needs to consider all possible expression formed out of the generators and quotient by the defining laws. For free gs-monoidal categories, this has been considered explicitly in [9, Definition 2.4] and [10, Definition 2]. However, finding a concrete combinatorial description is a different and more involved problem.
The same 1-category universal property, generalized to strong symmetric monoidal functors that are not necessarily identity-on-objects (first part of Corollary 4.7). This is the type of universal property considered by Corradini and Gadducci [8] for strict gs-monoidal categories, and in [21] for free colored PROPs.
A full-fledged 2-categorical universal property (Theorem 4.1). This property is somewhat more involved, but it is the one that we expect to be most relevant in practice, where identity-on-objects functors appear quite rarely. The formulation of this universal property follows an idea of Walters [22]. As far as we know, this type of universal property has not been considered much to date.
We place our emphasis on the third universal property, and merely note that the other two follow as a byproduct of essentially the same arguments.
Advertisement
In any case, it is clear that the mere existence of such free categories is not very useful: having a more explicit description of their hom-sets is a central tool for working with them in practice, and finding such a description is our main goal.
1.3 Are String Diagrams Topological or Combinatorial?
Since the morphisms in a free gs-monoidal category are gs-monoidal string diagrams, this paper also belongs to a line of work in which string diagrams are viewed as morphisms in free monoidal categories (possibly with extra structure) and characterized as suitable combinatorial objects. Among the earlier works approaching free symmetric monoidal categories in this way are results on free PROPs by Enriquez and Etingof [16, Lemma 2.1] and Vallette [17, p. 47].3 This contrasts with the more traditional topological approach, in which string diagrams are considered topological entities, as in the original work of Joyal and Street [23]. This distinction is analogous to the one in graph theory, where a graph can be considered (with somewhat different meaning) either as a continuous topological structure, for example as embedded on a surface, or as a purely combinatorial structure.
The topological formalization of string diagrams is adequate in particular in situations where higher categorical considerations or the cobordism hypothesis [24] play a role. In our present context, we believe that the combinatorial formalization is clearly preferable. This sentiment has also been expressed in the recent work on string diagram rewriting by Bonchi et al. [25]. Indeed the combinatorial approach is both more useful in practice (for example for computer formalization) and more faithful to the intuition of a string diagram as a kind of “network” than a topological picture would be. The fact that the relevant combinatorial structure is given by cospans of hypergraphs makes the combinatorial characterization match up nicely with the structured cospan approach to network theory [26].4
However, it is conceivable that interesting topological constructions of free Markov categories can be given as well. We refer to the independent and concurrent work of Yin for more on this [15].
1.4 Applications
One expected application is to computer implementations of gs-monoidal string diagrams. As with the existing work on rewriting of string diagrams in symmetric monoidal and hypergraph categories [19, 20, 27], it is of interest for computer implementations to have a data structure for representing string diagrams in gs-monoidal categories and Markov categories, and moreover to have a rewriting theory for these. While the former is given in this paper, the latter still remains to be developed.
Another expected area of application is to causal statistical models. As we argue in Sect. 7, gs-monoidal string diagrams constitute a natural generalization of Bayesian networks which already incorporates features like latent variables or input variables without the need for additional annotations. This is in line with recent work using gs-monoidal string diagrams in the context of causal inference [28, 29].5
1.5 Free Markov Categories as Examples
Besides the possible importance of free Markov categories for the theory of causal models and causal inference, free gs-monoidal and free Markov categories constitute an addition to the bestiary of examples of such categories, and as such may also be useful as a testing ground for future conjectures in categorical probability. In order to situate them in the landscape of examples, it would be useful to determine under what conditions they satisfy the additional axioms introduced in [1, Section 11].
While detailed definitions will be given in the main text, for now suffice it to say that the data that generates a free Markov category \(\textsf{FreeMarkov}_\Sigma \) is a collection of “boxes” \(\Sigma \), called a monoidal signature. These are exactly those boxes that appear in the string diagrams that form the morphisms of \(\textsf{FreeMarkov}_\Sigma \).
Question 1.1
Under what conditions on \(\Sigma \) does the free Markov category \(\textsf{FreeMarkov}_\Sigma \):
(i)
have conditionals?
(ii)
satisfy the causality axiom?
(iii)
satisfy the positivity axiom?
Also, the representability of a Markov category [3] is an important property relevant to categorical probability.
Conjecture 1.2
A free Markov category \(\textsf{FreeMarkov}_\Sigma \) is representable if and only if \(\Sigma \) contains no boxes with at least one output.
Adding or removing a box with no outputs to \(\Sigma \) leaves \(\textsf{FreeMarkov}_\Sigma \) invariant. Hence the conjecture equivalently states that the free Markov categories of that form are exactly the symmetric monoidal categories freely generated by a commutative comonoid on every generating object. These are well-known to be those of the form \((\textsf{FinSet}/ W)^\textrm{op}\) for any set W with the cartesian monoidal structure.
To approach the conjecture, one may want to prove first that the deterministic morphisms in a free Markov category are exactly the pure circuitry ones. We leave the details to future work.
1.6 Notation and Conventions
All categories in this paper will be assumed locally small. We use the term 2-category in the strict sense. \(\textsf{Cat}\) is the usual 2-category of categories, and similarly \(\textsf{MonCat}\) is the 2-category of monoidal categories, strong monoidal functors and monoidal transformations.
1.7 Acknowledgments
We thank Peter Czaban, Arthur Parzygnat, Richard Samuelson, Rob Spekkens, Elie Wolfe and Fabio Zanasi for discussions and helpful feedback on a draft. Special thanks are due to Fabio Gadducci for a long email exchange and copious help with the literature on gs-monoidal categories.
2 GS-Monoidal Categories and Markov Categories
We put our main focus here on stating the main definitions and refer to [1‐6] for applications to probability and statistics. We comment on the history in Remark 2.2.
Definition 2.1
A gs-monoidal category is a symmetric monoidal category \(({\textsf{C}}, \otimes , I)\) with a commutative comonoid structure on each object X, consisting of a comultiplication and counit,
(2.1)
which satisfy the commutative comonoid equations,
(2.2)
These comonoid structures must be multiplicative with respect to the monoidal structure:
(2.3)
A gs-monoidal category is a Markov category if the monoidal unit I is terminal.6
In this definition, “gs” stands for garbage (deletion) and sharing (copy), as per the intended interpretation of these comonoid structures. By definition, a Markov category is equivalently a gs-monoidal category which satisfies the naturality of discarding,
(2.4)
for all morphisms f. This corresponds to the normalization of probability. We refer to [1, Section 3–9] for a list of examples of Markov categories.
Remark 2.2
The notions of gs-monoidal category and Markov category already have a multifarious history. As far as we know, gs-monoidal categories made their first appearance in the 1996 thesis of Gadducci [7, Definition 3.9], with the minor difference that they were required to be strict. This was motivated by graphical notations for formal languages, and is relevant more generally for resource sharing in computer science [30]. In 1999, a similar definition was given in independent work of Golubtsov [31] as categories of information transformers, already with applications to statistics in mind.7
Subsequently, other works on string-diagrammatic approaches of probability appeared, such as by Coecke and Spekkens [32], apparently unaware of the above earlier works and using somewhat different categorical axiomatics. The first work in probability to consider something very close to gs-monoidal categories as defined above seems to have been Fong’s 2013 Master’s thesis [11], although no explicit definition of the relevant kind of category is given. GS-monoidal categories were considered in their present form as CD-categories in a 2019 paper of Cho and Jacobs [6]. Markov categories were introduced there as well under the name affine CD-categories. The term Markov category was then introduced in a 2020 paper by the first-named present author [1], based on the interpretation of the morphisms as generalized Markov kernels.
The following 2-category of gs-monoidal categories does not seem to have been considered before. However, it is an instance of the more general categorical machinery of [33, Definition 4.1], and its Markov version is [1, Definition 10.14].
Definition 2.3
Let \({\textsf{C}}\) and \({\textsf{D}}\) be gs-monoidal categories.
(a)
A strong gs-monoidal functor\(F: {\textsf{C}}\rightarrow {\textsf{D}}\) is a symmetric monoidal functor such that the diagrams
commute for all \(X \in {\textsf{C}}\), where the horizontal isomorphisms are the coherence isomorphisms of F.
(b)
A gs-monoidal transformation is a monoidal natural transformation between gs-monoidal functors.
We write \(\textsf{gsCat}\) for the 2-category of gs-monoidal categories, strong gs-monoidal functors and gs-monoidal transformations.
As with monoidal functors in general, the definition of strong gs-monoidal functor has a couple of variants: a lax gs-monoidal functor is a symmetric lax monoidal functor such that the above triangles commute with the laxators in place of the coherence isomorphisms. An oplax gs-monoidal functor is defined analogously. A strict gs-monoidal functor is a symmetric monoidal functor \(F: {\textsf{C}}\rightarrow {\textsf{D}}\) which preserves the gs-monoidal structure on the nose,
If \({\textsf{C}}\) and \({\textsf{D}}\) are Markov categories, then we also speak of strong/lax/strict Markov functors as well as Markov transformations, resulting in a 2-category of Markov categories that we denote by \(\textsf{MarkovCat}\). It is a full sub-2-category of \(\textsf{gsCat}\) by definition.
3 Construction of Free gs-Monoidal Categories
We start with some preparation by introducing the relevant combinatorial structures, following the definitions used by Bonchi et al. [19] with some minor adaptations.
Definition 3.1
We write \({\textsf{I}}\) for the category where:
Objects are pairs of natural numbers8\((k,\ell ) \in {\mathbb {N}} \times {\mathbb {N}}\), and there is one extra object denoted \(*\).
There are \(k + \ell \) non-identity morphisms from \((k,\ell )\) to \(*\), denoted
A hypergraph is a functor \(G: {\textsf{I}}\rightarrow \textsf{Set}\),9\(^,\)10
A few remarks may help clarify the definition.
We do not need to define composition in \({\textsf{I}}\) since there are no composable pairs of non-identity morphisms.
A hypergraph \(G: {\textsf{I}}\rightarrow \textsf{FinSet}\) has a set of nodes given by \(G(*)\). We will call nodes wires because of the role they play for string diagrams. Moreover, for all \(k,\ell \in {\mathbb {N}}\) there is a set \(G(k,\ell )\) of hyperedges, which we will call boxes, with k input wires and \(\ell \) output wires. The maps
for the sets of wires and boxes. We also abbreviate \(G({{\textsf{i}}}{{\textsf{n}}}_i)\) and \(G(\textsf{out}_j)\) to \({{\textsf{i}}}{{\textsf{n}}}_i\) and \(\textsf{out}_j\), respectively. For a box b and wire w, we put
$$\begin{aligned} {{\textsf{i}}}{{\textsf{n}}}(b,w)&{:}{=}|\{ i = 1, \ldots , k \, \mid \, {{\textsf{i}}}{{\textsf{n}}}_i(b) = w \}|, \\ \textsf{out}(b,w)&{:}{=}|\{ j = 1, \ldots , \ell \, \mid \, \textsf{out}_j(b) = w \}|, \end{aligned}$$
for the number of times that w appears as an input or output wire of b, respectively.
In [21], a very similar definition has been used under the term megagraph. A megagraph comes equipped with additional actions of symmetric groups corresponding to permutations of inputs and outputs.
Definition 3.2
For hypergraphs G and H, a hypergraph morphism\(G \rightarrow H\) is a natural transformation \(G \Rightarrow H\).
A morphism of hypergraphs \(p: G \Rightarrow H\) thus consists of a map \(p(*): W(G) \rightarrow W(H)\), taking wires to wires, and maps \(p(k,\ell ): G(k, \ell ) \rightarrow H(k, \ell )\), taking boxes to boxes, such that the diagrams
commute for all \(i=1,\ldots ,k\) and \(j=1,\ldots ,\ell \). These conditions state exactly that the input and output wires of each box must be preserved.
We thereby obtain a category of hypergraphs denoted \(\textsf{Hyp}\), which by definition is exactly the presheaf topos \(\textsf{Set}^{\textsf{I}}\).
Remark 3.3
Every monoidal category \({\textsf{C}}\) has an underlying hypergraph, in which the wires are the objects of \({\textsf{C}}\) and the boxes of arity \((k,\ell )\) are the morphisms from a k-fold tensor product of objects to an \(\ell \)-fold tensor product of objects.
Following an idea of Walters [22], we can refine this construction to a 2-functor
where \(\textsf{CatHyp}\) is the 2-category of categories internal to \(\textsf{Hyp}\). Indeed if \({\textsf{C}}\) is a small monoidal category, then it has an underlying \(\textsf{hyp}({\textsf{C}}) \in \textsf{CatHyp}\) defined as follows. Its category of wires is exactly \({\textsf{C}}\),
while the category of boxes \(B_{k,\ell }(\textsf{hyp}({\textsf{C}}))\) is the “hyperarrow category” of \({\textsf{C}}\), by which we mean the category with set of objects given by
consists of families of morphisms \(A_i \rightarrow A'_i\) and \(B_j \rightarrow B'_j\) making the obvious square commute, and with composition defined in the obvious way. The source and target functors \(B_{k,\ell }(\textsf{hyp}({\textsf{C}})) \rightarrow W(\textsf{hyp}({\textsf{C}}))\) are also the obvious ones.
If \(F: {\textsf{C}}\rightarrow {\textsf{D}}\) is a strong monoidal functor, then F induces an internal functor
defined as just F on the category of wires. On the category of boxes, it is defined on objects in terms of the composite
where the second arrow is given by composition with the relevant coherence isomorphisms of F. On morphisms in the category of boxes, \(\textsf{hyp}(F)\) acts as just F componentwise on morphisms. It is straightforward to see that this satisfies functoriality.
For strong monoidal functors \(F,\, G: {\textsf{C}}\rightarrow {\textsf{D}}\), a monoidal natural transformation \(\alpha : F \Rightarrow G\) induces an internal natural transformation
which indeed has the correct type, and where naturality is a straightforward consequence of the naturality of \(\alpha \).
It is straightforward to see that the above definitions assemble to a 2-functor \(\textsf{hyp}: \textsf{MonCat}\rightarrow \textsf{CatHyp}\) as promised above. Furthermore, by restriction along the forgetful 2-functor \(\textsf{gsCat}\rightarrow \textsf{MonCat}\), we obtain a 2-functor \(\textsf{hyp}: \textsf{gsCat}\rightarrow \textsf{CatHyp}\) as well, which is how we will understand \(\textsf{hyp}\) from now on.
Hypergraphs serve a dual purpose in our context: first, the data that generates a free gs-monoidal category is a hypergraph \(\Sigma \) that we call the monoidal signature.11 It may have infinitely many wires and/or boxes. See Fig. 1 for an example. Second, the morphisms in a free gs-monoidal category are themselves constructed in terms of finite hypergraphs. This is based on the idea that every string diagram is a hypergraph with wires and boxes, with given sequences of input and output wires for each box [19]. For a string diagram in a gs-monoidal category, the input and output wires of a copy morphism are considered as one and the same wire, so that the “wires” in our sense are actually the connected components of the “circuitry” built out of copies and discards. Figure 2 provides an example that we discuss in more detail below.
The formal construction that follows now elaborates on this intuitive idea: we will define a gs-monoidal string diagram as a hypergraph with additional labeling and interfacing information.
Definition 3.4
A hypergraph G is:
(i)
finite if both the set of wires W(G) and the set of boxes B(G) are finite.
(ii)
discrete if there are no boxes, \(B(G) = \emptyset \).
Fig. 1
An example of a hypergraph \(\Sigma \), drawn as a monoidal signature, with set of wires \(W(\Sigma ) = \{A,B,X\}\) and boxes \(B(\Sigma ) = \{p,f,g_1,g_2,\ldots \}\). Note that the input and output wires of a box are ordered, while the sets \(W(\Sigma )\) and \(B(\Sigma )\) themselves are not
×
Note that this finiteness condition is stronger than merely requiring G to be a functor \({\textsf{I}}\rightarrow \textsf{FinSet}\).12 The finite hypergraphs form a full subcategory of \(\textsf{Hyp}\) that we denote by \(\textsf{FinHyp}\).
String diagrams in gs-monoidal categories are “directed” in the sense that it is not possible to walk in a closed loop by traversing boxes from a source wire to a target wire. This is formalized as follows.
Definition 3.5
A cycle in a hypergraph G is a finite alternating sequence of wires and boxes \((w_1,b_1,\ldots ,w_n,b_n,w_{n+1})\) such that \(w_{n+1} = w_1\) and
for all \(i = 1, \ldots , n\). We call Gacyclic if it does not have a cycle.
Fig. 2
An example of a gs-monoidal categorical string diagram in the monoidal signature \(\Sigma \) of Fig. 1. The particular drawing in the plane is not part of the structure of the diagram, but the total orderings on input and output wires of each box as well as on input and output interfaces are
×
To construct the free gs-monoidal category generated by a monoidal signature \(\Sigma \), we consider the slice category \(\textsf{Hyp}/ \Sigma \), or rather its full subcategory \(\textsf{FinHyp}/ \Sigma \) (though \(\Sigma \) itself does not need to be finite). Its objects are hypergraph morphisms \(G \rightarrow \Sigma \) for finite G, where we think of as such a morphism as a labelling of wires of G by wires of \(\Sigma \) and of boxes of G by by boxes of \(\Sigma \) of the same arity and coarity. Morphisms are morphisms of hypergraphs that preserve the labeling.
In the following, we also write n as shorthand for the set \(\{1,\ldots ,n\}\), and use underline notation \({\underline{n}}\) for the discrete hypergraph with set of wires n.
Definition 3.6
Let \(\Sigma \) be a hypergraph. Then a gs-monoidal string diagram for the monoidal signature \(\Sigma \) is a cospan in \(\textsf{FinHyp}/ \Sigma \) of the form
for an acyclic finite hypergraph G and \(m, n \in {\mathbb {N}}\), such that left monogamy holds: for every wire \(w \in W(G)\), we have
We also keep mention of the labeling morphisms \(\sigma : G \rightarrow \Sigma \) implicit, which uniquely restrict to labeling morphisms \(\sigma : {\underline{m}}, {\underline{n}} \rightarrow \Sigma \).
The left leg of such a left monogamous cospan is a monomorphism. The idea of left monogamy is borrowed from [19], where essentially the same condition was used for both legs as part of a combinatorial formalization of string diagrams in hypergraph categories.
The main point is now that a string diagram in a gs-monoidal category—or rather an equivalence class of string diagrams modulo the gs-monoidal category axioms—is precisely a gs-monoidal string diagram in the above sense. While this idea is formalized by the universal property that we will prove in the next section, we illustrate it here intuitively with the example of Fig. 2. There are 8 connected components of wiring, which indicates that the hypergraph G has 8 wires, equipped with labels in \(W(\Sigma )\). There are 5 boxes, indicating that G has 5 boxes, equipped with labels in \(B(\Sigma )\). The incidences between the wires and the boxes depict the hypergraph structure; the fact that the labeling \(G \rightarrow \Sigma \) must be a hypergraph morphism ensures that the input and output wires of each box match the ones required by \(\Sigma \) both in number and in their sequences of labels. The acyclicity holds since all wires are consistently directed upward, although \(\Sigma \) itself (Fig. 1) need not be acyclic. The input interfaces 1 to 4 at the bottom describe the left leg of the cospan: each interface connects to a wire in G as determined by p. Similarly, q specifies how the output interfaces are connected to wires. The left monogamy condition amounts to the fact that every component of wiring is either an output of a box (and in a unique way), or connects with a unique input interface, but not both. Figure 3 displays examples of cospans which violate the acyclicity or the left monogamy condition, respectively; these can still be interpreted as string diagrams in the free hypergraph category generated by \(\Sigma \) [20], but not as string diagrams in a gs-monoidal category.
Fig. 3
Examples of cospans of hypergraphs over the \(\Sigma \) of Fig. 1 where either of the two combinatorial conditions of Definition 3.6 is violated. They can still be interpreted as string diagrams in hypergraph categories [20], which is how we draw them
×
The fact that \(\textsf{FinHyp}\) is a full subcategory of the presheaf topos \(\textsf{Hyp}\) closed under finite limits and colimits shows that pushouts in \(\textsf{FinHyp}\) exist and that they can be computed as separate pushouts in \(\textsf{Set}\) on wires and boxes of every arity \((k,\ell )\). Since the forgetful functor \(\textsf{FinHyp}/ \Sigma \rightarrow \textsf{FinHyp}\) creates (finite) colimits, the same statement applies to the slice category \(\textsf{FinHyp}/ \Sigma \).
It follows that we can form the category \(\textsf{cospan}(\textsf{FinHyp}/ \Sigma )\), where morphisms are isomorphism classes of cospans and composition is by pushout. This pushout is computed on wires and boxes of every arity separately, and the labels in \(\Sigma \) carry over automatically.
Definition 3.7
Given a hypergraph \(\Sigma \), the category of gs-monoidal string diagrams\(\textsf{FreeGS}_\Sigma \) is the subcategory of \(\textsf{cospan}(\textsf{FinHyp}/ \Sigma )\) where:
Objects are the pairs \((n, \sigma : {\underline{n}} \rightarrow \Sigma )\) with \(n \in {\mathbb {N}}\).
Morphisms are the isomorphism classes of gs-monoidal string diagrams (Definition 3.6).
Remark 3.8
In the special case of a single sort, meaning that \(|W(\Sigma )| = 1\), and when all boxes in \(\Sigma \) have exactly one output wire, an equivalent category has also been constructed in [8] as a category of term graphs.
By definition, the objects \({\underline{n}} \rightarrow \Sigma \) of \(\textsf{FreeGS}_\Sigma \) are in bijection with maps \(n \rightarrow W(\Sigma )\), or equivalently with words over \(W(\Sigma )\), as expected for the free gs-monoidal category: it has a monoid of objects given by the free monoid with generating set \(W(\Sigma )\).
Thus the composition of two gs-monoidal string diagrams is defined up to isomorphism, and is represented by the gs-monoidal string diagram obtained by pushout composition. Suppressing the (uniquely induced) labeling \(\sigma \) as usual, this pushout composition amounts to the composite cospan
(3.1)
In order for Definition 3.7 to make sense, we need to prove that this composite is indeed a gs-monoidal string diagram again. This is guaranteed by the following result, which has been obtained independently as [14, Lemma 22 and Proposition 28].13
Lemma 3.9
If both constituent cospans in (3.1) are gs-monoidal string diagrams, then so is the composite.
Independently of the proof, it is worth noting that \(B(G +_{{\underline{m}}} H)\) is the disjoint union of B(G) and B(H) since \(B({\underline{m}}) = \emptyset \). Moreover, \(W(G +_{{\underline{m}}} H)\) is the disjoint union of W(G) and W(H), with every wire in H that is in the image of r identified with its (unique) counterpart wire in G. These statements reflect obvious properties of string diagram drawings.
Proof
We show first that the composite satisfies left monogamy. To start, the morphism t is a pushout of the monomorphism r and therefore a monomorphism as well14. In particular, the composite leg tp is a monomorphism too. Given a wire \(w \in W(G +_{{\underline{m}}} H)\), we prove that the left monogamy condition holds for w by a case distinction:
\(w = t(w')\) for some \(w' \in W(G)\).
Then either \(w'\) is a target of a box in G in a unique way, or \(w'\) is in the image of p, but not both. The left monogamy at w follows in either case if we can show that w is not a target of any box in the image of u. But this is indeed the case, since otherwise \(w = u({\hat{w}})\) for some \({\hat{w}} \in W(H)\). Since this makes w a member of both the images of t and u, it must actually come from \({\underline{m}}\). But then \({\hat{w}}\) is both an output of a box in H and in the image of r, which contradicts the left monogamy of the second cospan.
w is not in the image of t.
In this case, we must have \(w = u({\hat{w}})\) for some \({\hat{w}} \in W(H)\). The preimage \({\hat{w}}\) is unique and not in the image of r, since otherwise w would also be in the image of t. Thus by left monogamy of the second cospan, \({\hat{w}}\) is a target of a box in H in a unique way, and it follows that w is a target of a box in the image of u in a unique way.
Next, we show the acyclicity of the composite cospan. We prove that the existence of a cycle as in Definition 3.5 is impossible by another case distinction.
If every \(b_i\) is in the image of t, then this also applies to every \(w_i\). This contradicts acyclicity of G, since taking preimages under G produces a cycle there based on the fact that t is a monomorphism.
If no \(b_i\) is in the image of t, then the boxes are all in the image of u. By left monogamy of the second cospan, all of the target wires of the corresponding boxes in H are not in the image of r, and therefore they are the unique preimages under u of all the target wires of the \(b_i\) in \(G +_{{\underline{m}}} H\). Hence we still obtain a cycle in H, contradicting the assumed acyclicity.
If some \(b_i\) are in the image of t and some in the image of u, then there must be i such that \(b_i \in B(H)\) and \(b_{i+1} \in B(G)\). But this not possible either, since by left monogamy of the second cospan, no target wire of \(b_i\) comes from \({\underline{m}}\), which would be the only way in which it could also be an input wire of \(b_{i+1}\).
\(\square \)
We have therefore defined the category \(\textsf{FreeGS}_\Sigma \), and we now explain how it becomes a gs-monoidal category. To define the monoidal structure, note first that every \(\underline{m + n}\) is a coproduct of \({\underline{m}}\) and \({\underline{n}}\) in \(\textsf{FinHyp}/ \Sigma \). Denoting the resulting copairing operation by angular brackets \(\langle \cdot , \cdot \rangle \), the monoidal structure on objects is given by
which under the canonical bijection between objects and words over \(W(\Sigma )\) simply corresponds to the concatenation of words.
The monoidal structure on morphisms is given by
(3.2)
again leaving it understood that the labels in \(\Sigma \) are induced in the obvious way. It is clear that the isomorphism class of the resulting cospan on the right only depends on the isomorphism classes of the factors, and its left monogamy and acyclicity follow directly from the definitions. Moreover, the bifunctoriality of this tensor product follows straightforwardly from the fact that a coproduct of two pushout squares is a pushout square as well. Since the tensor product is clearly associative, we therefore have equipped \(\textsf{FreeGS}_\Sigma \) with the structure of a strict monoidal category, where the monoidal unit is \({\underline{0}}\).
With symmetry isomorphisms given by
where the two legs are the obvious isomorphisms and the labeling is again left implicit, it is straightforward to see that \(\textsf{FreeGS}_\Sigma \) is strict symmetric monoidal.
To finally make \(\textsf{FreeGS}_\Sigma \) into a gs-monoidal category, it remains to equip every object \((n, f: {\underline{n}} \rightarrow \Sigma )\) with the structure of a comutative comonoid satisfying the relevant multiplicativity properties. Again leaving the labeling f implicit, the copy and discard maps are represented by the cospans
(3.3)
We leave it to the reader to verify that the properties required of a gs-monoidal category indeed hold.
Example 3.10
If the monoidal signature \(\Sigma \) has no boxes, then a gs-monoidal string diagram degenerates to a cospan of finite sets in which the left leg is a bijection (by left monogamy), and therefore without loss of generality an identity morphism. In this way, \(\textsf{FreeGS}_\Sigma \) degenerates to a gs-monoidal category equivalent to \((\textsf{FinSet}/ W(\Sigma ))^\textrm{op}\), which is cartesian monoidal. This matches up with the intuition that string diagrams in this case consist of pure wirings, and the pure wirings are in bijection with all the ways of mapping output interfaces to input interfaces such that the types are preserved.
Remark 3.11
For every generating box \(b \in B_{k,\ell }(\Sigma )\), there is a hypergraph \({\overline{b}}\) containing just b, by which we mean the hypergraph with
where the two legs are simply the inclusions of the inputs and outputs of b in their original order, respectively. When labeled in the obvious way, this cospan is the combinatorial representation of b drawn as a string diagram as in Fig. 1.
In this way, we obtain a canonical hypergraph morphism \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeGS}_\Sigma )\) mapping every generating wire to itself and every box b to the associated gs-monoidal string diagram \(\langle b \rangle \).
4 The Universal Property
In this section, we make precise and then prove the claim that \(\textsf{FreeGS}_\Sigma \) is the free gs-monoidal category generated by \(\Sigma \). A similar result was proven by Corradini and Gadducci [8, Theorem 23]. Ours improves on theirs in several ways:
We state and prove the “correct” 2-categorical universal property in addition to the 1-categorical one. This closely follows the ideas of Walters [22], who had developed a 2-categorical universal property for free categories with finite products and anticipated that this would apply very similarly to other categories with extra structure.
Our result applies for monoidal signatures with arbitrary (finite) arity and coarity and with arbitrarily many sorts. This possibility had already been anticipated in [8, Section 6].
We do not assume that the target gs-monoidal categories are strict. Although assuming strictness is possible without loss of generality by strictification, it should be noted that the standard strictification theorem for symmetric monoidal categories is not sufficient, since it does not account for the gs-monoidal structure. Fortunately, a more general strictification theorem for monoidal categories with extra structure is available and applicable [33, Corollary 4.10]. This indeed implies that every gs-monoidal category is equivalent to a strict one, in the sense of equivalence in the 2-category \(\textsf{gsCat}\).
There is a subtle gap in the proof [8]. In our notation, the unproven statement is the assertion that if \(|W(\Sigma )| = 1\), then the canonical functor \(\textsf{FinSet}\rightarrow \textsf{FreeGS}_\Sigma \), which throws in the generating boxes in addition to the generating wire, is faithful [8, top of p. 315]. This is not obvious: there are examples of multi-sorted algebraic theories for which freely adding extra generators to a free model collapses the model [34].
To begin, recall that in Remark 3.3 we associated to every gs-monoidal category \({\textsf{C}}\) a category \(\textsf{hyp}({\textsf{C}})\) internal to \(\textsf{Hyp}\), and this construction is a 2-functor \(\textsf{hyp}: \textsf{gsCat}\rightarrow \textsf{CatHyp}\). We now also consider a monoidal signature \(\Sigma \) as a category internal to \(\textsf{Hyp}\), namely with the hypergraph of morphisms being the empty one. Like this, the canonical hypergraph morphism \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeGS}_\Sigma )\) from Remark 3.11 is an internal functor with the trivial action on morphisms.
We can now state and prove the universal property.
Theorem 4.1
Let \(\Sigma \) be a monoidal signature. Then composing with the canonical hypergraph morphism \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeGS}_\Sigma )\) induces an equivalence
Most of the remainder of this section is dedicated to the proof.
Example 4.2
Continuing on from Example 3.10, suppose that \(\Sigma \) is the trivial hypergraph consisting of a single wire and no box. Then \(\textsf{FreeGS}_\Sigma \) is equivalent to \(\textsf{FinSet}^\textrm{op}\), and Theorem 4.1 specializes to the well-known fact that \(\textsf{FinSet}\) is equivalent to the PROP for commutative monoids, a well-known result [35].
Remark 4.3
The following proof of Theorem 4.1 is somewhat long-winded, involving a number of induction arguments and case distinctions. This is not surprising, since already the degenerate case mentioned in the previous example is nontrivial.
We had considered an alternative proof involving a reduction to the characterization of free hypergraph categories in [20]. While such an approach indeed seems to be feasible, amounting to an embedding of the free gs-monoidal category \(\textsf{FreeGS}_\Sigma \) generated by a monoidal signature \(\Sigma \) into the free hypergraph category generated by \(\Sigma \), we have ultimately decided against this method.15
We now start the proof, showing that the functor from left to right given by the restriction is fully faithful and essentially surjective.
For full faithfulness, suppose that we are given two strong gs-monoidal functors
$$\begin{aligned} F, G \,: \, \textsf{FreeGS}_\Sigma \longrightarrow {\textsf{C}}, \end{aligned}$$
and consider their adjuncts \(F^\flat , G^\flat : \Sigma \rightarrow \textsf{hyp}({\textsf{C}})\), which are the composites
Then we need to show that the gs-monoidal transformations \(\alpha : F \Rightarrow G\) restrict bijectively to the internal natural transformations \(\alpha ^\flat : F^\flat \Rightarrow G^\flat \). The monoidality property of \(\alpha \) implies that it is uniquely determined by its values on generating objects, which shows of the map \(\alpha \mapsto \alpha ^\flat \). Surjectivity holds for the same reason, together with the fact that the relevant naturality conditions are encoded in \(\textsf{CatHyp}\) at the level of boxes.
We address essential surjectivity over the course of the next few subsections. We assume that \({\textsf{C}}\) is a strict gs-monoidal category, which is without loss of generality by strictification [33, Corollary 4.10]. It is now enough to extend a given hypergraph morphism \(f: \Sigma \rightarrow \textsf{hyp}({\textsf{C}})\) to a strict gs-monoidal functor \(F: \textsf{FreeGS}_\Sigma \rightarrow {\textsf{C}}\). Since on objects we must necessarily have
As will become clear in the course of the proof, the idea is that this counts the number of boxes plus the minimal number of occurrences of a copy or discard morphism.
4.1 Piece Decompositions
In order to arrive at a gs-monoidal string diagram of lower complexity, we need to factor \(\alpha \) into morphisms of smaller complexity. We will do so by stripping off a “piece”, similarly as in [8, p. 307/8]. Also the independent work [14, Section 2.3] develops another method for decomposing \(\alpha \) into simpler parts.
Definition 4.4
A final wire is \(w \in W(G)\) that is not an input to any box,
$$\begin{aligned} {{\textsf{i}}}{{\textsf{n}}}(b,w) = 0 \qquad \forall b \in B(G). \end{aligned}$$
The following more particular notions will be used to decompose any gs-monoidal string diagram into pieces by induction on the complexity.
A final copy is a final wire w together with distinct \(i,j \in n\) such that
$$\begin{aligned} q(i) = q(j) = w. \end{aligned}$$
(c)
A final box is a box \(b \in B(G)\) such that each of its output wires \(w \in \textsf{out}(b)\) is final and satisfies \(|q^{-1}(w)| = 1\).
Intuitively, a final box is one whose outputs connect to output interfaces without further processing. In particular, every box without any inputs or outputs is a final box.
Lemma 4.6
Every non-permutation gs-monoidal string diagram has a piece.
Proof
Assume that neither of the three kinds of pieces exists in a gs-monoidal string diagram (4.1). Then every final wire w satisfies \(|q^{-1}(w)| = 1\), and by left monogamy is either an output of a box or a parallel wire. In particular, since by assumption there is at least one non-parallel wire, there must at least be one box. And since there is no final box, it follows that every box has an output wire that is not final. For every box b, we can therefore choose a “successor” box \(b'\) defined as any box that has a non-final output wire of b as an input. If we now start at an arbitrary box and consider its sequence of successors, by finiteness of G we end up with a cycle that contradicts the acyclicity of G. \(\square \)
The permutations (symmetry isomorphisms) in \(\textsf{FreeGS}_\Sigma \) are exactly those morphisms represented by cospans with no boxes and for which both legs are bijections on nodes. Equivalently, they are the morphisms of complexity zero. On these, the value of F is clear: since F is required to be a symmetric monoidal functor, this value must be the corresponding permutation in \({\textsf{C}}\).
Assume now that F has already been defined on all gs-monoidal string diagrams of lower complexity. We then define it on the gs-monoidal string diagram under consideration \(\alpha \) by stripping off a piece, applying F to the remaining gs-monoidal string diagram of lower complexity \(\alpha '\), and extending F to \(\alpha \) in the unique way. Delegating the question of well-definedness to further down, we do this by distinguishing the type of piece.
(a)
If there is a final discard w in \(\alpha \), then up to permutation of output interfaces, \(\alpha \) can be decomposed into the composite cospan of
(4.2)
Here, the unlabeled arrow is the trivial inclusion, and \(q'\) is given by q extended by \(n + 1 \longmapsto w\). This amounts to the creation of a new output interface for the wire w that was discarded in \(\alpha \). Then the composite gs-monoidal string diagram coincides with \(\alpha \) by construction. With \(\alpha '\) referring to the first cospan above (with the same labeling \(\sigma \)), we have \(C(\alpha ') = C(\alpha ) - 1\), since the summand associated to w is 0 in \(\alpha '\) and 1 in \(\alpha \).
This is the only possibility (subject to our requirements) since the second gs-monoidal string diagram above is equal to \(\textrm{id}_{{\underline{n}}} \otimes \textsf{del}_{\sigma (w)}\) in \(\textsf{FreeGS}_\Sigma \).
(b)
The case of a final copy w in \(\alpha \) is similar. By permuting output interfaces we can assume that \(q(n-1) = q(n) = w\). Then the gs-monoidal string diagram \(\alpha \) decomposes as the composite
(4.3)
Here, the unlabeled arrow maps \(n \longmapsto n-1\) and acts as the identity otherwise, and \(q'\) is the restriction of q to \(\underline{n-1}\). That the composite recovers \(\alpha \) and that the complexity of \(\alpha '\) has decreased can be seen as in the previous case.
and this is the only possibility since the second gs-monoidal string diagram above decomposes as \(\textrm{id}_{\underline{n-2}} \otimes \textsf{copy}_{\sigma (w)}\) in \(\textsf{FreeGS}_\Sigma \).
(c)
If \(\alpha \) has a final box b of arity \((k,\ell )\), then by output permutations we can assume that the outputs of b are exactly the wires connected to the output interfaces \(n-\ell +1,\ldots ,n\) in the same order. The gs-monoidal string diagram \(\alpha \) now decomposes as
(4.4)
Here, the second cospan is such that it represents the gs-monoidal string diagram \(\textrm{id}_{\underline{n-\ell }} \otimes \langle \sigma (b) \rangle \), and \(G'\) consists of G with the box b and the output wires of b removed. The right leg \(q'\) can be defined as q on \(\underline{n-\ell }\), and as mapping to the sequence of input wires17 of b on the remaining output interfaces. The gs-monoidal string diagram \(\alpha '\) represented by the left cospan has complexity \(C(\alpha ') = C(\alpha ) - 1 - \ell < C(\alpha )\).
and this is the only possibility due to the requirement that \(F(\langle \sigma (b) \rangle ) = f(\sigma (b))\).
Stripping off pieces repeatedly will completely decompose \(\alpha \) into pieces eventually, since the complexity decreases in every step. Thus if one starts out by successively removing final discards, copies and boxes, then this will ultimately result in a permutation, on which F is trivially defined.
4.2 Well-definedness
Showing that F is well-defined requires two steps. First, we need to check that the above definitions of \(F(\alpha )\) are independent of the particular permutations of inputs and outputs that have been used to arrive at the specified forms (4.2)–(4.4) in each step. This follows upon proving in the same induction that F satisfies functoriality whenever one of the morphisms involved is a permutation. This straightforwardly reduces in each case to precomposing the legs \(p'\) and \(q'\) by permutation on interfaces.18 We leave the detailed arguments to the reader.
Second, it must be shown that the above definitions are independent of the choice of piece. We thus assume that we are given two different pieces of \(\alpha \), and argue that applying the above prescriptions results in the same morphism \(F(\alpha )\).
After permutations of output interfaces, each case amounts to a factorization \(\alpha = (\textrm{id}\otimes \gamma ) \circ \alpha '\), where \(\gamma \) corresponds to either a single discard, copy or box. Then the well-definedness proof reduces to the following two exclusive cases, also using induction on the complexity.
The output interfaces appearing in the two pieces are disjoint.
Then both pieces can be stripped off at once. After another permutation of output interfaces, this results in a factorization
holds by the assumed well-definedness at lower complexity, the interchange law in \({\textsf{C}}\) proves that the two definitions of \(F(\alpha )\) are equal as morphisms of \({\textsf{C}}\).
Both pieces are final copies with overlapping output interfaces.
Then we can assume without loss of generality that these output interfaces are exactly \(n-2\) to n. It is straightforward to see that the well-definedness now holds because of the coassociativity of \(\textsf{copy}_{f(\sigma (w))}\) in \({\textsf{C}}\).
for any pair of composable gs-monoidal string diagrams \(\alpha : {\underline{\ell }} \rightarrow {\underline{m}}\) and \(\beta : {\underline{m}} \rightarrow {\underline{n}}\). If \(\beta \) is a permutation, then the claim was already established above, so suppose it is not. Then by Lemma 4.6 and the construction of F, there is a decomposition
and where \(\beta '\) is of lower complexity than \(\beta \). This way, we can prove the functoriality by induction on the complexity of \(\beta \): since \(F(\beta ' \circ \alpha ) = F(\beta ') \circ F(\alpha )\) by the induction assumption, we obtain
for arbitrary gs-monoidal string diagrams \(\alpha \) and \(\beta \). By the interchange law in both the domain and codomain categories as well as by functoriality, it is enough to consider the case where \(\alpha \) or \(\beta \) is an identity morphism, so suppose \(\beta = \textrm{id}\). In this case, the claim follows by another straightforward induction argument on the complexity of \(\alpha \), doing the induction step separately for each type of piece.
4.5 Preservation of gs-Monoidal Structure
It remains to prove that F preserves the gs-monoidal structure. This holds on a copy morphism of type \(\textsf{copy}_{{\underline{1}}}\) by construction in the final copy piece case. The general case then follows by the multiplicativity of \(\textsf{copy}\) across tensor products of objects. The analogous argument for discard then establishes the claim.
In conclusion, \(F: \textsf{FreeGS}_\Sigma \rightarrow {\textsf{C}}\) is a strict gs-monoidal functor extending the given hypergraph morphism \(f: \Sigma \rightarrow \textsf{hyp}({\textsf{C}})\). This finishes the proof of Theorem 4.1.
4.6 1-Categorical Universal Property
We also obtain two versions of a 1-categorical universal property analogous to the ones considered in [8]. While the 2-categorical universal property given in Theorem 4.1 is arguably the most relevant and useful one in practice, the following 1-categorical one has the advantage of being easier to understand. It also characterizes \(\textsf{FreeGS}_\Sigma \) up to isomorphism (rather than merely up to equivalence). In the following statement, we consider \(\textsf{hyp}({\textsf{C}})\) as a mere hypergraph again.
Corollary 4.7
Let \({\textsf{C}}\) be a strict gs-monoidal category whose monoid of objects is the free monoid with generating set \(W(\Sigma )\). Then restricting along the hypergraph morphism \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeGS}_\Sigma )\) induces a bijection between:
The strict gs-monoidal functors \(\textsf{FreeGS}_\Sigma \rightarrow {\textsf{C}}\),
The hypergraph morphisms \(\Sigma \rightarrow \textsf{hyp}({\textsf{C}})\).
This bijection restricts to a bijection between:
The identity-on-objects strict gs-monoidal functors \(\textsf{FreeGS}_\Sigma \rightarrow {\textsf{C}}\).
The identity-on-wires hypergraph morphisms \(\Sigma \rightarrow \textsf{hyp}({\textsf{C}})\).
The second claim is an immediate special case of the first. These statements do not follow directly from Theorem 4.1, because the latter characterizes \(\textsf{FreeGS}_\Sigma \) only up to equivalence. However, it follows by the same proof, since the gs-monoidal functor F constructed as the extension of the hypergraph morphism f is strict, and our construction also demonstrates its uniqueness since the given definition of \(F(\alpha )\) is the only possibility.
5 The Bloom-Circuitry Factorization
For any monoidal signature \(\Sigma \), we show that the free gs-monoidal category \(\textsf{FreeGS}_\Sigma \) has a canonical factorization system.
Definition 5.1
A morphism in \(\textsf{FreeGS}_\Sigma \) represented by a gs-monoidal string diagram
(5.1)
is:
(a)
pure bloom if the right leg q is a bijection (on wires).
(b)
pure circuitry if G has no boxes.
For example, the string diagram depicted in Fig. 4 is a pure bloom. The point is that every wire becomes an overall output in exactly one way.19 A pure circuity morphism in turn is a gs-monoidal string diagram that contains at most copies and discard operations.
The “bloom” terminology is inspired by and generalizes the one of [36], where blooms of a particularly simple form were considered. Our notion is similar to a condition used at [8, Lemma 4.7], which in our terminology amounts to surjectivity of q.
Fig. 4
A gs-monoidal string diagram that is a pure bloom since every wire becomes an output in exactly one way. The gs-monoidal string diagram of Fig. 2 factors into this pure bloom followed by pure circuitry
×
Lemma 5.2
The pure blooms form a symmetric monoidal subcategory of \(\textsf{FreeGS}_\Sigma \).
Proof
In a sequential composition (3.1), if q is a bijection on wires then so is u (since pushouts in \(\textsf{FinHyp}/ \Sigma \) are computed as pushouts in \(\textsf{Set}\) on the sets of wires). Since s is a bijection on wires by assumption as well, it follows that us is too, and hence the composite cospan is a pure bloom.
The preservation of pure blooms by parallel composition (3.2) is obvious, as is the fact that the symmetry isomorphisms are pure blooms. \(\square \)
We denote this symmetric monoidal subcategory by \(\textsf{Bloom}_\Sigma \). Of course, the gs-monoidal structure morphisms (3.3) are not pure blooms, so that \(\textsf{Bloom}_\Sigma \) is not a gs-monoidal category. On the other hand, the pure circuitry morphisms form a gs-monoidal subcategory which coincides with \(\textsf{FreeGS}_{\underline{W(\Sigma )}}\), which is equivalent to \((\textsf{FinSet}/ W(\Sigma ))^\textrm{op}\) (Example 3.10).
Lemma 5.3
The following are equivalent for a morphism \(\alpha \) in \(\textsf{FreeGS}_\Sigma \):
(i)
\(\alpha \) is pure bloom and pure circuitry.
(ii)
\(C(\alpha ) = 0\).
(iii)
\(\alpha \) is a permutation.
(iv)
\(\alpha \) is an isomorphism.
Proof
By left monogamy, a pure circuitry morphism is necessarily such that its left leg is an isomorphism. Assuming (i), we therefore obtain that both legs are isomorphisms. Together with \(\alpha \) having no boxes, we obtain (ii). The equivalence of (ii) and (iii) was already discussed in the previous section. The implication (iii)\(\Rightarrow \)(iv) is trivial. Assuming (iv), it is clear that \(\alpha \) must be pure circuitry. Since then the left leg is an isomorphism by left monogamy, the isomorphism assumption implies that so is the right leg, making \(\alpha \) pure bloom as well. \(\square \)
Proposition 5.4
The pure blooms and the pure circuitry morphisms form an orthogonal factorization system for \(\textsf{FreeGS}_\Sigma \):
(a)
Every morphism factors into a pure bloom followed by pure circuitry.
(b)
This factorization is unique up to a unique permutation of wires.
Proof
Given any gs-monoidal string diagram (5.1), we factor it in \(\textsf{cospan}(\textsf{FinHyp}/ \Sigma )\) as
The two constituent cospans become gs-monoidal string diagrams upon choosing any total ordering on W(G), or equivalently any hypergraph isomorphism \(\underline{W(G)} \cong \underline{|W(G)|}\), and considering \(\underline{|W(G)|}\) an object of \(\textsf{FinHyp}/ \Sigma \) by equipping it with the labeling inducing by this isomorphism. The left cospan is then a pure bloom and the right one pure circuitry by construction.
Concerning uniqueness, any factorization into pure bloom and pure circuitry results in two cospans such that the two middle legs are bijections on wires. This implies that the ambiguity in the factorization is exactly the choice of isomorphism \(\underline{W(G)} \cong \underline{|W(G)|}\). Choosing a different one amounts precisely to conjugation by a permutation isomorphism identifying the two intermediate objects. The uniqueness of the permutation is obvious, since in particular it must commute with the right leg of the pure bloom cospan.
We therefore indeed have an orthogonal factorization system by [37, Proposition 14.7], since the isomorphisms in \(\textsf{FreeGS}_\Sigma \) are exactly the permutations. \(\square \)
In particular, Proposition 5.4 implies that the two subcategories define a distributive law of colored PROPs [38, Theorem 4.6].
6 Free Markov Categories
Given a monoidal signature \(\Sigma \), we now investigate the free Markov category \(\textsf{FreeMarkov}_\Sigma \), satisfying an analogous 2-categorical universal property as \(\textsf{FreeGS}_\Sigma \).
Example 6.1
\(\textsf{FreeGS}_\Sigma \) is a Markov category if and only if the monoidal signature \(\Sigma \) has no boxes, \(B(\Sigma ) = \emptyset \).
Indeed the “if” direction is obvious since we then are in the degenerate case of Example 3.10, where the monoidal structure is cartesian, and in particular the monoidal unit is terminal. For the “only if” direction, suppose that \(\Sigma \) contains a box \(b \in B(\Sigma )\). Then consider \(\langle b\rangle \), the gs-monoidal string diagram consisting of b alone. Then discarding all outputs of b (if any) produces a gs-monoidal string diagram which still has one box, contradicting the naturality of discarding.
In order to construct \(\textsf{FreeMarkov}_\Sigma \), we can simply start with \(\textsf{FreeGS}_\Sigma \) and quotient by the naturality of discarding. However, in practice it will be more convenient to choose one representative of each equivalence class. We thus introduce the following normal form.
Definition 6.2
Let a gs-monoidal string diagram
be given.
(i)
A box \(b \in B(G)\) is eliminable if each one of its output gets discarded: for every \(w \in W(G)\),
\(\alpha \) is normalized if it has no eliminable boxes.
Every gs-monoidal string diagram can be turned into a normalized one by repeatedly removing eliminable boxes and their output wires (if any), while all other boxes and wires remain unchanged. Removing a box like this decreases the number of boxes, and therefore repeatedly eliminating boxes eventually terminates. If two distinct boxes \(b_1, b_2 \in B(G)\) are both eliminable, then they can be removed in either order, which implies confluence. Therefore the process is guaranteed to terminate in a unique normalized form. We call it the normalization. For a simple example, the normalization of a single effect (in the monoidal signature of Fig. 1) is given by
Definition 6.3
Given a hypergraph \(\Sigma \), \(\textsf{FreeMarkov}_\Sigma \) is the category with:
Objects are the pairs \((n, \sigma : {\underline{n}} \rightarrow \Sigma )\) with \(n \in {\mathbb {N}}\).
Morphisms are the isomorphism classes of normalized gs-monoidal string diagrams (Definition 3.6).
Composition is defined as in \(\textsf{FreeGS}_\Sigma \) and subsequent normalization.
By Example 6.1, a composite of normalized gs-monoidal string diagrams need not be normalized, and a separate normalization step is required in general. However, if \(\alpha \) and \(\beta \) are normalized gs-monoidal string diagrams, then also \(\alpha \otimes \beta \) is already normalized: if \(\alpha \otimes \beta \) contains an eliminable box, then this same box is also eliminable in \(\alpha \) or \(\beta \). Thus the monoidal structure of \(\textsf{FreeGS}_\Sigma \) directly restricts to \(\textsf{FreeMarkov}_\Sigma \), and the same applies to the gs-monoidal structure. Hence \(\textsf{FreeMarkov}_\Sigma \) is clearly a gs-monoidal category.
Lemma 6.4
\(\textsf{FreeMarkov}_\Sigma \) is a Markov category.
Proof
It is enough to show that the monoidal unit \({\underline{0}}\) is terminal. If \(\alpha : {\underline{n}} \rightarrow {\underline{0}}\) is any normalized string diagram, then it cannot have any boxes, since every such box would be eliminable. Thus \(\alpha \) is pure circuitry, and therefore equal to the gs-monoidal string diagram which simply discards all inputs. \(\square \)
Lemma 6.5
Mapping every gs-monoidal string diagram to its normalization is an identity-on-objects strict gs-monoidal functor
whenever these make sense. By the normal form property of normalization, for functoriality it is enough to show that \(\alpha \circ \beta \) reduces to \(\textsf{norm}(\alpha ) \circ \textsf{norm}(\beta )\), which follows by induction on the number of boxes, noting that any eliminable box in \(\alpha \) or \(\beta \) is still eliminable in \(\alpha \circ \beta \), and noting that removing an eliminable box and its output wires does not interfere with the pushout composition. The monoidality follows similarly by showing that \(\alpha \otimes \beta \) reduces to \(\textsf{norm}(\alpha ) \otimes \textsf{norm}(\beta )\). \(\square \)
Under the correspondence of Corollary 4.7, the functor \(\textsf{norm}\) corresponds to the hypergraph morphism \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeMarkov}_\Sigma )\) given by the composite
This identity-on-wires morphism sends every box b to \(\textsf{norm}{\langle b\rangle }\), which is \(\langle b \rangle \) itself unless b has no outputs, in which case it gets mapped to the gs-monoidal string diagram that discards all its inputs.
Here is the Markov category version of Theorem 4.1.
Theorem 6.6
Let \(\Sigma \) be a monoidal signature. Then composing with the canonical hypergraph morphism \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeMarkov}_\Sigma )\) induces an equivalence
By Theorem 4.1, it is enough to show that composing with \(\textsf{norm}\) induces an equivalence
for every Markov category \({\textsf{C}}\). Faithfulness is obvious since \(\textsf{norm}\) is identity-on-objects. Fullness holds by the same reason together with fullness of \(\textsf{norm}\), which enters in the verification of naturality. For essential surjectivity, it is enough to argue that every strong gs-monoidal functor \(F: \textsf{FreeGS}_\Sigma \rightarrow {\textsf{C}}\) factors through \(\textsf{norm}\), or equivalently that \(F(\alpha ) = F(\beta )\) whenever \(\textsf{norm}(\alpha ) = \textsf{norm}(\beta )\). We can assume without loss of generality that \(\alpha \) and \(\beta \) differ by a single reduction step, consisting of the elimination of an eliminable box b in \(\alpha \). We can then write \(\alpha \) as a composite gs-monoidal string diagram
The naturality of discarding in \({\textsf{C}}\) then implies \(F(\alpha ) = F(\beta )\). \(\square \)
Proceeding by essentially the same arguments, we also obtain the following.
Corollary 6.7
Let \({\textsf{C}}\) be a strict Markov category whose monoid of objects is the free monoid with generating set \(W(\Sigma )\). Then restricting along \(\Sigma \rightarrow \textsf{hyp}(\textsf{FreeMarkov}_\Sigma )\) induces a bijection between:
The strict gs-monoidal functors \(\textsf{FreeMarkov}_\Sigma \rightarrow {\textsf{C}}\).
The hypergraph morphisms \(\Sigma \rightarrow \textsf{hyp}({\textsf{C}})\).
This bijection restricts to a bijection between:
The identity-on-objects strict gs-monoidal functors \(\textsf{FreeMarkov}_\Sigma \rightarrow {\textsf{C}}\).
The identity-on-wires hypergraph morphisms \(\Sigma \rightarrow \textsf{hyp}({\textsf{C}})\).
7 GS-Monoidal String Diagrams as Generalized Causal Models
Here, we briefly discuss how free Markov categories provide a notion of causal model which is both more general and more intuitive than the traditional one. We refer to [13] for more details and examples as well as a proof of the d-separation criterion for Bayesian networks in categorical terms.20 Besides the greater generality of the categorical formalism, another important advantage is that this criterion can be formulated as a statement about topological connectedness of string diagrams, which makes it more intuitive than the traditional one.
Traditionally, causal models are defined as directed acyclic graphs. A Bayesian network is an assignment of random variables to the vertices in such a way that their dependencies suitably match the causal structure defined by the graph [40]. In the following, no prior knowledge of Bayesian networks will be needed. Instead, let us focus on our proposed definition.
Definition 7.1
A generalized causal model is a normalized gs-monoidal string diagram
in a monoidal signature \(\Sigma \), or equivalently a morphism in \(\textsf{FreeMarkov}_\Sigma \), such that the right leg q is injective.
The injectivity condition for q amounts to the requirement that every wire can become an overall output in at most one way. This guarantees that every output can be interpreted as its own random variable; while if q is not injective, then several outputs represent copies of the same random variable, which is an uninteresting case.
Fig. 5
A normalized gs-monoidal string diagram in the monoidal signature \(\Sigma \) of Fig. 1
×
For example, consider the normalized gs-monoidal string diagram depicted in Fig. 5, and denote it by \(\alpha \). It depicts a generalized causal model for a Markov kernel with four inputs and three outputs, where the three outputs are of the same type as the first and third input. In other words, it is a statistical model for Markov kernels of the form
$$\begin{aligned} M \,: \, A' \otimes X' \otimes A' \otimes B' \longrightarrow A' \otimes A' \otimes A', \end{aligned}$$
where \(A'\), \(B'\) and \(X'\) are fixed measurable spaces (or just finite sets). We say that such M is compatible with the model \(\alpha \) if there exists a Markov functor \(F: \textsf{FreeMarkov}_\Sigma \rightarrow \textsf{Stoch}\) such that
This last equation is the main compatibility condition, saying that M needs to be implementable using a causal structure of the given shape \(\alpha \). It formalizes the intuitive idea of the gs-monoidal string diagram \(\alpha \) depicting the actual causal mechanisms: compatibility means that one can find a particular distribution p and a Markov kernel f such that plugging these pieces together, using \(\alpha \) as a blueprint, results in M.
Remark 7.2
Of course, there is nothing specific to Markov kernels in the category \(\textsf{Stoch}\) here: the same definitions can be used as the definition of compatibility between a morphism in any Markov category and the specification of a causal structure by a gs-monoidal string diagram.
Defined like this, generalized causal models have the following advantage over causal models as usually defined in terms of directed acyclic graphs:
Latent variables are built in from the start. For example in Fig. 5, the left output of p does not connect to an output interface and is therefore not part of the Markov kernel that is being modeled. In the traditional setting of Bayesian networks, this would be considered a latent variable. The analogous statement applies to the output of the first instance of f.
The gs-monoidal string diagrams that do not have any latent variables in this sense—and do not have any unnecessary duplications either—are exactly the pure blooms (Definition 5.1).
It is possible and natural to encode the requirement for the same causal mechanism to appear multiple times, as in the Markov kernel f appearing twice in Fig. 5. For example, this is relevant for the inflation technique in causal inference [29, 41]. It seems like a natural condition in general, since real-world systems often contain one and the same mechanisms several times.
Generalized causal models are models for Markov kernels rather than probability distributions. In other words, they naturally allow for the consideration of “control” quantities which do not have any particular distribution, but rather serve as overall input variables. This is a situation often considered for example in physics in the context of Bell’s theorem, where the “settings” of the two “parties” do not have a fixed distribution [42]. It is sometimes implemented in the conventional formalism by an additional annotation that writes observed variables in circles and control variables in squares [43].
GS-monoidal string diagrams provide an arguably more intuitive representation of the information flow than a directed acyclic graph does. One simply needs to represent each quantity as a wire, and work out the mechanisms by which particular variables get transformed into other ones and draw these as boxes. This is related to the fact that interventions have a simple and intuitive description in terms of string diagram surgery [28].
More specifically, conditional independences are very easy to read off from the gs-monoidal string diagram. It amounts to first marginalizing over all outputs that one is not interested in (and applying a normalization), and then the conditional independence holds if and only if the diagram disconnects upon further removing all the wires that one conditions on [1, Remark 12.21].22 This is in stark contrast with the high complexity of the d-separation criterion for Bayesian networks.
Variables taking values in arbitrary measurable spaces, and continuous variables in particular, can be dealt with in the exact same way as discrete variables. The difference merely lies in the choice of a different target category, namely \(\textsf{Stoch}\) or \(\textsf{BorelStoch}\) as opposed to \(\textsf{FinStoch}\).
Of course, the first four features are merely about notation, since it is easy to introduce additional annotations on Bayesian networks. But this does not make them insignificant. The last feature really is a feature of the Markov categories approach to probability in general, and is thus not specific to causal models.
In summary, our claims are that defining a generalized causal model as a morphism in a free Markov categories is feasible, and that this has a number of attractive features that the traditional notion of causal model does not have. We leave more detailed investigations of generalized causal models in this sense to future work. One may expect Patterson’s work on statistical models in terms of Markov categories on the connections to categorical logic [44] to be helpful in this regard.
Acknowledgements
We thank Andreas Klingler for discussions and fruitful collaboration on [13]. The first author acknowledges funding by the Austrian Science Fund (FWF) through project P 35992-N. The authors have no relevant financial or non-financial interests to disclose.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A minor technical difference is that our additional restrictions on the leg of a cospan, in the form of a monogamy condition adopted from [19, 20], have not been considered in the literature on categorical network theory so far. Thus our construction is not technically an instance of the structured cospan framework in its present form.
Note that the definition used in [19] and [20] requires the functor to land in \(\textsf{FinSet}\). We prefer to allow infinite hypergraphs, since otherwise we could only consider free gs-monoidal categories generated by finitely many morphisms, which would be unnecessarily restrictive.
This has apparently has been missed in [19], where the functor \({\textsf{I}}\rightarrow \textsf{FinSet}\) definition is stated but Definition 3.4 is used.
The main reason is that Zanasi’s proof has two gaps: first, no argument for the functoriality of Zanasi’s purported functor \(\gamma \) [20, Theorem 3.2] is given; second, in contrast to what is stated, the result on amalgamations of categories referenced in the proof of [20, Corollary 3.4] does not transfer to amalgamations of symmetric monoidal categories in any obvious way due to the interchange law imposing additional equations between morphisms.
This nicely matches up with the traditional random variable setting of probability theory, and in particular with Bayesian networks: every random variable in a Bayesian network forms part of the overall joint distribution, and is therefore wired to exactly one output interface in our sense.
This equation must be understood as holding modulo the coherence isomorphisms of F, which make the domain of the left-hand side, which is \(F(A \otimes X \otimes A \otimes B)\), match up with the domain of the right-hand side, which is \(F(A) \otimes F(X) \otimes F(A) \otimes F(B)\).
which satisfy the commutative comonoid equations,
These comonoid structures must be multiplicative with respect to the monoidal structure:
A gs-monoidal category is a Markov category if the monoidal unit I is terminal.6
for all morphisms f. This corresponds to the normalization of probability. We refer to [1, Section 3–9] for a list of examples of Markov categories.
commute for all \(X \in {\textsf{C}}\), where the horizontal isomorphisms are the coherence isomorphisms of F.
where the second arrow is given by composition with the relevant coherence isomorphisms of F. On morphisms in the category of boxes, \(\textsf{hyp}(F)\) acts as just F componentwise on morphisms. It is straightforward to see that this satisfies functoriality.
for an acyclic finite hypergraph G and \(m, n \in {\mathbb {N}}\), such that left monogamy holds: for every wire \(w \in W(G)\), we haveWe also keep mention of the labeling morphisms \(\sigma : G \rightarrow \Sigma \) implicit, which uniquely restrict to labeling morphisms \(\sigma : {\underline{m}}, {\underline{n}} \rightarrow \Sigma \).
In order for Definition 3.7 to make sense, we need to prove that this composite is indeed a gs-monoidal string diagram again. This is guaranteed by the following result, which has been obtained independently as [14, Lemma 22 and Proposition 28].13
again leaving it understood that the labels in \(\Sigma \) are induced in the obvious way. It is clear that the isomorphism class of the resulting cospan on the right only depends on the isomorphism classes of the factors, and its left monogamy and acyclicity follow directly from the definitions. Moreover, the bifunctoriality of this tensor product follows straightforwardly from the fact that a coproduct of two pushout squares is a pushout square as well. Since the tensor product is clearly associative, we therefore have equipped \(\textsf{FreeGS}_\Sigma \) with the structure of a strict monoidal category, where the monoidal unit is \({\underline{0}}\).
where the two legs are the obvious isomorphisms and the labeling is again left implicit, it is straightforward to see that \(\textsf{FreeGS}_\Sigma \) is strict symmetric monoidal.
We leave it to the reader to verify that the properties required of a gs-monoidal category indeed hold.
where the two legs are simply the inclusions of the inputs and outputs of b in their original order, respectively. When labeled in the obvious way, this cospan is the combinatorial representation of b drawn as a string diagram as in Fig. 1.
Then we need to show that the gs-monoidal transformations \(\alpha : F \Rightarrow G\) restrict bijectively to the internal natural transformations \(\alpha ^\flat : F^\flat \Rightarrow G^\flat \). The monoidality property of \(\alpha \) implies that it is uniquely determined by its values on generating objects, which shows of the map \(\alpha \mapsto \alpha ^\flat \). Surjectivity holds for the same reason, together with the fact that the relevant naturality conditions are encoded in \(\textsf{CatHyp}\) at the level of boxes.
We do so by induction on the complexity of \(\alpha \), by which we mean the quantityAs will become clear in the course of the proof, the idea is that this counts the number of boxes plus the minimal number of occurrences of a copy or discard morphism.
Here, the unlabeled arrow is the trivial inclusion, and \(q'\) is given by q extended by \(n + 1 \longmapsto w\). This amounts to the creation of a new output interface for the wire w that was discarded in \(\alpha \). Then the composite gs-monoidal string diagram coincides with \(\alpha \) by construction. With \(\alpha '\) referring to the first cospan above (with the same labeling \(\sigma \)), we have \(C(\alpha ') = C(\alpha ) - 1\), since the summand associated to w is 0 in \(\alpha '\) and 1 in \(\alpha \).
Here, the unlabeled arrow maps \(n \longmapsto n-1\) and acts as the identity otherwise, and \(q'\) is the restriction of q to \(\underline{n-1}\). That the composite recovers \(\alpha \) and that the complexity of \(\alpha '\) has decreased can be seen as in the previous case.
Here, the second cospan is such that it represents the gs-monoidal string diagram \(\textrm{id}_{\underline{n-\ell }} \otimes \langle \sigma (b) \rangle \), and \(G'\) consists of G with the box b and the output wires of b removed. The right leg \(q'\) can be defined as q on \(\underline{n-\ell }\), and as mapping to the sequence of input wires17 of b on the remaining output interfaces. The gs-monoidal string diagram \(\alpha '\) represented by the left cospan has complexity \(C(\alpha ') = C(\alpha ) - 1 - \ell < C(\alpha )\).
is: 
The two constituent cospans become gs-monoidal string diagrams upon choosing any total ordering on W(G), or equivalently any hypergraph isomorphism \(\underline{W(G)} \cong \underline{|W(G)|}\), and considering \(\underline{|W(G)|}\) an object of \(\textsf{FinHyp}/ \Sigma \) by equipping it with the labeling inducing by this isomorphism. The left cospan is then a pure bloom and the right one pure circuitry by construction.
be given. 
This identity-on-wires morphism sends every box b to \(\textsf{norm}{\langle b\rangle }\), which is \(\langle b \rangle \) itself unless b has no outputs, in which case it gets mapped to the gs-monoidal string diagram that discards all its inputs.
for every Markov category \({\textsf{C}}\). Faithfulness is obvious since \(\textsf{norm}\) is identity-on-objects. Fullness holds by the same reason together with fullness of \(\textsf{norm}\), which enters in the verification of naturality. For essential surjectivity, it is enough to argue that every strong gs-monoidal functor \(F: \textsf{FreeGS}_\Sigma \rightarrow {\textsf{C}}\) factors through \(\textsf{norm}\), or equivalently that \(F(\alpha ) = F(\beta )\) whenever \(\textsf{norm}(\alpha ) = \textsf{norm}(\beta )\). We can assume without loss of generality that \(\alpha \) and \(\beta \) differ by a single reduction step, consisting of the elimination of an eliminable box b in \(\alpha \). We can then write \(\alpha \) as a composite gs-monoidal string diagramin such a way thatThe naturality of discarding in \({\textsf{C}}\) then implies \(F(\alpha ) = F(\beta )\). \(\square \)
in a monoidal signature \(\Sigma \), or equivalently a morphism in \(\textsf{FreeMarkov}_\Sigma \), such that the right leg q is injective.