Joyal's CatLab
Spans and cospans

Context

Category theory

Category theory

Contents

Spans

Recall that a span between two objects AA and BB of a category E\mathbf{E} is a pair of maps

We shall write (S,u,v):AB(S,u,v):A\Rightarrow B to indicate that u:SAu:S\to A and v:SBv:S\to B. The object AA is the domain and the object BB the codomain of (S,u,v)(S,u,v). The map uu is the source map and the map vv the target map of the span (S,u,v)(S,u,v). The transpose of a span (S,u,v):AB(S,u,v):A\Rightarrow B is the span (S,v,u):BA(S,v,u):B\Rightarrow A,

If (S,u,v)(S,u,v) and (S,u,v)(S',u',v') are two spans ABA\Rightarrow B, then a map f:(S,u,v)(S,u,v)f:(S,u,v)\to (S',u',v') is an arrow f:SSf:S\to S' in E\mathbf{E} such that the following diagram commutes,

The spans ABA\Rightarrow B form a category Span(A,B)Span(A,B). If the cartesian product A×BA\, \times\, B exists, then a span (S,u,v):AB(S,u,v):A\Rightarrow B can be described by a single map (u,v):SA×B(u,v):S\to A\times B. Moreover, the category Span(A,B)Span(A,B) is isomorphic to the category E/(A×B).\mathbf{E}/(A\times B).

Let us now suppose that the category E\mathbf{E} has finite limits. Recall that the composite of a span S=(S,s,t):ABS=(S,s,t):A\Rightarrow B with a span T=(T,u,v):BCT=(T,u,v):B\Rightarrow C is the span TS=(S× BT,spr 1,vpr 2):ACT \circ S=(S\times_B T, s pr_1, v pr_2): A \Rightarrow C, defined by the following diagram with a cartesian square,

The composition operation (T,S)TS(T,S)\mapsto T\circ S defines a functor of two variables

Span(B,C)×Span(A,B)Span(A,C).Span(B,C)\,\times\, Span(A,B) \to Span(A,C).

The composition of spans is coherently associative. More precisely, if S=(S,s,t):ABS=(S,s,t):A\Rightarrow B, T=(T,u,v):BCT=(T,u,v):B\Rightarrow C and U=(U,x,y):CDU=(U,x,y):C\Rightarrow D, then the composite of the natural isomorphisms,

(S× BT)× CUS× BT× CUS× B(T× CU),(S\,\times_B \, T)\,\times_C\, U\simeq S\, \times_B\, T\times_C\, U\simeq S\,\times_B\, (T\, \times_C\, U),

obtained from the diagram

is a natural isomorphism U(TS)(UT)S.U\circ (T\circ S) \simeq (U\circ T)\circ S.

Cospans

References

Stephen Lack, R.F.C. Walters, R.J. Wood: Bicategory of spans as bicartesian categories. Theory and Applications of Categories. Vol 24 (2010). here

Revised on November 20, 2020 at 16:55:00 by Dmitri Pavlov