decorated cospan

Decorated cospan


Decorated cospans are a convenient formalism to deal with open networks, i.e. networks were some nodes are interpreted to be ‘inputs’ and some other to be ‘outputs’. In fact, a natural way to do such labelling is to specify some function assigning the set of inputs to those nodes in the network tasked with receiving them, and analogously, a function assigning to outputs those nodes which provide them. This is, morally, a cospan: the network is the vertex, and inputs and outputs are the feet. However, the two things sit in ‘different categories’: e.g., inputs and outputs may be sets of wires and sockets, while the network has a more complicated description. Nevertheless, the network is just a set of nodes with more information attached, namely the way those nodes are connected. The key insight here is that to specify inputs/outputs of the network, we don’t really care about this additional information. Hence we can use a ‘cospan of nodes’ (formally, a cospan in FinSet), and deal with the network structure later, as a decoration.

Surprisingly, this formalism naturally captures also other operations such as sequential and parallel composition of networks.


Categories of cospans

In a category C\mathbf C with finite colimits (or even just pushouts) cospans can be composed in a natural way. In fact, given xsyx \to s \leftarrow y and ytzy \to t \leftarrow z, we get a new cospan xpzx \to p \leftarrow z by taking a pushout in the middle:

s+ yt p s p t s t f g h i x y z \array{ &&&& s +_y t \\& && {}^{p_s}\nearrow && \nwarrow^{p_t} \\ && s &&&& t \\ & {}^{f}\nearrow && \nwarrow^{g} & & {}^{h}\nearrow && \nwarrow^{i} \\ x &&&& y &&&& z }

Therefore cospans form a compositional structure: a category Cospan(C)\mathrm{Cospan}(\mathbf C) where objects are the same of C\mathbf C but morphisms from xx to yy are replaced by cospans with feet xx and yy. Since the pushout we choose to form the composite of two cospans is, in general, unique only up to unique isomorphism, we actually need to define a 22-category. Morphisms of cospans (xpy)(xqy)(x \to p \leftarrow y) \Rightarrow (x \to q \leftarrow y) are given by any C\mathbf C-morphism η:pq\eta : p \to q making the following commute

p f g x η z f g q \array{ && p \\ & {}^{f}\nearrow && \nwarrow^{g} \\ x &&\downarrow^\eta&& z \\ & {}_{f'}\searrow && \swarrow_{g'} \\ && q }

It is also customary to ignore the 22-structure and simply work with Cospan(C)\mathrm{Cospan}(\mathbf C) as a 11-category whose morphisms are isomorphism classes of cospans.

Categories of decorated cospans


(B. Fong 2015) Let C\mathbf C be a category with finite colimits, and

(F,ϕ):(C,+)(D,) (F, \phi): (\mathbf C, +) \to (\mathbf D, \otimes)

be a lax monoidal functor. A decorated cospan, or more precisely an FF-decorated cospan, is a pair (xinoy,1sFn)(x \overset{i}\to n \overset{o}\leftarrow y,\, 1 \overset{s}\to Fn). We shall call the element 1sFn1 \overset{s}\to Fn the decoration of the decorated cospan. A morphism of decorated cospans

f:(xinoy,1sFn)(xinoy,1sFn) f : (x \overset{i}\to n \overset{o}\leftarrow y,\, 1 \overset{s}\to Fn) \to (x \overset{i}\to n' \overset{o}\leftarrow y,\, 1 \overset{s'}\to Fn')

is a morphism of cospans such that the following commutes:

