left and right euclidean;
where is some other object of the category. (The word “correspondence” is also sometimes used for a profunctor.)
This diagram is also called a ‘span’ because it looks like a little bridge; ‘roof’ is similar. The term ‘correspondence’ is prevalent in geometry and related areas; it comes about because a correspondence is a generalisation of a binary relation.
Note that a span with is just a morphism from to , while a span with is a morphism from to . So, a span can be thought of as a generalization of a morphism in which there is no longer any asymmetry between source and target.
If the category has pullbacks, we can compose spans. Namely, given a span from to and a span from to :
we can take a pullback in the middle:
and obtain a span from to :
This way of composing spans lets us define a 2-category with:
This is a weak 2-category: it has a nontrivial associator: composition of spans is not strictly associative, because pullbacks are defined only up to canonical isomorphism. A naturally defined strict 2-category which is equivalent to is the strict 2-category of linear polynomial functors between slice categories of .
(Note that we must choose a specific pullback when defining the composite of a pair of morphisms in , if we want to obtain a bicategory as traditionally defined; this requires the axiom of choice. Otherwise we obtain a bicategory with ‘composites of morphisms defined only up to canonical iso-2-morphism’; such a structure can be modeled by an anabicategory or an opetopic bicategory?.)
Let be a category with pullbacks and let be the 1-category of objects of and isomorphism class of spans between them as morphisms.
(Dawson-Paré-Pronk 04) (…)
Correspondences may be seen as generalizations of relations. A relation is a correspondence which is (-1)-truncated as a morphism into the cartesian product. See at relation and at Rel for more on this.
Spans in FinSet behave like the categorification of matrices with entries in the natural numbers: for a span of finite sets, the cardinality of the fiber over any two elements and plays the role of the corresponding matrix entry. Under this identification composition of spans indeed corresponds to matrix multiplication.
A cobordism from to is an example of a cospan in the category of smooth manifolds. However, composition of cobordisms is not quite the pushpout-composition of these cospans: to make the composition be a smooth manifold again some extra technical aspects must be added (“collars”).
A hypergraph is a span from a set of vertices to a set of (hyper)edges.
A category of correspondences is a refinement of a category Rel of relations. See there for more.
The construction was introduced by Jean Bénabou (as an example of a bicategory) in
Bénabou cites an article by Yoneda (1954) for introducing the concept of span (in the category of categories).
An exposition discussing the role of spans in quantum theory:
The relationship between spans and bimodules is briefly discussed in
The relation to van Kampen colimits is discussed in
The universal property of categories of spans is discussed in
Generally, an (∞,n)-category of spans is indicated in section 3.2 of