# Hypergraph categories of cospans
*guest post by [Jonathan Lorand](http://user.math.uzh.ch/lorand/) and [Fabrizio Genovese](https://www.cs.ox.ac.uk/people/fabrizio.genovese/)*
In the [Applied Category Theory Seminar](http://www.appliedcategorytheory.org/school/), we most recently read Brendan Fong's article on [decorated cospans](https://arxiv.org/abs/1502.00872). This construction is part of a larger framework, developed in Brendan Fong's [PhD thesis](https://arxiv.org/abs/1609.05382), for studying interconnected, open, network-style systems. A paradigmatic example: systems composed of electric circuits having input and output terminals, allowing for composition of smaller circuits into larger. An aim of Brendan's framework is to give, for any such kind of system, a unified categorical way to describe both the formal, symbolic language of such systems (their "syntax") as well as the behavior of the systems that these formal symbols represent (the "semantics"). For circuits: syntax is formal rules for combining circuit diagram nomenclature; semantics is a (mathematical) description of how real-life circuits behave in the presence of voltages, currents, etc.. Decorated cospans are a tool ideal for "syntax"; decorated corelations are designed to handle "semantics" and are flexible enough to model any so-called hypergraph category. We'll focus on the former, and hint at the latter.
---
John Baez has made several nice blog posts already about [decorated cospans](https://johncarlosbaez.wordpress.com/2015/05/01/decorated-cospans/), [corelations](https://johncarlosbaez.wordpress.com/2016/02/02/corelations-in-network-theory/), and his work with Brendan Fong on [passive linear networks of circuits](https://johncarlosbaez.wordpress.com/2015/04/28/a-compositional-framework-for-passive-linear-networks/); we hope the present post navigates a course which complements these. We set the scene with hypergraph categories, then discuss (decorated) cospans, and give a very brief introduction to corelations.
We'd like to thank Brendan for his many helpful comments, his technical support, and diagram sharing. Also thanks to Brendan, Nina and the whole "Adjoint team" for a great seminar experience so far.
## Hypergraph categories
The name "hypergraph category" is rather new, introduced in [[F1]](https://arxiv.org/abs/1502.00872) and [[K]](https://arxiv.org/abs/1406.5942). The concept itself is apparently older, going back at least to Carboni and Walters.
First of all, why "hypergraph"? There are several notions which fall under the name "hypergraph", and we do not follow conventions too closely here. For us, a hypergraph is simply a kind of graph which has different types of nodes and edges, with edges allowed to be possibly "open" in the sense that they are attached only on one end to some node. Composition of such graphs to build new graphs is possible by connecting open edges together (though we only allow edges of the same type to connect). The following picture illustrates such a composition, with different types of edges indicated by different types of lines.
A hypergraph category is a categorical version of hypergraphs, where we think of edges as objects and nodes as morphisms. Here is a concise definition, we'll then do some unpacking: a hypergraph category is a symmetric monoidal category such that each object is equipped with the structure of a special commutative Frobenius monoid, and such that these structures satisfy a certain compatibility with the monoidal product.
We'll use the string diagram language for symmetric monoidal categories, and introduce four new symbols corresponding to (co)monoid maps. A special commutative Frobenius monoid structure (SCFM structure) on an object $X$ of a symmetric monoidal category $(C, \otimes)$ is given by maps
(called the *multiplication*, *unit*, *comultiplication*, and *counit*),
satisfying the axioms of a commutative monoid
and cocommutative comonoid
as well as the "Frobenius" and "special" axioms
This set of axioms is not minimal; in particular, if a monoid and comonoid structure satisfies the Frobenius law, then commutativity and cocommutativity imply each other. Thus the term "commutative" Frobenius monoid entails "bicommutativity".
Suppose an object $X$ in $(C, \otimes)$ carries a SCFM structure. A coherence result know as the "spider theorem" tells us, roughly, that any morphism $f: X^m \rightarrow X^n$ described by a connected string diagram, and defined only using operations and canonical maps coming from $(C,\otimes)$ and the maps $( \mu, \eta, \delta, \epsilon)$, can be depicted simply as a "spider": a diagram with one node, $m$ input legs and $n$ output legs.
This result, though, is only about maps between monoidal powers of a single object $X$.
The interaction of SCFM structures on different objects of a hypergraph category is provided by the following compatibility axioms: in a hypergraph category we require
In this way one obtains a kind of category whose calculus of string diagrams reflects the initial intuition given by hypergraphs. More details, in particular on diagrammatics, can be found in [[BGKSZ]](arXiv:1602.06771) and [[K]](https://arxiv.org/abs/1406.5942).
As indicated above, hypergraphs are a natural structure for describing open, network-like systems. The word "open" means that one has a notion of input, output and composition/interaction. Here is a summary of this "network intuition" in terms of hypergraph categories
One wishes also to compare/translate between different hypergraph categories.
A hypergraph functor $(C, \otimes) \rightarrow (C', \boxtimes)$ between hypergraph categories is a strong symmetric monoidal functor $(F, \varphi)$ such that, for each object $X$ of $C$, the SCFM structure $(FX, \mu_{FX}, \eta_{FX} ,\delta_{FX} , \epsilon_{FX})$ on $FX$ must coincide with the one induced by $F$:
$$
(FX, F \mu_{X} \circ \varphi_{X,X}, F \eta_{X} \circ \varphi_I, \varphi_{X,X}^{-1} \circ F \delta_{X} , \varphi_I^{-1} \circ F\epsilon_{X})
$$
An equivalence of hypergraph categories is an equivalence of symmetric monoidal categories which is built of hypergraph functors.
An important remark about hypergraph categories is that the SCFM maps $(\mu_X, \eta_X, \delta_X, \epsilon_X)$ on each object $X$ in $C$ are not required to be natural in $X$. Morphisms in $C$ need not interact in a coherent way with the SCFM structures. In particular, a given symmetric monoidal category may admit two hypergraph structures which are hypergraph inequivalent.
Another remark is that hypergraph categories are automatically compact closed, with every object self-dual: the maps
and
(think: cup and cap) satisfy
as well as the vertically reflected equations (think: snake!). The first equality uses the Frobenius law, the second the (co)unital laws.
## Cospan Categories
Cospans lead to hypergraph categories following a familiar construction. One starts with a category $C$ having finite colimits, viewing it as a symmetric monoidal category $(C, +)$ with the coproduct as monoidal product. From this we define a category whose objects are the objects of $C$, and whose morphisms $X \rightarrow Y$ are cospans in $C$
considered up to a notion of isomorphism. The source and target of the cospan are the "feet", while $N$ is the "apex". Cospans are isomorphic for us if they have the same feet and if there exists an isomorphism between their apexes which makes the evident triangles commute. The maps $i$ and $o$ (the "legs" of the cospan) are labeled to hint at the interpretation that we are thinking of $X$ as representing inputs, and $Y$ as representing outputs.
Composition of cospans $X \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y$ and $Y \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z$ is given by taking a pushout over the shared foot
Considering only isomorphism classes of cospans makes this composition well-defined and associative, and one checks that this builds us a category. It's called $Cospan(C)$.
$Cospan(C)$ has a symmetric monoidal structure induced from $C$, and comes with a canonical hypergraph structure. To see roughly how this works,
note that we have an "identity on objects" embedding
$C \hookrightarrow Cospan(C)$ defined by sending a morphism $f: X \rightarrow Y$ in $C$ to the cospan $X \overset{f}{\rightarrow} Y \overset{1_Y}{\leftarrow} Y$.
This gives us a copy of $C$ inside $Cospan(C)$ and induces a monoidal structure on $Cospan(C)$.
The directional symmetry in the definition of a cospan means that cospans actually come in pairs
Call such cospans *opposites* of one another. Note that, alongside the above embedding, there is an analogous embedding $C^{op} \hookrightarrow Cospan(C)$, sending $f^{op}: Y \rightarrow X$ to $Y \overset{1_Y}{\rightarrow} Y\overset{f}{\leftarrow} X$.
For each object $X$ in $(C,+)$ we have the copairing $[1_X, 1_X]: X + X \rightarrow X$ and a unique map $! : \emptyset \rightarrow X$ from our initial object $\emptyset$ in $(C,+)$. The images of these morphisms under $C \hookrightarrow Cospan(C)$ give us a multiplication map $\mu$ and a unit map $\eta$ for a commutative monoid structure on $X$. By defining comultiplication $\delta$ and counit $\epsilon$ via the cospans which are opposite to $\mu$ and $\eta$, respectively, one obtains a SCFM on each object of $Cospan(C)$, with compatibility making $Cospan(C)$ a hypergraph category.
As a simple example to play with, consider the category $FinSet$ whose objects are the sets $\emptyset$, $\{1\}$, $\{1, 2 \}$, $\{1,2,3\}$, ... and whose morphisms are functions between these sets. This category has finite colimits, with initial object $\emptyset$ and coproduct defined by $\{1,2,...,n\} + \{1,2,...,m\} = \{1,2,..,n+m \}$; these make $(FinSet,+)$ a symmetric strict monoidal category.
We think of $\{1\}$ as the generator of the objects; all other objects may be built from this one using the coproduct (thinking of $\emptyset$ as the zero-th monoidal power of $\{1\}$). Graphically we depict $\{1\}$ as a black dot, and any object $\{1,2,...,n\}$ as a cloud of $n$ dots (since our monoidal product is strictly commutative, the order of how we juxtapose our dots doesn't matter, so we just use "clouds").
Suppose we are composing cospans $X \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y$ and $Y \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z$ in $FinSet$. The pushout over the shared foot $Y$ implements the merging of the two apexes according to the "instructions" given by the output function $o_Y$ of the first cospan and the input function $i_Y$ of the second, as illustrated below in red
In this image, the bottom "cloud" is $Y$, on the left is $N$, on the right is $M$, and above is $N +_Y M$, while $X$ and $Z$, and the maps from them, are not depicted.
## Decorated cospans
In the setting of electrical circuits, one may view circuit diagrams as a set of nodes $N$ which is "decorated" by the other symbols of the circuit diagram. For given $N$, this information may be encoded mathematically by specifying, for example, a set of edges E with target and source maps $s,t : E \rightarrow N$, as well as other information, such as an assignment of resistances to edges by specifying a function $r : E \rightarrow (0, \infty)$.
Thinking of the set of nodes $N$ as the apex of a cospan in $FinSet$, the images in $N$ of the feet $X$ and $Y$ correspond to choices of input and output terminals, respectively, and the legs of the cospan allow further flexibility in connecting, for example, multiple inputs of one circuit to an output terminal of another, as illustrated above. John Baez's [blog post](https://johncarlosbaez.wordpress.com/2015/05/01/decorated-cospans/) has nice examples of circuits being composed.
Decorated cospans are designed to capture this intuitive notion of composition of network diagrams. This must be done in such a way that the cospans and their decorations compose together in the desired manner.
Formally, Brendan achieves this using a lax monoidal functor
$(F, \varphi) : (C, +) \rightarrow (Set, \times)$ to encode the decorations on the apexes of cospans in Cospan(C). (One may actually use any monoidal category $(D, \otimes)$ in place of $(Set, \times)$). Given such a functor $F$, he constructs a category $FCospan(C)$ of "F-decorated cospans in C" where the objects are the objects of $C$, and morphisms are represented by pairs consisting of a cospan $X \overset{i}{\rightarrow} N \overset{o}{\leftarrow} Y$ in $C$ and an element $s \in FN$ of the image of the apex $N$ under $F$. This element is the *decoration* of the apex. On the nose, morphisms in $FCospan(C)$ are isomorphism classes of such pairs; two such pairs are isomorphic if their constituting cospans are isomorphic via an isomorphism $n : N \rightarrow N'$ between their apexes which is also compatible with the decorations: $(Fn)(s) = s'$.
Composition of decorated cospans works, on representatives of morphisms in $FCospan(C)$, by composing the constituent cospans and composing the decorations $s$ and $t$ by sending $(s, t) \in FN \times FM$ to a decoration on the composed apex $N +_Y M$ via the map
$$
F[j_N,j_M]: FN \times FM \rightarrow F(N+_Y M)
$$
(recall that $j_N$ and $j_M$ denote the pushout maps involved in composing our cospans). A key point is that we can use the copairing $[j_N, j_M] : N + M \rightarrow N +_Y M$ to implement the "merging" of the decorations on $N$ and $M$.
Under the assumptions that the "decoration category" $(D, \otimes)$, and $F$, are braided (we keep these assumptions now), the category $FCospan(C)$ inherits a monoidal and hypergraph structure from $Cospan(C)$.
Here is a summary:
In [[F1]](https://arxiv.org/abs/1502.00872) (see Theorem 4.1) a method is given for constructing hypergraph functors between decorated cospan categories $FCospan(C)$ and $GCospan(C')$, starting from the data of a natural transformation which relates $C$ and $F$ to $C'$ and $G$.
In [[F2]](https://arxiv.org/abs/1502.00872), decorated cospans are generalized to decorated corelations, and in this setting a theorem is proved which is analogous to the one mentioned above. This gives, in particular, a way of constructing functors from hypergraph categories of decorated cospans (think: syntax) to hypergraph categories of corelations (think: semantics).
Although we won't have the space to explain decorated corelations properly, we'll conclude our post by introducing the basic idea of corelations and indicating their potential for describing the "semantics", or behavior, of open, network-like systems.
## Corelations
The corelation approach to describing the behavior of open systems is linked to the idea of "black-boxing". Suppose one has two different circuit diagrams - described in a decorated cospan category as above - which have the same set of input and output terminals $X$ and $Y$, and suppose we build these circuits. The real-life circuits will impose certain relations on the values of the voltages and currents which may be simultaneously measured at all of the terminals. Not every configuration of possible values is realizable because circuits obey certain laws, such as Ohm's law relating currents, voltages and resistances.
Note that two different circuits might impose the same relations between their terminals.
With respect to an agreed upon mode of measurement, the relations imposed by a circuit on its terminals may be called the (external) "behavior" of a circuit. We'll say that two circuits behave the same way if they are indistinguishable by making measurements at their terminals. In other words, if each circuit were covered by an opaque black box, with only the terminals exposed, we would not know which circuit is which.
Decorated corelations are designed to capture exactly the information about the "black-box behavior" of open, network-style systems. Brendan gives at least two reasons why one might wish to keep track only of this "behavioral" information, rather than all of the internal workings of components of open systems. One reason is conceptual clarity: the focus is kept on the behaviorally relevant information. A second reason is computational: when smaller components are composed into larger, the amount of syntactical information may increase explosively, while semantically relevant information may be more stable. As a simplified illustration: in the below composition of circuit diagrams, the parts of the resulting larger circuit which have no paths to any terminals are not relevant for the behavior of the circuit.
To give a sketch of how corelations work, let's use the category FinSet mentioned above. Suppose we have cospans in FinSet $X \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y$ and $Y \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z$, ready to be composed as so
Their composition
is the cospan $X \overset{j_N o_Y}{\rightarrow} N +_Y M \overset{j_M i_Y}{\leftarrow} Z$. The union of the images of the legs of this cospan is precisely the image of the copairing $[j_N o_Y, j_M i_Y]: X + Z \longrightarrow N+_Y M$. Points outside of this image may be irrelevant, we may wish to "discard" them. A way of implementing "discarding" is to focus our attention on cospans $X \overset{i}{\rightarrow} N \overset{o}{\leftarrow} Y$ for which $[i,o]: X + Y \rightarrow N$ is surjective. These are called corelations. To compose corelations $X \overset{i_X}{\rightarrow} N \overset{o_Y}{\leftarrow} Y$ and $Y \overset{i_Y}{\rightarrow} M \overset{o_Z}{\leftarrow} Z$, we compose them as cospans to obtain $X \overset{j_N i_N}{\rightarrow} N +_Y M \overset{j_M o_M}{\leftarrow} Z$ and then restrict the map $[j_N o_Y, j_M i_Y]$ to its "surjective part", to obtain again a corelation.
Factorization systems $(\mathcal{E}, \mathcal{M})$ in a category give a way to make this idea precise and general; in [[F2]](https://arxiv.org/abs/1502.00872) factorization systems are used define a general notion of corelation which is modeled on the above example. Then, given a category $C$ with finite colimits and a factorization system $(\mathcal{E}, \mathcal{M})$ with suitable properties, one can build a hypergraph category $(Corel_{(\mathcal{E}, \mathcal{M})}(C), +)$ where objects are those of $C$ and morphisms are so-called $(\mathcal{E}, \mathcal{M})$-corelations. As in the case of cospans, corelations can be decorated, leading to decorated corelation categories. The scope of this construction turns out to be quite general: in [[F3]](https://arxiv.org/abs/1609.05382) it is proved that any hypergraph category is hypergraph equivalent to some decorated corelation category.
## Further reading
* [BF] Baez, J., Fong, B., [A compositional framework for passive linear networks](https://arxiv.org/abs/1504.05625), arXiv:1504.05625
* [BGKSZ] F. Bonchi, F. Gadducci, A. Kissinger, P. Sobocinski, F. Zanasi, [Rewriting modulo symmetric monoidal structure](https://arxiv.org/abs/1602.06771), _Proceedings of Logic in Computer Science, LICS16_ (2016), 710--719
* [F1] Fong, B., [Decorated Cospans](https://arxiv.org/abs/1502.00872), _Theory and Applications of Categories_ *30* (2015), 1096--1120.
* [F2] Fong, B., [Decorated Corelations](https://arxiv.org/abs/1502.00872), arXiv:1703.09888
* [F3] Fong, B., [PhD Thesis](https://arxiv.org/abs/1609.05382), arXiv:1609.05382
* [K] Kissinger, A., [Finite matrices are complete for (dagger-)hypergraph categories](https://arxiv.org/abs/1406.5942), arXiv:1406.5942.