Fn s 1 Ff s Fn \array{ && Fn\\ & \nearrow^s\\ 1 & & \downarrow^{Ff}\\ & \searrow^{s'}\\ && Fn' }

Given a cospan xnyx \to n \leftarrow y in C\mathbf C, the empty decoration on nn is the unique map

1ϕ 1FF!Fn 1 \overset{\phi_1}\longrightarrow F\varnothing \overset{F!}\longrightarrow Fn

where \varnothing is inital in C\mathbf C and !! denotes the universal morphism from such object.


(B. Fong 2015) There is a category FCospanF\mathrm{Cospan} of FF-decorated cospans, with objects the objects of C\mathbf C and morphisms isomorphism classes of FF-decorated cospans. Composition in this category is given by the class of the pushout of two representatives:

n+ ym j n j m n m i x o y i y o z x y z \array{ &&&& n +_y m \\& && {}^{j_n}\nearrow && \nwarrow^{j_m} \\ && n &&&& m \\ & {}^{i_x}\nearrow && \nwarrow^{o_y} & & {}^{i_y}\nearrow && \nwarrow^{o_z} \\ x &&&& y &&&& z }

along with the decoration

1λ 111ssFnFmϕ n,mF(n+m)F[j n,j m]F(n+ ym). 1 \overset{\lambda^{-1}}\longrightarrow 1 \otimes 1 \overset{s \otimes s'}\longrightarrow Fn \otimes Fm \overset{\phi_{n,m}}\longrightarrow F(n+m) \overset{F[j_n,j_m]}\longrightarrow F(n +_y m).

where 1sFn1 \overset{s}\to Fn and 1sFm1 \overset{s'}\to Fm are decorations of the first and second cospan, respectively.


The identity morphism of an object xx in FCospanF\mathrm{Cospan} is simply xidxidxx \overset{\mathrm{id}}\to x \overset{\mathrm{id}}\leftarrow x equipped with the empty decoration on xx. The check that all relevant axioms are satisfied can be found in (B. Fong 2015, Appendix A)


The composition of decorations is the key construction of the decorated cospans formalisms. In fact, returning to the analogy with open networks, it constructs the composite network of a given ‘link’ of two networks. Hence the compositional structures of the cospans is leveraged to describe the compositional structure of a richer structure.


Notice that the empty decoration gives a canonical way to decorate any cospan on C\mathbf C. Indeed, it can be shown this defines a wide functor Cospan(C)FCospan\mathrm{Cospan}(\mathbf C) \embedsin F\mathrm{Cospan}, as the composition of two empty-decorated cospans is again empty-decorated.

The monoidal and hypergraph structures

In the presence of a braiding on D\mathbf D (the ‘decorating category’), the category of decorated cospans becomes not just symmetric monoidal, but a full-blown hypergraph category.


(B. Fong, 2015) Let C\mathbf C be a category with finite colimts, (D,)(\mathbf D, \otimes) a braided monoidal category and (F,ϕ):(C,+)(D,)(F, \phi) : (\mathbf C, +) \to (\mathbf D, \otimes) a lax braided monoidal functor. Then we may equip FCospanF\mathrm{Cospan} with a symmetric monoidal and hypergraph structure, such that there is a wide embedding of hypergraph categories

Cospan(C)FCospan. \mathrm{Cospan}(\mathbf C) \embedsin F\mathrm{Cospan}.

We define the monoidal product of objects xx and yy of FCospanF\mathrm{Cospan} to be their coproduct x+yx+y in C\mathbf C, and defined the monoidal product of decorated cospans (xinoy,1sFn)(x \overset{i}\to n \overset{o}\leftarrow y, 1 \overset{s}\to Fn) and (xinoy,1sFn)(x \overset{i}\to n' \overset{o}\leftarrow y, 1 \overset{s'}\to Fn') to be

n+n i x+i x o y+o y , 1λ 111ssFnFnϕ n,nF(n+n) x+x y+y \array{ && n + n' \\ & {}^{i_x + i_{x'}}\nearrow && \nwarrow^{o_y + o_{y'}} &&,&& 1 \overset{\lambda^{-1}}\longrightarrow 1 \otimes 1 \overset{s \otimes s'}\longrightarrow Fn \otimes Fn' \overset{\phi_{n,n'}}\longrightarrow F(n+n') \\ x+x' &&&& y+y' }

The braiding in D\mathbf D can be now used to show this product is indeed functorial. Finally, we choose associator, unitors and braiding to be the images of those in Cospan(C)\mathrm{Cospan}(\mathbf C). The necessary checks are done in (B. Fong 2015, Appendix A).

The hypergraph structure is defined by equipping each object xFCospanx \in F\mathrm{Cospan} with the image of the special commutative Frobenius monoid specified by the hypergraph structure of Cospan(C)\mathrm{Cospan}(\mathbf C). The fact that the ‘empty-decoration’ embedding is an hypergraph functor is evident.

If the monoidal unit of (D,)(\mathbf D, \otimes) is the initial object, then each object admits only a decoration — the empty one. This implies Cospan(C)\mathrm{Cospan}(\mathbf C) and 1 CCospan1_{\mathbf C}\mathrm{Cospan} are isomorphic as hypergraph categories.



Decorated cospans were first defined by Brendan Fong: