nLab
span

This entry is about the notion of spans/correspondences which generalizes that of relations. For spans in vector spaces or modules, see linear span.

Context

Relations

Category theory

2-Category theory

Contents

Definition

Correspondences

In any category CC, a span, or roof, or correspondence, from an object xx to an object yy is a diagram of the form

s f g x y \array{ && s \\ & {}^{f}\swarrow && \searrow^{g} \\ x &&&& y }

where ss 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 f=1f = 1 is just a morphism from xx to yy, while a span with g=1g = 1 is a morphism from yy to xx. 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.

A span in the opposite category C opC^op is called a co-span in CC.

A span that has a cocone is called a coquadrable span.

Categories of correspondences

If the category CC has pullbacks, we can compose spans. Namely, given a span from xx to yy and a span from yy to zz:

s t f g h i x y z \array{ && s &&&& t \\ & {}^{f}\swarrow && \searrow^{g} & & {}^{h}\swarrow && \searrow^{i} \\ x &&&& y &&&& z }

we can take a pullback in the middle:

s× yt p s p t s t f g h i x y z \array{ &&&& s \times_y t \\& && {}^{p_s}\swarrow && \searrow^{p_t} \\ && s &&&& t \\ & {}^{f}\swarrow && \searrow^{g} & & {}^{h}\swarrow && \searrow^{i} \\ x &&&& y &&&& z }

and obtain a span from xx to zz:

s× yt fp s ip t x z \array{ && s \times_y t \\ & {}^{f p_s}\swarrow && \searrow^{i p_t} \\ x &&&& z }

This way of composing spans lets us define a 2-category Span(C)Span(C) with:

  • objects of CC as objects
  • spans as morphisms
  • maps between spans as 2-morphisms

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 Span(C)Span(C) is the strict 2-category of linear polynomial functors between slice categories of CC.

(Note that we must choose a specific pullback when defining the composite of a pair of morphisms in Span(C)Span(C), 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?.)

Properties

The 1-category of spans

Let CC be a category with pullbacks and let Span 1(C):=(Span(C)) 1Span_1(C) := (Span(C))_{\sim 1} be the 1-category of objects of CC and isomorphism class of spans between them as morphisms.

Then

Next assume that CC is a cartesian monoidal category. Then clearly Span 1(C)Span_1(C) naturally becomes a monoidal category itself, but more: then

Universal property of the 2-category of spans

(Dawson-Paré-Pronk 04) (…)

Limits and colimits

Since a category of spans/correspondences Corr(𝒞)Corr(\mathcal{C}) is evidently equivalent to its opposite category, it follows that to the extent that limits exists they are also colimits and vice versa.

If the underlying category 𝒞\mathcal{C} is an extensive category, then the coproduct/product in Corr(𝒞)Corr(\mathcal{C}) is given by the disjoint union in 𝒞\mathcal{C}. (See also this MO discussion).

More generally, every van Kampen colimit in 𝒞\mathcal{C} is a (co)limit in Corr(𝒞)Corr(\mathcal{C}) — and conversely, this property characterizes van Kampen colimits. (Sobocinski-Heindel 11).

Relation to relations

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.

Examples

A category of correspondences is a refinement of a category Rel of relations. See there for more.

References

An exposition discussing the role of spans in quantum field 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

The structure of a monoidal tricategory on spans in 2-categories is discussed in

Generally, an (∞,n)-category of spans is indicated in section 3.2 of

Revised on July 2, 2014 10:31:02 by Urs Schreiber (82.136.246.44)